diff options
| author | Marten Kenbeek <marten.knbk@gmail.com> | 2015-02-20 05:43:45 +0100 |
|---|---|---|
| committer | Markus Holtermann <info@markusholtermann.eu> | 2015-02-23 12:55:43 +0100 |
| commit | 980dfca7174a3e00a214ad554bb9199529139796 (patch) | |
| tree | a5c5954377992cace273c243d934c3ec3f281a64 /tests | |
| parent | ed941ef2d0c0560e4eb98e0801e698d18f01d77b (diff) | |
[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
Diffstat (limited to 'tests')
| -rw-r--r-- | tests/migrations/test_graph.py | 22 |
1 files changed, 20 insertions, 2 deletions
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): |