Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# sql/visitors.py
2# Copyright (C) 2005-2025 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
8"""Visitor/traversal interface and library functions."""
10from __future__ import annotations
12from collections import deque
13from enum import Enum
14import itertools
15import operator
16import typing
17from typing import Any
18from typing import Callable
19from typing import cast
20from typing import ClassVar
21from typing import Dict
22from typing import Iterable
23from typing import Iterator
24from typing import List
25from typing import Mapping
26from typing import Optional
27from typing import overload
28from typing import Tuple
29from typing import Type
30from typing import TYPE_CHECKING
31from typing import TypeVar
32from typing import Union
34from .. import exc
35from .. import util
36from ..util import langhelpers
37from ..util._has_cy import HAS_CYEXTENSION
38from ..util.typing import Literal
39from ..util.typing import Protocol
40from ..util.typing import Self
42if TYPE_CHECKING:
43 from .annotation import _AnnotationDict
44 from .elements import ColumnElement
46if typing.TYPE_CHECKING or not HAS_CYEXTENSION:
47 from ._py_util import prefix_anon_map as prefix_anon_map
48 from ._py_util import cache_anon_map as anon_map
49else:
50 from sqlalchemy.cyextension.util import ( # noqa: F401,E501
51 prefix_anon_map as prefix_anon_map,
52 )
53 from sqlalchemy.cyextension.util import ( # noqa: F401,E501
54 cache_anon_map as anon_map,
55 )
58__all__ = [
59 "iterate",
60 "traverse_using",
61 "traverse",
62 "cloned_traverse",
63 "replacement_traverse",
64 "Visitable",
65 "ExternalTraversal",
66 "InternalTraversal",
67 "anon_map",
68]
71class _CompilerDispatchType(Protocol):
72 def __call__(_self, self: Visitable, visitor: Any, **kw: Any) -> Any: ...
75class Visitable:
76 """Base class for visitable objects.
78 :class:`.Visitable` is used to implement the SQL compiler dispatch
79 functions. Other forms of traversal such as for cache key generation
80 are implemented separately using the :class:`.HasTraverseInternals`
81 interface.
83 .. versionchanged:: 2.0 The :class:`.Visitable` class was named
84 :class:`.Traversible` in the 1.4 series; the name is changed back
85 to :class:`.Visitable` in 2.0 which is what it was prior to 1.4.
87 Both names remain importable in both 1.4 and 2.0 versions.
89 """
91 __slots__ = ()
93 __visit_name__: str
95 _original_compiler_dispatch: _CompilerDispatchType
97 if typing.TYPE_CHECKING:
99 def _compiler_dispatch(self, visitor: Any, **kw: Any) -> str: ...
101 def __init_subclass__(cls) -> None:
102 if "__visit_name__" in cls.__dict__:
103 cls._generate_compiler_dispatch()
104 super().__init_subclass__()
106 @classmethod
107 def _generate_compiler_dispatch(cls) -> None:
108 visit_name = cls.__visit_name__
110 if "_compiler_dispatch" in cls.__dict__:
111 # class has a fixed _compiler_dispatch() method.
112 # copy it to "original" so that we can get it back if
113 # sqlalchemy.ext.compiles overrides it.
114 cls._original_compiler_dispatch = cls._compiler_dispatch
115 return
117 if not isinstance(visit_name, str):
118 raise exc.InvalidRequestError(
119 f"__visit_name__ on class {cls.__name__} must be a string "
120 "at the class level"
121 )
123 name = "visit_%s" % visit_name
124 getter = operator.attrgetter(name)
126 def _compiler_dispatch(
127 self: Visitable, visitor: Any, **kw: Any
128 ) -> str:
129 """Look for an attribute named "visit_<visit_name>" on the
130 visitor, and call it with the same kw params.
132 """
133 try:
134 meth = getter(visitor)
135 except AttributeError as err:
136 return visitor.visit_unsupported_compilation(self, err, **kw) # type: ignore # noqa: E501
137 else:
138 return meth(self, **kw) # type: ignore # noqa: E501
140 cls._compiler_dispatch = ( # type: ignore
141 cls._original_compiler_dispatch
142 ) = _compiler_dispatch
144 def __class_getitem__(cls, key: Any) -> Any:
145 # allow generic classes in py3.9+
146 return cls
149class InternalTraversal(Enum):
150 r"""Defines visitor symbols used for internal traversal.
152 The :class:`.InternalTraversal` class is used in two ways. One is that
153 it can serve as the superclass for an object that implements the
154 various visit methods of the class. The other is that the symbols
155 themselves of :class:`.InternalTraversal` are used within
156 the ``_traverse_internals`` collection. Such as, the :class:`.Case`
157 object defines ``_traverse_internals`` as ::
159 class Case(ColumnElement[_T]):
160 _traverse_internals = [
161 ("value", InternalTraversal.dp_clauseelement),
162 ("whens", InternalTraversal.dp_clauseelement_tuples),
163 ("else_", InternalTraversal.dp_clauseelement),
164 ]
166 Above, the :class:`.Case` class indicates its internal state as the
167 attributes named ``value``, ``whens``, and ``else_``. They each
168 link to an :class:`.InternalTraversal` method which indicates the type
169 of datastructure to which each attribute refers.
171 Using the ``_traverse_internals`` structure, objects of type
172 :class:`.InternalTraversible` will have the following methods automatically
173 implemented:
175 * :meth:`.HasTraverseInternals.get_children`
177 * :meth:`.HasTraverseInternals._copy_internals`
179 * :meth:`.HasCacheKey._gen_cache_key`
181 Subclasses can also implement these methods directly, particularly for the
182 :meth:`.HasTraverseInternals._copy_internals` method, when special steps
183 are needed.
185 .. versionadded:: 1.4
187 """
189 dp_has_cache_key = "HC"
190 """Visit a :class:`.HasCacheKey` object."""
192 dp_has_cache_key_list = "HL"
193 """Visit a list of :class:`.HasCacheKey` objects."""
195 dp_clauseelement = "CE"
196 """Visit a :class:`_expression.ClauseElement` object."""
198 dp_fromclause_canonical_column_collection = "FC"
199 """Visit a :class:`_expression.FromClause` object in the context of the
200 ``columns`` attribute.
202 The column collection is "canonical", meaning it is the originally
203 defined location of the :class:`.ColumnClause` objects. Right now
204 this means that the object being visited is a
205 :class:`_expression.TableClause`
206 or :class:`_schema.Table` object only.
208 """
210 dp_clauseelement_tuples = "CTS"
211 """Visit a list of tuples which contain :class:`_expression.ClauseElement`
212 objects.
214 """
216 dp_clauseelement_list = "CL"
217 """Visit a list of :class:`_expression.ClauseElement` objects.
219 """
221 dp_clauseelement_tuple = "CT"
222 """Visit a tuple of :class:`_expression.ClauseElement` objects.
224 """
226 dp_executable_options = "EO"
228 dp_with_context_options = "WC"
230 dp_fromclause_ordered_set = "CO"
231 """Visit an ordered set of :class:`_expression.FromClause` objects. """
233 dp_string = "S"
234 """Visit a plain string value.
236 Examples include table and column names, bound parameter keys, special
237 keywords such as "UNION", "UNION ALL".
239 The string value is considered to be significant for cache key
240 generation.
242 """
244 dp_string_list = "SL"
245 """Visit a list of strings."""
247 dp_anon_name = "AN"
248 """Visit a potentially "anonymized" string value.
250 The string value is considered to be significant for cache key
251 generation.
253 """
255 dp_boolean = "B"
256 """Visit a boolean value.
258 The boolean value is considered to be significant for cache key
259 generation.
261 """
263 dp_operator = "O"
264 """Visit an operator.
266 The operator is a function from the :mod:`sqlalchemy.sql.operators`
267 module.
269 The operator value is considered to be significant for cache key
270 generation.
272 """
274 dp_type = "T"
275 """Visit a :class:`.TypeEngine` object
277 The type object is considered to be significant for cache key
278 generation.
280 """
282 dp_plain_dict = "PD"
283 """Visit a dictionary with string keys.
285 The keys of the dictionary should be strings, the values should
286 be immutable and hashable. The dictionary is considered to be
287 significant for cache key generation.
289 """
291 dp_dialect_options = "DO"
292 """Visit a dialect options structure."""
294 dp_string_clauseelement_dict = "CD"
295 """Visit a dictionary of string keys to :class:`_expression.ClauseElement`
296 objects.
298 """
300 dp_string_multi_dict = "MD"
301 """Visit a dictionary of string keys to values which may either be
302 plain immutable/hashable or :class:`.HasCacheKey` objects.
304 """
306 dp_annotations_key = "AK"
307 """Visit the _annotations_cache_key element.
309 This is a dictionary of additional information about a ClauseElement
310 that modifies its role. It should be included when comparing or caching
311 objects, however generating this key is relatively expensive. Visitors
312 should check the "_annotations" dict for non-None first before creating
313 this key.
315 """
317 dp_plain_obj = "PO"
318 """Visit a plain python object.
320 The value should be immutable and hashable, such as an integer.
321 The value is considered to be significant for cache key generation.
323 """
325 dp_named_ddl_element = "DD"
326 """Visit a simple named DDL element.
328 The current object used by this method is the :class:`.Sequence`.
330 The object is only considered to be important for cache key generation
331 as far as its name, but not any other aspects of it.
333 """
335 dp_prefix_sequence = "PS"
336 """Visit the sequence represented by :class:`_expression.HasPrefixes`
337 or :class:`_expression.HasSuffixes`.
339 """
341 dp_table_hint_list = "TH"
342 """Visit the ``_hints`` collection of a :class:`_expression.Select`
343 object.
345 """
347 dp_setup_join_tuple = "SJ"
349 dp_memoized_select_entities = "ME"
351 dp_statement_hint_list = "SH"
352 """Visit the ``_statement_hints`` collection of a
353 :class:`_expression.Select`
354 object.
356 """
358 dp_unknown_structure = "UK"
359 """Visit an unknown structure.
361 """
363 dp_dml_ordered_values = "DML_OV"
364 """Visit the values() ordered tuple list of an
365 :class:`_expression.Update` object."""
367 dp_dml_values = "DML_V"
368 """Visit the values() dictionary of a :class:`.ValuesBase`
369 (e.g. Insert or Update) object.
371 """
373 dp_dml_multi_values = "DML_MV"
374 """Visit the values() multi-valued list of dictionaries of an
375 :class:`_expression.Insert` object.
377 """
379 dp_propagate_attrs = "PA"
380 """Visit the propagate attrs dict. This hardcodes to the particular
381 elements we care about right now."""
383 """Symbols that follow are additional symbols that are useful in
384 caching applications.
386 Traversals for :class:`_expression.ClauseElement` objects only need to use
387 those symbols present in :class:`.InternalTraversal`. However, for
388 additional caching use cases within the ORM, symbols dealing with the
389 :class:`.HasCacheKey` class are added here.
391 """
393 dp_ignore = "IG"
394 """Specify an object that should be ignored entirely.
396 This currently applies function call argument caching where some
397 arguments should not be considered to be part of a cache key.
399 """
401 dp_inspectable = "IS"
402 """Visit an inspectable object where the return value is a
403 :class:`.HasCacheKey` object."""
405 dp_multi = "M"
406 """Visit an object that may be a :class:`.HasCacheKey` or may be a
407 plain hashable object."""
409 dp_multi_list = "MT"
410 """Visit a tuple containing elements that may be :class:`.HasCacheKey` or
411 may be a plain hashable object."""
413 dp_has_cache_key_tuples = "HT"
414 """Visit a list of tuples which contain :class:`.HasCacheKey`
415 objects.
417 """
419 dp_inspectable_list = "IL"
420 """Visit a list of inspectable objects which upon inspection are
421 HasCacheKey objects."""
424_TraverseInternalsType = List[Tuple[str, InternalTraversal]]
425"""a structure that defines how a HasTraverseInternals should be
426traversed.
428This structure consists of a list of (attributename, internaltraversal)
429tuples, where the "attributename" refers to the name of an attribute on an
430instance of the HasTraverseInternals object, and "internaltraversal" refers
431to an :class:`.InternalTraversal` enumeration symbol defining what kind
432of data this attribute stores, which indicates to the traverser how it should
433be handled.
435"""
438class HasTraverseInternals:
439 """base for classes that have a "traverse internals" element,
440 which defines all kinds of ways of traversing the elements of an object.
442 Compared to :class:`.Visitable`, which relies upon an external visitor to
443 define how the object is travered (i.e. the :class:`.SQLCompiler`), the
444 :class:`.HasTraverseInternals` interface allows classes to define their own
445 traversal, that is, what attributes are accessed and in what order.
447 """
449 __slots__ = ()
451 _traverse_internals: _TraverseInternalsType
453 _is_immutable: bool = False
455 @util.preload_module("sqlalchemy.sql.traversals")
456 def get_children(
457 self, *, omit_attrs: Tuple[str, ...] = (), **kw: Any
458 ) -> Iterable[HasTraverseInternals]:
459 r"""Return immediate child :class:`.visitors.HasTraverseInternals`
460 elements of this :class:`.visitors.HasTraverseInternals`.
462 This is used for visit traversal.
464 \**kw may contain flags that change the collection that is
465 returned, for example to return a subset of items in order to
466 cut down on larger traversals, or to return child items from a
467 different context (such as schema-level collections instead of
468 clause-level).
470 """
472 traversals = util.preloaded.sql_traversals
474 try:
475 traverse_internals = self._traverse_internals
476 except AttributeError:
477 # user-defined classes may not have a _traverse_internals
478 return []
480 dispatch = traversals._get_children.run_generated_dispatch
481 return itertools.chain.from_iterable(
482 meth(obj, **kw)
483 for attrname, obj, meth in dispatch(
484 self, traverse_internals, "_generated_get_children_traversal"
485 )
486 if attrname not in omit_attrs and obj is not None
487 )
490class _InternalTraversalDispatchType(Protocol):
491 def __call__(s, self: object, visitor: HasTraversalDispatch) -> Any: ...
494class HasTraversalDispatch:
495 r"""Define infrastructure for classes that perform internal traversals
497 .. versionadded:: 2.0
499 """
501 __slots__ = ()
503 _dispatch_lookup: ClassVar[Dict[Union[InternalTraversal, str], str]] = {}
505 def dispatch(self, visit_symbol: InternalTraversal) -> Callable[..., Any]:
506 """Given a method from :class:`.HasTraversalDispatch`, return the
507 corresponding method on a subclass.
509 """
510 name = _dispatch_lookup[visit_symbol]
511 return getattr(self, name, None) # type: ignore
513 def run_generated_dispatch(
514 self,
515 target: object,
516 internal_dispatch: _TraverseInternalsType,
517 generate_dispatcher_name: str,
518 ) -> Any:
519 dispatcher: _InternalTraversalDispatchType
520 try:
521 dispatcher = target.__class__.__dict__[generate_dispatcher_name]
522 except KeyError:
523 # traversals.py -> _preconfigure_traversals()
524 # may be used to run these ahead of time, but
525 # is not enabled right now.
526 # this block will generate any remaining dispatchers.
527 dispatcher = self.generate_dispatch(
528 target.__class__, internal_dispatch, generate_dispatcher_name
529 )
530 return dispatcher(target, self)
532 def generate_dispatch(
533 self,
534 target_cls: Type[object],
535 internal_dispatch: _TraverseInternalsType,
536 generate_dispatcher_name: str,
537 ) -> _InternalTraversalDispatchType:
538 dispatcher = self._generate_dispatcher(
539 internal_dispatch, generate_dispatcher_name
540 )
541 # assert isinstance(target_cls, type)
542 setattr(target_cls, generate_dispatcher_name, dispatcher)
543 return dispatcher
545 def _generate_dispatcher(
546 self, internal_dispatch: _TraverseInternalsType, method_name: str
547 ) -> _InternalTraversalDispatchType:
548 names = []
549 for attrname, visit_sym in internal_dispatch:
550 meth = self.dispatch(visit_sym)
551 if meth is not None:
552 visit_name = _dispatch_lookup[visit_sym]
553 names.append((attrname, visit_name))
555 code = (
556 (" return [\n")
557 + (
558 ", \n".join(
559 " (%r, self.%s, visitor.%s)"
560 % (attrname, attrname, visit_name)
561 for attrname, visit_name in names
562 )
563 )
564 + ("\n ]\n")
565 )
566 meth_text = ("def %s(self, visitor):\n" % method_name) + code + "\n"
567 return cast(
568 _InternalTraversalDispatchType,
569 langhelpers._exec_code_in_env(meth_text, {}, method_name),
570 )
573ExtendedInternalTraversal = InternalTraversal
576def _generate_traversal_dispatch() -> None:
577 lookup = _dispatch_lookup
579 for sym in InternalTraversal:
580 key = sym.name
581 if key.startswith("dp_"):
582 visit_key = key.replace("dp_", "visit_")
583 sym_name = sym.value
584 assert sym_name not in lookup, sym_name
585 lookup[sym] = lookup[sym_name] = visit_key
588_dispatch_lookup = HasTraversalDispatch._dispatch_lookup
589_generate_traversal_dispatch()
592class ExternallyTraversible(HasTraverseInternals, Visitable):
593 __slots__ = ()
595 _annotations: Mapping[Any, Any] = util.EMPTY_DICT
597 if typing.TYPE_CHECKING:
599 def _annotate(self, values: _AnnotationDict) -> Self: ...
601 def get_children(
602 self, *, omit_attrs: Tuple[str, ...] = (), **kw: Any
603 ) -> Iterable[ExternallyTraversible]: ...
605 def _clone(self, **kw: Any) -> Self:
606 """clone this element"""
607 raise NotImplementedError()
609 def _copy_internals(
610 self, *, omit_attrs: Tuple[str, ...] = (), **kw: Any
611 ) -> None:
612 """Reassign internal elements to be clones of themselves.
614 Called during a copy-and-traverse operation on newly
615 shallow-copied elements to create a deep copy.
617 The given clone function should be used, which may be applying
618 additional transformations to the element (i.e. replacement
619 traversal, cloned traversal, annotations).
621 """
622 raise NotImplementedError()
625_ET = TypeVar("_ET", bound=ExternallyTraversible)
627_CE = TypeVar("_CE", bound="ColumnElement[Any]")
629_TraverseCallableType = Callable[[_ET], None]
632class _CloneCallableType(Protocol):
633 def __call__(self, element: _ET, **kw: Any) -> _ET: ...
636class _TraverseTransformCallableType(Protocol[_ET]):
637 def __call__(self, element: _ET, **kw: Any) -> Optional[_ET]: ...
640_ExtT = TypeVar("_ExtT", bound="ExternalTraversal")
643class ExternalTraversal(util.MemoizedSlots):
644 """Base class for visitor objects which can traverse externally using
645 the :func:`.visitors.traverse` function.
647 Direct usage of the :func:`.visitors.traverse` function is usually
648 preferred.
650 """
652 __slots__ = ("_visitor_dict", "_next")
654 __traverse_options__: Dict[str, Any] = {}
655 _next: Optional[ExternalTraversal]
657 def traverse_single(self, obj: Visitable, **kw: Any) -> Any:
658 for v in self.visitor_iterator:
659 meth = getattr(v, "visit_%s" % obj.__visit_name__, None)
660 if meth:
661 return meth(obj, **kw)
663 def iterate(
664 self, obj: Optional[ExternallyTraversible]
665 ) -> Iterator[ExternallyTraversible]:
666 """Traverse the given expression structure, returning an iterator
667 of all elements.
669 """
670 return iterate(obj, self.__traverse_options__)
672 @overload
673 def traverse(self, obj: Literal[None]) -> None: ...
675 @overload
676 def traverse(
677 self, obj: ExternallyTraversible
678 ) -> ExternallyTraversible: ...
680 def traverse(
681 self, obj: Optional[ExternallyTraversible]
682 ) -> Optional[ExternallyTraversible]:
683 """Traverse and visit the given expression structure."""
685 return traverse(obj, self.__traverse_options__, self._visitor_dict)
687 def _memoized_attr__visitor_dict(
688 self,
689 ) -> Dict[str, _TraverseCallableType[Any]]:
690 visitors = {}
692 for name in dir(self):
693 if name.startswith("visit_"):
694 visitors[name[6:]] = getattr(self, name)
695 return visitors
697 @property
698 def visitor_iterator(self) -> Iterator[ExternalTraversal]:
699 """Iterate through this visitor and each 'chained' visitor."""
701 v: Optional[ExternalTraversal] = self
702 while v:
703 yield v
704 v = getattr(v, "_next", None)
706 def chain(self: _ExtT, visitor: ExternalTraversal) -> _ExtT:
707 """'Chain' an additional ExternalTraversal onto this ExternalTraversal
709 The chained visitor will receive all visit events after this one.
711 """
712 tail = list(self.visitor_iterator)[-1]
713 tail._next = visitor
714 return self
717class CloningExternalTraversal(ExternalTraversal):
718 """Base class for visitor objects which can traverse using
719 the :func:`.visitors.cloned_traverse` function.
721 Direct usage of the :func:`.visitors.cloned_traverse` function is usually
722 preferred.
725 """
727 __slots__ = ()
729 def copy_and_process(
730 self, list_: List[ExternallyTraversible]
731 ) -> List[ExternallyTraversible]:
732 """Apply cloned traversal to the given list of elements, and return
733 the new list.
735 """
736 return [self.traverse(x) for x in list_]
738 @overload
739 def traverse(self, obj: Literal[None]) -> None: ...
741 @overload
742 def traverse(
743 self, obj: ExternallyTraversible
744 ) -> ExternallyTraversible: ...
746 def traverse(
747 self, obj: Optional[ExternallyTraversible]
748 ) -> Optional[ExternallyTraversible]:
749 """Traverse and visit the given expression structure."""
751 return cloned_traverse(
752 obj, self.__traverse_options__, self._visitor_dict
753 )
756class ReplacingExternalTraversal(CloningExternalTraversal):
757 """Base class for visitor objects which can traverse using
758 the :func:`.visitors.replacement_traverse` function.
760 Direct usage of the :func:`.visitors.replacement_traverse` function is
761 usually preferred.
763 """
765 __slots__ = ()
767 def replace(
768 self, elem: ExternallyTraversible
769 ) -> Optional[ExternallyTraversible]:
770 """Receive pre-copied elements during a cloning traversal.
772 If the method returns a new element, the element is used
773 instead of creating a simple copy of the element. Traversal
774 will halt on the newly returned element if it is re-encountered.
775 """
776 return None
778 @overload
779 def traverse(self, obj: Literal[None]) -> None: ...
781 @overload
782 def traverse(
783 self, obj: ExternallyTraversible
784 ) -> ExternallyTraversible: ...
786 def traverse(
787 self, obj: Optional[ExternallyTraversible]
788 ) -> Optional[ExternallyTraversible]:
789 """Traverse and visit the given expression structure."""
791 def replace(
792 element: ExternallyTraversible,
793 **kw: Any,
794 ) -> Optional[ExternallyTraversible]:
795 for v in self.visitor_iterator:
796 e = cast(ReplacingExternalTraversal, v).replace(element)
797 if e is not None:
798 return e
800 return None
802 return replacement_traverse(obj, self.__traverse_options__, replace)
805# backwards compatibility
806Traversible = Visitable
808ClauseVisitor = ExternalTraversal
809CloningVisitor = CloningExternalTraversal
810ReplacingCloningVisitor = ReplacingExternalTraversal
813def iterate(
814 obj: Optional[ExternallyTraversible],
815 opts: Mapping[str, Any] = util.EMPTY_DICT,
816) -> Iterator[ExternallyTraversible]:
817 r"""Traverse the given expression structure, returning an iterator.
819 Traversal is configured to be breadth-first.
821 The central API feature used by the :func:`.visitors.iterate`
822 function is the
823 :meth:`_expression.ClauseElement.get_children` method of
824 :class:`_expression.ClauseElement` objects. This method should return all
825 the :class:`_expression.ClauseElement` objects which are associated with a
826 particular :class:`_expression.ClauseElement` object. For example, a
827 :class:`.Case` structure will refer to a series of
828 :class:`_expression.ColumnElement` objects within its "whens" and "else\_"
829 member variables.
831 :param obj: :class:`_expression.ClauseElement` structure to be traversed
833 :param opts: dictionary of iteration options. This dictionary is usually
834 empty in modern usage.
836 """
837 if obj is None:
838 return
840 yield obj
841 children = obj.get_children(**opts)
843 if not children:
844 return
846 stack = deque([children])
847 while stack:
848 t_iterator = stack.popleft()
849 for t in t_iterator:
850 yield t
851 stack.append(t.get_children(**opts))
854@overload
855def traverse_using(
856 iterator: Iterable[ExternallyTraversible],
857 obj: Literal[None],
858 visitors: Mapping[str, _TraverseCallableType[Any]],
859) -> None: ...
862@overload
863def traverse_using(
864 iterator: Iterable[ExternallyTraversible],
865 obj: ExternallyTraversible,
866 visitors: Mapping[str, _TraverseCallableType[Any]],
867) -> ExternallyTraversible: ...
870def traverse_using(
871 iterator: Iterable[ExternallyTraversible],
872 obj: Optional[ExternallyTraversible],
873 visitors: Mapping[str, _TraverseCallableType[Any]],
874) -> Optional[ExternallyTraversible]:
875 """Visit the given expression structure using the given iterator of
876 objects.
878 :func:`.visitors.traverse_using` is usually called internally as the result
879 of the :func:`.visitors.traverse` function.
881 :param iterator: an iterable or sequence which will yield
882 :class:`_expression.ClauseElement`
883 structures; the iterator is assumed to be the
884 product of the :func:`.visitors.iterate` function.
886 :param obj: the :class:`_expression.ClauseElement`
887 that was used as the target of the
888 :func:`.iterate` function.
890 :param visitors: dictionary of visit functions. See :func:`.traverse`
891 for details on this dictionary.
893 .. seealso::
895 :func:`.traverse`
898 """
899 for target in iterator:
900 meth = visitors.get(target.__visit_name__, None)
901 if meth:
902 meth(target)
903 return obj
906@overload
907def traverse(
908 obj: Literal[None],
909 opts: Mapping[str, Any],
910 visitors: Mapping[str, _TraverseCallableType[Any]],
911) -> None: ...
914@overload
915def traverse(
916 obj: ExternallyTraversible,
917 opts: Mapping[str, Any],
918 visitors: Mapping[str, _TraverseCallableType[Any]],
919) -> ExternallyTraversible: ...
922def traverse(
923 obj: Optional[ExternallyTraversible],
924 opts: Mapping[str, Any],
925 visitors: Mapping[str, _TraverseCallableType[Any]],
926) -> Optional[ExternallyTraversible]:
927 """Traverse and visit the given expression structure using the default
928 iterator.
930 e.g.::
932 from sqlalchemy.sql import visitors
934 stmt = select(some_table).where(some_table.c.foo == "bar")
937 def visit_bindparam(bind_param):
938 print("found bound value: %s" % bind_param.value)
941 visitors.traverse(stmt, {}, {"bindparam": visit_bindparam})
943 The iteration of objects uses the :func:`.visitors.iterate` function,
944 which does a breadth-first traversal using a stack.
946 :param obj: :class:`_expression.ClauseElement` structure to be traversed
948 :param opts: dictionary of iteration options. This dictionary is usually
949 empty in modern usage.
951 :param visitors: dictionary of visit functions. The dictionary should
952 have strings as keys, each of which would correspond to the
953 ``__visit_name__`` of a particular kind of SQL expression object, and
954 callable functions as values, each of which represents a visitor function
955 for that kind of object.
957 """
958 return traverse_using(iterate(obj, opts), obj, visitors)
961@overload
962def cloned_traverse(
963 obj: Literal[None],
964 opts: Mapping[str, Any],
965 visitors: Mapping[str, _TraverseCallableType[Any]],
966) -> None: ...
969# a bit of controversy here, as the clone of the lead element
970# *could* in theory replace with an entirely different kind of element.
971# however this is really not how cloned_traverse is ever used internally
972# at least.
973@overload
974def cloned_traverse(
975 obj: _ET,
976 opts: Mapping[str, Any],
977 visitors: Mapping[str, _TraverseCallableType[Any]],
978) -> _ET: ...
981def cloned_traverse(
982 obj: Optional[ExternallyTraversible],
983 opts: Mapping[str, Any],
984 visitors: Mapping[str, _TraverseCallableType[Any]],
985) -> Optional[ExternallyTraversible]:
986 """Clone the given expression structure, allowing modifications by
987 visitors for mutable objects.
989 Traversal usage is the same as that of :func:`.visitors.traverse`.
990 The visitor functions present in the ``visitors`` dictionary may also
991 modify the internals of the given structure as the traversal proceeds.
993 The :func:`.cloned_traverse` function does **not** provide objects that are
994 part of the :class:`.Immutable` interface to the visit methods (this
995 primarily includes :class:`.ColumnClause`, :class:`.Column`,
996 :class:`.TableClause` and :class:`.Table` objects). As this traversal is
997 only intended to allow in-place mutation of objects, :class:`.Immutable`
998 objects are skipped. The :meth:`.Immutable._clone` method is still called
999 on each object to allow for objects to replace themselves with a different
1000 object based on a clone of their sub-internals (e.g. a
1001 :class:`.ColumnClause` that clones its subquery to return a new
1002 :class:`.ColumnClause`).
1004 .. versionchanged:: 2.0 The :func:`.cloned_traverse` function omits
1005 objects that are part of the :class:`.Immutable` interface.
1007 The central API feature used by the :func:`.visitors.cloned_traverse`
1008 and :func:`.visitors.replacement_traverse` functions, in addition to the
1009 :meth:`_expression.ClauseElement.get_children`
1010 function that is used to achieve
1011 the iteration, is the :meth:`_expression.ClauseElement._copy_internals`
1012 method.
1013 For a :class:`_expression.ClauseElement`
1014 structure to support cloning and replacement
1015 traversals correctly, it needs to be able to pass a cloning function into
1016 its internal members in order to make copies of them.
1018 .. seealso::
1020 :func:`.visitors.traverse`
1022 :func:`.visitors.replacement_traverse`
1024 """
1026 cloned: Dict[int, ExternallyTraversible] = {}
1027 stop_on = set(opts.get("stop_on", []))
1029 def deferred_copy_internals(
1030 obj: ExternallyTraversible,
1031 ) -> ExternallyTraversible:
1032 return cloned_traverse(obj, opts, visitors)
1034 def clone(elem: ExternallyTraversible, **kw: Any) -> ExternallyTraversible:
1035 if elem in stop_on:
1036 return elem
1037 else:
1038 if id(elem) not in cloned:
1039 if "replace" in kw:
1040 newelem = cast(
1041 Optional[ExternallyTraversible], kw["replace"](elem)
1042 )
1043 if newelem is not None:
1044 cloned[id(elem)] = newelem
1045 return newelem
1047 # the _clone method for immutable normally returns "self".
1048 # however, the method is still allowed to return a
1049 # different object altogether; ColumnClause._clone() will
1050 # based on options clone the subquery to which it is associated
1051 # and return the new corresponding column.
1052 cloned[id(elem)] = newelem = elem._clone(clone=clone, **kw)
1053 newelem._copy_internals(clone=clone, **kw)
1055 # however, visit methods which are tasked with in-place
1056 # mutation of the object should not get access to the immutable
1057 # object.
1058 if not elem._is_immutable:
1059 meth = visitors.get(newelem.__visit_name__, None)
1060 if meth:
1061 meth(newelem)
1062 return cloned[id(elem)]
1064 if obj is not None:
1065 obj = clone(
1066 obj, deferred_copy_internals=deferred_copy_internals, **opts
1067 )
1068 clone = None # type: ignore[assignment] # remove gc cycles
1069 return obj
1072@overload
1073def replacement_traverse(
1074 obj: Literal[None],
1075 opts: Mapping[str, Any],
1076 replace: _TraverseTransformCallableType[Any],
1077) -> None: ...
1080@overload
1081def replacement_traverse(
1082 obj: _CE,
1083 opts: Mapping[str, Any],
1084 replace: _TraverseTransformCallableType[Any],
1085) -> _CE: ...
1088@overload
1089def replacement_traverse(
1090 obj: ExternallyTraversible,
1091 opts: Mapping[str, Any],
1092 replace: _TraverseTransformCallableType[Any],
1093) -> ExternallyTraversible: ...
1096def replacement_traverse(
1097 obj: Optional[ExternallyTraversible],
1098 opts: Mapping[str, Any],
1099 replace: _TraverseTransformCallableType[Any],
1100) -> Optional[ExternallyTraversible]:
1101 """Clone the given expression structure, allowing element
1102 replacement by a given replacement function.
1104 This function is very similar to the :func:`.visitors.cloned_traverse`
1105 function, except instead of being passed a dictionary of visitors, all
1106 elements are unconditionally passed into the given replace function.
1107 The replace function then has the option to return an entirely new object
1108 which will replace the one given. If it returns ``None``, then the object
1109 is kept in place.
1111 The difference in usage between :func:`.visitors.cloned_traverse` and
1112 :func:`.visitors.replacement_traverse` is that in the former case, an
1113 already-cloned object is passed to the visitor function, and the visitor
1114 function can then manipulate the internal state of the object.
1115 In the case of the latter, the visitor function should only return an
1116 entirely different object, or do nothing.
1118 The use case for :func:`.visitors.replacement_traverse` is that of
1119 replacing a FROM clause inside of a SQL structure with a different one,
1120 as is a common use case within the ORM.
1122 """
1124 cloned = {}
1125 stop_on = {id(x) for x in opts.get("stop_on", [])}
1127 def deferred_copy_internals(
1128 obj: ExternallyTraversible,
1129 ) -> ExternallyTraversible:
1130 return replacement_traverse(obj, opts, replace)
1132 def clone(elem: ExternallyTraversible, **kw: Any) -> ExternallyTraversible:
1133 if (
1134 id(elem) in stop_on
1135 or "no_replacement_traverse" in elem._annotations
1136 ):
1137 return elem
1138 else:
1139 newelem = replace(elem)
1140 if newelem is not None:
1141 stop_on.add(id(newelem))
1142 return newelem # type: ignore
1143 else:
1144 # base "already seen" on id(), not hash, so that we don't
1145 # replace an Annotated element with its non-annotated one, and
1146 # vice versa
1147 id_elem = id(elem)
1148 if id_elem not in cloned:
1149 if "replace" in kw:
1150 newelem = kw["replace"](elem)
1151 if newelem is not None:
1152 cloned[id_elem] = newelem
1153 return newelem # type: ignore
1155 cloned[id_elem] = newelem = elem._clone(**kw)
1156 newelem._copy_internals(clone=clone, **kw)
1157 return cloned[id_elem] # type: ignore
1159 if obj is not None:
1160 obj = clone(
1161 obj, deferred_copy_internals=deferred_copy_internals, **opts
1162 )
1163 clone = None # type: ignore[assignment] # remove gc cycles
1164 return obj