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 e983b7b17a ("kconfig/menu.c: fix
multiple references to expressions in menu_add_prop()").
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
P_SYMBOL is a pseudo property that was previously used for data linking
purposes.
It is no longer used except for debug prints. Remove it.
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>
E_LIST was preveously used to form an expression tree consisting of
choice members.
It is no longer used.
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:
- 422c809f03 ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
- 23a5dfdad2 ("Revert "kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG"")
- 8357b48549 ("kconfig: fix randomising choice entries in presence of KCONFIG_ALLCONFIG")
- 490f161711 ("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>
expr_trans_bool() performs an incorrect transformation.
[Test Code]
config MODULES
def_bool y
modules
config A
def_bool y
select C if B != n
config B
def_tristate m
config C
tristate
[Result]
CONFIG_MODULES=y
CONFIG_A=y
CONFIG_B=m
CONFIG_C=m
This output is incorrect because CONFIG_C=y is expected.
Documentation/kbuild/kconfig-language.rst clearly explains the function
of the '!=' operator:
If the values of both symbols are equal, it returns 'n',
otherwise 'y'.
Therefore, the statement:
select C if B != n
should be equivalent to:
select C if y
Or, more simply:
select C
Hence, the symbol C should be selected by the value of A, which is 'y'.
However, expr_trans_bool() wrongly transforms it to:
select C if B
Therefore, the symbol C is selected by (A && B), which is 'm'.
The comment block of expr_trans_bool() correctly explains its intention:
* bool FOO!=n => FOO
^^^^
If FOO is bool, FOO!=n can be simplified into FOO. This is correct.
However, the actual code performs this transformation when FOO is
tristate:
if (e->left.sym->type == S_TRISTATE) {
^^^^^^^^^^
While it can be fixed to S_BOOLEAN, there is no point in doing so
because expr_tranform() already transforms FOO!=n to FOO when FOO is
bool. (see the "case E_UNEQUAL" part)
expr_trans_bool() is wrong and unnecessary.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Acked-by: Randy Dunlap <rdunlap@infradead.org>
This has not been used since commit e911503085 ("Kconfig: Remove
bad inference rules expr_eliminate_dups2()").
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
This flag is set to symbols that are not intended to be written
to the .config file.
Since commit b75b0a819a ("kconfig: change defconfig_list option to
environment variable"), SYMBOL_NO_WRITE is only set to choices.
Therefore, (sym->flags & SYMBOL_NO_WRITE) is equivalent to
sym_is_choice(sym). This flag is no longer necessary.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
The 'choice' statement is primarily used to exclusively select one
option, but the 'optional' property allows all entries to be disabled.
In the following example, both A and B can be disabled simultaneously:
choice
prompt "choose A, B, or nothing"
optional
config A
bool "A"
config B
bool "B"
endchoice
You can achieve the equivalent outcome by other means.
A common solution is to add another option to guard the choice block.
In the following example, you can set ENABLE_A_B_CHOICE=n to disable
the entire choice block:
choice
prompt "choose A or B"
depends on ENABLE_A_B_CHOICE
config A
bool "A"
config B
bool "B"
endchoice
Another approach is to insert one more entry:
choice
prompt "choose A, B, or disable both"
config A
bool "A"
config B
bool "B"
config DISABLE_A_AND_B
bool "choose this to disable both A and B"
endchoice
Some real examples are DEBUG_INFO_NONE, INITRAMFS_COMPRESSION_NONE,
LTO_NONE, etc.
The 'optional' property is even more unnecessary for a tristate choice.
Without the 'optional' property, you can disable A and B; you can set
'm' in the choice prompt, and disable A and B individually:
choice
prompt "choose one built-in or make them modular"
config A
tristate "A"
config B
tristate "B"
endchoice
In conclusion, the 'optional' property was unneeded.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nicolas Schier <n.schier@avm.de>
All symbols except choices have a name.
Previously, choices were allowed to have a name, but commit c83f020973
("kconfig: remove named choice support") eliminated that possibility.
Now, it is easy to distinguish choices from normal symbols; if the name
is NULL, it is a choice.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nicolas Schier <n.schier@avm.de>
Currently, there is no direct link from (struct symbol) to (struct menu).
It is still possible to access associated menus through the P_SYMBOL
property, because property::menu is the relevant menu entry, but it
results in complex code, as seen in get_symbol_str().
Use a linked list for simpler traversal of relevant menus.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Reviewed-by: Nicolas Schier <nicolas@fjasle.eu>
Use helper macros in hashtable.h for generic hashtable implementation.
We can git rid of the hash head index of for_all_symbols().
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
The struct list_head is often embedded in other structures, while other
code is used in C functions.
By separating struct list_head into its own header, other headers are no
longer required to include the entire list.h.
This is similar to the kernel space, where struct list_head is defined
in <linux/types.h> instead of <linux/list.h>.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
Currently, file_lookup() returns a pointer to (struct file), but the
callers use only file->name.
Make it return the ->name member directly.
This adjustment encapsulates struct file and file_list as internal
implementation.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
struct file has two link nodes, 'next' and 'parent'.
The former is used to link files in the 'file_list' linked list,
which manages the list of Kconfig files seen so far.
The latter is used to link files in the 'current_file' linked list,
which manages the inclusion ("source") tree.
The latter should be tracked together with the lexer state.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
struct property is linked to struct file for diagnostic purposes.
It is always used to retrieve the file name through prop->file->name.
Associate struct property with the file name directly.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
struct menu is linked to struct file for diagnostic purposes.
It is always used to retrieve the file name through menu->file->name.
Associate struct menu with the file name directly.
Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
