1# sql/visitors.py
2# Copyright (C) 2005-2021 the SQLAlchemy authors and contributors
3# <see AUTHORS file>
4#
5# This module is part of SQLAlchemy and is released under
6# the MIT License: https://www.opensource.org/licenses/mit-license.php
7
8"""Visitor/traversal interface and library functions.
9
10SQLAlchemy schema and expression constructs rely on a Python-centric
11version of the classic "visitor" pattern as the primary way in which
12they apply functionality.  The most common use of this pattern
13is statement compilation, where individual expression classes match
14up to rendering methods that produce a string result.   Beyond this,
15the visitor system is also used to inspect expressions for various
16information and patterns, as well as for the purposes of applying
17transformations to expressions.
18
19Examples of how the visit system is used can be seen in the source code
20of for example the ``sqlalchemy.sql.util`` and the ``sqlalchemy.sql.compiler``
21modules.  Some background on clause adaption is also at
22https://techspot.zzzeek.org/2008/01/23/expression-transformations/ .
23
24"""
25
26from collections import deque
27import itertools
28import operator
29
30from .. import exc
31from .. import util
32from ..util import langhelpers
33from ..util import symbol
34
35__all__ = [
36    "iterate",
37    "traverse_using",
38    "traverse",
39    "cloned_traverse",
40    "replacement_traverse",
41    "Traversible",
42    "TraversibleType",
43    "ExternalTraversal",
44    "InternalTraversal",
45]
46
47
48def _generate_compiler_dispatch(cls):
49    """Generate a _compiler_dispatch() external traversal on classes with a
50    __visit_name__ attribute.
51
52    """
53    visit_name = cls.__visit_name__
54
55    if "_compiler_dispatch" in cls.__dict__:
56        # class has a fixed _compiler_dispatch() method.
57        # copy it to "original" so that we can get it back if
58        # sqlalchemy.ext.compiles overrides it.
59        cls._original_compiler_dispatch = cls._compiler_dispatch
60        return
61
62    if not isinstance(visit_name, util.compat.string_types):
63        raise exc.InvalidRequestError(
64            "__visit_name__ on class %s must be a string at the class level"
65            % cls.__name__
66        )
67
68    name = "visit_%s" % visit_name
69    getter = operator.attrgetter(name)
70
71    def _compiler_dispatch(self, visitor, **kw):
72        """Look for an attribute named "visit_<visit_name>" on the
73        visitor, and call it with the same kw params.
74
75        """
76        try:
77            meth = getter(visitor)
78        except AttributeError as err:
79            return visitor.visit_unsupported_compilation(self, err, **kw)
80
81        else:
82            return meth(self, **kw)
83
84    cls._compiler_dispatch = (
85        cls._original_compiler_dispatch
86    ) = _compiler_dispatch
87
88
89class TraversibleType(type):
90    """Metaclass which assigns dispatch attributes to various kinds of
91    "visitable" classes.
92
93    Attributes include:
94
95    * The ``_compiler_dispatch`` method, corresponding to ``__visit_name__``.
96      This is called "external traversal" because the caller of each visit()
97      method is responsible for sub-traversing the inner elements of each
98      object. This is appropriate for string compilers and other traversals
99      that need to call upon the inner elements in a specific pattern.
100
101    * internal traversal collections ``_children_traversal``,
102      ``_cache_key_traversal``, ``_copy_internals_traversal``, generated from
103      an optional ``_traverse_internals`` collection of symbols which comes
104      from the :class:`.InternalTraversal` list of symbols.  This is called
105      "internal traversal" MARKMARK
106
107    """
108
109    def __init__(cls, clsname, bases, clsdict):
110        if clsname != "Traversible":
111            if "__visit_name__" in clsdict:
112                _generate_compiler_dispatch(cls)
113
114        super(TraversibleType, cls).__init__(clsname, bases, clsdict)
115
116
117class Traversible(util.with_metaclass(TraversibleType)):
118    """Base class for visitable objects, applies the
119    :class:`.visitors.TraversibleType` metaclass.
120
121    """
122
123    def __class_getitem__(cls, key):
124        # allow generic classes in py3.9+
125        return cls
126
127    @util.preload_module("sqlalchemy.sql.traversals")
128    def get_children(self, omit_attrs=(), **kw):
129        r"""Return immediate child :class:`.visitors.Traversible`
130        elements of this :class:`.visitors.Traversible`.
131
132        This is used for visit traversal.
133
134        \**kw may contain flags that change the collection that is
135        returned, for example to return a subset of items in order to
136        cut down on larger traversals, or to return child items from a
137        different context (such as schema-level collections instead of
138        clause-level).
139
140        """
141
142        traversals = util.preloaded.sql_traversals
143
144        try:
145            traverse_internals = self._traverse_internals
146        except AttributeError:
147            # user-defined classes may not have a _traverse_internals
148            return []
149
150        dispatch = traversals._get_children.run_generated_dispatch
151        return itertools.chain.from_iterable(
152            meth(obj, **kw)
153            for attrname, obj, meth in dispatch(
154                self, traverse_internals, "_generated_get_children_traversal"
155            )
156            if attrname not in omit_attrs and obj is not None
157        )
158
159
160class _InternalTraversalType(type):
161    def __init__(cls, clsname, bases, clsdict):
162        if cls.__name__ in ("InternalTraversal", "ExtendedInternalTraversal"):
163            lookup = {}
164            for key, sym in clsdict.items():
165                if key.startswith("dp_"):
166                    visit_key = key.replace("dp_", "visit_")
167                    sym_name = sym.name
168                    assert sym_name not in lookup, sym_name
169                    lookup[sym] = lookup[sym_name] = visit_key
170            if hasattr(cls, "_dispatch_lookup"):
171                lookup.update(cls._dispatch_lookup)
172            cls._dispatch_lookup = lookup
173
174        super(_InternalTraversalType, cls).__init__(clsname, bases, clsdict)
175
176
177def _generate_dispatcher(visitor, internal_dispatch, method_name):
178    names = []
179    for attrname, visit_sym in internal_dispatch:
180        meth = visitor.dispatch(visit_sym)
181        if meth:
182            visit_name = ExtendedInternalTraversal._dispatch_lookup[visit_sym]
183            names.append((attrname, visit_name))
184
185    code = (
186        ("    return [\n")
187        + (
188            ", \n".join(
189                "        (%r, self.%s, visitor.%s)"
190                % (attrname, attrname, visit_name)
191                for attrname, visit_name in names
192            )
193        )
194        + ("\n    ]\n")
195    )
196    meth_text = ("def %s(self, visitor):\n" % method_name) + code + "\n"
197    # print(meth_text)
198    return langhelpers._exec_code_in_env(meth_text, {}, method_name)
199
200
201class InternalTraversal(util.with_metaclass(_InternalTraversalType, object)):
202    r"""Defines visitor symbols used for internal traversal.
203
204    The :class:`.InternalTraversal` class is used in two ways.  One is that
205    it can serve as the superclass for an object that implements the
206    various visit methods of the class.   The other is that the symbols
207    themselves of :class:`.InternalTraversal` are used within
208    the ``_traverse_internals`` collection.   Such as, the :class:`.Case`
209    object defines ``_traverse_internals`` as ::
210
211        _traverse_internals = [
212            ("value", InternalTraversal.dp_clauseelement),
213            ("whens", InternalTraversal.dp_clauseelement_tuples),
214            ("else_", InternalTraversal.dp_clauseelement),
215        ]
216
217    Above, the :class:`.Case` class indicates its internal state as the
218    attributes named ``value``, ``whens``, and ``else_``.    They each
219    link to an :class:`.InternalTraversal` method which indicates the type
220    of datastructure referred towards.
221
222    Using the ``_traverse_internals`` structure, objects of type
223    :class:`.InternalTraversible` will have the following methods automatically
224    implemented:
225
226    * :meth:`.Traversible.get_children`
227
228    * :meth:`.Traversible._copy_internals`
229
230    * :meth:`.Traversible._gen_cache_key`
231
232    Subclasses can also implement these methods directly, particularly for the
233    :meth:`.Traversible._copy_internals` method, when special steps
234    are needed.
235
236    .. versionadded:: 1.4
237
238    """
239
240    def dispatch(self, visit_symbol):
241        """Given a method from :class:`.InternalTraversal`, return the
242        corresponding method on a subclass.
243
244        """
245        name = self._dispatch_lookup[visit_symbol]
246        return getattr(self, name, None)
247
248    def run_generated_dispatch(
249        self, target, internal_dispatch, generate_dispatcher_name
250    ):
251        try:
252            dispatcher = target.__class__.__dict__[generate_dispatcher_name]
253        except KeyError:
254            # most of the dispatchers are generated up front
255            # in sqlalchemy/sql/__init__.py ->
256            # traversals.py-> _preconfigure_traversals().
257            # this block will generate any remaining dispatchers.
258            dispatcher = self.generate_dispatch(
259                target.__class__, internal_dispatch, generate_dispatcher_name
260            )
261        return dispatcher(target, self)
262
263    def generate_dispatch(
264        self, target_cls, internal_dispatch, generate_dispatcher_name
265    ):
266        dispatcher = _generate_dispatcher(
267            self, internal_dispatch, generate_dispatcher_name
268        )
269        # assert isinstance(target_cls, type)
270        setattr(target_cls, generate_dispatcher_name, dispatcher)
271        return dispatcher
272
273    dp_has_cache_key = symbol("HC")
274    """Visit a :class:`.HasCacheKey` object."""
275
276    dp_has_cache_key_list = symbol("HL")
277    """Visit a list of :class:`.HasCacheKey` objects."""
278
279    dp_clauseelement = symbol("CE")
280    """Visit a :class:`_expression.ClauseElement` object."""
281
282    dp_fromclause_canonical_column_collection = symbol("FC")
283    """Visit a :class:`_expression.FromClause` object in the context of the
284    ``columns`` attribute.
285
286    The column collection is "canonical", meaning it is the originally
287    defined location of the :class:`.ColumnClause` objects.   Right now
288    this means that the object being visited is a
289    :class:`_expression.TableClause`
290    or :class:`_schema.Table` object only.
291
292    """
293
294    dp_clauseelement_tuples = symbol("CTS")
295    """Visit a list of tuples which contain :class:`_expression.ClauseElement`
296    objects.
297
298    """
299
300    dp_clauseelement_list = symbol("CL")
301    """Visit a list of :class:`_expression.ClauseElement` objects.
302
303    """
304
305    dp_clauseelement_tuple = symbol("CT")
306    """Visit a tuple of :class:`_expression.ClauseElement` objects.
307
308    """
309
310    dp_executable_options = symbol("EO")
311
312    dp_with_context_options = symbol("WC")
313
314    dp_fromclause_ordered_set = symbol("CO")
315    """Visit an ordered set of :class:`_expression.FromClause` objects. """
316
317    dp_string = symbol("S")
318    """Visit a plain string value.
319
320    Examples include table and column names, bound parameter keys, special
321    keywords such as "UNION", "UNION ALL".
322
323    The string value is considered to be significant for cache key
324    generation.
325
326    """
327
328    dp_string_list = symbol("SL")
329    """Visit a list of strings."""
330
331    dp_anon_name = symbol("AN")
332    """Visit a potentially "anonymized" string value.
333
334    The string value is considered to be significant for cache key
335    generation.
336
337    """
338
339    dp_boolean = symbol("B")
340    """Visit a boolean value.
341
342    The boolean value is considered to be significant for cache key
343    generation.
344
345    """
346
347    dp_operator = symbol("O")
348    """Visit an operator.
349
350    The operator is a function from the :mod:`sqlalchemy.sql.operators`
351    module.
352
353    The operator value is considered to be significant for cache key
354    generation.
355
356    """
357
358    dp_type = symbol("T")
359    """Visit a :class:`.TypeEngine` object
360
361    The type object is considered to be significant for cache key
362    generation.
363
364    """
365
366    dp_plain_dict = symbol("PD")
367    """Visit a dictionary with string keys.
368
369    The keys of the dictionary should be strings, the values should
370    be immutable and hashable.   The dictionary is considered to be
371    significant for cache key generation.
372
373    """
374
375    dp_dialect_options = symbol("DO")
376    """Visit a dialect options structure."""
377
378    dp_string_clauseelement_dict = symbol("CD")
379    """Visit a dictionary of string keys to :class:`_expression.ClauseElement`
380    objects.
381
382    """
383
384    dp_string_multi_dict = symbol("MD")
385    """Visit a dictionary of string keys to values which may either be
386    plain immutable/hashable or :class:`.HasCacheKey` objects.
387
388    """
389
390    dp_annotations_key = symbol("AK")
391    """Visit the _annotations_cache_key element.
392
393    This is a dictionary of additional information about a ClauseElement
394    that modifies its role.  It should be included when comparing or caching
395    objects, however generating this key is relatively expensive.   Visitors
396    should check the "_annotations" dict for non-None first before creating
397    this key.
398
399    """
400
401    dp_plain_obj = symbol("PO")
402    """Visit a plain python object.
403
404    The value should be immutable and hashable, such as an integer.
405    The value is considered to be significant for cache key generation.
406
407    """
408
409    dp_named_ddl_element = symbol("DD")
410    """Visit a simple named DDL element.
411
412    The current object used by this method is the :class:`.Sequence`.
413
414    The object is only considered to be important for cache key generation
415    as far as its name, but not any other aspects of it.
416
417    """
418
419    dp_prefix_sequence = symbol("PS")
420    """Visit the sequence represented by :class:`_expression.HasPrefixes`
421    or :class:`_expression.HasSuffixes`.
422
423    """
424
425    dp_table_hint_list = symbol("TH")
426    """Visit the ``_hints`` collection of a :class:`_expression.Select`
427    object.
428
429    """
430
431    dp_setup_join_tuple = symbol("SJ")
432
433    dp_memoized_select_entities = symbol("ME")
434
435    dp_statement_hint_list = symbol("SH")
436    """Visit the ``_statement_hints`` collection of a
437    :class:`_expression.Select`
438    object.
439
440    """
441
442    dp_unknown_structure = symbol("UK")
443    """Visit an unknown structure.
444
445    """
446
447    dp_dml_ordered_values = symbol("DML_OV")
448    """Visit the values() ordered tuple list of an
449    :class:`_expression.Update` object."""
450
451    dp_dml_values = symbol("DML_V")
452    """Visit the values() dictionary of a :class:`.ValuesBase`
453    (e.g. Insert or Update) object.
454
455    """
456
457    dp_dml_multi_values = symbol("DML_MV")
458    """Visit the values() multi-valued list of dictionaries of an
459    :class:`_expression.Insert` object.
460
461    """
462
463    dp_propagate_attrs = symbol("PA")
464    """Visit the propagate attrs dict.  This hardcodes to the particular
465    elements we care about right now."""
466
467
468class ExtendedInternalTraversal(InternalTraversal):
469    """Defines additional symbols that are useful in caching applications.
470
471    Traversals for :class:`_expression.ClauseElement` objects only need to use
472    those symbols present in :class:`.InternalTraversal`.  However, for
473    additional caching use cases within the ORM, symbols dealing with the
474    :class:`.HasCacheKey` class are added here.
475
476    """
477
478    dp_ignore = symbol("IG")
479    """Specify an object that should be ignored entirely.
480
481    This currently applies function call argument caching where some
482    arguments should not be considered to be part of a cache key.
483
484    """
485
486    dp_inspectable = symbol("IS")
487    """Visit an inspectable object where the return value is a
488    :class:`.HasCacheKey` object."""
489
490    dp_multi = symbol("M")
491    """Visit an object that may be a :class:`.HasCacheKey` or may be a
492    plain hashable object."""
493
494    dp_multi_list = symbol("MT")
495    """Visit a tuple containing elements that may be :class:`.HasCacheKey` or
496    may be a plain hashable object."""
497
498    dp_has_cache_key_tuples = symbol("HT")
499    """Visit a list of tuples which contain :class:`.HasCacheKey`
500    objects.
501
502    """
503
504    dp_inspectable_list = symbol("IL")
505    """Visit a list of inspectable objects which upon inspection are
506    HasCacheKey objects."""
507
508
509class ExternalTraversal(object):
510    """Base class for visitor objects which can traverse externally using
511    the :func:`.visitors.traverse` function.
512
513    Direct usage of the :func:`.visitors.traverse` function is usually
514    preferred.
515
516    """
517
518    __traverse_options__ = {}
519
520    def traverse_single(self, obj, **kw):
521        for v in self.visitor_iterator:
522            meth = getattr(v, "visit_%s" % obj.__visit_name__, None)
523            if meth:
524                return meth(obj, **kw)
525
526    def iterate(self, obj):
527        """Traverse the given expression structure, returning an iterator
528        of all elements.
529
530        """
531        return iterate(obj, self.__traverse_options__)
532
533    def traverse(self, obj):
534        """Traverse and visit the given expression structure."""
535
536        return traverse(obj, self.__traverse_options__, self._visitor_dict)
537
538    @util.memoized_property
539    def _visitor_dict(self):
540        visitors = {}
541
542        for name in dir(self):
543            if name.startswith("visit_"):
544                visitors[name[6:]] = getattr(self, name)
545        return visitors
546
547    @property
548    def visitor_iterator(self):
549        """Iterate through this visitor and each 'chained' visitor."""
550
551        v = self
552        while v:
553            yield v
554            v = getattr(v, "_next", None)
555
556    def chain(self, visitor):
557        """'Chain' an additional ClauseVisitor onto this ClauseVisitor.
558
559        The chained visitor will receive all visit events after this one.
560
561        """
562        tail = list(self.visitor_iterator)[-1]
563        tail._next = visitor
564        return self
565
566
567class CloningExternalTraversal(ExternalTraversal):
568    """Base class for visitor objects which can traverse using
569    the :func:`.visitors.cloned_traverse` function.
570
571    Direct usage of the :func:`.visitors.cloned_traverse` function is usually
572    preferred.
573
574
575    """
576
577    def copy_and_process(self, list_):
578        """Apply cloned traversal to the given list of elements, and return
579        the new list.
580
581        """
582        return [self.traverse(x) for x in list_]
583
584    def traverse(self, obj):
585        """Traverse and visit the given expression structure."""
586
587        return cloned_traverse(
588            obj, self.__traverse_options__, self._visitor_dict
589        )
590
591
592class ReplacingExternalTraversal(CloningExternalTraversal):
593    """Base class for visitor objects which can traverse using
594    the :func:`.visitors.replacement_traverse` function.
595
596    Direct usage of the :func:`.visitors.replacement_traverse` function is
597    usually preferred.
598
599    """
600
601    def replace(self, elem):
602        """Receive pre-copied elements during a cloning traversal.
603
604        If the method returns a new element, the element is used
605        instead of creating a simple copy of the element.  Traversal
606        will halt on the newly returned element if it is re-encountered.
607        """
608        return None
609
610    def traverse(self, obj):
611        """Traverse and visit the given expression structure."""
612
613        def replace(elem):
614            for v in self.visitor_iterator:
615                e = v.replace(elem)
616                if e is not None:
617                    return e
618
619        return replacement_traverse(obj, self.__traverse_options__, replace)
620
621
622# backwards compatibility
623Visitable = Traversible
624VisitableType = TraversibleType
625ClauseVisitor = ExternalTraversal
626CloningVisitor = CloningExternalTraversal
627ReplacingCloningVisitor = ReplacingExternalTraversal
628
629
630def iterate(obj, opts=util.immutabledict()):
631    r"""Traverse the given expression structure, returning an iterator.
632
633    Traversal is configured to be breadth-first.
634
635    The central API feature used by the :func:`.visitors.iterate`
636    function is the
637    :meth:`_expression.ClauseElement.get_children` method of
638    :class:`_expression.ClauseElement` objects.  This method should return all
639    the :class:`_expression.ClauseElement` objects which are associated with a
640    particular :class:`_expression.ClauseElement` object. For example, a
641    :class:`.Case` structure will refer to a series of
642    :class:`_expression.ColumnElement` objects within its "whens" and "else\_"
643    member variables.
644
645    :param obj: :class:`_expression.ClauseElement` structure to be traversed
646
647    :param opts: dictionary of iteration options.   This dictionary is usually
648     empty in modern usage.
649
650    """
651    yield obj
652    children = obj.get_children(**opts)
653
654    if not children:
655        return
656
657    stack = deque([children])
658    while stack:
659        t_iterator = stack.popleft()
660        for t in t_iterator:
661            yield t
662            stack.append(t.get_children(**opts))
663
664
665def traverse_using(iterator, obj, visitors):
666    """Visit the given expression structure using the given iterator of
667    objects.
668
669    :func:`.visitors.traverse_using` is usually called internally as the result
670    of the :func:`.visitors.traverse` function.
671
672    :param iterator: an iterable or sequence which will yield
673     :class:`_expression.ClauseElement`
674     structures; the iterator is assumed to be the
675     product of the :func:`.visitors.iterate` function.
676
677    :param obj: the :class:`_expression.ClauseElement`
678     that was used as the target of the
679     :func:`.iterate` function.
680
681    :param visitors: dictionary of visit functions.  See :func:`.traverse`
682     for details on this dictionary.
683
684    .. seealso::
685
686        :func:`.traverse`
687
688
689    """
690    for target in iterator:
691        meth = visitors.get(target.__visit_name__, None)
692        if meth:
693            meth(target)
694    return obj
695
696
697def traverse(obj, opts, visitors):
698    """Traverse and visit the given expression structure using the default
699    iterator.
700
701     e.g.::
702
703        from sqlalchemy.sql import visitors
704
705        stmt = select(some_table).where(some_table.c.foo == 'bar')
706
707        def visit_bindparam(bind_param):
708            print("found bound value: %s" % bind_param.value)
709
710        visitors.traverse(stmt, {}, {"bindparam": visit_bindparam})
711
712    The iteration of objects uses the :func:`.visitors.iterate` function,
713    which does a breadth-first traversal using a stack.
714
715    :param obj: :class:`_expression.ClauseElement` structure to be traversed
716
717    :param opts: dictionary of iteration options.   This dictionary is usually
718     empty in modern usage.
719
720    :param visitors: dictionary of visit functions.   The dictionary should
721     have strings as keys, each of which would correspond to the
722     ``__visit_name__`` of a particular kind of SQL expression object, and
723     callable functions  as values, each of which represents a visitor function
724     for that kind of object.
725
726    """
727    return traverse_using(iterate(obj, opts), obj, visitors)
728
729
730def cloned_traverse(obj, opts, visitors):
731    """Clone the given expression structure, allowing modifications by
732    visitors.
733
734    Traversal usage is the same as that of :func:`.visitors.traverse`.
735    The visitor functions present in the ``visitors`` dictionary may also
736    modify the internals of the given structure as the traversal proceeds.
737
738    The central API feature used by the :func:`.visitors.cloned_traverse`
739    and :func:`.visitors.replacement_traverse` functions, in addition to the
740    :meth:`_expression.ClauseElement.get_children`
741    function that is used to achieve
742    the iteration, is the :meth:`_expression.ClauseElement._copy_internals`
743    method.
744    For a :class:`_expression.ClauseElement`
745    structure to support cloning and replacement
746    traversals correctly, it needs to be able to pass a cloning function into
747    its internal members in order to make copies of them.
748
749    .. seealso::
750
751        :func:`.visitors.traverse`
752
753        :func:`.visitors.replacement_traverse`
754
755    """
756
757    cloned = {}
758    stop_on = set(opts.get("stop_on", []))
759
760    def deferred_copy_internals(obj):
761        return cloned_traverse(obj, opts, visitors)
762
763    def clone(elem, **kw):
764        if elem in stop_on:
765            return elem
766        else:
767            if id(elem) not in cloned:
768
769                if "replace" in kw:
770                    newelem = kw["replace"](elem)
771                    if newelem is not None:
772                        cloned[id(elem)] = newelem
773                        return newelem
774
775                cloned[id(elem)] = newelem = elem._clone(**kw)
776                newelem._copy_internals(clone=clone, **kw)
777                meth = visitors.get(newelem.__visit_name__, None)
778                if meth:
779                    meth(newelem)
780            return cloned[id(elem)]
781
782    if obj is not None:
783        obj = clone(
784            obj, deferred_copy_internals=deferred_copy_internals, **opts
785        )
786    clone = None  # remove gc cycles
787    return obj
788
789
790def replacement_traverse(obj, opts, replace):
791    """Clone the given expression structure, allowing element
792    replacement by a given replacement function.
793
794    This function is very similar to the :func:`.visitors.cloned_traverse`
795    function, except instead of being passed a dictionary of visitors, all
796    elements are unconditionally passed into the given replace function.
797    The replace function then has the option to return an entirely new object
798    which will replace the one given.  If it returns ``None``, then the object
799    is kept in place.
800
801    The difference in usage between :func:`.visitors.cloned_traverse` and
802    :func:`.visitors.replacement_traverse` is that in the former case, an
803    already-cloned object is passed to the visitor function, and the visitor
804    function can then manipulate the internal state of the object.
805    In the case of the latter, the visitor function should only return an
806    entirely different object, or do nothing.
807
808    The use case for :func:`.visitors.replacement_traverse` is that of
809    replacing a FROM clause inside of a SQL structure with a different one,
810    as is a common use case within the ORM.
811
812    """
813
814    cloned = {}
815    stop_on = {id(x) for x in opts.get("stop_on", [])}
816
817    def deferred_copy_internals(obj):
818        return replacement_traverse(obj, opts, replace)
819
820    def clone(elem, **kw):
821        if (
822            id(elem) in stop_on
823            or "no_replacement_traverse" in elem._annotations
824        ):
825            return elem
826        else:
827            newelem = replace(elem)
828            if newelem is not None:
829                stop_on.add(id(newelem))
830                return newelem
831            else:
832                # base "already seen" on id(), not hash, so that we don't
833                # replace an Annotated element with its non-annotated one, and
834                # vice versa
835                id_elem = id(elem)
836                if id_elem not in cloned:
837                    if "replace" in kw:
838                        newelem = kw["replace"](elem)
839                        if newelem is not None:
840                            cloned[id_elem] = newelem
841                            return newelem
842
843                    cloned[id_elem] = newelem = elem._clone(**kw)
844                    newelem._copy_internals(clone=clone, **kw)
845                return cloned[id_elem]
846
847    if obj is not None:
848        obj = clone(
849            obj, deferred_copy_internals=deferred_copy_internals, **opts
850        )
851    clone = None  # remove gc cycles
852    return obj
853