kconfig: Sync with upstream v4.16

This commit introduces the following upstream changes:

5ae6fcc4bb82 kconfig: fix line number in recursive inclusion error message
1a90ce36c6ef kconfig: Update ncurses package names for menuconfig
bf0bbdcf1003 kconfig: Don't leak choice names during parsing
f4bc1eefc160 kconfig: set SYMBOL_AUTO to the symbol marked with defconfig_list
cd81fc82b93f kconfig: add xstrdup() helper
523ca58b7db2 kconfig: remove const qualifier from sym_expand_string_value()
d717f24d8c68 kconfig: add xrealloc() helper
9e3e10c72536 kconfig: send error messages to stderr
f3ff6fb5db68 kconfig: echo stdin to stdout if either is redirected
d2a04648a5db kconfig: remove check_stdin()
cd58a91def2a kconfig: remove 'config*' pattern from .gitignnore
4f208f392103 kconfig: show '?' prompt even if no help text is available
cb67ab2cd2b8 kconfig: do not write choice values when their dependency becomes n
1b9eda2e4892 kconfig: Warn if help text is blank
cedd55d49dee kconfig: Remove silentoldconfig from help and docs; fix kconfig/conf's help
1ccb27143360 kconfig: make "Selected by:" and "Implied by:" readable
312ee68752fa kconfig: announce removal of oldnoconfig if used
d0fd0428ecf0 kconfig: fix make xconfig when gettext is missing
b53688014e33 kconfig: Clarify menu and 'if' dependency propagation
9d1a9e8bc18b kconfig: Document 'if' flattening logic
d3465af60f44 kconfig: Clarify choice dependency propagation
3e41ba05b6d6 kconfig: Document SYMBOL_OPTIONAL logic
765f4cdef6f8 kconfig: use default 'yy' prefix for lexer and parser
84dd95d4f87a kconfig: make conf_unsaved a local variable of conf_read()
5a3dc717b3c7 kconfig: make xfgets() really static
52e58a3caeba kconfig: make input_mode static
6479f327dea6 kconfig: Warn if there is more than one help text
b92d804a5179 kconfig: drop 'boolean' keyword
df60f4b92d3d kconfig: Remove menu_end_entry()
0735f7e5def2 kconfig: Document important expression functions
05cccce58045 kconfig: Document automatic submenu creation code
7cf33f88e294 kconfig: Fix choice symbol expression leak
5b1374b3b3c2 kconfig: Fix expr_free() E_NOT leak
ae7440ef0c80 kconfig: Fix automatic menu creation mem leak
0724a7c32a54 kconfig: Don't leak main menus during parsing
bc28fe1d5ede kconfig: Don't leak 'option' arguments during parsing
24161a6711c9 kconfig: Don't leak 'source' filenames during parsing
26e47a3c11a2 kconfig: Don't leak symbol names during parsing
29c833061c1d kconfig: generate lexer and parser during build instead of shipping
e3b03bf29d6b kconfig: display recursive dependency resolution hint just once
f77850d3fe0c kconfig: Clean up modules handling and fix crash
fa8cedaef814 kconfig: Clarify expression rewriting
9a826842ff2f kconfig: Rename menu_check_dep() to rewrite_m()
c873443430eb kconfig: Sync zconf.y with zconf.tab.c_shipped
52aede4ba5ef kconfig: Document the 'symbol' struct
33ca1a248663 kconfig: Document the 'menu' struct
2c37e08464a8 kconfig: Warn if choice default is not in choice

Signed-off-by: Chris Packham <judge.packham@gmail.com>

1 files changed, 133 insertions, 7 deletions

diff --git a/kconfig/expr.c b/kconfig/expr.c
index 8cee597..d453819 100644
--- a/kconfig/expr.c
+++ b/kconfig/expr.c
@@ -94,7 +94,7 @@ struct expr *expr_copy(const struct expr *org)
 		e->right.expr = expr_copy(org->right.expr);
 		break;
 	default:
-		printf("can't copy type %d\n", e->type);
+		fprintf(stderr, "can't copy type %d\n", e->type);
 		free(e);
 		e = NULL;
 		break;
@@ -113,7 +113,7 @@ void expr_free(struct expr *e)
 		break;
 	case E_NOT:
 		expr_free(e->left.expr);
-		return;
+		break;
 	case E_EQUAL:
 	case E_GEQ:
 	case E_GTH:
@@ -127,7 +127,7 @@ void expr_free(struct expr *e)
 		expr_free(e->right.expr);
 		break;
 	default:
-		printf("how to free type %d?\n", e->type);
+		fprintf(stderr, "how to free type %d?\n", e->type);
 		break;
 	}
 	free(e);
@@ -138,8 +138,18 @@ static int trans_count;
 #define e1 (*ep1)
 #define e2 (*ep2)
 
+/*
+ * expr_eliminate_eq() helper.
+ *
+ * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
+ * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
+ * against all other leaves. Two equal leaves are both replaced with either 'y'
+ * or 'n' as appropriate for 'type', to be eliminated later.
+ */
 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
 {
+	/* Recurse down to leaves */
+
 	if (e1->type == type) {
 		__expr_eliminate_eq(type, &e1->left.expr, &e2);
 		__expr_eliminate_eq(type, &e1->right.expr, &e2);
@@ -150,12 +160,18 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e
 		__expr_eliminate_eq(type, &e1, &e2->right.expr);
 		return;
 	}
+
+	/* e1 and e2 are leaves. Compare them. */
+
 	if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
 	    e1->left.sym == e2->left.sym &&
 	    (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
 		return;
 	if (!expr_eq(e1, e2))
 		return;
+
+	/* e1 and e2 are equal leaves. Prepare them for elimination. */
+
 	trans_count++;
 	expr_free(e1); expr_free(e2);
 	switch (type) {
@@ -172,6 +188,35 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e
 	}
 }
 
+/*
+ * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both.
+ * Example reductions:
+ *
+ *	ep1: A && B           ->  ep1: y
+ *	ep2: A && B && C      ->  ep2: C
+ *
+ *	ep1: A || B           ->  ep1: n
+ *	ep2: A || B || C      ->  ep2: C
+ *
+ *	ep1: A && (B && FOO)  ->  ep1: FOO
+ *	ep2: (BAR && B) && A  ->  ep2: BAR
+ *
+ *	ep1: A && (B || C)    ->  ep1: y
+ *	ep2: (C || B) && A    ->  ep2: y
+ *
+ * Comparisons are done between all operands at the same "level" of && or ||.
+ * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the
+ * following operands will be compared:
+ *
+ *	- 'e1', 'e2 || e3', and 'e4 || e5', against each other
+ *	- e2 against e3
+ *	- e4 against e5
+ *
+ * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and
+ * '(e1 && e2) && e3' are both a single level.
+ *
+ * See __expr_eliminate_eq() as well.
+ */
 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
 {
 	if (!e1 || !e2)
@@ -197,6 +242,12 @@ void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
 #undef e1
 #undef e2
 
+/*
+ * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two
+ * &&/|| expressions are considered equal if every operand in one expression
+ * equals some operand in the other (operands do not need to appear in the same
+ * order), recursively.
+ */
 static int expr_eq(struct expr *e1, struct expr *e2)
 {
 	int res, old_count;
@@ -243,6 +294,17 @@ static int expr_eq(struct expr *e1, struct expr *e2)
 	return 0;
 }
 
+/*
+ * Recursively performs the following simplifications in-place (as well as the
+ * corresponding simplifications with swapped operands):
+ *
+ *	expr && n  ->  n
+ *	expr && y  ->  expr
+ *	expr || n  ->  expr
+ *	expr || y  ->  y
+ *
+ * Returns the optimized expression.
+ */
 static struct expr *expr_eliminate_yn(struct expr *e)
 {
 	struct expr *tmp;
@@ -516,12 +578,21 @@ static struct expr *expr_join_and(struct expr *e1, struct expr *e2)
 	return NULL;
 }
 
+/*
+ * expr_eliminate_dups() helper.
+ *
+ * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
+ * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
+ * against all other leaves to look for simplifications.
+ */
 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
 {
 #define e1 (*ep1)
 #define e2 (*ep2)
 	struct expr *tmp;
 
+	/* Recurse down to leaves */
+
 	if (e1->type == type) {
 		expr_eliminate_dups1(type, &e1->left.expr, &e2);
 		expr_eliminate_dups1(type, &e1->right.expr, &e2);
@@ -532,6 +603,9 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct
 		expr_eliminate_dups1(type, &e1, &e2->right.expr);
 		return;
 	}
+
+	/* e1 and e2 are leaves. Compare and process them. */
+
 	if (e1 == e2)
 		return;
 
@@ -568,6 +642,17 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct
 #undef e2
 }
 
+/*
+ * Rewrites 'e' in-place to remove ("join") duplicate and other redundant
+ * operands.
+ *
+ * Example simplifications:
+ *
+ *	A || B || A    ->  A || B
+ *	A && B && A=y  ->  A=y && B
+ *
+ * Returns the deduplicated expression.
+ */
 struct expr *expr_eliminate_dups(struct expr *e)
 {
 	int oldcount;
@@ -584,6 +669,7 @@ struct expr *expr_eliminate_dups(struct expr *e)
 			;
 		}
 		if (!trans_count)
+			/* No simplifications done in this pass. We're done */
 			break;
 		e = expr_eliminate_yn(e);
 	}
@@ -591,6 +677,12 @@ struct expr *expr_eliminate_dups(struct expr *e)
 	return e;
 }
 
+/*
+ * Performs various simplifications involving logical operators and
+ * comparisons.
+ *
+ * Allocates and returns a new expression.
+ */
 struct expr *expr_transform(struct expr *e)
 {
 	struct expr *tmp;
@@ -805,6 +897,20 @@ bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
  	return false;
 }
 
+/*
+ * Inserts explicit comparisons of type 'type' to symbol 'sym' into the
+ * expression 'e'.
+ *
+ * Examples transformations for type == E_UNEQUAL, sym == &symbol_no:
+ *
+ *	A              ->  A!=n
+ *	!A             ->  A=n
+ *	A && B         ->  !(A=n || B=n)
+ *	A || B         ->  !(A=n && B=n)
+ *	A && (B || C)  ->  !(A=n || (B=n && C=n))
+ *
+ * Allocates and returns a new expression.
+ */
 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
 {
 	struct expr *e1, *e2;
@@ -1073,7 +1179,7 @@ struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2)
 	return expr_get_leftmost_symbol(ret);
 }
 
-void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
+static void __expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken, bool revdep)
 {
 	if (!e) {
 		fn(data, NULL, "y");
@@ -1128,9 +1234,14 @@ void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *
 		fn(data, e->right.sym, e->right.sym->name);
 		break;
 	case E_OR:
-		expr_print(e->left.expr, fn, data, E_OR);
-		fn(data, NULL, " || ");
-		expr_print(e->right.expr, fn, data, E_OR);
+		if (revdep && e->left.expr->type != E_OR)
+			fn(data, NULL, "\n  - ");
+		__expr_print(e->left.expr, fn, data, E_OR, revdep);
+		if (revdep)
+			fn(data, NULL, "\n  - ");
+		else
+			fn(data, NULL, " || ");
+		__expr_print(e->right.expr, fn, data, E_OR, revdep);
 		break;
 	case E_AND:
 		expr_print(e->left.expr, fn, data, E_AND);
@@ -1163,6 +1274,11 @@ void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *
 		fn(data, NULL, ")");
 }
 
+void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
+{
+	__expr_print(e, fn, data, prevtoken, false);
+}
+
 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
 {
 	xfwrite(str, strlen(str), 1, data);
@@ -1207,3 +1323,13 @@ void expr_gstr_print(struct expr *e, struct gstr *gs)
 {
 	expr_print(e, expr_print_gstr_helper, gs, E_NONE);
 }
+
+/*
+ * Transform the top level "||" tokens into newlines and prepend each
+ * line with a minus. This makes expressions much easier to read.
+ * Suitable for reverse dependency expressions.
+ */
+void expr_gstr_print_revdep(struct expr *e, struct gstr *gs)
+{
+	__expr_print(e, expr_print_gstr_helper, gs, E_NONE, true);
+}