Commits

Simon Law committed f698ca9

Make cycle detection part of dependency computation.

  • Participants
  • Parent commits 11db72f

Comments (0)

Files changed (4)

File south/migration/__init__.py

 from south.signals import pre_migrate, post_migrate
 
 
-def check_dependencies(migrations, seen=[]):
-    for migration in migrations:
-        here = seen + [migration]
-        if migration in seen:
-            raise exceptions.CircularDependency(here)
-        check_dependencies(migration.dependencies(), here)
-    return True
-
 def to_apply(forwards, done):
     return [m for m in forwards if m not in done]
 
     if not migrations:
         print "? You have no migrations for the '%s' app. You might want some." % app_name
         return
-    # Check that all the dependencies are sane
-    check_dependencies(migrations)
     # Check there's no strange ones in the database
     histories = MigrationHistory.objects.filter(applied__isnull=False)
     check_migration_histories(histories)

File south/migration/base.py

 
 from django.core.exceptions import ImproperlyConfigured
 from django.db import models
-from django.utils.datastructures import SortedDict
 
 from south import exceptions
 from south.migration.utils import depends, dfs, flatten, get_app_name

File south/migration/utils.py

 
 from django.utils.datastructures import SortedDict
 
+from south import exceptions
+
+
+class SortedSet(SortedDict):
+    def __init__(self, data):
+        self.extend(data)
+
+    def add(self, value):
+        self[value] = True
+
+    def remove(self, value):
+        del self[value]
+
+    def extend(self, iterable):
+        [self.add(k) for k in iterable]
+
 
 def get_app_name(app):
     """
     while stack:
         try:
             x = stack[0].next()
+        except AttributeError:
+            stack[0] = iter(stack[0])
+            x = stack[0].next()
         except StopIteration:
             stack.popleft()
             continue
             yield x
 
 def _dfs(start, get_children):
-    children = get_children(start)
+    # Prepend ourselves to the result
+    yield start
+    children = reversed(get_children(start))
     if children:
         # We need to apply all the migrations this one depends on
         yield (_dfs(n, get_children) for n in children)
-    # Append ourselves to the result
-    yield start
 
 def dfs(start, get_children):
-    return list(flatten(_dfs(start, get_children)))
+    return flatten(_dfs(start, get_children))
+
+def detect_cycles(iterable):
+    result = []
+    i = iter(iterable)
+    try:
+        # Point to the tortoise
+        tortoise = 0
+        result.append(i.next())
+        # Point to the hare
+        hare = 1
+        result.append(i.next())
+        # Start looking for cycles
+        power = 1
+        while True:
+            # Use Richard P. Brent's algorithm to find an element that
+            # repeats.
+            while result[tortoise] != result[hare]:
+                if power == (hare - tortoise):
+                    tortoise = hare
+                    power *= 2
+                hare += 1
+                result.append(i.next())
+            # Brent assumes the sequence is stateless, but since we're
+            # dealing with a DFS tree, we need to make sure that all
+            # the items between `tortoise` and `hare` are identical.
+            cycle = True
+            for j in xrange(0, hare - tortoise + 1):
+                tortoise += 1
+                hare += 1
+                result.append(i.next())
+                if result[tortoise] != result[hare]:
+                    # False alarm: no cycle here.
+                    cycle = False
+                    power = 1
+                    tortoise = hare
+                    hare += 1
+                    result.append(i.next())
+                    break
+            # Both loops are done, so we must have a cycle
+            if cycle:
+                raise exceptions.CircularDependency(result[tortoise:hare+1])
+    except StopIteration:
+        # Return when `iterable` is exhausted. Obviously, there are no cycles.
+        return result
 
 def depends(start, get_children):
-    result = SortedDict([(n, None) for n in dfs(start, get_children)])
+    result = SortedSet(reversed(detect_cycles(dfs(start, get_children))))
     return list(result)

File south/tests/logic.py

 import StringIO
 
 from south import exceptions, migration
-from south.migration import Migrations
+from south.migration.base import Migration, Migrations
 from south.migration.utils import depends, dfs, flatten, get_app_name
 from south.tests import Monkeypatcher
 from south.utils import snd
 class TestCircularDependencies(Monkeypatcher):
     installed_apps = ["circular_a", "circular_b"]
 
-    def test_check_dependencies(self):
+    def test_plans(self):
         circular_a = Migrations('circular_a')
         circular_b = Migrations('circular_b')
         self.assertRaises(exceptions.CircularDependency,
-                          migration.check_dependencies, circular_a)
+                          Migration.forwards_plan, circular_a[-1])
         self.assertRaises(exceptions.CircularDependency,
-                          migration.check_dependencies, circular_b)
+                          Migration.forwards_plan, circular_b[-1])
+        self.assertRaises(exceptions.CircularDependency,
+                          Migration.backwards_plan, circular_a[-1])
+        self.assertRaises(exceptions.CircularDependency,
+                          Migration.backwards_plan, circular_b[-1])
 
 
 class TestMigrations(Monkeypatcher):
         self.assertEqual([1, 2, 3], list(flatten(iter([iter([1, 2]), 3]))))
         self.assertEqual([1, 2, 3],
                          list(flatten(iter([iter([1]), iter([2]), 3]))))
+        self.assertEqual([1, 2, 3],
+                         list(flatten([[1], [2], 3])))
 
     def test_depends(self):
         graph = {'A1': []}
         self.assertEqual(['A1', 'A2', 'B1', 'C1', 'C2', 'B2', 'A3'],
                          depends('A3', lambda n: graph[n]))
 
+    def assertCircularDependency(self, trace, target, graph):
+        self.assertRaises(exceptions.CircularDependency,
+                          depends, target, lambda n: graph[n])
+        try:
+            depends(target, lambda n: graph[n])
+        except exceptions.CircularDependency, e:
+            self.assertEqual(trace, e.trace)
+
+    def test_depends_cycle(self):
+        graph = {'A1': ['A1']}
+        self.assertCircularDependency(['A1', 'A1'],
+                                      'A1', graph)
+        graph = {'A1': [],
+                 'A2': ['A1', 'A2'],
+                 'A3': ['A2']}
+        self.assertCircularDependency(['A2', 'A2'],
+                                      'A3', graph)
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2', 'A3'],
+                 'A4': ['A3']}
+        self.assertCircularDependency(['A3', 'A3'],
+                                      'A4', graph)
+        graph = {'A1': ['B1'],
+                 'B1': ['A1']}
+        self.assertCircularDependency(['A1', 'B1', 'A1'],
+                                      'A1', graph)
+        graph = {'A1': [],
+                 'A2': ['A1', 'B2'],
+                 'A3': ['A2'],
+                 'B1': [],
+                 'B2': ['B1', 'A2'],
+                 'B3': ['B2']}
+        self.assertCircularDependency(['B2', 'A2', 'B2'],
+                                      'A3', graph)
+        graph = {'A1': [],
+                 'A2': ['A1', 'B3'],
+                 'A3': ['A2'],
+                 'B1': [],
+                 'B2': ['B1', 'A2'],
+                 'B3': ['B2']}
+        self.assertCircularDependency(['A2', 'B3', 'B2', 'A2'],
+                                      'A3', graph)
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2', 'B2'],
+                 'A4': ['A3'],
+                 'B1': ['A3'],
+                 'B2': ['B1']}
+        self.assertCircularDependency(['A3', 'B2', 'B1', 'A3'],
+                                      'A4', graph)
+