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)

12 files changed, 125 insertions, 0 deletions

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