topological sort: fix loop detection

1 files changed, 16 insertions, 5 deletions

diff --git a/yoyo/topologicalsort.py b/yoyo/topologicalsort.py
index 9afa6f1..d8320a6 100644
--- a/yoyo/topologicalsort.py
+++ b/yoyo/topologicalsort.py
@@ -23,21 +23,32 @@ def topological_sort(
     items: Iterable[T], dependency_graph: Mapping[T, Collection[T]]
 ) -> Iterable[T]:
 
-    seen_since_last_output = 0
+    seen_since_last_change = 0
     stack = list(reversed(list(items)))
     output: Set[T] = set()
     blocked_on: Dict[T, Set[T]] = defaultdict(set)
     while stack:
-        if seen_since_last_output == len(stack):
+        if seen_since_last_change == len(stack):
+            for item in blocked_on:
+                if item not in stack:
+                    raise ValueError(
+                        f"Dependency graph contains a non-existent node {item!r}"
+                    )
             raise CycleError("Dependency graph loop detected", stack)
         n = stack.pop()
         if all(d in output for d in dependency_graph.get(n, [])):
-            seen_since_last_output = 0
+            changed = True
             output.add(n)
             yield n
             for blocked in blocked_on[n]:
                 stack.append(blocked)
         else:
-            seen_since_last_output += 1
+            changed = False
             for d in dependency_graph.get(n, []):
-                blocked_on[d].add(n)
+                if n not in blocked_on[d]:
+                    blocked_on[d].add(n)
+                    changed = True
+        if changed:
+            seen_since_last_change = 0
+        else:
+            seen_since_last_change += 1