Revert "Use topological sort for migration operation dependency resolution"

This commit broke the tests on Python 3.

This reverts commit 13d613f80011852404198dfafd1f09c0c0ea42e6.

4 files changed, 25 insertions, 53 deletions

diff --git a/AUTHORS b/AUTHORS
index dd78347071..949de416f5 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -378,7 +378,6 @@ 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 8b0e77a93e..7369cfad5c 100644
--- a/django/db/migrations/autodetector.py
+++ b/django/db/migrations/autodetector.py
@@ -14,8 +14,6 @@ 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):
     """
@@ -193,19 +191,28 @@ 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()):
-
-            # 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)
+            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
 
         # 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
deleted file mode 100644
index dc127cc7cf..0000000000
--- a/django/db/migrations/topological_sort.py
+++ /dev/null
@@ -1,34 +0,0 @@
-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 d891a83401..bd6763e4db 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", "RemoveField", "DeleteModel", "DeleteModel"])
+        self.assertOperationTypes(changes, "testapp", 0, ["RemoveField", "RemoveField", "DeleteModel", "RemoveField", "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="publisher")
-        self.assertOperationAttributes(changes, "testapp", 0, 3, name="Author")
+        self.assertOperationAttributes(changes, "testapp", 0, 2, name="Author")
+        self.assertOperationAttributes(changes, "testapp", 0, 3, name="publisher")
         self.assertOperationAttributes(changes, "testapp", 0, 4, name="Contract")
 
     def test_non_circular_foreignkey_dependency_removal(self):