Fixed bug in circular dependency algo for migration dependencies.

Previous algo only worked if the first item was a part of the loop,
and you would get an infinite loop otherwise (see test).

To fix this, it was much easier to do a pre-pass.

A bonus is that you now get an error message that actually helps you debug
the dependency problem.

1 files changed, 14 insertions, 0 deletions

diff --git a/tests/migrations/test_graph.py b/tests/migrations/test_graph.py
index 5b3f5b8467..abb2b28dc1 100644
--- a/tests/migrations/test_graph.py
+++ b/tests/migrations/test_graph.py
@@ -134,6 +134,20 @@ class GraphTests(TestCase):
             graph.forwards_plan, ("app_a", "0003"),
         )
 
+    def test_circular_graph_2(self):
+        graph = MigrationGraph()
+        graph.add_node(('A', '0001'), None)
+        graph.add_node(('C', '0001'), None)
+        graph.add_node(('B', '0001'), None)
+        graph.add_dependency('A.0001', ('A', '0001'),('B', '0001'))
+        graph.add_dependency('B.0001', ('B', '0001'),('A', '0001'))
+        graph.add_dependency('C.0001', ('C', '0001'),('B', '0001'))
+
+        self.assertRaises(
+            CircularDependencyError,
+            graph.forwards_plan, ('C', '0001')
+        )
+
     def test_dfs(self):
         graph = MigrationGraph()
         root = ("app_a", "1")