Use topological sort for migration operation dependency resolution

rather than an ad-hoc algorithm

4 files changed, 53 insertions, 25 deletions

diff --git a/AUTHORS b/AUTHORS
index ab62be513c..475ac4585e 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -377,6 +377,7 @@ answer newbie questions, and generally made Django that much better:
     Kevin McConnell <kevin.mcconnell@gmail.com>
     Kieran Holland <http://www.kieranholland.com>
     kilian <kilian.cavalotti@lip6.fr>
+    Klaas van Schelven <klaas@vanschelven.com>
     knox <christobzr@gmail.com>
     konrad@gwu.edu
     Kowito Charoenratchatabhan <kowito@felspar.com>
diff --git a/django/db/migrations/autodetector.py b/django/db/migrations/autodetector.py
index 7369cfad5c..8b0e77a93e 100644
--- a/django/db/migrations/autodetector.py
+++ b/django/db/migrations/autodetector.py
@@ -14,6 +14,8 @@ from django.db.migrations.questioner import MigrationQuestioner
 from django.db.migrations.optimizer import MigrationOptimizer
 from django.db.migrations.operations.models import AlterModelOptions
 
+from .topological_sort import stable_topological_sort
+
 
 class MigrationAutodetector(object):
     """
@@ -191,28 +193,19 @@ class MigrationAutodetector(object):
         # isn't bad, but we need to pull a few things around so FKs work nicely
         # inside the same app
         for app_label, ops in sorted(self.generated_operations.items()):
-            for i in range(10000):
-                found = False
-                for i, op in enumerate(ops):
-                    for dep in op._auto_deps:
-                        if dep[0] == app_label:
-                            # Alright, there's a dependency on the same app.
-                            for j, op2 in enumerate(ops):
-                                if j > i and self.check_dependency(op2, dep):
-                                    # shift the operation from position i after
-                                    # the operation at position j
-                                    ops = ops[:i] + ops[i + 1:j + 1] + [op] + ops[j + 1:]
-                                    found = True
-                                    break
-                        if found:
-                            break
-                    if found:
-                        break
-                if not found:
-                    break
-            else:
-                raise ValueError("Infinite loop caught in operation dependency resolution")
-            self.generated_operations[app_label] = ops
+
+            # construct a dependency-graph for in-app dependencies
+            dependency_graph = dict((op, set()) for op in ops)
+            for op in ops:
+                for dep in op._auto_deps:
+                    if dep[0] == app_label:
+                        for op2 in ops:
+                            if self.check_dependency(op2, dep):
+                                dependency_graph[op].add(op2)
+
+            # we use a stable sort for deterministic tests & general behavior
+            self.generated_operations[app_label] = stable_topological_sort(
+                ops, dependency_graph)
 
         # Now, we need to chop the lists of operations up into migrations with
         # dependencies on each other.
diff --git a/django/db/migrations/topological_sort.py b/django/db/migrations/topological_sort.py
new file mode 100644
index 0000000000..dc127cc7cf
--- /dev/null
+++ b/django/db/migrations/topological_sort.py
@@ -0,0 +1,34 @@
+def topological_sort_as_sets(dependency_graph):
+    """Variation of Kahn's algorithm (1962) that returns sets.
+
+    Takes a dependency graph as a dictionary of node => dependencies.
+
+    Yields sets of items in topological order, where the first set contains
+    all nodes without dependencies, and each following set contains all
+    nodes that depend on the nodes in the previously yielded sets.
+    """
+
+    todo = dependency_graph.copy()
+
+    while todo:
+        current = set(node for node, deps in todo.items() if len(deps) == 0)
+
+        if not current:
+            raise ValueError('Cyclic dependency in graph: {}'.format(
+                ', '.join(repr(x) for x in todo.items())))
+
+        yield current
+
+        # remove current from todo's nodes & dependencies
+        todo = {node: (dependencies - current) for node, dependencies in
+                todo.items() if node not in current}
+
+
+def stable_topological_sort(l, dependency_graph):
+    result = []
+    for layer in topological_sort_as_sets(dependency_graph):
+        for node in l:
+            if node in layer:
+                result.append(node)
+
+    return result
diff --git a/tests/migrations/test_autodetector.py b/tests/migrations/test_autodetector.py
index bd6763e4db..d891a83401 100644
--- a/tests/migrations/test_autodetector.py
+++ b/tests/migrations/test_autodetector.py
@@ -1107,12 +1107,12 @@ class AutodetectorTests(TestCase):
         # Right number of migrations?
         self.assertNumberMigrations(changes, "testapp", 1)
         # Right actions in right order?
-        self.assertOperationTypes(changes, "testapp", 0, ["RemoveField", "RemoveField", "DeleteModel", "RemoveField", "DeleteModel"])
+        self.assertOperationTypes(changes, "testapp", 0, ["RemoveField", "RemoveField", "RemoveField", "DeleteModel", "DeleteModel"])
         # Actions touching the right stuff?
         self.assertOperationAttributes(changes, "testapp", 0, 0, name="publishers")
         self.assertOperationAttributes(changes, "testapp", 0, 1, name="author")
-        self.assertOperationAttributes(changes, "testapp", 0, 2, name="Author")
-        self.assertOperationAttributes(changes, "testapp", 0, 3, name="publisher")
+        self.assertOperationAttributes(changes, "testapp", 0, 2, name="publisher")
+        self.assertOperationAttributes(changes, "testapp", 0, 3, name="Author")
         self.assertOperationAttributes(changes, "testapp", 0, 4, name="Contract")
 
     def test_non_circular_foreignkey_dependency_removal(self):