tools/syz-kconfig: suggest reasons for wrongly selected configs

The most frustrating part of updating syzbot configs is figuring out
what config options (possibly transivitely) selected the configs we
wanted to stay disabled.

For each "X is present in the final config" message, auto-generate
a small list of enabled config options that may have transitively
"select"ed X.

2 files changed, 75 insertions, 8 deletions

diff --git a/pkg/kconfig/kconfig.go b/pkg/kconfig/kconfig.go
index 021929781..7cb54a1bb 100644
--- a/pkg/kconfig/kconfig.go
+++ b/pkg/kconfig/kconfig.go
@@ -30,13 +30,15 @@ type Menu struct {
 	Elems  []*Menu    // sub-elements for menus
 	Parent *Menu      // parent menu, non-nil for everythign except for mainmenu
 
-	kconf     *KConfig // back-link to the owning KConfig
-	prompts   []prompt
-	defaults  []defaultVal
-	dependsOn expr
-	visibleIf expr
-	deps      map[string]bool
-	depsOnce  sync.Once
+	kconf      *KConfig // back-link to the owning KConfig
+	prompts    []prompt
+	defaults   []defaultVal
+	dependsOn  expr
+	visibleIf  expr
+	deps       map[string]bool
+	depsOnce   sync.Once
+	selects    []string
+	selectedBy []string // filled in in setSelectedBy()
 }
 
 type prompt struct {
@@ -144,6 +146,7 @@ func ParseData(target *targets.Target, data []byte, file string) (*KConfig, erro
 		Configs: make(map[string]*Menu),
 	}
 	kconf.walk(root, nil, nil)
+	kconf.setSelectedBy()
 	return kconf, nil
 }
 
@@ -159,6 +162,37 @@ func (kconf *KConfig) walk(m *Menu, dependsOn, visibleIf expr) {
 	}
 }
 
+// NOTE: the function is ignoring the "if" part of select/imply.
+func (kconf *KConfig) setSelectedBy() {
+	for name, cfg := range kconf.Configs {
+		for _, selectedName := range cfg.selects {
+			selected := kconf.Configs[selectedName]
+			if selected == nil {
+				continue
+			}
+			selected.selectedBy = append(selected.selectedBy, name)
+		}
+	}
+}
+
+// NOTE: the function is ignoring the "if" part of select/imply.
+func (kconf *KConfig) SelectedBy(name string) map[string]bool {
+	ret := map[string]bool{}
+	toVisit := []string{name}
+	for len(toVisit) > 0 {
+		next := kconf.Configs[toVisit[len(toVisit)-1]]
+		toVisit = toVisit[:len(toVisit)-1]
+		if next == nil {
+			continue
+		}
+		for _, selectedBy := range next.selectedBy {
+			ret[selectedBy] = true
+			toVisit = append(toVisit, selectedBy)
+		}
+	}
+	return ret
+}
+
 func (kp *kconfigParser) parseFile() {
 	for kp.nextLine() {
 		kp.parseLine()
@@ -293,7 +327,8 @@ func (kp *kconfigParser) parseProperty(prop string) {
 		kp.MustConsume("if")
 		cur.visibleIf = exprAnd(cur.visibleIf, kp.parseExpr())
 	case "select", "imply":
-		_ = kp.Ident()
+		name := kp.Ident()
+		cur.selects = append(cur.selects, name)
 		if kp.TryConsume("if") {
 			_ = kp.parseExpr()
 		}
diff --git a/pkg/kconfig/kconfig_test.go b/pkg/kconfig/kconfig_test.go
index 994f1856f..44eda3168 100644
--- a/pkg/kconfig/kconfig_test.go
+++ b/pkg/kconfig/kconfig_test.go
@@ -8,6 +8,7 @@ import (
 	"testing"
 
 	"github.com/google/syzkaller/sys/targets"
+	"github.com/stretchr/testify/assert"
 )
 
 func TestParseKConfig(t *testing.T) {
@@ -35,6 +36,37 @@ config FOO
 	}
 }
 
+func TestSelectedby(t *testing.T) {
+	configData := `
+mainmenu "test"
+
+config FEATURE_A
+    bool "Feature A"
+    select FEATURE_B
+
+config FEATURE_B
+    bool "Feature B"
+    select FEATURE_C
+
+config FEATURE_C
+    bool "Feature C"
+
+`
+	target := targets.Get("linux", "amd64")
+	kconf, err := ParseData(target, []byte(configData), "Kconfig")
+	if err != nil {
+		t.Fatal(err)
+	}
+	assert.Empty(t, kconf.SelectedBy("FEATURE_A"))
+	assert.Equal(t, map[string]bool{
+		"FEATURE_A": true,
+	}, kconf.SelectedBy("FEATURE_B"))
+	assert.Equal(t, map[string]bool{
+		"FEATURE_A": true,
+		"FEATURE_B": true,
+	}, kconf.SelectedBy("FEATURE_C"))
+}
+
 func TestFuzzParseKConfig(t *testing.T) {
 	for _, data := range []string{
 		``,