kconfig: refactor choice value calculation

Handling choices has always been in a PITA in Kconfig.

For example, fixes and reverts were repeated for randconfig with
KCONFIG_ALLCONFIG:

 - 422c809f03f0 ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
 - 23a5dfdad22a ("Revert "kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG"")
 - 8357b48549e1 ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
 - 490f16171119 ("Revert "kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG"")

As these commits pointed out, randconfig does not randomize choices when
KCONFIG_ALLCONFIG is used. This issue still remains.

[Test Case]

    choice
            prompt "choose"

    config A
            bool "A"

    config B
            bool "B"

    endchoice

    $ echo > all.config
    $ make KCONFIG_ALLCONFIG=1 randconfig

The output is always as follows:

    CONFIG_A=y
    # CONFIG_B is not set

Not only randconfig, but other all*config variants are also broken with
KCONFIG_ALLCONFIG.

With the same Kconfig,

    $ echo '# CONFIG_A is not set' > all.config
    $ make KCONFIG_ALLCONFIG=1 allyesconfig

You will get this:

    CONFIG_A=y
    # CONFIG_B is not set

This is incorrect because it does not respect all.config.

The correct output should be:

    # CONFIG_A is not set
    CONFIG_B=y

To handle user inputs more accurately, this commit refactors the code
based on the following principles:

 - When a user value is given, Kconfig must set it immediately.
   Do not defer it by setting SYMBOL_NEED_SET_CHOICE_VALUES.

 - The SYMBOL_DEF_USER flag must not be cleared, unless a new config
   file is loaded. Kconfig must not forget user inputs.

In addition, user values for choices must be managed with priority.
If user inputs conflict within a choice block, the newest value wins.
The values given by randconfig have lower priority than explicit user
inputs.

This commit implements it by using a linked list. Every time a choice
block gets a new input, it is moved to the top of the list.

Let me explain how it works.

Let's say, we have a choice block that consists of five symbols:
A, B, C, D, and E.

Initially, the linked list looks like this:

    A(=?) --> B(=?) --> C(=?) --> D(=?) --> E(=?)

Suppose randconfig is executed with the following KCONFIG_ALLCONFIG:

    CONFIG_C=y
    # CONFIG_A is not set
    CONFIG_D=y

First, CONFIG_C=y is read. C is set to 'y' and moved to the top.

    C(=y) --> A(=?) --> B(=?) --> D(=?) --> E(=?)

Next, '# CONFIG_A is not set' is read. A is set to 'n' and moved to
the top.

    A(=n) --> C(=y) --> B(=?) --> D(=?) --> E(=?)

Then, 'CONFIG_D=y' is read. D is set to 'y' and moved to the top.

    D(=y) --> A(=n) --> C(=y) --> B(=?) --> E(=?)

Lastly, randconfig shuffles the order of the remaining symbols,
resulting in:

    D(=y) --> A(=n) --> C(=y) --> B(=y) --> E(=y)
or
    D(=y) --> A(=n) --> C(=y) --> E(=y) --> B(=y)

When calculating the output, the linked list is traversed and the first
visible symbol with 'y' is taken. In this case, it is D if visible.

If D is hidden by 'depends on', the next node, A, is examined. Since
it is already specified as 'n', it is skipped. Next, C is checked, and
selected if it is visible.

If C is also invisible, either B or E is chosen as a result of the
randomization.

If B and E are also invisible, the linked list is traversed in the
reverse order, and the least prioritized 'n' symbol is chosen. It is
A in this case.

Now, Kconfig remembers all user values. This is a big difference from
the previous implementation, where Kconfig would forget CONFIG_C=y when
CONFIG_D=y appeared in the same input file.

The new appaorch respects user-specified values as much as possible.

Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

1 files changed, 10 insertions, 44 deletions

diff --git a/scripts/kconfig/confdata.c b/scripts/kconfig/confdata.c
index 1ac7fc9ad756..05823f85402a 100644
--- a/scripts/kconfig/confdata.c
+++ b/scripts/kconfig/confdata.c
@@ -382,10 +382,7 @@ load:
 
 	def_flags = SYMBOL_DEF << def;
 	for_all_symbols(sym) {
-		sym->flags |= SYMBOL_CHANGED;
 		sym->flags &= ~(def_flags|SYMBOL_VALID);
-		if (sym_is_choice(sym))
-			sym->flags |= def_flags;
 		switch (sym->type) {
 		case S_INT:
 		case S_HEX:
@@ -399,6 +396,8 @@ load:
 	}
 
 	while (getline_stripped(&line, &line_asize, in) != -1) {
+		struct menu *choice;
+
 		conf_lineno++;
 
 		if (!line[0]) /* blank line */
@@ -460,15 +459,14 @@ load:
 		if (conf_set_sym_val(sym, def, def_flags, val))
 			continue;
 
-		if (sym && sym_is_choice_value(sym)) {
-			struct symbol *cs = prop_get_symbol(sym_get_choice_prop(sym));
-			if (sym->def[def].tri == yes) {
-				if (cs->def[def].tri != no)
-					conf_warning("override: %s changes choice state", sym->name);
-				cs->def[def].val = sym;
-				cs->def[def].tri = yes;
-			}
-		}
+		/*
+		 * If this is a choice member, give it the highest priority.
+		 * If conflicting CONFIG options are given from an input file,
+		 * the last one wins.
+		 */
+		choice = sym_get_choice_menu(sym);
+		if (choice)
+			list_move(&sym->choice_link, &choice->choice_members);
 	}
 	free(line);
 	fclose(in);
@@ -514,18 +512,6 @@ int conf_read(const char *name)
 		/* maybe print value in verbose mode... */
 	}
 
-	for_all_symbols(sym) {
-		if (sym_has_value(sym) && !sym_is_choice_value(sym)) {
-			/* Reset values of generates values, so they'll appear
-			 * as new, if they should become visible, but that
-			 * doesn't quite work if the Kconfig and the saved
-			 * configuration disagree.
-			 */
-			if (sym->visible == no && !conf_unsaved)
-				sym->flags &= ~SYMBOL_DEF_USER;
-		}
-	}
-
 	if (conf_warnings || conf_unsaved)
 		conf_set_changed(true);
 
@@ -1146,23 +1132,3 @@ void conf_set_changed_callback(void (*fn)(bool))
 {
 	conf_changed_callback = fn;
 }
-
-void set_all_choice_values(struct symbol *csym)
-{
-	struct property *prop;
-	struct symbol *sym;
-	struct expr *e;
-
-	prop = sym_get_choice_prop(csym);
-
-	/*
-	 * Set all non-assinged choice values to no
-	 */
-	expr_list_for_each_sym(prop->expr, e, sym) {
-		if (!sym_has_value(sym))
-			sym->def[S_DEF_USER].tri = no;
-	}
-	csym->flags |= SYMBOL_DEF_USER;
-	/* clear VALID to get value calculated */
-	csym->flags &= ~(SYMBOL_VALID | SYMBOL_NEED_SET_CHOICE_VALUES);
-}