Merge branch 'bb_issue_3084' of https://bitbucket.org/xflr6/sqlalchemy into pr47

5 files changed, 59 insertions, 10 deletions

diff --git a/lib/sqlalchemy/sql/ddl.py b/lib/sqlalchemy/sql/ddl.py
index 3834f25f4..bbac6456e 100644
--- a/lib/sqlalchemy/sql/ddl.py
+++ b/lib/sqlalchemy/sql/ddl.py
@@ -1041,7 +1041,8 @@ def sort_tables_and_constraints(
     try:
         candidate_sort = list(
             topological.sort(
-                fixed_dependencies.union(mutable_dependencies), tables
+                fixed_dependencies.union(mutable_dependencies), tables,
+                deterministic_order=True
             )
         )
     except exc.CircularDependencyError as err:
@@ -1058,7 +1059,8 @@ def sort_tables_and_constraints(
                         mutable_dependencies.discard((dependent_on, table))
         candidate_sort = list(
             topological.sort(
-                fixed_dependencies.union(mutable_dependencies), tables
+                fixed_dependencies.union(mutable_dependencies), tables,
+                deterministic_order=True
             )
         )
 
diff --git a/lib/sqlalchemy/sql/schema.py b/lib/sqlalchemy/sql/schema.py
index 3aeba9804..e40909850 100644
--- a/lib/sqlalchemy/sql/schema.py
+++ b/lib/sqlalchemy/sql/schema.py
@@ -3450,7 +3450,7 @@ class MetaData(SchemaItem):
 
 
         """
-        return ddl.sort_tables(self.tables.values())
+        return ddl.sort_tables(sorted(self.tables.values(), key=lambda t: t.key))
 
     def reflect(self, bind=None, schema=None, views=False, only=None,
                 extend_existing=False,
diff --git a/lib/sqlalchemy/util/topological.py b/lib/sqlalchemy/util/topological.py
index 80735c4df..0cd2bae29 100644
--- a/lib/sqlalchemy/util/topological.py
+++ b/lib/sqlalchemy/util/topological.py
@@ -13,18 +13,20 @@ from .. import util
 __all__ = ['sort', 'sort_as_subsets', 'find_cycles']
 
 
-def sort_as_subsets(tuples, allitems):
+def sort_as_subsets(tuples, allitems, deterministic_order=False):
 
     edges = util.defaultdict(set)
     for parent, child in tuples:
         edges[child].add(parent)
 
-    todo = set(allitems)
+    Set = util.OrderedSet if deterministic_order else set
+
+    todo = Set(allitems)
 
     while todo:
-        output = set()
-        for node in list(todo):
-            if not todo.intersection(edges[node]):
+        output = Set()
+        for node in todo:
+            if todo.isdisjoint(edges[node]):
                 output.add(node)
 
         if not output:
@@ -38,13 +40,14 @@ def sort_as_subsets(tuples, allitems):
         yield output
 
 
-def sort(tuples, allitems):
+def sort(tuples, allitems, deterministic_order=False):
     """sort the given list of items by dependency.
 
     'tuples' is a list of tuples representing a partial ordering.
+    'deterministic_order' keeps items within a dependency tier in list order.
     """
 
-    for set_ in sort_as_subsets(tuples, allitems):
+    for set_ in sort_as_subsets(tuples, allitems, deterministic_order):
         for s in set_:
             yield s
 
diff --git a/test/base/test_dependency.py b/test/base/test_dependency.py
index b16516f15..a06bd5a51 100644
--- a/test/base/test_dependency.py
+++ b/test/base/test_dependency.py
@@ -14,6 +14,11 @@ class DependencySortTest(fixtures.TestBase):
         result = list(topological.sort(tuples, allitems))
         assert conforms_partial_ordering(tuples, result)
 
+    def assert_sort_deterministic(self, tuples, allitems, expected):
+        result = list(topological.sort(tuples, allitems, deterministic_order=True))
+        assert conforms_partial_ordering(tuples, result)
+        assert result == expected
+
     def _nodes_from_tuples(self, tups):
         s = set()
         for tup in tups:
@@ -63,6 +68,30 @@ class DependencySortTest(fixtures.TestBase):
                   (node3, node2)]
         self.assert_sort(tuples)
 
+    def test_sort_deterministic_one(self):
+        node1 = 'node1'
+        node2 = 'node2'
+        node3 = 'node3'
+        node4 = 'node4'
+        node5 = 'node5'
+        node6 = 'node6'
+        allitems = [node6, node5, node4, node3, node2, node1]
+        tuples = [(node6, node5), (node2, node1)]
+        expected = [node6, node4, node3, node2, node5, node1]
+        self.assert_sort_deterministic(tuples, allitems, expected)
+
+    def test_sort_deterministic_two(self):
+        node1 = 1
+        node2 = 2
+        node3 = 3
+        node4 = 4
+        node5 = 5
+        node6 = 6
+        allitems = [node6, node5, node4, node3, node2, node1]
+        tuples = [(node6, node5), (node4, node3), (node2, node1)]
+        expected = [node6, node4, node2, node5, node3, node1]
+        self.assert_sort_deterministic(tuples, allitems, expected)
+
     def test_raise_on_cycle_one(self):
         node1 = 'node1'
         node2 = 'node2'
diff --git a/test/sql/test_metadata.py b/test/sql/test_metadata.py
index 1eec502e7..65e1e60ce 100644
--- a/test/sql/test_metadata.py
+++ b/test/sql/test_metadata.py
@@ -492,6 +492,21 @@ class MetaDataTest(fixtures.TestBase, ComparesTables):
             [d, b, a, c, e]
         )
 
+    def test_deterministic_order(self):
+        meta = MetaData()
+        a = Table('a', meta, Column('foo', Integer))
+        b = Table('b', meta, Column('foo', Integer))
+        c = Table('c', meta, Column('foo', Integer))
+        d = Table('d', meta, Column('foo', Integer))
+        e = Table('e', meta, Column('foo', Integer))
+
+        e.add_is_dependent_on(c)
+        a.add_is_dependent_on(b)
+        eq_(
+            meta.sorted_tables,
+            [b, c, d, a, e]
+        )
+
     def test_nonexistent(self):
         assert_raises(tsa.exc.NoSuchTableError, Table,
                       'fake_table',