make sort_tables order deterministic

4 files changed, 30 insertions, 10 deletions

diff --git a/lib/sqlalchemy/sql/ddl.py b/lib/sqlalchemy/sql/ddl.py
index 7a1c7fef6..b4d2f17aa 100644
--- a/lib/sqlalchemy/sql/ddl.py
+++ b/lib/sqlalchemy/sql/ddl.py
@@ -1031,7 +1031,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:
@@ -1048,7 +1049,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 fa48a16cc..c027f2f96 100644
--- a/lib/sqlalchemy/sql/schema.py
+++ b/lib/sqlalchemy/sql/schema.py
@@ -3422,7 +3422,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 2bfcccc63..300c01641 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/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',