Add dependency loop detection

Pretty long overdue.

Until now, dependency loops have raised a hard-to-debug Python
RecursionError during evaluation. A Kconfiglib exception is raised now
instead, with a message that lists all the items in the loop.

See the comment at the start of _check_dep_loop_sym() for an overview of
the algorithm. At a high level, it's loop detection in a directed graph
by keeping track of unvisited/visited nodes during depth-first search.
(A third "visited, known to not be in a dependency loop" state is used
as well.)

Choices complicate things, as they're inherently loopy: The choice
depends on the choice symbols and vice versa, and the choice symbols in
a sense all depend on each other.

Add the choice-to-choice-symbol dependencies separately after dependency
loop detection, so that there's just the choice-symbol-to-choice
dependencies to deal with. It simplifies things, as it makes it possible
to tell dependencies from 'prompt' and 'default' conditions on the
choice from choice symbol dependencies.

Do some flag shenanigans to prevent the choice from being "re-entered"
while looping through the choice symbols. Maybe this could be cleaned up
a bit somehow...

Example exception message:

Dependency loop
===============

A (defined at tests/Kdeploop10:1), with definition...

config A
	bool
	depends on B

...depends on B (defined at tests/Kdeploop10:5), with definition...

config B
	bool
	depends on C = 7

...depends on C (defined at tests/Kdeploop10:9), with definition...

config C
	int
	range D 8

...depends on D (defined at tests/Kdeploop10:13), with definition...

config D
	int
	default 3 if E
	default 8

...depends on E (defined at tests/Kdeploop10:18), with definition...

config E
	bool

(select-related dependencies: F && G)

...depends on G (defined at tests/Kdeploop10:25), with definition...

config G
	bool
	depends on H

...depends on the choice symbol H (defined at tests/Kdeploop10:32), with definition...

config H
	bool
	prompt "H" if I && <choice>
	depends on I && <choice>

...depends on the choice symbol I (defined at tests/Kdeploop10:41), with definition...

config I
	bool
	prompt "I" if <choice>
	depends on <choice>

...depends on <choice> (defined at tests/Kdeploop10:38), with definition...

choice
	bool
	prompt "choice" if J

...depends on J (defined at tests/Kdeploop10:46), with definition...

config J
	bool
	depends on A

...depends again on A (defined at tests/Kdeploop10:1)

15 files changed, 344 insertions, 1 deletions

diff --git a/README.rst b/README.rst
index 650947d..b4bcd79 100644
--- a/README.rst
+++ b/README.rst
@@ -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))