Add new infrastructure to support greater use of __slots__

* Changed AliasedInsp to use __slots__
* Migrated all of strategy_options to use __slots__ for objects.
  Adds new infrastructure to traversals to support shallow
  copy, to dict and from dict based on internal traversal
  attributes.  Load / _LoadElement then leverage this to
  provide clone / generative / getstate without the need
  for __dict__ or explicit attribute lists.

Doing this change revealed that there are lots of things that
trigger off of whether or not a class has a __visit_name__ attribute.
so to suit that we've gone back to having Visitable, which is
a better name than Traversible at this point  (I think
Traversible is mis-spelled too).

Change-Id: I13d04e494339fac9dbda0b8e78153418abebaf72
References: #7527

5 files changed, 297 insertions, 46 deletions

diff --git a/lib/sqlalchemy/sql/base.py b/lib/sqlalchemy/sql/base.py
index 74469b035..8ae8f8f65 100644
--- a/lib/sqlalchemy/sql/base.py
+++ b/lib/sqlalchemy/sql/base.py
@@ -17,6 +17,7 @@ from itertools import zip_longest
 import operator
 import re
 import typing
+from typing import TypeVar
 
 from . import roles
 from . import visitors
@@ -571,11 +572,14 @@ class CompileState:
         return decorate
 
 
+SelfGenerative = TypeVar("SelfGenerative", bound="Generative")
+
+
 class Generative(HasMemoized):
     """Provide a method-chaining pattern in conjunction with the
     @_generative decorator."""
 
-    def _generate(self):
+    def _generate(self: SelfGenerative) -> SelfGenerative:
         skip = self._memoized_keys
         cls = self.__class__
         s = cls.__new__(cls)
@@ -783,6 +787,8 @@ class Options(metaclass=_MetaOptions):
 
 
 class CacheableOptions(Options, HasCacheKey):
+    __slots__ = ()
+
     @hybridmethod
     def _gen_cache_key(self, anon_map, bindparams):
         return HasCacheKey._gen_cache_key(self, anon_map, bindparams)
@@ -797,6 +803,8 @@ class CacheableOptions(Options, HasCacheKey):
 
 
 class ExecutableOption(HasCopyInternals):
+    __slots__ = ()
+
     _annotations = util.EMPTY_DICT
 
     __visit_name__ = "executable_option"
diff --git a/lib/sqlalchemy/sql/cache_key.py b/lib/sqlalchemy/sql/cache_key.py
index 8dd44dbf0..42bd60353 100644
--- a/lib/sqlalchemy/sql/cache_key.py
+++ b/lib/sqlalchemy/sql/cache_key.py
@@ -47,6 +47,11 @@ class CacheTraverseTarget(enum.Enum):
 class HasCacheKey:
     """Mixin for objects which can produce a cache key.
 
+    This class is usually in a hierarchy that starts with the
+    :class:`.HasTraverseInternals` base, but this is optional.  Currently,
+    the class should be able to work on its own without including
+    :class:`.HasTraverseInternals`.
+
     .. seealso::
 
         :class:`.CacheKey`
@@ -55,6 +60,8 @@ class HasCacheKey:
 
     """
 
+    __slots__ = ()
+
     _cache_key_traversal = NO_CACHE
 
     _is_has_cache_key = True
@@ -106,11 +113,17 @@ class HasCacheKey:
             _cache_key_traversal = getattr(cls, "_cache_key_traversal", None)
             if _cache_key_traversal is None:
                 try:
+                    # this would be HasTraverseInternals
                     _cache_key_traversal = cls._traverse_internals
                 except AttributeError:
                     cls._generated_cache_key_traversal = NO_CACHE
                     return NO_CACHE
 
+            assert _cache_key_traversal is not NO_CACHE, (
+                f"class {cls} has _cache_key_traversal=NO_CACHE, "
+                "which conflicts with inherit_cache=True"
+            )
+
             # TODO: wouldn't we instead get this from our superclass?
             # also, our superclass may not have this yet, but in any case,
             # we'd generate for the superclass that has it.   this is a little
@@ -323,6 +336,8 @@ class HasCacheKey:
 
 
 class MemoizedHasCacheKey(HasCacheKey, HasMemoized):
+    __slots__ = ()
+
     @HasMemoized.memoized_instancemethod
     def _generate_cache_key(self):
         return HasCacheKey._generate_cache_key(self)
diff --git a/lib/sqlalchemy/sql/elements.py b/lib/sqlalchemy/sql/elements.py
index 43979b4ae..d14521ba7 100644
--- a/lib/sqlalchemy/sql/elements.py
+++ b/lib/sqlalchemy/sql/elements.py
@@ -46,7 +46,7 @@ from .traversals import HasCopyInternals
 from .visitors import cloned_traverse
 from .visitors import InternalTraversal
 from .visitors import traverse
-from .visitors import Traversible
+from .visitors import Visitable
 from .. import exc
 from .. import inspection
 from .. import util
@@ -126,7 +126,7 @@ def literal_column(text, type_=None):
     return ColumnClause(text, type_=type_, is_literal=True)
 
 
-class CompilerElement(Traversible):
+class CompilerElement(Visitable):
     """base class for SQL elements that can be compiled to produce a
     SQL string.
 
diff --git a/lib/sqlalchemy/sql/traversals.py b/lib/sqlalchemy/sql/traversals.py
index 2fa3a0408..18fd1d4b8 100644
--- a/lib/sqlalchemy/sql/traversals.py
+++ b/lib/sqlalchemy/sql/traversals.py
@@ -10,12 +10,22 @@ import collections.abc as collections_abc
 import itertools
 from itertools import zip_longest
 import operator
+import typing
+from typing import Any
+from typing import Callable
+from typing import Dict
+from typing import Type
+from typing import TypeVar
 
 from . import operators
+from .cache_key import HasCacheKey
+from .visitors import _TraverseInternalsType
 from .visitors import anon_map
+from .visitors import ExtendedInternalTraversal
+from .visitors import HasTraverseInternals
 from .visitors import InternalTraversal
 from .. import util
-
+from ..util import langhelpers
 
 SKIP_TRAVERSE = util.symbol("skip_traverse")
 COMPARE_FAILED = False
@@ -47,11 +57,158 @@ def _preconfigure_traversals(target_hierarchy):
             )
 
 
+SelfHasShallowCopy = TypeVar("SelfHasShallowCopy", bound="HasShallowCopy")
+
+
+class HasShallowCopy(HasTraverseInternals):
+    """attribute-wide operations that are useful for classes that use
+    __slots__ and therefore can't operate on their attributes in a dictionary.
+
+
+    """
+
+    __slots__ = ()
+
+    if typing.TYPE_CHECKING:
+
+        def _generated_shallow_copy_traversal(
+            self: SelfHasShallowCopy, other: SelfHasShallowCopy
+        ) -> None:
+            ...
+
+        def _generated_shallow_from_dict_traversal(
+            self, d: Dict[str, Any]
+        ) -> None:
+            ...
+
+        def _generated_shallow_to_dict_traversal(self) -> Dict[str, Any]:
+            ...
+
+    @classmethod
+    def _generate_shallow_copy(
+        cls: Type[SelfHasShallowCopy],
+        internal_dispatch: _TraverseInternalsType,
+        method_name: str,
+    ) -> Callable[[SelfHasShallowCopy, SelfHasShallowCopy], None]:
+        code = "\n".join(
+            f"    other.{attrname} = self.{attrname}"
+            for attrname, _ in internal_dispatch
+        )
+        meth_text = f"def {method_name}(self, other):\n{code}\n"
+        return langhelpers._exec_code_in_env(meth_text, {}, method_name)
+
+    @classmethod
+    def _generate_shallow_to_dict(
+        cls: Type[SelfHasShallowCopy],
+        internal_dispatch: _TraverseInternalsType,
+        method_name: str,
+    ) -> Callable[[SelfHasShallowCopy], Dict[str, Any]]:
+        code = ",\n".join(
+            f"    '{attrname}': self.{attrname}"
+            for attrname, _ in internal_dispatch
+        )
+        meth_text = f"def {method_name}(self):\n    return {{{code}}}\n"
+        return langhelpers._exec_code_in_env(meth_text, {}, method_name)
+
+    @classmethod
+    def _generate_shallow_from_dict(
+        cls: Type[SelfHasShallowCopy],
+        internal_dispatch: _TraverseInternalsType,
+        method_name: str,
+    ) -> Callable[[SelfHasShallowCopy, Dict[str, Any]], None]:
+        code = "\n".join(
+            f"    self.{attrname} = d['{attrname}']"
+            for attrname, _ in internal_dispatch
+        )
+        meth_text = f"def {method_name}(self, d):\n{code}\n"
+        return langhelpers._exec_code_in_env(meth_text, {}, method_name)
+
+    def _shallow_from_dict(self, d: Dict) -> None:
+        cls = self.__class__
+
+        try:
+            shallow_from_dict = cls.__dict__[
+                "_generated_shallow_from_dict_traversal"
+            ]
+        except KeyError:
+            shallow_from_dict = (
+                cls._generated_shallow_from_dict_traversal  # type: ignore
+            ) = self._generate_shallow_from_dict(
+                cls._traverse_internals,
+                "_generated_shallow_from_dict_traversal",
+            )
+
+        shallow_from_dict(self, d)
+
+    def _shallow_to_dict(self) -> Dict[str, Any]:
+        cls = self.__class__
+
+        try:
+            shallow_to_dict = cls.__dict__[
+                "_generated_shallow_to_dict_traversal"
+            ]
+        except KeyError:
+            shallow_to_dict = (
+                cls._generated_shallow_to_dict_traversal  # type: ignore
+            ) = self._generate_shallow_to_dict(
+                cls._traverse_internals, "_generated_shallow_to_dict_traversal"
+            )
+
+        return shallow_to_dict(self)
+
+    def _shallow_copy_to(self: SelfHasShallowCopy, other: SelfHasShallowCopy):
+        cls = self.__class__
+
+        try:
+            shallow_copy = cls.__dict__["_generated_shallow_copy_traversal"]
+        except KeyError:
+            shallow_copy = (
+                cls._generated_shallow_copy_traversal  # type: ignore
+            ) = self._generate_shallow_copy(
+                cls._traverse_internals, "_generated_shallow_copy_traversal"
+            )
+
+        shallow_copy(self, other)
+
+    def _clone(self: SelfHasShallowCopy, **kw) -> SelfHasShallowCopy:
+        """Create a shallow copy"""
+        c = self.__class__.__new__(self.__class__)
+        self._shallow_copy_to(c)
+        return c
+
+
+SelfGenerativeOnTraversal = TypeVar(
+    "SelfGenerativeOnTraversal", bound="GenerativeOnTraversal"
+)
+
+
+class GenerativeOnTraversal(HasShallowCopy):
+    """Supplies Generative behavior but making use of traversals to shallow
+    copy.
+
+    .. seealso::
+
+        :class:`sqlalchemy.sql.base.Generative`
+
+
+    """
+
+    __slots__ = ()
+
+    def _generate(
+        self: SelfGenerativeOnTraversal,
+    ) -> SelfGenerativeOnTraversal:
+        cls = self.__class__
+        s = cls.__new__(cls)
+        self._shallow_copy_to(s)
+        return s
+
+
 def _clone(element, **kw):
     return element._clone()
 
 
-class HasCopyInternals:
+class HasCopyInternals(HasTraverseInternals):
     __slots__ = ()
 
     def _clone(self, **kw):
@@ -304,7 +461,9 @@ def _resolve_name_for_compare(element, name, anon_map, **kw):
     return name
 
 
-class TraversalComparatorStrategy(InternalTraversal, util.MemoizedSlots):
+class TraversalComparatorStrategy(
+    ExtendedInternalTraversal, util.MemoizedSlots
+):
     __slots__ = "stack", "cache", "anon_map"
 
     def __init__(self):
@@ -377,6 +536,10 @@ class TraversalComparatorStrategy(InternalTraversal, util.MemoizedSlots):
                     continue
 
                 dispatch = self.dispatch(left_visit_sym)
+                assert dispatch, (
+                    f"{self.__class__} has no dispatch for "
+                    f"'{self._dispatch_lookup[left_visit_sym]}'"
+                )
                 left_child = operator.attrgetter(left_attrname)(left)
                 right_child = operator.attrgetter(right_attrname)(right)
                 if left_child is None:
@@ -517,6 +680,46 @@ class TraversalComparatorStrategy(InternalTraversal, util.MemoizedSlots):
     ):
         return left == right
 
+    def visit_string_multi_dict(
+        self, attrname, left_parent, left, right_parent, right, **kw
+    ):
+
+        for lk, rk in zip_longest(
+            sorted(left.keys()), sorted(right.keys()), fillvalue=(None, None)
+        ):
+            if lk != rk:
+                return COMPARE_FAILED
+
+            lv, rv = left[lk], right[rk]
+
+            lhc = isinstance(left, HasCacheKey)
+            rhc = isinstance(right, HasCacheKey)
+            if lhc and rhc:
+                if lv._gen_cache_key(
+                    self.anon_map[0], []
+                ) != rv._gen_cache_key(self.anon_map[1], []):
+                    return COMPARE_FAILED
+            elif lhc != rhc:
+                return COMPARE_FAILED
+            elif lv != rv:
+                return COMPARE_FAILED
+
+    def visit_multi(
+        self, attrname, left_parent, left, right_parent, right, **kw
+    ):
+
+        lhc = isinstance(left, HasCacheKey)
+        rhc = isinstance(right, HasCacheKey)
+        if lhc and rhc:
+            if left._gen_cache_key(
+                self.anon_map[0], []
+            ) != right._gen_cache_key(self.anon_map[1], []):
+                return COMPARE_FAILED
+        elif lhc != rhc:
+            return COMPARE_FAILED
+        else:
+            return left == right
+
     def visit_anon_name(
         self, attrname, left_parent, left, right_parent, right, **kw
     ):
diff --git a/lib/sqlalchemy/sql/visitors.py b/lib/sqlalchemy/sql/visitors.py
index 70c4dc133..78384782b 100644
--- a/lib/sqlalchemy/sql/visitors.py
+++ b/lib/sqlalchemy/sql/visitors.py
@@ -26,11 +26,14 @@ https://techspot.zzzeek.org/2008/01/23/expression-transformations/ .
 from collections import deque
 import itertools
 import operator
+from typing import List
+from typing import Tuple
 
 from .. import exc
 from .. import util
 from ..util import langhelpers
 from ..util import symbol
+from ..util.langhelpers import _symbol
 
 try:
     from sqlalchemy.cyextension.util import cache_anon_map as anon_map  # noqa
@@ -43,14 +46,67 @@ __all__ = [
     "traverse",
     "cloned_traverse",
     "replacement_traverse",
-    "Traversible",
+    "Visitable",
     "ExternalTraversal",
     "InternalTraversal",
 ]
 
+_TraverseInternalsType = List[Tuple[str, _symbol]]
 
-class Traversible:
-    """Base class for visitable objects."""
+
+class HasTraverseInternals:
+    """base for classes that have a "traverse internals" element,
+    which defines all kinds of ways of traversing the elements of an object.
+
+    """
+
+    __slots__ = ()
+
+    _traverse_internals: _TraverseInternalsType
+
+    @util.preload_module("sqlalchemy.sql.traversals")
+    def get_children(self, omit_attrs=(), **kw):
+        r"""Return immediate child :class:`.visitors.Visitable`
+        elements of this :class:`.visitors.Visitable`.
+
+        This is used for visit traversal.
+
+        \**kw may contain flags that change the collection that is
+        returned, for example to return a subset of items in order to
+        cut down on larger traversals, or to return child items from a
+        different context (such as schema-level collections instead of
+        clause-level).
+
+        """
+
+        traversals = util.preloaded.sql_traversals
+
+        try:
+            traverse_internals = self._traverse_internals
+        except AttributeError:
+            # user-defined classes may not have a _traverse_internals
+            return []
+
+        dispatch = traversals._get_children.run_generated_dispatch
+        return itertools.chain.from_iterable(
+            meth(obj, **kw)
+            for attrname, obj, meth in dispatch(
+                self, traverse_internals, "_generated_get_children_traversal"
+            )
+            if attrname not in omit_attrs and obj is not None
+        )
+
+
+class Visitable:
+    """Base class for visitable objects.
+
+    .. versionchanged:: 2.0  The :class:`.Visitable` class was named
+       :class:`.Traversible` in the 1.4 series; the name is changed back
+       to :class:`.Visitable` in 2.0 which is what it was prior to 1.4.
+
+       Both names remain importable in both 1.4 and 2.0 versions.
+
+    """
 
     __slots__ = ()
 
@@ -120,38 +176,6 @@ class Traversible:
         # allow generic classes in py3.9+
         return cls
 
-    @util.preload_module("sqlalchemy.sql.traversals")
-    def get_children(self, omit_attrs=(), **kw):
-        r"""Return immediate child :class:`.visitors.Traversible`
-        elements of this :class:`.visitors.Traversible`.
-
-        This is used for visit traversal.
-
-        \**kw may contain flags that change the collection that is
-        returned, for example to return a subset of items in order to
-        cut down on larger traversals, or to return child items from a
-        different context (such as schema-level collections instead of
-        clause-level).
-
-        """
-
-        traversals = util.preloaded.sql_traversals
-
-        try:
-            traverse_internals = self._traverse_internals
-        except AttributeError:
-            # user-defined classes may not have a _traverse_internals
-            return []
-
-        dispatch = traversals._get_children.run_generated_dispatch
-        return itertools.chain.from_iterable(
-            meth(obj, **kw)
-            for attrname, obj, meth in dispatch(
-                self, traverse_internals, "_generated_get_children_traversal"
-            )
-            if attrname not in omit_attrs and obj is not None
-        )
-
 
 class _HasTraversalDispatch:
     r"""Define infrastructure for the :class:`.InternalTraversal` class.
@@ -261,14 +285,14 @@ class InternalTraversal(_HasTraversalDispatch):
     :class:`.InternalTraversible` will have the following methods automatically
     implemented:
 
-    * :meth:`.Traversible.get_children`
+    * :meth:`.HasTraverseInternals.get_children`
 
-    * :meth:`.Traversible._copy_internals`
+    * :meth:`.HasTraverseInternals._copy_internals`
 
-    * :meth:`.Traversible._gen_cache_key`
+    * :meth:`.HasCacheKey._gen_cache_key`
 
     Subclasses can also implement these methods directly, particularly for the
-    :meth:`.Traversible._copy_internals` method, when special steps
+    :meth:`.HasTraverseInternals._copy_internals` method, when special steps
     are needed.
 
     .. versionadded:: 1.4
@@ -625,7 +649,8 @@ class ReplacingExternalTraversal(CloningExternalTraversal):
 
 
 # backwards compatibility
-Visitable = Traversible
+Traversible = Visitable
+
 ClauseVisitor = ExternalTraversal
 CloningVisitor = CloningExternalTraversal
 ReplacingCloningVisitor = ReplacingExternalTraversal