Fixed #29243 -- Improved efficiency of migration graph algorithm.

2 files changed, 33 insertions, 94 deletions

diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py
index 1f0bafb00e..0096392c5d 100644
--- a/django/db/migrations/graph.py
+++ b/django/db/migrations/graph.py
@@ -1,18 +1,9 @@
-import warnings
 from functools import total_ordering
 
 from django.db.migrations.state import ProjectState
-from django.utils.datastructures import OrderedSet
 
 from .exceptions import CircularDependencyError, NodeNotFoundError
 
-RECURSION_DEPTH_WARNING = (
-    "Maximum recursion depth exceeded while generating migration graph, "
-    "falling back to iterative approach. If you're experiencing performance issues, "
-    "consider squashing migrations as described at "
-    "https://docs.djangoproject.com/en/dev/topics/migrations/#squashing-migrations."
-)
-
 
 @total_ordering
 class Node:
@@ -49,49 +40,20 @@ class Node:
     def add_parent(self, parent):
         self.parents.add(parent)
 
-    # Use manual caching, @cached_property effectively doubles the
-    # recursion depth for each recursion.
-    def ancestors(self):
-        # Use self.key instead of self to speed up the frequent hashing
-        # when constructing an OrderedSet.
-        if '_ancestors' not in self.__dict__:
-            ancestors = []
-            for parent in sorted(self.parents, reverse=True):
-                ancestors += parent.ancestors()
-            ancestors.append(self.key)
-            self.__dict__['_ancestors'] = list(OrderedSet(ancestors))
-        return self.__dict__['_ancestors']
-
-    # Use manual caching, @cached_property effectively doubles the
-    # recursion depth for each recursion.
-    def descendants(self):
-        # Use self.key instead of self to speed up the frequent hashing
-        # when constructing an OrderedSet.
-        if '_descendants' not in self.__dict__:
-            descendants = []
-            for child in sorted(self.children, reverse=True):
-                descendants += child.descendants()
-            descendants.append(self.key)
-            self.__dict__['_descendants'] = list(OrderedSet(descendants))
-        return self.__dict__['_descendants']
-
 
 class DummyNode(Node):
+    """
+    A node that doesn't correspond to a migration file on disk.
+    (A squashed migration that was removed, for example.)
+
+    After the migration graph is processed, all dummy nodes should be removed.
+    If there are any left, a nonexistent dependency error is raised.
+    """
     def __init__(self, key, origin, error_message):
         super().__init__(key)
         self.origin = origin
         self.error_message = error_message
 
-    def promote(self):
-        """
-        Transition dummy to a normal node and clean off excess attribs.
-        Creating a Node object from scratch would be too much of a
-        hassle as many dependendies would need to be remapped.
-        """
-        del self.origin
-        del self.error_message
-        self.__class__ = Node
-
     def raise_error(self):
         raise NodeNotFoundError(self.error_message, self.key, origin=self.origin)
 
@@ -122,19 +84,12 @@ class MigrationGraph:
     def __init__(self):
         self.node_map = {}
         self.nodes = {}
-        self.cached = False
 
     def add_node(self, key, migration):
-        # If the key already exists, then it must be a dummy node.
-        dummy_node = self.node_map.get(key)
-        if dummy_node:
-            # Promote DummyNode to Node.
-            dummy_node.promote()
-        else:
-            node = Node(key)
-            self.node_map[key] = node
+        assert key not in self.node_map
+        node = Node(key)
+        self.node_map[key] = node
         self.nodes[key] = migration
-        self.clear_cache()
 
     def add_dummy_node(self, key, origin, error_message):
         node = DummyNode(key, origin, error_message)
@@ -163,7 +118,6 @@ class MigrationGraph:
         self.node_map[parent].add_child(self.node_map[child])
         if not skip_validation:
             self.validate_consistency()
-        self.clear_cache()
 
     def remove_replaced_nodes(self, replacement, replaced):
         """
@@ -199,7 +153,6 @@ class MigrationGraph:
                     if parent.key not in replaced:
                         replacement_node.add_parent(parent)
                         parent.add_child(replacement_node)
-        self.clear_cache()
 
     def remove_replacement_node(self, replacement, replaced):
         """
@@ -236,19 +189,11 @@ class MigrationGraph:
             parent.children.remove(replacement_node)
             # NOTE: There is no need to remap parent dependencies as we can
             # assume the replaced nodes already have the correct ancestry.
-        self.clear_cache()
 
     def validate_consistency(self):
         """Ensure there are no dummy nodes remaining in the graph."""
         [n.raise_error() for n in self.node_map.values() if isinstance(n, DummyNode)]
 
-    def clear_cache(self):
-        if self.cached:
-            for node in self.nodes:
-                self.node_map[node].__dict__.pop('_ancestors', None)
-                self.node_map[node].__dict__.pop('_descendants', None)
-            self.cached = False
-
     def forwards_plan(self, target):
         """
         Given a node, return a list of which previous nodes (dependencies) must
@@ -257,16 +202,7 @@ class MigrationGraph:
         """
         if target not in self.nodes:
             raise NodeNotFoundError("Node %r not a valid node" % (target,), target)
-        # Use parent.key instead of parent to speed up the frequent hashing in ensure_not_cyclic
-        self.ensure_not_cyclic(target, lambda x: (parent.key for parent in self.node_map[x].parents))
-        self.cached = True
-        node = self.node_map[target]
-        try:
-            return node.ancestors()
-        except RuntimeError:
-            # fallback to iterative dfs
-            warnings.warn(RECURSION_DEPTH_WARNING, RuntimeWarning)
-            return self.iterative_dfs(node)
+        return self.iterative_dfs(self.node_map[target])
 
     def backwards_plan(self, target):
         """
@@ -276,26 +212,24 @@ class MigrationGraph:
         """
         if target not in self.nodes:
             raise NodeNotFoundError("Node %r not a valid node" % (target,), target)
-        # Use child.key instead of child to speed up the frequent hashing in ensure_not_cyclic
-        self.ensure_not_cyclic(target, lambda x: (child.key for child in self.node_map[x].children))
-        self.cached = True
-        node = self.node_map[target]
-        try:
-            return node.descendants()
-        except RuntimeError:
-            # fallback to iterative dfs
-            warnings.warn(RECURSION_DEPTH_WARNING, RuntimeWarning)
-            return self.iterative_dfs(node, forwards=False)
+        return self.iterative_dfs(self.node_map[target], forwards=False)
 
     def iterative_dfs(self, start, forwards=True):
         """Iterative depth-first search for finding dependencies."""
         visited = []
-        stack = [start]
+        visited_set = set()
+        stack = [(start, False)]
         while stack:
-            node = stack.pop()
-            visited.append(node)
-            stack += sorted(node.parents if forwards else node.children)
-        return list(OrderedSet(reversed(visited)))
+            node, processed = stack.pop()
+            if node in visited_set:
+                pass
+            elif processed:
+                visited_set.add(node)
+                visited.append(node.key)
+            else:
+                stack.append((node, True))
+                stack += [(n, False) for n in sorted(node.parents if forwards else node.children)]
+        return visited
 
     def root_nodes(self, app=None):
         """
@@ -322,7 +256,7 @@ class MigrationGraph:
                 leaves.add(node)
         return sorted(leaves)
 
-    def ensure_not_cyclic(self, start, get_children):
+    def ensure_not_cyclic(self):
         # Algo from GvR:
         # http://neopythonic.blogspot.co.uk/2009/01/detecting-cycles-in-directed-graph.html
         todo = set(self.nodes)
@@ -331,7 +265,10 @@ class MigrationGraph:
             stack = [node]
             while stack:
                 top = stack[-1]
-                for node in get_children(top):
+                for child in self.node_map[top].children:
+                    # Use child.key instead of child to speed up the frequent
+                    # hashing.
+                    node = child.key
                     if node in stack:
                         cycle = stack[stack.index(node):]
                         raise CircularDependencyError(", ".join("%s.%s" % n for n in cycle))
diff --git a/django/db/migrations/loader.py b/django/db/migrations/loader.py
index 4147cc3f09..79de511860 100644
--- a/django/db/migrations/loader.py
+++ b/django/db/migrations/loader.py
@@ -213,11 +213,12 @@ class MigrationLoader:
         self.replacements = {}
         for key, migration in self.disk_migrations.items():
             self.graph.add_node(key, migration)
-            # Internal (aka same-app) dependencies.
-            self.add_internal_dependencies(key, migration)
             # Replacing migrations.
             if migration.replaces:
                 self.replacements[key] = migration
+        for key, migration in self.disk_migrations.items():
+            # Internal (same app) dependencies.
+            self.add_internal_dependencies(key, migration)
         # Add external dependencies now that the internal ones have been resolved.
         for key, migration in self.disk_migrations.items():
             self.add_external_dependencies(key, migration)
@@ -268,6 +269,7 @@ class MigrationLoader:
                         exc.node
                     ) from exc
             raise exc
+        self.graph.ensure_not_cyclic()
 
     def check_consistent_history(self, connection):
         """