Fixed #23844 -- Used topological sort for migration operation dependency resolution.

This removes the concept of equality between operations to guarantee
compatilibity with Python 3.

Python 3 requires equality to result in identical object hashes. It's
impossible to implement a unique hash that preserves equality as
operations such as field creation depend on being able to accept
arbitrary dicts that cannot be hashed reliably.

Thanks Klaas van Schelven for the original patch in
13d613f80011852404198dfafd1f09c0c0ea42e6.

4 files changed, 20 insertions, 35 deletions

diff --git a/tests/custom_migration_operations/more_operations.py b/tests/custom_migration_operations/more_operations.py
index 6fe3d1cf93..30cf246ceb 100644
--- a/tests/custom_migration_operations/more_operations.py
+++ b/tests/custom_migration_operations/more_operations.py
@@ -5,6 +5,13 @@ class TestOperation(Operation):
     def __init__(self):
         pass
 
+    def deconstruct(self):
+        return (
+            self.__class__.__name__,
+            [],
+            {}
+        )
+
     @property
     def reversible(self):
         return True
diff --git a/tests/custom_migration_operations/operations.py b/tests/custom_migration_operations/operations.py
index fc084f8412..3a4127d753 100644
--- a/tests/custom_migration_operations/operations.py
+++ b/tests/custom_migration_operations/operations.py
@@ -5,6 +5,13 @@ class TestOperation(Operation):
     def __init__(self):
         pass
 
+    def deconstruct(self):
+        return (
+            self.__class__.__name__,
+            [],
+            {}
+        )
+
     @property
     def reversible(self):
         return True
diff --git a/tests/migrations/test_autodetector.py b/tests/migrations/test_autodetector.py
index 3f024fe523..25aaf939ce 100644
--- a/tests/migrations/test_autodetector.py
+++ b/tests/migrations/test_autodetector.py
@@ -1268,12 +1268,12 @@ class AutodetectorTests(TestCase):
         # Right number/type of migrations?
         self.assertNumberMigrations(changes, "testapp", 1)
         self.assertOperationTypes(changes, "testapp", 0, [
-            "RemoveField", "RemoveField", "DeleteModel", "RemoveField", "DeleteModel"
+            "RemoveField", "RemoveField", "RemoveField", "DeleteModel", "DeleteModel"
         ])
         self.assertOperationAttributes(changes, "testapp", 0, 0, name="publishers", model_name='author')
         self.assertOperationAttributes(changes, "testapp", 0, 1, name="author", model_name='contract')
-        self.assertOperationAttributes(changes, "testapp", 0, 2, name="Author")
-        self.assertOperationAttributes(changes, "testapp", 0, 3, name="publisher", model_name='contract')
+        self.assertOperationAttributes(changes, "testapp", 0, 2, name="publisher", model_name='contract')
+        self.assertOperationAttributes(changes, "testapp", 0, 3, name="Author")
         self.assertOperationAttributes(changes, "testapp", 0, 4, name="Contract")
 
     def test_non_circular_foreignkey_dependency_removal(self):
diff --git a/tests/migrations/test_optimizer.py b/tests/migrations/test_optimizer.py
index d36b93355e..dba07c2878 100644
--- a/tests/migrations/test_optimizer.py
+++ b/tests/migrations/test_optimizer.py
@@ -20,43 +20,14 @@ class OptimizerTests(TestCase):
 
     def assertOptimizesTo(self, operations, expected, exact=None, less_than=None):
         result, iterations = self.optimize(operations)
+        result = [repr(f.deconstruct()) for f in result]
+        expected = [repr(f.deconstruct()) for f in expected]
         self.assertEqual(expected, result)
         if exact is not None and iterations != exact:
             raise self.failureException("Optimization did not take exactly %s iterations (it took %s)" % (exact, iterations))
         if less_than is not None and iterations >= less_than:
             raise self.failureException("Optimization did not take less than %s iterations (it took %s)" % (less_than, iterations))
 
-    def test_operation_equality(self):
-        """
-        Tests the equality operator on lists of operations.
-        If this is broken, then the optimizer will get stuck in an
-        infinite loop, so it's kind of important.
-        """
-        self.assertEqual(
-            [migrations.DeleteModel("Test")],
-            [migrations.DeleteModel("Test")],
-        )
-        self.assertEqual(
-            [migrations.CreateModel("Test", [("name", models.CharField(max_length=255))])],
-            [migrations.CreateModel("Test", [("name", models.CharField(max_length=255))])],
-        )
-        self.assertNotEqual(
-            [migrations.CreateModel("Test", [("name", models.CharField(max_length=255))])],
-            [migrations.CreateModel("Test", [("name", models.CharField(max_length=100))])],
-        )
-        self.assertEqual(
-            [migrations.AddField("Test", "name", models.CharField(max_length=255))],
-            [migrations.AddField("Test", "name", models.CharField(max_length=255))],
-        )
-        self.assertNotEqual(
-            [migrations.AddField("Test", "name", models.CharField(max_length=255))],
-            [migrations.AddField("Test", "name", models.CharField(max_length=100))],
-        )
-        self.assertNotEqual(
-            [migrations.AddField("Test", "name", models.CharField(max_length=255))],
-            [migrations.AlterField("Test", "name", models.CharField(max_length=255))],
-        )
-
     def test_single(self):
         """
         Tests that the optimizer does nothing on a single operation,
@@ -331,7 +302,7 @@ class OptimizerTests(TestCase):
                 migrations.AlterField("Foo", "age", models.FloatField(default=2.4)),
             ],
             [
-                migrations.AddField("Foo", "age", models.FloatField(default=2.4)),
+                migrations.AddField("Foo", name="age", field=models.FloatField(default=2.4)),
             ],
         )