[Sqlalchemy-tickets] Issue #3084: make sort_tables() stable (zzzeek/sqlalchemy)

[Sebastian B. <iss...@bi...>]

New issue 3084: make sort_tables() stable
https://bitbucket.org/zzzeek/sqlalchemy/issue/3084/make-sort_tables-stable

Sebastian Bank:

I use the [mock-engine recipe](http://docs.sqlalchemy.org/en/latest/faq.html#how-can-i-get-the-create-table-drop-table-output-as-a-string) from the FAQ to get and compare the schema of different instances of a database on different platforms. As the table creation order is not completely fixed, I need to monkey-patch `sqlalchemy.util.topological.sort` to make `diff` work on the resulting SQL dumps.

I propose to change `sqlalchemy.sql.ddl.sort_tables` to first **totally order** the tables and then use a **stable topological sort** roughly like the following:

    def sort_as_subsets_stable(tuples, allitems):
    
        edges = collections.defaultdict(set)
        for parent, child in tuples:
            edges[child].add(parent)
    
        todo = set(allitems)
        queue = list(allitems)
    
        while queue:
            output = []
            later = []
            for node in queue:
                if not todo.intersection(edges[node]):
                    output.append(node)
                else:
                    later.append(node)
    
            if not output:
                raise RuntimeError
    
            todo.difference_update(output)
            queue = later
            yield output

    def sort_stable(tuples, allitems):
        for set_ in sort_as_subsets_stable(tuples, allitems):
            for s in set_:
                yield s

For the deterministic ordering prior to the topological sort, name or definition order would do (I prefer the latter).

I suppose the performance impact does not matter, if this is only used in database creation.

I have not tried, but I think that the [hash randomization](https://docs.python.org/3/reference/datamodel.html#object.__hash__) in Python 3.3+ might shuffle the table order with each invocation with the current implementation.