diff options
| -rw-r--r-- | README.rst | 1 | ||||
| -rw-r--r-- | kconfiglib.py | 184 | ||||
| -rw-r--r-- | tests/Kchoice | 19 | ||||
| -rw-r--r-- | tests/Kdeploop0 | 3 | ||||
| -rw-r--r-- | tests/Kdeploop1 | 3 | ||||
| -rw-r--r-- | tests/Kdeploop10 | 48 | ||||
| -rw-r--r-- | tests/Kdeploop2 | 3 | ||||
| -rw-r--r-- | tests/Kdeploop3 | 3 | ||||
| -rw-r--r-- | tests/Kdeploop4 | 7 | ||||
| -rw-r--r-- | tests/Kdeploop5 | 7 | ||||
| -rw-r--r-- | tests/Kdeploop6 | 6 | ||||
| -rw-r--r-- | tests/Kdeploop7 | 11 | ||||
| -rw-r--r-- | tests/Kdeploop8 | 8 | ||||
| -rw-r--r-- | tests/Kdeploop9 | 7 | ||||
| -rw-r--r-- | testsuite.py | 35 |
15 files changed, 344 insertions, 1 deletions
@@ -248,6 +248,7 @@ Other features - **Warning parity with the C implementation** Generates the same warnings as the C implementation, plus a few extra ones. + Also detects dependency loops and ``source`` loops. This is less important if the input is assumed to be well-formed, but makes Kconfiglib a viable replacement for the C tools if e.g. a ``menuconfig`` diff --git a/kconfiglib.py b/kconfiglib.py index 7f5c122..608a2bb 100644 --- a/kconfiglib.py +++ b/kconfiglib.py @@ -726,9 +726,17 @@ class Kconfig(object): _check_choice_sanity(choice) - # Build Symbol._dependents for all symbols + # Build Symbol._dependents for all symbols and choices self._build_dep() + # Check for dependency loops + for sym in self.defined_syms: + _check_dep_loop_sym(sym, False) + + # Add extra dependencies from choices to choice symbols that get + # awkward during dependency loop detection + self._add_choice_deps() + self._warn_for_no_prompt = True @property @@ -2485,6 +2493,17 @@ class Kconfig(object): for _, cond in choice.defaults: _make_depend_on(choice, cond) + def _add_choice_deps(self): + # Choices also depend on the choice symbols themselves, because the + # y-mode selection of the choice might change if a choice symbol's + # visibility changes. + # + # We add these dependencies separately after dependency loop detection. + # The invalidation algorithm can handle the resulting + # <choice symbol> <-> <choice> dependency loops, but they make loop + # detection awkward. + + for choice in self.choices: # The choice symbols themselves, because the y mode selection might # change if a choice symbol's visibility changes for sym in choice.syms: @@ -2924,6 +2943,7 @@ class Symbol(object): "_cached_str_val", "_cached_tri_val", "_cached_vis", + "_checked", "_dependents", "_old_val", "_was_set", @@ -3435,6 +3455,9 @@ class Symbol(object): # See Kconfig._build_dep() self._dependents = set() + # Used during dependency loop detection + self._checked = 0 + def _assignable(self): # Worker function for the 'assignable' attribute @@ -3752,6 +3775,7 @@ class Choice(object): "_cached_assignable", "_cached_selection", "_cached_vis", + "_checked", "_dependents", "_was_set", "defaults", @@ -3974,6 +3998,9 @@ class Choice(object): # See Kconfig._build_dep() self._dependents = set() + # Used during dependency loop detection + self._checked = 0 + def _assignable(self): # Worker function for the 'assignable' attribute @@ -4827,6 +4854,161 @@ def _finalize_choice(node): if sym.orig_type == UNKNOWN: sym.orig_type = choice.orig_type +def _check_dep_loop_sym(sym, ignore_choice): + # Detects dependency loops using depth-first search on the dependency graph + # (which is calculated earlier in Kconfig._build_dep()). + # + # Algorithm: + # + # 1. Symbols/choices start out with _checked = 0, meaning unvisited. + # + # 2. When a symbol/choice is first visited, _checked is set to 1, meaning + # "visited, potentially part of a dependency loop". The recursive + # search then continues from the symbol/choice. + # + # 3. If we run into a symbol/choice X with _checked already set to 1, + # there's a dependency loop. The loop is found on the call stack by + # recording symbols while returning ("on the way back") until X is seen + # again. + # + # 4. Once a symbol/choice and all its dependencies (or dependents in this + # case) have been checked recursively without detecting any loops, its + # _checked is set to 2, meaning "visited, not part of a dependency + # loop". + # + # This saves work if we run into the symbol/choice again in later calls + # to _check_dep_loop_sym(). We just return immediately. + # + # Choices complicate things, as every choice symbol depends on every other + # choice symbol in a sense. When a choice is "entered" via a choice symbol + # X, we visit all choice symbols from the choice except X, and prevent + # immediately revisiting the choice with a flag (ignore_choice). + # + # Maybe there's a better way to handle this (different flags or the + # like...) + + if not sym._checked: + # sym._checked == 0, unvisited + + sym._checked = 1 + + for dep in sym._dependents: + # Choices show up in Symbol._dependents when the choice has the + # symbol in a 'prompt' or 'default' condition (e.g. + # 'default ... if SYM'). + # + # Since we aren't entering the choice via a choice symbol, all + # choice symbols need to be checked, hence the None. + loop = _check_dep_loop_choice(dep, None) \ + if isinstance(dep, Choice) \ + else _check_dep_loop_sym(dep, False) + + if loop: + # Dependency loop found + return _found_dep_loop(loop, sym) + + if sym.choice and not ignore_choice: + loop = _check_dep_loop_choice(sym.choice, sym) + if loop: + # Dependency loop found + return _found_dep_loop(loop, sym) + + # The symbol is not part of a dependency loop + sym._checked = 2 + + # No dependency loop found + return None + + if sym._checked == 2: + # The symbol was checked earlier and is already known to not be part of + # a dependency loop + return None + + # sym._checked == 1, found a dependency loop. Return the symbol as the + # first element in it. + return (sym,) + +def _check_dep_loop_choice(choice, skip): + if not choice._checked: + # choice._checked == 0, unvisited + + choice._checked = 1 + + # Check for loops involving choice symbols. If we came here via a + # choice symbol, skip that one, as we'd get a false positive + # '<sym FOO> -> <choice> -> <sym FOO>' loop otherwise. + for sym in choice.syms: + if sym is not skip: + # Prevent the choice from being immediately re-entered via the + # "is a choice symbol" path by passing True + loop = _check_dep_loop_sym(sym, True) + if loop: + # Dependency loop found + return _found_dep_loop(loop, choice) + + # The choice is not part of a dependency loop + choice._checked = 2 + + # No dependency loop found + return None + + if choice._checked == 2: + # The choice was checked earlier and is already known to not be part of + # a dependency loop + return None + + # choice._checked == 1, found a dependency loop. Return the choice as the + # first element in it. + return (choice,) + +def _found_dep_loop(loop, cur): + # Called "on the way back" when we know we have a loop + + # Is the symbol/choice 'cur' where the loop started? + if cur is not loop[0]: + # Nope, it's just a part of the loop + return loop + (cur,) + + # Yep, we have the entire loop. Throw an exception that shows it. + + msg = "\nDependency loop\n" \ + "===============\n\n" + + for item in loop: + if item is not loop[0]: + msg += "...depends on " + if isinstance(item, Symbol) and item.choice: + msg += "the choice symbol " + + msg += "{}, with definition...\n\n{}\n" \ + .format(_name_and_loc(item), item) + + # Small wart: Since we reuse the already calculated + # Symbol/Choice._dependents sets for recursive dependency detection, we + # lose information on whether a dependency came from a 'select'/'imply' + # condition or e.g. a 'depends on'. + # + # This might cause selecting symbols to "disappear". For example, + # a symbol B having 'select A if C' gives a direct dependency from A to + # C, since it corresponds to a reverse dependency of B && C. + # + # Always print reverse dependencies for symbols that have them to make + # sure information isn't lost. I wonder if there's some neat way to + # improve this. + + if isinstance(item, Symbol): + if item.rev_dep is not item.kconfig.n: + msg += "(select-related dependencies: {})\n\n" \ + .format(expr_str(item.rev_dep)) + + if item.weak_rev_dep is not item.kconfig.n: + msg += "(imply-related dependencies: {})\n\n" \ + .format(expr_str(item.rev_dep)) + + msg += "...depends again on {}".format(_name_and_loc(loop[0])) + + raise KconfigSyntaxError(msg) + def _check_sym_sanity(sym): # Checks various symbol properties that are handiest to check after # parsing. Only generates errors and warnings. diff --git a/tests/Kchoice b/tests/Kchoice index f635ccc..16b38d4 100644 --- a/tests/Kchoice +++ b/tests/Kchoice @@ -132,6 +132,25 @@ config MMT_5 bool endchoice +# Choice where the default selection (the first symbol) depends on another +# symbol. If that symbol becomes 'n', the default selection should change to +# the first visible symbol in the choice. + +choice DEFAULT_WITH_DEP + bool "default with dep" + +config A + bool "A" + depends on DEP + +config B + bool "B" + +endchoice + +config DEP + bool "dep" + # Choice with symbols that shouldn't be considered choice symbols because they # depend on the preceding symbol. This might be a kconfig bug, but some things # use it, so we need to emulate it. diff --git a/tests/Kdeploop0 b/tests/Kdeploop0 new file mode 100644 index 0000000..98d3e3c --- /dev/null +++ b/tests/Kdeploop0 @@ -0,0 +1,3 @@ +config FOO + bool + depends on FOO diff --git a/tests/Kdeploop1 b/tests/Kdeploop1 new file mode 100644 index 0000000..134cd29 --- /dev/null +++ b/tests/Kdeploop1 @@ -0,0 +1,3 @@ +config FOO + bool + select FOO diff --git a/tests/Kdeploop10 b/tests/Kdeploop10 new file mode 100644 index 0000000..2e616ae --- /dev/null +++ b/tests/Kdeploop10 @@ -0,0 +1,48 @@ +config A + bool + depends on B + +config B + bool + depends on C = 7 + +config C + int + range D 8 + +config D + int + default 3 if E + default 8 + +config E + bool + +config F + bool + select E if G + +config G + bool + depends on H + +choice + bool "choice" + +config H + bool "H" + depends on I + +endchoice + +choice + bool "choice" if J + +config I + bool "I" + +endchoice + +config J + bool + depends on A diff --git a/tests/Kdeploop2 b/tests/Kdeploop2 new file mode 100644 index 0000000..c997243 --- /dev/null +++ b/tests/Kdeploop2 @@ -0,0 +1,3 @@ +config FOO + bool + default FOO diff --git a/tests/Kdeploop3 b/tests/Kdeploop3 new file mode 100644 index 0000000..90c83d5 --- /dev/null +++ b/tests/Kdeploop3 @@ -0,0 +1,3 @@ +config FOO + bool + default y if FOO diff --git a/tests/Kdeploop4 b/tests/Kdeploop4 new file mode 100644 index 0000000..789d8b7 --- /dev/null +++ b/tests/Kdeploop4 @@ -0,0 +1,7 @@ +config FOO + bool + depends on BAR + +config BAR + bool + depends on FOO diff --git a/tests/Kdeploop5 b/tests/Kdeploop5 new file mode 100644 index 0000000..f12fe6b --- /dev/null +++ b/tests/Kdeploop5 @@ -0,0 +1,7 @@ +config FOO + bool + select BAR + +config BAR + bool + select FOO diff --git a/tests/Kdeploop6 b/tests/Kdeploop6 new file mode 100644 index 0000000..cb1e701 --- /dev/null +++ b/tests/Kdeploop6 @@ -0,0 +1,6 @@ +config FOO + bool + +config BAR + bool + select FOO if FOO diff --git a/tests/Kdeploop7 b/tests/Kdeploop7 new file mode 100644 index 0000000..63d2c57 --- /dev/null +++ b/tests/Kdeploop7 @@ -0,0 +1,11 @@ +choice + bool "choice" + +config FOO + bool "foo" + depends on BAR + +config BAR + bool "bar" + +endchoice diff --git a/tests/Kdeploop8 b/tests/Kdeploop8 new file mode 100644 index 0000000..84efd8d --- /dev/null +++ b/tests/Kdeploop8 @@ -0,0 +1,8 @@ +choice + bool "choice" + default FOO if FOO + +config FOO + bool "foo" + +endchoice diff --git a/tests/Kdeploop9 b/tests/Kdeploop9 new file mode 100644 index 0000000..939f7f4 --- /dev/null +++ b/tests/Kdeploop9 @@ -0,0 +1,7 @@ +choice + bool "choice" if FOO + +config FOO + bool "foo" + +endchoice diff --git a/testsuite.py b/testsuite.py index b02c51a..8f33736 100644 --- a/testsuite.py +++ b/testsuite.py @@ -1917,6 +1917,24 @@ g verify(c.syms["MMT_3"].orig_type == TRISTATE, "Expected MMT_3 to have type tristate") + # Verify that the default selection can change depending on the + # visibility of the choice symbols + + default_with_dep_choice = c.named_choices["DEFAULT_WITH_DEP"] + + verify(default_with_dep_choice.selection is c.syms["B"], + "Wrong choice default with unsatisfied deps on default") + + c.syms["DEP"].set_value("y") + + verify(default_with_dep_choice.selection is c.syms["A"], + "Wrong choice default with satisfied deps on default") + + c.syms["DEP"].set_value("n") + + verify(default_with_dep_choice.selection is c.syms["B"], + "Wrong choice default with unsatisfied deps on default (round two)") + # Verify that symbols in choices that depend on the preceding symbol aren't # considered choice symbols @@ -1978,6 +1996,19 @@ g "A B C D E") + print("Testing dependency loop detection") + + # These are all expected to raise dependency loop errors + for i in range(11): + filename = "Kconfiglib/tests/Kdeploop" + str(i) + try: + Kconfig(filename) + except KconfigSyntaxError as e: + pass + else: + fail("dependency loop in {} not detected".format(filename)) + + print("\nAll selftests passed\n" if all_passed else "\nSome selftests failed\n") @@ -2179,6 +2210,10 @@ def test_sanity(conf, arch, srcarch): verify(not (sym.orig_type not in (BOOL, TRISTATE) and sym.choice), sym.name + " is a choice symbol but not bool/tristate") + verify(sym._checked == 2, + "{} has broken dependency loop detection (_checked = {})" + .format(sym.name, sym._checked)) + for key, sym in conf.const_syms.items(): verify(isinstance(key, str), "weird key '{}' in const_syms dict".format(key)) |