[PATCH] kconfig: fix submenu rendering of negative dependencies

[Julian Braha <julianbraha@gmail.com>]

This fixes the "ironic visualization" issue reported here:
https://lore.kernel.org/linux-kbuild/cbe95c15d2760f6fce8eaf207c969ce8fd3703aa.camel@xry111.site/

where a config option FOO is nested in the submenu of the previous option
BAR, despite FOO actually depending on !BAR.

I've only tested locally on x86, but as far as I can tell, this only
changes how 2 options are rendered in the menu:
1. NTFS3_FS, no longer in the NTFS_FS submenu, and
2. MTD_BLOCK_RO, no longer in the MTD_BLOCK submenu.

Assisted-by: Claude:claude-4.8-opus
Signed-off-by: Julian Braha <julianbraha@gmail.com>
---
 scripts/kconfig/expr.c | 33 +++++++++++++++++++++++++++++++++
 scripts/kconfig/expr.h |  1 +
 scripts/kconfig/menu.c | 10 ++++++++++
 3 files changed, 44 insertions(+)

diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c
index 16f92c4a775a..2b91d16bf14f 100644
--- a/scripts/kconfig/expr.c
+++ b/scripts/kconfig/expr.c
@@ -738,6 +738,39 @@ bool expr_contains_symbol(struct expr *dep, struct symbol *sym)
 	return false;
 }
 
+/*
+ * Check if the expression references 'sym' in a way that is satisfiable
+ * with 'sym' disabled, e.g.'sym!=y'.
+ *
+ * Expects that expr_transform() was already called on 'expr'.
+ */
+bool expr_contains_symbol_negated(struct expr *dep, struct symbol *sym)
+{
+	if (!dep)
+		return false;
+
+	switch (dep->type) {
+	case E_AND:
+	case E_OR:
+		return expr_contains_symbol_negated(dep->left.expr, sym) ||
+		       expr_contains_symbol_negated(dep->right.expr, sym);
+	case E_NOT:
+		return dep->left.expr->type == E_SYMBOL &&
+		       dep->left.expr->left.sym == sym;
+	case E_EQUAL:
+		/* sym=n */
+		return dep->left.sym == sym && dep->right.sym == &symbol_no;
+	case E_UNEQUAL:
+		/* sym!=y, sym!=m */
+		return dep->left.sym == sym &&
+		       (dep->right.sym == &symbol_yes ||
+			dep->right.sym == &symbol_mod);
+	default:
+		break;
+	}
+	return false;
+}
+
 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
 {
 	if (!dep)
diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h
index fa3823a97d72..b580f9fa0f29 100644
--- a/scripts/kconfig/expr.h
+++ b/scripts/kconfig/expr.h
@@ -307,6 +307,7 @@ tristate expr_calc_value(struct expr *e);
 struct expr *expr_eliminate_dups(struct expr *e);
 struct expr *expr_transform(struct expr *e);
 bool expr_contains_symbol(struct expr *dep, struct symbol *sym);
+bool expr_contains_symbol_negated(struct expr *dep, struct symbol *sym);
 bool expr_depends_symbol(struct expr *dep, struct symbol *sym);
 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym);
 
diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
index b2d8d4e11e07..9c079e92a9ed 100644
--- a/scripts/kconfig/menu.c
+++ b/scripts/kconfig/menu.c
@@ -428,9 +428,19 @@ static void _menu_finalize(struct menu *parent, bool inside_choice)
 			if (!expr_contains_symbol(dep, sym))
 				/* No dependency, quit */
 				break;
+			/*
+			 * Note that it's actually possible to depend on both
+			 * 'SYM!=y' and 'SYM=y', so we need to first check if
+			 * it's a positive dependency before checking if it's
+			 * a negative dependency. See example:
+			 * 'SFC && MTD && !(SFC=y && MTD=m)'
+			 */
 			if (expr_depends_symbol(dep, sym))
 				/* Absolute dependency, put in submenu */
 				goto next;
+			if (expr_contains_symbol_negated(dep, sym))
+				/* Negative dependency, quit */
+				break;
 
 			/*
 			 * Also consider it a dependency on sym if our
-- 
2.54.0