From 75430be86f4c90b7fb8a370d2b080a8a7cc925a0 Mon Sep 17 00:00:00 2001 From: Marten Kenbeek Date: Sat, 28 Mar 2015 17:46:10 +0100 Subject: Refs #24366 -- Fixed recursion depth error in migration graph Made MigrationGraph forwards_plan() and backwards_plan() fall back to an iterative approach in case the recursive approach exceeds the recursion depth limit. --- django/db/migrations/graph.py | 45 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 43 insertions(+), 2 deletions(-) (limited to 'django') diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py index 8d332edb98..46b6485300 100644 --- a/django/db/migrations/graph.py +++ b/django/db/migrations/graph.py @@ -1,5 +1,6 @@ from __future__ import unicode_literals +import warnings from collections import deque from django.db.migrations.state import ProjectState @@ -7,6 +8,13 @@ from django.utils.datastructures import OrderedSet from django.utils.encoding import python_2_unicode_compatible from django.utils.functional import total_ordering +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." +) + @python_2_unicode_compatible @total_ordering @@ -139,7 +147,12 @@ class MigrationGraph(object): 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] - return node.ancestors() + try: + return node.ancestors() + except RuntimeError: + # fallback to iterative dfs + warnings.warn(RECURSION_DEPTH_WARNING, RuntimeWarning) + return self.iterative_dfs(node) def backwards_plan(self, target): """ @@ -154,7 +167,35 @@ class MigrationGraph(object): 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] - return node.descendants() + try: + return node.descendants() + except RuntimeError: + # fallback to iterative dfs + warnings.warn(RECURSION_DEPTH_WARNING, RuntimeWarning) + return self.iterative_dfs(node, forwards=False) + + def iterative_dfs(self, start, forwards=True): + """ + Iterative depth first search, for finding dependencies. + """ + visited = deque() + visited.append(start) + if forwards: + stack = deque(sorted(start.parents)) + else: + stack = deque(sorted(start.children)) + while stack: + node = stack.popleft() + visited.appendleft(node) + if forwards: + children = sorted(node.parents, reverse=True) + else: + children = sorted(node.children, reverse=True) + # reverse sorting is needed because prepending using deque.extendleft + # also effectively reverses values + stack.extendleft(children) + + return list(OrderedSet(visited)) def root_nodes(self, app=None): """ -- cgit v1.3