From b3f9698c63e1b863bb780fbe7cd6460454f9ec6a Mon Sep 17 00:00:00 2001
From: Sebastian Bank <sebastian.bank@uni-leipzig.de>
Date: Sat, 7 Mar 2015 14:04:14 +0100
Subject: [PATCH] make sort_tables order deterministic

---
 lib/sqlalchemy/sql/ddl.py          |  6 ++++--
 lib/sqlalchemy/sql/schema.py       |  2 +-
 lib/sqlalchemy/util/topological.py | 17 ++++++++++-------
 test/sql/test_metadata.py          | 15 +++++++++++++++
 4 files changed, 30 insertions(+), 10 deletions(-)

diff --git a/lib/sqlalchemy/sql/ddl.py b/lib/sqlalchemy/sql/ddl.py
index 7a1c7fef6a..b4d2f17aaa 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 fa48a16ccf..c027f2f96e 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 2bfcccc635..300c01641f 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 1eec502e7a..65e1e60cef 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',
-- 
2.47.3