diff options
Diffstat (limited to 'kconfiglib.py')
| -rw-r--r-- | kconfiglib.py | 184 |
1 files changed, 183 insertions, 1 deletions
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. |