Commits

Simon Law committed bfcf82e

Use generators instead of recursion for toplogical sort of dependencies.

  • Participants
  • Parent commits 3633831

Comments (0)

Files changed (3)

south/migration/base.py

 from django.utils.datastructures import SortedDict
 
 from south import exceptions
-from south.migration.utils import get_app_name
+from south.migration.utils import depends, dfs, flatten, get_app_name
 from south.orm import LazyFakeORM, FakeORM
 from south.utils import memoize
 
     def backwards(self):
         return self.migration_instance().backwards
 
-
     def _forwards_plan(self):
         result = SortedDict()
         # We need to apply all the migrations this one depends on
 
         This list includes `self`, which will be applied last.
         """
-        return list(self._forwards_plan())
+        return depends(self, self.__class__.dependencies)
 
     def _backwards_plan(self):
-        result = SortedDict()
-        # We need to apply all the migrations this one depends on
-        for migration in self.dependents():
-            result.update(migration._backwards_plan())
-        # Append ourselves to the result
-        result[self] = None
-        return result
+        return depends(self, self.__class__.dependents)
 
     def backwards_plan(self):
         """
             return migration_class.no_dry_run
         except AttributeError:
             return False
-
-
-def get_app_name(app):
-    """
-    Returns the _internal_ app name for the given app module.
-    i.e. for <module django.contrib.auth.models> will return 'auth'
-    """
-    return app.__name__.split('.')[-2]

south/migration/utils.py

+from collections import deque
+
+from django.utils.datastructures import SortedDict
+
+
+def get_app_name(app):
+    """
+    Returns the _internal_ app name for the given app module.
+    i.e. for <module django.contrib.auth.models> will return 'auth'
+    """
+    return app.__name__.split('.')[-2]
+
+def flatten(*stack):
+    stack = deque(stack)
+    while stack:
+        try:
+            x = stack[0].next()
+        except StopIteration:
+            stack.popleft()
+            continue
+        if hasattr(x, '__iter__'):
+            stack.appendleft(x)
+        else:
+            yield x
+
+def _dfs(start, get_children):
+    children = 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)))
+
+def depends(start, get_children):
+    result = SortedDict([(n, None) for n in dfs(start, get_children)])
+    return list(result)

south/tests/logic.py

 import unittest
+
+from collections import deque
 import datetime
 import sys
 import os
 
 from south import exceptions, migration
 from south.migration import Migrations
-from south.migration.base import get_app_name
+from south.migration.utils import depends, dfs, flatten, get_app_name
 from south.tests import Monkeypatcher
 from south.utils import snd
 
         self.assertRaises(exceptions.DependsOnHigherMigration,
                           depends_on_higher.dependencies)
 
-    def test_forwards_plan(self):
-        self.assertEqual([[self.fakeapp['0001_spam']],
-                          [self.fakeapp['0001_spam'],
-                           self.fakeapp['0002_eggs']],
-                          [self.fakeapp['0001_spam'],
-                           self.fakeapp['0002_eggs'],
-                           self.fakeapp['0003_alter_spam']]],
-                         [m.forwards_plan() for m in self.fakeapp])
-        self.assertEqual([[self.fakeapp['0001_spam'],
-                           self.otherfakeapp['0001_first']],
-                          [self.fakeapp['0001_spam'],
-                           self.otherfakeapp['0001_first'],
-                           self.otherfakeapp['0002_second']],
-                          [self.fakeapp['0001_spam'],
-                           self.otherfakeapp['0001_first'],
-                           self.otherfakeapp['0002_second'],
-                           self.fakeapp['0002_eggs'],
-                           self.fakeapp['0003_alter_spam'],
-                           self.otherfakeapp['0003_third']]],
-                         [m.forwards_plan() for m in self.otherfakeapp])
+    # def test_forwards_plan(self):
+    #     self.assertEqual([[self.fakeapp['0001_spam']],
+    #                       [self.fakeapp['0001_spam'],
+    #                        self.fakeapp['0002_eggs']],
+    #                       [self.fakeapp['0001_spam'],
+    #                        self.fakeapp['0002_eggs'],
+    #                        self.fakeapp['0003_alter_spam']]],
+    #                      [m.forwards_plan() for m in self.fakeapp])
+    #     self.assertEqual([[self.fakeapp['0001_spam'],
+    #                        self.otherfakeapp['0001_first']],
+    #                       [self.fakeapp['0001_spam'],
+    #                        self.otherfakeapp['0001_first'],
+    #                        self.otherfakeapp['0002_second']],
+    #                       [self.fakeapp['0001_spam'],
+    #                        self.otherfakeapp['0001_first'],
+    #                        self.otherfakeapp['0002_second'],
+    #                        self.fakeapp['0002_eggs'],
+    #                        self.fakeapp['0003_alter_spam'],
+    #                        self.otherfakeapp['0003_third']]],
+    #                      [m.forwards_plan() for m in self.otherfakeapp])
 
     def test_is_before(self):
         F1 = self.fakeapp['0001_spam']
                          [m.dependencies() for m in self.deps_c])
 
     def test_dependents(self):
-        self.assertEqual([[self.deps_a['0002_a']],
-                          [self.deps_c['0005_c'],
-                           self.deps_b['0002_b'],
-                           self.deps_a['0003_a']],
-                          [self.deps_b['0003_b'],
-                           self.deps_a['0004_a']],
-                          [self.deps_a['0005_a']],
-                          []],
+        self.assertEqual([deque([self.deps_a['0002_a']]),
+                          deque([self.deps_c['0005_c'],
+                                 self.deps_b['0002_b'],
+                                 self.deps_a['0003_a']]),
+                          deque([self.deps_b['0003_b'],
+                                 self.deps_a['0004_a']]),
+                          deque([self.deps_a['0005_a']]),
+                          deque([])],
                          [m.dependents() for m in self.deps_a])
-        self.assertEqual([[self.deps_b['0002_b']],
-                          [self.deps_b['0003_b']],
-                          [self.deps_b['0004_b'],
-                           self.deps_a['0004_a']],
-                          [self.deps_b['0005_b']],
-                          []],
+        self.assertEqual([deque([self.deps_b['0002_b']]),
+                          deque([self.deps_b['0003_b']]),
+                          deque([self.deps_b['0004_b'],
+                                 self.deps_a['0004_a']]),
+                          deque([self.deps_b['0005_b']]),
+                          deque([])],
                          [m.dependents() for m in self.deps_b])
-        self.assertEqual([[self.deps_c['0002_c']],
-                          [self.deps_c['0003_c']],
-                          [self.deps_c['0004_c']],
-                          [self.deps_c['0005_c']],
-                          []],
+        self.assertEqual([deque([self.deps_c['0002_c']]),
+                          deque([self.deps_c['0003_c']]),
+                          deque([self.deps_c['0004_c']]),
+                          deque([self.deps_c['0005_c']]),
+                          deque([])],
                          [m.dependents() for m in self.deps_c])
 
     def test_forwards_plan(self):
             "baz",
             get_app_name(self.create_fake_app("foo.bar.baz.models")),
         )
+
+class TestUtils(unittest.TestCase):
+
+    def test_flatten(self):
+        self.assertEqual([], list(flatten(iter([]))))
+        self.assertEqual([], list(flatten(iter([iter([]), ]))))
+        self.assertEqual([1], list(flatten(iter([1]))))
+        self.assertEqual([1, 2], list(flatten(iter([1, 2]))))
+        self.assertEqual([1, 2], list(flatten(iter([iter([1]), 2]))))
+        self.assertEqual([1, 2], list(flatten(iter([iter([1, 2])]))))
+        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]))))
+
+    def test_depends(self):
+        graph = {'A1': []}
+        self.assertEqual(['A1'],
+                         depends('A1', lambda n: graph[n]))
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2']}
+        self.assertEqual(['A1', 'A2', 'A3'],
+                         depends('A3', lambda n: graph[n]))
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2', 'A1']}
+        self.assertEqual(['A1', 'A2', 'A3'],
+                         depends('A3', lambda n: graph[n]))
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2', 'A1', 'B1'],
+                 'B1': []}
+        self.assertEqual(['A1', 'A2', 'B1', 'A3'],
+                         depends('A3', lambda n: graph[n]))
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2', 'A1', 'B2'],
+                 'B1': [],
+                 'B2': ['B1']}
+        self.assertEqual(['A1', 'A2', 'B1', 'B2', 'A3'],
+                         depends('A3', lambda n: graph[n]))
+        graph = {'A1': [],
+                 'A2': ['A1', 'B1'],
+                 'A3': ['A2'],
+                 'B1': ['A1']}
+        self.assertEqual(['A1', 'B1', 'A2', 'A3'],
+                         depends('A3', lambda n: graph[n]))
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2', 'A1', 'B2'],
+                 'B1': [],
+                 'B2': ['B1', 'C1'],
+                 'C1': ['B1']}
+        self.assertEqual(['A1', 'A2', 'B1', 'C1', 'B2', 'A3'],
+                         depends('A3', lambda n: graph[n]))
+        graph = {'A1': [],
+                 'A2': ['A1'],
+                 'A3': ['A2', 'B2', 'A1', 'C1'],
+                 'B1': ['A1'],
+                 'B2': ['B1', 'C2', 'A1'],
+                 'C1': ['B1'],
+                 'C2': ['C1', 'A1'],
+                 'C3': ['C2']}
+        self.assertEqual(['A1', 'A2', 'B1', 'C1', 'C2', 'B2', 'A3'],
+                         depends('A3', lambda n: graph[n]))
+