Replace ``OrderedDict`` with a normal ``dict`` in python 3.7+

References: #5735

Change-Id: I0a73f727fb6820d32eca590b1e8afbfe2872adb8

8 files changed, 156 insertions, 85 deletions

diff --git a/lib/sqlalchemy/orm/decl_base.py b/lib/sqlalchemy/orm/decl_base.py
index 0649247a7..8da326b0e 100644
--- a/lib/sqlalchemy/orm/decl_base.py
+++ b/lib/sqlalchemy/orm/decl_base.py
@@ -569,7 +569,9 @@ class _ClassScanMapperConfig(_MapperConfig):
         our_stuff = self.properties
 
         # set up attributes in the order they were created
-        our_stuff.sort(key=lambda key: our_stuff[key]._creation_order)
+        util.sort_dictionary(
+            our_stuff, key=lambda key: our_stuff[key]._creation_order
+        )
 
         # extract columns from the class dict
         declared_columns = self.declared_columns
diff --git a/lib/sqlalchemy/util/__init__.py b/lib/sqlalchemy/util/__init__.py
index d632f7fed..2db1adb8d 100644
--- a/lib/sqlalchemy/util/__init__.py
+++ b/lib/sqlalchemy/util/__init__.py
@@ -35,6 +35,7 @@ from ._collections import OrderedSet  # noqa
 from ._collections import PopulateDict  # noqa
 from ._collections import Properties  # noqa
 from ._collections import ScopedRegistry  # noqa
+from ._collections import sort_dictionary  # noqa
 from ._collections import ThreadLocalRegistry  # noqa
 from ._collections import to_column_set  # noqa
 from ._collections import to_list  # noqa
diff --git a/lib/sqlalchemy/util/_collections.py b/lib/sqlalchemy/util/_collections.py
index b50d9885d..69457994a 100644
--- a/lib/sqlalchemy/util/_collections.py
+++ b/lib/sqlalchemy/util/_collections.py
@@ -17,6 +17,7 @@ from .compat import binary_types
 from .compat import collections_abc
 from .compat import itertools_filterfalse
 from .compat import py2k
+from .compat import py37
 from .compat import string_types
 from .compat import threading
 
@@ -235,101 +236,128 @@ class ImmutableProperties(ImmutableContainer, Properties):
     __slots__ = ()
 
 
-class OrderedDict(dict):
-    """A dict that returns keys/values/items in the order they were added."""
+def _ordered_dictionary_sort(d, key=None):
+    """Sort an OrderedDict in-place."""
 
-    __slots__ = ("_list",)
+    items = [(k, d[k]) for k in sorted(d, key=key)]
 
-    def __reduce__(self):
-        return OrderedDict, (self.items(),)
+    d.clear()
 
-    def __init__(self, ____sequence=None, **kwargs):
-        self._list = []
-        if ____sequence is None:
-            if kwargs:
-                self.update(**kwargs)
-        else:
-            self.update(____sequence, **kwargs)
+    d.update(items)
 
-    def clear(self):
-        self._list = []
-        dict.clear(self)
 
-    def copy(self):
-        return self.__copy__()
+if py37:
+    OrderedDict = dict
+    sort_dictionary = _ordered_dictionary_sort
+
+else:
+    # prevent sort_dictionary from being used against a plain dictionary
+    # for Python < 3.7
 
-    def __copy__(self):
-        return OrderedDict(self)
+    def sort_dictionary(d, key=None):
+        """Sort an OrderedDict in place."""
 
-    def sort(self, *arg, **kw):
-        self._list.sort(*arg, **kw)
+        d._ordered_dictionary_sort(key=key)
+
+    class OrderedDict(dict):
+        """Dictionary that maintains insertion order.
+
+        Superseded by Python dict as of Python 3.7
+
+        """
+
+        __slots__ = ("_list",)
+
+        def _ordered_dictionary_sort(self, key=None):
+            _ordered_dictionary_sort(self, key=key)
+
+        def __reduce__(self):
+            return OrderedDict, (self.items(),)
 
-    def update(self, ____sequence=None, **kwargs):
-        if ____sequence is not None:
-            if hasattr(____sequence, "keys"):
-                for key in ____sequence.keys():
-                    self.__setitem__(key, ____sequence[key])
+        def __init__(self, ____sequence=None, **kwargs):
+            self._list = []
+            if ____sequence is None:
+                if kwargs:
+                    self.update(**kwargs)
             else:
-                for key, value in ____sequence:
-                    self[key] = value
-        if kwargs:
-            self.update(kwargs)
+                self.update(____sequence, **kwargs)
 
-    def setdefault(self, key, value):
-        if key not in self:
-            self.__setitem__(key, value)
-            return value
-        else:
-            return self.__getitem__(key)
+        def clear(self):
+            self._list = []
+            dict.clear(self)
+
+        def copy(self):
+            return self.__copy__()
+
+        def __copy__(self):
+            return OrderedDict(self)
+
+        def update(self, ____sequence=None, **kwargs):
+            if ____sequence is not None:
+                if hasattr(____sequence, "keys"):
+                    for key in ____sequence.keys():
+                        self.__setitem__(key, ____sequence[key])
+                else:
+                    for key, value in ____sequence:
+                        self[key] = value
+            if kwargs:
+                self.update(kwargs)
 
-    def __iter__(self):
-        return iter(self._list)
+        def setdefault(self, key, value):
+            if key not in self:
+                self.__setitem__(key, value)
+                return value
+            else:
+                return self.__getitem__(key)
 
-    def keys(self):
-        return list(self)
+        def __iter__(self):
+            return iter(self._list)
 
-    def values(self):
-        return [self[key] for key in self._list]
+        def keys(self):
+            return list(self)
 
-    def items(self):
-        return [(key, self[key]) for key in self._list]
+        def values(self):
+            return [self[key] for key in self._list]
 
-    if py2k:
+        def items(self):
+            return [(key, self[key]) for key in self._list]
 
-        def itervalues(self):
-            return iter(self.values())
+        if py2k:
 
-        def iterkeys(self):
-            return iter(self)
+            def itervalues(self):
+                return iter(self.values())
 
-        def iteritems(self):
-            return iter(self.items())
+            def iterkeys(self):
+                return iter(self)
 
-    def __setitem__(self, key, obj):
-        if key not in self:
-            try:
-                self._list.append(key)
-            except AttributeError:
-                # work around Python pickle loads() with
-                # dict subclass (seems to ignore __setstate__?)
-                self._list = [key]
-        dict.__setitem__(self, key, obj)
+            def iteritems(self):
+                return iter(self.items())
 
-    def __delitem__(self, key):
-        dict.__delitem__(self, key)
-        self._list.remove(key)
+        def __setitem__(self, key, obj):
+            if key not in self:
+                try:
+                    self._list.append(key)
+                except AttributeError:
+                    # work around Python pickle loads() with
+                    # dict subclass (seems to ignore __setstate__?)
+                    self._list = [key]
+            dict.__setitem__(self, key, obj)
 
-    def pop(self, key, *default):
-        present = key in self
-        value = dict.pop(self, key, *default)
-        if present:
+        def __delitem__(self, key):
+            dict.__delitem__(self, key)
             self._list.remove(key)
-        return value
 
-    def popitem(self):
-        item = dict.popitem(self)
-        self._list.remove(item[0])
-        return item
+        def pop(self, key, *default):
+            present = key in self
+            value = dict.pop(self, key, *default)
+            if present:
+                self._list.remove(key)
+            return value
+
+        def popitem(self):
+            item = dict.popitem(self)
+            self._list.remove(item[0])
+            return item
 
 
 class OrderedSet(set):
diff --git a/test/base/test_utils.py b/test/base/test_utils.py
index 876cb7a44..6d2bb60c9 100644
--- a/test/base/test_utils.py
+++ b/test/base/test_utils.py
@@ -131,6 +131,33 @@ class OrderedDictTest(fixtures.TestBase):
         o3 = copy.copy(o)
         eq_(list(o3.keys()), list(o.keys()))
 
+    def test_no_sort_legacy_dictionary(self):
+        d1 = {"c": 1, "b": 2, "a": 3}
+
+        if testing.requires.python37.enabled:
+            util.sort_dictionary(d1)
+            eq_(list(d1), ["a", "b", "c"])
+        else:
+            assert_raises(AttributeError, util.sort_dictionary, d1)
+
+    def test_sort_dictionary(self):
+        o = util.OrderedDict()
+
+        o["za"] = 1
+        o["az"] = 2
+        o["cc"] = 3
+
+        eq_(
+            list(o),
+            ["za", "az", "cc"],
+        )
+
+        util.sort_dictionary(o)
+        eq_(list(o), ["az", "cc", "za"])
+
+        util.sort_dictionary(o, lambda key: key[1])
+        eq_(list(o), ["za", "cc", "az"])
+
 
 class OrderedSetTest(fixtures.TestBase):
     def test_mutators_against_iter(self):
diff --git a/test/orm/test_collection.py b/test/orm/test_collection.py
index c5e6063a2..7c7662618 100644
--- a/test/orm/test_collection.py
+++ b/test/orm/test_collection.py
@@ -6,6 +6,7 @@ from sqlalchemy import exc as sa_exc
 from sqlalchemy import ForeignKey
 from sqlalchemy import Integer
 from sqlalchemy import String
+from sqlalchemy import testing
 from sqlalchemy import text
 from sqlalchemy import util
 from sqlalchemy.orm import attributes
@@ -69,7 +70,18 @@ class Canary(object):
         return value
 
 
-class CollectionsTest(fixtures.ORMTest):
+class OrderedDictFixture(object):
+    @testing.fixture
+    def ordered_dict_mro(self):
+        if testing.requires.python37.enabled:
+            return type("ordered", (collections.MappedCollection,), {})
+        else:
+            return type(
+                "ordered", (util.OrderedDict, collections.MappedCollection), {}
+            )
+
+
+class CollectionsTest(OrderedDictFixture, fixtures.ORMTest):
     class Entity(object):
         def __init__(self, a=None, b=None, c=None):
             self.a = a
@@ -1287,8 +1299,8 @@ class CollectionsTest(fixtures.ORMTest):
         self._test_dict_bulk(MyEasyDict)
         self.assert_(getattr(MyEasyDict, "_sa_instrumented") == id(MyEasyDict))
 
-    def test_dict_subclass3(self):
-        class MyOrdered(util.OrderedDict, collections.MappedCollection):
+    def test_dict_subclass3(self, ordered_dict_mro):
+        class MyOrdered(ordered_dict_mro):
             def __init__(self):
                 collections.MappedCollection.__init__(self, lambda e: e.a)
                 util.OrderedDict.__init__(self)
@@ -1680,7 +1692,7 @@ class CollectionsTest(fixtures.ORMTest):
         self.assert_(e3 in canary.data)
 
 
-class DictHelpersTest(fixtures.MappedTest):
+class DictHelpersTest(OrderedDictFixture, fixtures.MappedTest):
     @classmethod
     def define_tables(cls, metadata):
         Table(
@@ -1922,8 +1934,8 @@ class DictHelpersTest(fixtures.MappedTest):
         )
         self._test_composite_mapped(collection_class)
 
-    def test_mixin(self):
-        class Ordered(util.OrderedDict, collections.MappedCollection):
+    def test_mixin(self, ordered_dict_mro):
+        class Ordered(ordered_dict_mro):
             def __init__(self):
                 collections.MappedCollection.__init__(self, lambda v: v.a)
                 util.OrderedDict.__init__(self)
@@ -1931,8 +1943,8 @@ class DictHelpersTest(fixtures.MappedTest):
         collection_class = Ordered
         self._test_scalar_mapped(collection_class)
 
-    def test_mixin2(self):
-        class Ordered2(util.OrderedDict, collections.MappedCollection):
+    def test_mixin2(self, ordered_dict_mro):
+        class Ordered2(ordered_dict_mro):
             def __init__(self, keyfunc):
                 collections.MappedCollection.__init__(self, keyfunc)
                 util.OrderedDict.__init__(self)
diff --git a/test/orm/test_lazy_relations.py b/test/orm/test_lazy_relations.py
index c1cc85261..4b7ba0da0 100644
--- a/test/orm/test_lazy_relations.py
+++ b/test/orm/test_lazy_relations.py
@@ -14,6 +14,7 @@ from sqlalchemy import select
 from sqlalchemy import SmallInteger
 from sqlalchemy import String
 from sqlalchemy import testing
+from sqlalchemy import util
 from sqlalchemy.orm import aliased
 from sqlalchemy.orm import attributes
 from sqlalchemy.orm import configure_mappers
@@ -1423,7 +1424,7 @@ class RefersToSelfLazyLoadInterferenceTest(fixtures.MappedTest):
         bmp = bm._props
         configure_mappers()
         # Bug is order-dependent, must sort the "zc" property to the end
-        bmp.sort()
+        util.sort_dictionary(bmp, key=lambda item: item[0])
 
     def test_lazy_doesnt_interfere(self):
         A, B, C = self.classes("A", "B", "C")
diff --git a/test/orm/test_options.py b/test/orm/test_options.py
index cde66d400..b4befcea3 100644
--- a/test/orm/test_options.py
+++ b/test/orm/test_options.py
@@ -238,7 +238,7 @@ class LoadTest(PathTest, QueryTest):
 
         l1 = Load(User)
         l2 = l1.joinedload("addresses")
-        to_bind = l2.context.values()[0]
+        to_bind = list(l2.context.values())[0]
         eq_(
             l1.context,
             {("loader", self._make_path([User, "addresses"])): to_bind},
diff --git a/test/profiles.txt b/test/profiles.txt
index 08cdf911b..71788209a 100644
--- a/test/profiles.txt
+++ b/test/profiles.txt
@@ -260,8 +260,8 @@ test.aaa_profiling.test_orm.AttributeOverheadTest.test_collection_append_remove
 
 test.aaa_profiling.test_orm.BranchedOptionTest.test_query_opts_key_bound_branching x86_64_linux_cpython_2.7_sqlite_pysqlite_dbapiunicode_cextensions 60
 test.aaa_profiling.test_orm.BranchedOptionTest.test_query_opts_key_bound_branching x86_64_linux_cpython_2.7_sqlite_pysqlite_dbapiunicode_nocextensions 60
-test.aaa_profiling.test_orm.BranchedOptionTest.test_query_opts_key_bound_branching x86_64_linux_cpython_3.8_sqlite_pysqlite_dbapiunicode_cextensions 73
-test.aaa_profiling.test_orm.BranchedOptionTest.test_query_opts_key_bound_branching x86_64_linux_cpython_3.8_sqlite_pysqlite_dbapiunicode_nocextensions 73
+test.aaa_profiling.test_orm.BranchedOptionTest.test_query_opts_key_bound_branching x86_64_linux_cpython_3.8_sqlite_pysqlite_dbapiunicode_cextensions 61
+test.aaa_profiling.test_orm.BranchedOptionTest.test_query_opts_key_bound_branching x86_64_linux_cpython_3.8_sqlite_pysqlite_dbapiunicode_nocextensions 61
 
 # TEST: test.aaa_profiling.test_orm.BranchedOptionTest.test_query_opts_unbound_branching