Fixed #23835: Changed circular dependency in DFS to be less infinite

2 files changed, 29 insertions, 2 deletions

diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py
index 23808e2af1..b454d17f35 100644
--- a/django/db/migrations/graph.py
+++ b/django/db/migrations/graph.py
@@ -116,8 +116,8 @@ class MigrationGraph(object):
             visited.insert(0, node)
             children = sorted(get_children(node))
 
-            if not children:
-                path = []
+            if path[-1] == node:
+                path.pop()
 
             stack = children + stack
 
diff --git a/tests/migrations/test_graph.py b/tests/migrations/test_graph.py
index e70481a462..5b3f5b8467 100644
--- a/tests/migrations/test_graph.py
+++ b/tests/migrations/test_graph.py
@@ -188,3 +188,30 @@ class GraphTests(TestCase):
         msg = "Migration app_a.0002 dependencies reference nonexistent child node ('app_a', '0002')"
         with self.assertRaisesMessage(NodeNotFoundError, msg):
             graph.add_dependency("app_a.0002", ("app_a", "0002"), ("app_a", "0001"))
+
+    def test_infinite_loop(self):
+        """
+        Tests a complex dependency graph:
+
+        app_a:        0001 <-
+                             \
+        app_b:        0001 <- x 0002 <-
+                       /               \
+        app_c:   0001<-  <------------- x 0002
+
+        And apply sqashing on app_c.
+        """
+        graph = MigrationGraph()
+
+        graph.add_node(("app_a", "0001"), None)
+        graph.add_node(("app_b", "0001"), None)
+        graph.add_node(("app_b", "0002"), None)
+        graph.add_node(("app_c", "0001_squashed_0002"), None)
+
+        graph.add_dependency("app_b.0001", ("app_b", "0001"), ("app_c", "0001_squashed_0002"))
+        graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_a", "0001"))
+        graph.add_dependency("app_b.0002", ("app_b", "0002"), ("app_b", "0001"))
+        graph.add_dependency("app_c.0001_squashed_0002", ("app_c", "0001_squashed_0002"), ("app_b", "0002"))
+
+        with self.assertRaises(CircularDependencyError):
+            graph.forwards_plan(("app_c", "0001_squashed_0002"))