Fix toposort of migrations when multiple migrations have the same dependency

This fixes #23

2 files changed, 21 insertions, 9 deletions

diff --git a/yoyo/migrations.py b/yoyo/migrations.py
index dfc0c32..8aab47c 100755
--- a/yoyo/migrations.py
+++ b/yoyo/migrations.py
@@ -13,7 +13,7 @@
 # limitations under the License.
 
 from collections import (defaultdict, OrderedDict, Counter, MutableSequence,
-                         Iterable)
+                         Iterable, deque)
 from copy import copy
 from itertools import chain, count
 from logging import getLogger
@@ -508,17 +508,17 @@ def topological_sort(migration_list):
     to_toposort = set(chain(forward_edges, backward_edges))
 
     # Starting migrations: those with no dependencies
-    # This is a reversed list so that popping/pushing from the end maintains
-    # the desired order
-    S = list(reversed([m for m in to_toposort
-                       if not any(n in valid_migrations for n in m.depends)]))
+    # To make this a stable sort we always need to pop from the left end
+    # of this list, hence use a deque.
+    S = deque(m for m in to_toposort
+              if not any(n in valid_migrations for n in m.depends))
 
     while S:
-        n = S.pop()
+        n = S.popleft()
         L.append(n)
 
         # for each node M with an edge E from N to M
-        for m in forward_edges[n]:
+        for m in list(forward_edges[n]):
 
             # remove edge E from the graph
             del forward_edges[n][m]
diff --git a/yoyo/tests/test_migrations.py b/yoyo/tests/test_migrations.py
index 8173c9a..376fcab 100644
--- a/yoyo/tests/test_migrations.py
+++ b/yoyo/tests/test_migrations.py
@@ -236,8 +236,13 @@ def test_migrations_display_selected_data(tmpdir):
 class TestTopologicalSort(object):
 
     def get_mock_migrations(self):
-        return [Mock(id='m1', depends=set()), Mock(id='m2', depends=set()),
-                Mock(id='m3', depends=set()), Mock(id='m4', depends=set())]
+        class MockMigration(Mock):
+            def __repr__(self):
+                return "<MockMigration {}>".format(self.id)
+        return [MockMigration(id='m1', depends=set()),
+                MockMigration(id='m2', depends=set()),
+                MockMigration(id='m3', depends=set()),
+                MockMigration(id='m4', depends=set())]
 
     def test_it_keeps_stable_order(self):
         m1, m2, m3, m4 = self.get_mock_migrations()
@@ -265,6 +270,13 @@ class TestTopologicalSort(object):
         with pytest.raises(exceptions.BadMigration):
             list(topological_sort([m1, m2, m3, m4]))
 
+    def test_it_handles_multiple_edges_to_the_same_node(self):
+        m1, m2, m3, m4 = self.get_mock_migrations()
+        m2.depends.add(m1)
+        m3.depends.add(m1)
+        m4.depends.add(m1)
+        assert list(topological_sort([m1, m2, m3, m4])) == [m1, m2, m3, m4]
+
 
 class TestMigrationList(object):