Since commit f79dc03fe68c ("kconfig: refactor choice value
calculation"), when EXPERT is disabled, nothing within the "if INPUT"
... "endif" block in drivers/input/Kconfig is displayed. This issue
affects all command-line interfaces and GUI frontends.

The prompt for INPUT is hidden when EXPERT is disabled. Previously,
menu_is_visible() returned true in this case; however, it now returns
false, resulting in all sub-menu entries being skipped.

Here is a simplified test case illustrating the issue:

    config A
           bool "A" if X
           default y

    config B
           bool "B"
           depends on A

When X is disabled, A becomes unconfigurable and is forced to y.
B should be displayed, as its dependency is met.

This commit restores the necessary code, so menu_is_visible() functions
as it did previously.

Fixes: f79dc03fe68c ("kconfig: refactor choice value calculation")
Reported-by: Edmund Raile <edmund.raile@proton.me>
Closes: https://lore.kernel.org/all/5fd0dfc7ff171aa74352e638c276069a5f2e888d.camel@proton.me/
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>

Currently, every expression in Kconfig files produces a new abstract
syntax tree (AST), even if it is identical to a previously encountered
one.

Consider the following code:

    config FOO
           bool "FOO"
           depends on (A || B) && C

    config BAR
           bool "BAR"
           depends on (A || B) && C

    config BAZ
           bool "BAZ"
           depends on A || B

The "depends on" lines are similar, but currently a separate AST is
allocated for each one.

The current data structure looks like this:

  FOO->dep ==> AND        BAR->dep ==> AND        BAZ->dep ==> OR
              /   \                   /   \                   /  \
            OR     C                OR     C                 A    B
           /  \                    /  \
          A    B                  A    B

This is redundant; FOO->dep and BAR->dep have identical ASTs but
different memory instances.

We can optimize this; FOO->dep and BAR->dep can share the same AST, and
BAZ->dep can reference its sub tree.

The optimized data structure looks like this:

  FOO->dep, BAR->dep ==> AND
                        /   \
         BAZ->dep ==> OR     C
                     /  \
                    A    B

This commit introduces a hash table to keep track of allocated
expressions. If an identical expression is found, it is reused.

This does not necessarily result in memory savings, as menu_finalize()
transforms expressions without freeing up stale ones. This will be
addressed later.

One optimization that can be easily implemented is caching the
expression's value. Once FOO's dependency, (A || B) && C, is calculated,
it can be cached, eliminating the need to recalculate it for BAR.

This commit also reverts commit e983b7b17ad1 ("kconfig/menu.c: fix
multiple references to expressions in menu_add_prop()").

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

These functions will be useful for other host programs.

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

I believe its last usage was in the following code:

    if (prop == NULL)
            prop = stack->sym->prop;

This code was previously used to print the file name and line number of
associated symbols in sym_check_print_recursive(), which was removed by
commit 9d0d26604657 ("kconfig: recursive checks drop file/lineno").

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

Move array_size.h, hashtable.h, list.h, list_types.h from scripts/kconfig/
to scripts/include/.

These headers will be useful for other host programs.

Remove scripts/mod/list.h.

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

This flag is unneeded because a choice member can be detected by
other means.

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

Clarify that the given structures are not modified.

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

When a prompt is followed by "if <expr>", the symbol is configurable
when the if-conditional evaluates to true.

A typical usage is as follows:

    menuconfig BLOCK
            bool "Enable the block layer" if EXPERT
            default y

When EXPERT=n, the prompt is hidden, but this config entry is still
active, and BLOCK is set to its default value 'y'. When EXPERT=y, the
prompt is shown, making BLOCK a user-configurable option.

This usage is common throughout the kernel tree, but it has never worked
within a choice block.

[Test Code]

    config EXPERT
            bool "Allow expert users to modify more options"

    choice
            prompt "Choose" if EXPERT

    config A
            bool "A"

    config B
            bool "B"

    endchoice

[Result]

    # CONFIG_EXPERT is not set

When the prompt is hidden, the choice block should produce the default
without asking for the user's preference. Hence, the output should be:

    # CONFIG_EXPERT is not set
    CONFIG_A=y
    # CONFIG_B is not set

Removing unnecessary hacks fixes the issue.

This commit also changes the behavior of 'select' by choice members.

[Test Code 2]

    config MODULES
            def_bool y
            modules

    config DEP
            def_tristate m

    if DEP

    choice
            prompt "choose"

    config A
            bool "A"
            select C

    endchoice

    config B
            def_bool y
            select D

    endif

    config C
            tristate

    config D
            tristate

The current output is as follows:

    CONFIG_MODULES=y
    CONFIG_DEP=m
    CONFIG_A=y
    CONFIG_B=y
    CONFIG_C=y
    CONFIG_D=m

With this commit, the output will be changed as follows:

    CONFIG_MODULES=y
    CONFIG_DEP=m
    CONFIG_A=y
    CONFIG_B=y
    CONFIG_C=m
    CONFIG_D=m

CONFIG_C will be changed to 'm' because 'select C' will inherit the
dependency on DEP, which is 'm'.

This change is aligned with the behavior of 'select' outside a choice
block; 'select D' depends on DEP, therefore D is selected by (B && DEP).

Note:

With this commit, allmodconfig will set CONFIG_USB_ROLE_SWITCH to 'm'
instead of 'y'. I did not see any build regression with this change.

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

P_CHOICE is a pseudo property used to link a choice with its members.

There is no more code relying on this, except for some debug code.

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

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>