During kernel option migrations (e.g. CONFIG_CFI_CLANG to CONFIG_CFI),
existing .config files need to maintain backward compatibility while
preventing deprecated options from appearing in newly generated
configurations. This is challenging with existing Kconfig mechanisms
because:

1. Simply removing old options breaks existing .config files.
2. Manually listing an option as "deprecated" leaves it needlessly
   visible and still writes them to new .config files.
3. Using any method to remove visibility (.e.g no 'prompt', 'if n',
   etc) prevents the option from being processed at all.

Add a "transitional" attribute that creates symbols which are:
- Processed during configuration (can influence other symbols' defaults)
- Hidden from user menus (no prompts appear)
- Omitted from newly written .config files (gets migrated)
- Restricted to only having help sections (no defaults, selects, etc)
  making it truly just a "prior value pass-through" option.

The transitional syntax requires a type argument and prevents type
redefinition:

    config NEW_OPTION
        bool "New option"
        default OLD_OPTION

    config OLD_OPTION
        bool
        transitional
        help
          Transitional config for OLD_OPTION migration.

This allows seamless migration: olddefconfig processes existing
CONFIG_OLD_OPTION=y settings to enable CONFIG_NEW_OPTION=y, while
CONFIG_OLD_OPTION is omitted from newly generated .config files.

Added positive and negative testing via "testconfig" make target.

Co-developed-by: Vegard Nossum <vegard.nossum@oracle.com>
Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
Reviewed-by: Nathan Chancellor <nathan@kernel.org>
Tested-by: Nathan Chancellor <nathan@kernel.org>
Link: https://lore.kernel.org/r/20250923213422.1105654-2-kees@kernel.org
Signed-off-by: Kees Cook <kees@kernel.org>

Currently, menu->prompt->type is checked to distinguish "comment"
(P_COMMENT) and "menu" (P_MENU) entries from regular "config" entries.
This is odd because P_COMMENT and P_MENU are not properties.

This commit introduces menu type enum to distinguish menu types more
naturally.

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

Cache expression values to avoid recalculating them repeatedly.

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>

This clarifies the behavior of these functions.

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>

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>

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>