From 980dfca7174a3e00a214ad554bb9199529139796 Mon Sep 17 00:00:00 2001
From: Marten Kenbeek <marten.knbk@gmail.com>
Date: Fri, 20 Feb 2015 05:43:45 +0100
Subject: [1.8.x] Fixed #24366 -- Optimized traversal of large migration
 dependency graphs.

Switched from an adjancency list and uncached, iterative depth-first
search to a Node-based design with direct parent/child links and a
cached, recursive depth-first search. With this change, calculating
a migration plan for a large graph takes several seconds instead of
several hours.

Marked test `migrations.test_graph.GraphTests.test_dfs` as an expected
failure due to reaching the maximum recursion depth.

Backport of 78d43a5e1064b63db1c486516c4263ef1c4c975c from master
---
 tests/migrations/test_graph.py | 22 ++++++++++++++++++++--
 1 file changed, 20 insertions(+), 2 deletions(-)

(limited to 'tests')

diff --git a/tests/migrations/test_graph.py b/tests/migrations/test_graph.py
index cfb61d355f..50a8314c8b 100644
--- a/tests/migrations/test_graph.py
+++ b/tests/migrations/test_graph.py
@@ -1,3 +1,5 @@
+from unittest import expectedFailure
+
 from django.db.migrations.graph import (
     CircularDependencyError, MigrationGraph, NodeNotFoundError,
 )
@@ -151,7 +153,23 @@ class GraphTests(TestCase):
             graph.forwards_plan, ('C', '0001')
         )
 
-    def test_dfs(self):
+    def test_deep_graph(self):
+        graph = MigrationGraph()
+        root = ("app_a", "1")
+        graph.add_node(root, None)
+        expected = [root]
+        for i in range(2, 750):
+            parent = ("app_a", str(i - 1))
+            child = ("app_a", str(i))
+            graph.add_node(child, None)
+            graph.add_dependency(str(i), child, parent)
+            expected.append(child)
+
+        actual = graph.node_map[root].descendants()
+        self.assertEqual(expected[::-1], actual)
+
+    @expectedFailure
+    def test_recursion_depth(self):
         graph = MigrationGraph()
         root = ("app_a", "1")
         graph.add_node(root, None)
@@ -163,7 +181,7 @@ class GraphTests(TestCase):
             graph.add_dependency(str(i), child, parent)
             expected.append(child)
 
-        actual = graph.dfs(root, lambda x: graph.dependents.get(x, set()))
+        actual = graph.node_map[root].descendants()
         self.assertEqual(expected[::-1], actual)
 
     def test_plan_invalid_node(self):
-- 
cgit v1.3