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)

1 files changed, 35 insertions, 0 deletions

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))