Initial version of MigrationOptimizer and tests

5 files changed, 237 insertions, 0 deletions

diff --git a/django/db/migrations/operations/base.py b/django/db/migrations/operations/base.py
index 1e5789f29c..4251436b63 100644
--- a/django/db/migrations/operations/base.py
+++ b/django/db/migrations/operations/base.py
@@ -63,3 +63,16 @@ class Operation(object):
         Outputs a brief summary of what the action does.
         """
         return "%s: %s" % (self.__class__.__name__, self._constructor_args)
+
+    def __repr__(self):
+        return "<%s %s%s>" % (
+            self.__class__.__name__,
+            ", ".join(map(repr, self._constructor_args[0])),
+            ",".join(" %s=%r" % x for x in self._constructor_args[1].items()),
+        )
+
+    def __eq__(self, other):
+        return (self.__class__ == other.__class__) and (self.deconstruct() == other.deconstruct())
+
+    def __ne__(self, other):
+        return not (self == other)
diff --git a/django/db/migrations/operations/fields.py b/django/db/migrations/operations/fields.py
index 7c619d49ce..6a567d727a 100644
--- a/django/db/migrations/operations/fields.py
+++ b/django/db/migrations/operations/fields.py
@@ -29,6 +29,14 @@ class AddField(Operation):
     def describe(self):
         return "Add field %s to %s" % (self.name, self.model_name)
 
+    def __eq__(self, other):
+        return (
+            (self.__class__ == other.__class__) and
+            (self.name == other.name) and
+            (self.model_name == other.model_name) and
+            (self.field.deconstruct()[1:] == other.field.deconstruct()[1:])
+        )
+
 
 class RemoveField(Operation):
     """
@@ -92,6 +100,14 @@ class AlterField(Operation):
     def describe(self):
         return "Alter field %s on %s" % (self.name, self.model_name)
 
+    def __eq__(self, other):
+        return (
+            (self.__class__ == other.__class__) and
+            (self.name == other.name) and
+            (self.model_name == other.model_name) and
+            (self.field.deconstruct()[1:] == other.field.deconstruct()[1:])
+        )
+
 
 class RenameField(Operation):
     """
diff --git a/django/db/migrations/operations/models.py b/django/db/migrations/operations/models.py
index 406efa6ef1..b86c0776c1 100644
--- a/django/db/migrations/operations/models.py
+++ b/django/db/migrations/operations/models.py
@@ -32,6 +32,15 @@ class CreateModel(Operation):
     def describe(self):
         return "Create model %s" % (self.name, )
 
+    def __eq__(self, other):
+        return (
+            (self.__class__ == other.__class__) and
+            (self.name == other.name) and
+            (self.options == other.options) and
+            (self.bases == other.bases) and
+            ([(k, f.deconstruct()[1:]) for k, f in self.fields] == [(k, f.deconstruct()[1:]) for k, f in other.fields])
+        )
+
 
 class DeleteModel(Operation):
     """
diff --git a/django/db/migrations/optimizer.py b/django/db/migrations/optimizer.py
new file mode 100644
index 0000000000..9c9613bb37
--- /dev/null
+++ b/django/db/migrations/optimizer.py
@@ -0,0 +1,104 @@
+from django.db import migrations
+
+class MigrationOptimizer(object):
+    """
+    Powers the optimization process, where you provide a list of Operations
+    and you are returned a list of equal or shorter length - operations
+    are merged into one if possible.
+
+    For example, a CreateModel and an AddField can be optimised into a
+    new CreateModel, and CreateModel and DeleteModel can be optimised into
+    nothing.
+    """
+
+    def optimize(self, operations):
+        """
+        Main optimization entry point. Pass in a list of Operation instances,
+        get out a new list of Operation instances.
+
+        Unfortunately, due to the scope of the optimisation (two combinable
+        operations might be separated by several hundred others), this can't be
+        done as a peephole optimisation with checks/output implemented on
+        the Operations themselves; instead, the optimizer looks at each
+        individual operation and scans forwards in the list to see if there
+        are any matches, stopping at boundaries - operations which can't
+        be optimized over (RunSQL, operations on the same field/model, etc.)
+
+        The inner loop is run until the starting list is the same as the result
+        list, and then the result is returned. This means that operation
+        optimization must be stable and always return an equal or shorter list.
+        """
+        # Internal tracking variable for test assertions about # of loops
+        self._iterations = 0
+        while True:
+            result = self.optimize_inner(operations)
+            self._iterations += 1
+            if result == operations:
+                return result
+            operations = result
+
+    def optimize_inner(self, operations):
+        """
+        Inner optimization loop.
+        """
+        new_operations = []
+        for i, operation in enumerate(operations):
+            # Compare it to each operation after it
+            for j, other in enumerate(operations[i+1:]):
+                result = self.reduce(operation, other)
+                if result is not None:
+                    # Optimize! Add result, then remaining others, then return
+                    new_operations.extend(result)
+                    new_operations.extend(operations[i+1:i+1+j])
+                    new_operations.extend(operations[i+j+2:])
+                    return new_operations
+                if not self.can_optimize_through(operation, other):
+                    new_operations.append(operation)
+                    break
+            else:
+                new_operations.append(operation)
+        return new_operations
+
+    #### REDUCTION ####
+
+    def reduce(self, operation, other):
+        """
+        Either returns a list of zero, one or two operations,
+        or None, meaning this pair cannot be optimized.
+        """
+        submethods = [
+            (migrations.CreateModel, migrations.DeleteModel, self.reduce_model_create_delete),
+            (migrations.AlterModelTable, migrations.DeleteModel, self.reduce_model_alter_delete),
+            (migrations.AlterUniqueTogether, migrations.DeleteModel, self.reduce_model_alter_delete),
+            (migrations.AlterIndexTogether, migrations.DeleteModel, self.reduce_model_alter_delete),
+        ]
+        for ia, ib, om in submethods:
+            if isinstance(operation, ia) and isinstance(other, ib):
+                return om(operation, other)
+        return None
+
+    def reduce_model_create_delete(self, operation, other):
+        """
+        Folds a CreateModel and a DeleteModel into nothing.
+        """
+        if operation.name == other.name:
+            return []
+        return None
+
+    def reduce_model_alter_delete(self, operation, other):
+        """
+        Folds an AlterModelSomething and a DeleteModel into nothing.
+        """
+        if operation.name == other.name:
+            return [other]
+        return None
+
+    #### THROUGH CHECKS ####
+
+    def can_optimize_through(self, operation, other):
+        """
+        Returns True if it's possible to optimize 'operation' with something
+        the other side of 'other'. This is possible if, for example, they
+        affect different models.
+        """
+        return False
diff --git a/tests/migrations/test_optimizer.py b/tests/migrations/test_optimizer.py
new file mode 100644
index 0000000000..f2b6e58a84
--- /dev/null
+++ b/tests/migrations/test_optimizer.py
@@ -0,0 +1,95 @@
+# encoding: utf8
+import operator
+from django.test import TestCase
+from django.db.migrations.optimizer import MigrationOptimizer
+from django.db import migrations
+from django.db import models
+
+
+class OptimizerTests(TestCase):
+    """
+    Tests the migration autodetector.
+    """
+
+    def optimize(self, operations):
+        """
+        Handy shortcut for getting results + number of loops
+        """
+        optimizer = MigrationOptimizer()
+        return optimizer.optimize(operations), optimizer._iterations
+
+    def assertOptimizesTo(self, operations, expected, exact=None, less_than=None):
+        result, iterations = self.optimize(operations)
+        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,
+        and that it does it in just one pass.
+        """
+        self.assertOptimizesTo(
+            [migrations.DeleteModel("Foo")],
+            [migrations.DeleteModel("Foo")],
+            exact = 1,
+        )
+
+    def test_create_delete_model(self):
+        """
+        CreateModel and DeleteModel should collapse into nothing.
+        """
+        self.assertOptimizesTo(
+            [
+                migrations.CreateModel("Foo", [("name", models.CharField(max_length=255))]),
+                migrations.DeleteModel("Foo"),
+            ],
+            [],
+        )
+
+    def test_create_alter_delete_model(self):
+        """
+        CreateModel, AlterModelTable, AlterUniqueTogether, and DeleteModel should collapse into nothing.
+        """
+        self.assertOptimizesTo(
+            [
+                migrations.CreateModel("Foo", [("name", models.CharField(max_length=255))]),
+                migrations.AlterModelTable("Foo", "woohoo"),
+                migrations.AlterUniqueTogether("Foo", [["a", "b"]]),
+                migrations.DeleteModel("Foo"),
+            ],
+            [],
+        )