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.
11"""
13from __future__ import annotations
15from collections import deque
16from enum import Enum
17import itertools
18import operator
19import typing
20from typing import Any
21from typing import Callable
22from typing import cast
23from typing import ClassVar
24from typing import Dict
25from typing import Iterable
26from typing import Iterator
27from typing import List
28from typing import Mapping
29from typing import Optional
30from typing import overload
31from typing import Tuple
32from typing import Type
33from typing import TYPE_CHECKING
34from typing import TypeVar
35from typing import Union
37from .. import exc
38from .. import util
39from ..util import langhelpers
40from ..util._has_cy import HAS_CYEXTENSION
41from ..util.typing import Literal
42from ..util.typing import Protocol
43from ..util.typing import Self
45if TYPE_CHECKING:
46 from .annotation import _AnnotationDict
47 from .elements import ColumnElement
49if typing.TYPE_CHECKING or not HAS_CYEXTENSION:
50 from ._py_util import prefix_anon_map as prefix_anon_map
51 from ._py_util import cache_anon_map as anon_map
52else:
53 from sqlalchemy.cyextension.util import ( # noqa: F401,E501
54 prefix_anon_map as prefix_anon_map,
55 )
56 from sqlalchemy.cyextension.util import ( # noqa: F401,E501
57 cache_anon_map as anon_map,
58 )
61__all__ = [
62 "iterate",
63 "traverse_using",
64 "traverse",
65 "cloned_traverse",
66 "replacement_traverse",
67 "Visitable",
68 "ExternalTraversal",
69 "InternalTraversal",
70 "anon_map",
71]
74class _CompilerDispatchType(Protocol):
75 def __call__(_self, self: Visitable, visitor: Any, **kw: Any) -> Any: ...
78class Visitable:
79 """Base class for visitable objects.
81 :class:`.Visitable` is used to implement the SQL compiler dispatch
82 functions. Other forms of traversal such as for cache key generation
83 are implemented separately using the :class:`.HasTraverseInternals`
84 interface.
86 .. versionchanged:: 2.0 The :class:`.Visitable` class was named
87 :class:`.Traversible` in the 1.4 series; the name is changed back
88 to :class:`.Visitable` in 2.0 which is what it was prior to 1.4.
90 Both names remain importable in both 1.4 and 2.0 versions.
92 """
94 __slots__ = ()
96 __visit_name__: str
98 _original_compiler_dispatch: _CompilerDispatchType
100 if typing.TYPE_CHECKING:
102 def _compiler_dispatch(self, visitor: Any, **kw: Any) -> str: ...
104 def __init_subclass__(cls) -> None:
105 if "__visit_name__" in cls.__dict__:
106 cls._generate_compiler_dispatch()
107 super().__init_subclass__()
109 @classmethod
110 def _generate_compiler_dispatch(cls) -> None:
111 visit_name = cls.__visit_name__
113 if "_compiler_dispatch" in cls.__dict__:
114 # class has a fixed _compiler_dispatch() method.
115 # copy it to "original" so that we can get it back if
116 # sqlalchemy.ext.compiles overrides it.
117 cls._original_compiler_dispatch = cls._compiler_dispatch
118 return
120 if not isinstance(visit_name, str):
121 raise exc.InvalidRequestError(
122 f"__visit_name__ on class {cls.__name__} must be a string "
123 "at the class level"
124 )
126 name = "visit_%s" % visit_name
127 getter = operator.attrgetter(name)
129 def _compiler_dispatch(
130 self: Visitable, visitor: Any, **kw: Any
131 ) -> str:
132 """Look for an attribute named "visit_<visit_name>" on the
133 visitor, and call it with the same kw params.
135 """
136 try:
137 meth = getter(visitor)
138 except AttributeError as err:
139 return visitor.visit_unsupported_compilation(self, err, **kw) # type: ignore # noqa: E501
140 else:
141 return meth(self, **kw) # type: ignore # noqa: E501
143 cls._compiler_dispatch = ( # type: ignore
144 cls._original_compiler_dispatch
145 ) = _compiler_dispatch
147 def __class_getitem__(cls, key: Any) -> Any:
148 # allow generic classes in py3.9+
149 return cls
152class InternalTraversal(Enum):
153 r"""Defines visitor symbols used for internal traversal.
155 The :class:`.InternalTraversal` class is used in two ways. One is that
156 it can serve as the superclass for an object that implements the
157 various visit methods of the class. The other is that the symbols
158 themselves of :class:`.InternalTraversal` are used within
159 the ``_traverse_internals`` collection. Such as, the :class:`.Case`
160 object defines ``_traverse_internals`` as ::
162 class Case(ColumnElement[_T]):
163 _traverse_internals = [
164 ("value", InternalTraversal.dp_clauseelement),
165 ("whens", InternalTraversal.dp_clauseelement_tuples),
166 ("else_", InternalTraversal.dp_clauseelement),
167 ]
169 Above, the :class:`.Case` class indicates its internal state as the
170 attributes named ``value``, ``whens``, and ``else_``. They each
171 link to an :class:`.InternalTraversal` method which indicates the type
172 of datastructure to which each attribute refers.
174 Using the ``_traverse_internals`` structure, objects of type
175 :class:`.InternalTraversible` will have the following methods automatically
176 implemented:
178 * :meth:`.HasTraverseInternals.get_children`
180 * :meth:`.HasTraverseInternals._copy_internals`
182 * :meth:`.HasCacheKey._gen_cache_key`
184 Subclasses can also implement these methods directly, particularly for the
185 :meth:`.HasTraverseInternals._copy_internals` method, when special steps
186 are needed.
188 .. versionadded:: 1.4
190 """
192 dp_has_cache_key = "HC"
193 """Visit a :class:`.HasCacheKey` object."""
195 dp_has_cache_key_list = "HL"
196 """Visit a list of :class:`.HasCacheKey` objects."""
198 dp_clauseelement = "CE"
199 """Visit a :class:`_expression.ClauseElement` object."""
201 dp_fromclause_canonical_column_collection = "FC"
202 """Visit a :class:`_expression.FromClause` object in the context of the
203 ``columns`` attribute.
205 The column collection is "canonical", meaning it is the originally
206 defined location of the :class:`.ColumnClause` objects. Right now
207 this means that the object being visited is a
208 :class:`_expression.TableClause`
209 or :class:`_schema.Table` object only.
211 """
213 dp_clauseelement_tuples = "CTS"
214 """Visit a list of tuples which contain :class:`_expression.ClauseElement`
215 objects.
217 """
219 dp_clauseelement_list = "CL"
220 """Visit a list of :class:`_expression.ClauseElement` objects.
222 """
224 dp_clauseelement_tuple = "CT"
225 """Visit a tuple of :class:`_expression.ClauseElement` objects.
227 """
229 dp_executable_options = "EO"
231 dp_with_context_options = "WC"
233 dp_fromclause_ordered_set = "CO"
234 """Visit an ordered set of :class:`_expression.FromClause` objects. """
236 dp_string = "S"
237 """Visit a plain string value.
239 Examples include table and column names, bound parameter keys, special
240 keywords such as "UNION", "UNION ALL".
242 The string value is considered to be significant for cache key
243 generation.
245 """
247 dp_string_list = "SL"
248 """Visit a list of strings."""
250 dp_anon_name = "AN"
251 """Visit a potentially "anonymized" string value.
253 The string value is considered to be significant for cache key
254 generation.
256 """
258 dp_boolean = "B"
259 """Visit a boolean value.
261 The boolean value is considered to be significant for cache key
262 generation.
264 """
266 dp_operator = "O"
267 """Visit an operator.
269 The operator is a function from the :mod:`sqlalchemy.sql.operators`
270 module.
272 The operator value is considered to be significant for cache key
273 generation.
275 """
277 dp_type = "T"
278 """Visit a :class:`.TypeEngine` object
280 The type object is considered to be significant for cache key
281 generation.
283 """
285 dp_plain_dict = "PD"
286 """Visit a dictionary with string keys.
288 The keys of the dictionary should be strings, the values should
289 be immutable and hashable. The dictionary is considered to be
290 significant for cache key generation.
292 """
294 dp_dialect_options = "DO"
295 """Visit a dialect options structure."""
297 dp_string_clauseelement_dict = "CD"
298 """Visit a dictionary of string keys to :class:`_expression.ClauseElement`
299 objects.
301 """
303 dp_string_multi_dict = "MD"
304 """Visit a dictionary of string keys to values which may either be
305 plain immutable/hashable or :class:`.HasCacheKey` objects.
307 """
309 dp_annotations_key = "AK"
310 """Visit the _annotations_cache_key element.
312 This is a dictionary of additional information about a ClauseElement
313 that modifies its role. It should be included when comparing or caching
314 objects, however generating this key is relatively expensive. Visitors
315 should check the "_annotations" dict for non-None first before creating
316 this key.
318 """
320 dp_plain_obj = "PO"
321 """Visit a plain python object.
323 The value should be immutable and hashable, such as an integer.
324 The value is considered to be significant for cache key generation.
326 """
328 dp_named_ddl_element = "DD"
329 """Visit a simple named DDL element.
331 The current object used by this method is the :class:`.Sequence`.
333 The object is only considered to be important for cache key generation
334 as far as its name, but not any other aspects of it.
336 """
338 dp_prefix_sequence = "PS"
339 """Visit the sequence represented by :class:`_expression.HasPrefixes`
340 or :class:`_expression.HasSuffixes`.
342 """
344 dp_table_hint_list = "TH"
345 """Visit the ``_hints`` collection of a :class:`_expression.Select`
346 object.
348 """
350 dp_setup_join_tuple = "SJ"
352 dp_memoized_select_entities = "ME"
354 dp_statement_hint_list = "SH"
355 """Visit the ``_statement_hints`` collection of a
356 :class:`_expression.Select`
357 object.
359 """
361 dp_unknown_structure = "UK"
362 """Visit an unknown structure.
364 """
366 dp_dml_ordered_values = "DML_OV"
367 """Visit the values() ordered tuple list of an
368 :class:`_expression.Update` object."""
370 dp_dml_values = "DML_V"
371 """Visit the values() dictionary of a :class:`.ValuesBase`
372 (e.g. Insert or Update) object.
374 """
376 dp_dml_multi_values = "DML_MV"
377 """Visit the values() multi-valued list of dictionaries of an
378 :class:`_expression.Insert` object.
380 """
382 dp_propagate_attrs = "PA"
383 """Visit the propagate attrs dict. This hardcodes to the particular
384 elements we care about right now."""
386 """Symbols that follow are additional symbols that are useful in
387 caching applications.
389 Traversals for :class:`_expression.ClauseElement` objects only need to use
390 those symbols present in :class:`.InternalTraversal`. However, for
391 additional caching use cases within the ORM, symbols dealing with the
392 :class:`.HasCacheKey` class are added here.
394 """
396 dp_ignore = "IG"
397 """Specify an object that should be ignored entirely.
399 This currently applies function call argument caching where some
400 arguments should not be considered to be part of a cache key.
402 """
404 dp_inspectable = "IS"
405 """Visit an inspectable object where the return value is a
406 :class:`.HasCacheKey` object."""
408 dp_multi = "M"
409 """Visit an object that may be a :class:`.HasCacheKey` or may be a
410 plain hashable object."""
412 dp_multi_list = "MT"
413 """Visit a tuple containing elements that may be :class:`.HasCacheKey` or
414 may be a plain hashable object."""
416 dp_has_cache_key_tuples = "HT"
417 """Visit a list of tuples which contain :class:`.HasCacheKey`
418 objects.
420 """
422 dp_inspectable_list = "IL"
423 """Visit a list of inspectable objects which upon inspection are
424 HasCacheKey objects."""
427_TraverseInternalsType = List[Tuple[str, InternalTraversal]]
428"""a structure that defines how a HasTraverseInternals should be
429traversed.
431This structure consists of a list of (attributename, internaltraversal)
432tuples, where the "attributename" refers to the name of an attribute on an
433instance of the HasTraverseInternals object, and "internaltraversal" refers
434to an :class:`.InternalTraversal` enumeration symbol defining what kind
435of data this attribute stores, which indicates to the traverser how it should
436be handled.
438"""
441class HasTraverseInternals:
442 """base for classes that have a "traverse internals" element,
443 which defines all kinds of ways of traversing the elements of an object.
445 Compared to :class:`.Visitable`, which relies upon an external visitor to
446 define how the object is travered (i.e. the :class:`.SQLCompiler`), the
447 :class:`.HasTraverseInternals` interface allows classes to define their own
448 traversal, that is, what attributes are accessed and in what order.
450 """
452 __slots__ = ()
454 _traverse_internals: _TraverseInternalsType
456 _is_immutable: bool = False
458 @util.preload_module("sqlalchemy.sql.traversals")
459 def get_children(
460 self, *, omit_attrs: Tuple[str, ...] = (), **kw: Any
461 ) -> Iterable[HasTraverseInternals]:
462 r"""Return immediate child :class:`.visitors.HasTraverseInternals`
463 elements of this :class:`.visitors.HasTraverseInternals`.
465 This is used for visit traversal.
467 \**kw may contain flags that change the collection that is
468 returned, for example to return a subset of items in order to
469 cut down on larger traversals, or to return child items from a
470 different context (such as schema-level collections instead of
471 clause-level).
473 """
475 traversals = util.preloaded.sql_traversals
477 try:
478 traverse_internals = self._traverse_internals
479 except AttributeError:
480 # user-defined classes may not have a _traverse_internals
481 return []
483 dispatch = traversals._get_children.run_generated_dispatch
484 return itertools.chain.from_iterable(
485 meth(obj, **kw)
486 for attrname, obj, meth in dispatch(
487 self, traverse_internals, "_generated_get_children_traversal"
488 )
489 if attrname not in omit_attrs and obj is not None
490 )
493class _InternalTraversalDispatchType(Protocol):
494 def __call__(s, self: object, visitor: HasTraversalDispatch) -> Any: ...
497class HasTraversalDispatch:
498 r"""Define infrastructure for classes that perform internal traversals
500 .. versionadded:: 2.0
502 """
504 __slots__ = ()
506 _dispatch_lookup: ClassVar[Dict[Union[InternalTraversal, str], str]] = {}
508 def dispatch(self, visit_symbol: InternalTraversal) -> Callable[..., Any]:
509 """Given a method from :class:`.HasTraversalDispatch`, return the
510 corresponding method on a subclass.
512 """
513 name = _dispatch_lookup[visit_symbol]
514 return getattr(self, name, None) # type: ignore
516 def run_generated_dispatch(
517 self,
518 target: object,
519 internal_dispatch: _TraverseInternalsType,
520 generate_dispatcher_name: str,
521 ) -> Any:
522 dispatcher: _InternalTraversalDispatchType
523 try:
524 dispatcher = target.__class__.__dict__[generate_dispatcher_name]
525 except KeyError:
526 # traversals.py -> _preconfigure_traversals()
527 # may be used to run these ahead of time, but
528 # is not enabled right now.
529 # this block will generate any remaining dispatchers.
530 dispatcher = self.generate_dispatch(
531 target.__class__, internal_dispatch, generate_dispatcher_name
532 )
533 return dispatcher(target, self)
535 def generate_dispatch(
536 self,
537 target_cls: Type[object],
538 internal_dispatch: _TraverseInternalsType,
539 generate_dispatcher_name: str,
540 ) -> _InternalTraversalDispatchType:
541 dispatcher = self._generate_dispatcher(
542 internal_dispatch, generate_dispatcher_name
543 )
544 # assert isinstance(target_cls, type)
545 setattr(target_cls, generate_dispatcher_name, dispatcher)
546 return dispatcher
548 def _generate_dispatcher(
549 self, internal_dispatch: _TraverseInternalsType, method_name: str
550 ) -> _InternalTraversalDispatchType:
551 names = []
552 for attrname, visit_sym in internal_dispatch:
553 meth = self.dispatch(visit_sym)
554 if meth is not None:
555 visit_name = _dispatch_lookup[visit_sym]
556 names.append((attrname, visit_name))
558 code = (
559 (" return [\n")
560 + (
561 ", \n".join(
562 " (%r, self.%s, visitor.%s)"
563 % (attrname, attrname, visit_name)
564 for attrname, visit_name in names
565 )
566 )
567 + ("\n ]\n")
568 )
569 meth_text = ("def %s(self, visitor):\n" % method_name) + code + "\n"
570 return cast(
571 _InternalTraversalDispatchType,
572 langhelpers._exec_code_in_env(meth_text, {}, method_name),
573 )
576ExtendedInternalTraversal = InternalTraversal
579def _generate_traversal_dispatch() -> None:
580 lookup = _dispatch_lookup
582 for sym in InternalTraversal:
583 key = sym.name
584 if key.startswith("dp_"):
585 visit_key = key.replace("dp_", "visit_")
586 sym_name = sym.value
587 assert sym_name not in lookup, sym_name
588 lookup[sym] = lookup[sym_name] = visit_key
591_dispatch_lookup = HasTraversalDispatch._dispatch_lookup
592_generate_traversal_dispatch()
595class ExternallyTraversible(HasTraverseInternals, Visitable):
596 __slots__ = ()
598 _annotations: Mapping[Any, Any] = util.EMPTY_DICT
600 if typing.TYPE_CHECKING:
602 def _annotate(self, values: _AnnotationDict) -> Self: ...
604 def get_children(
605 self, *, omit_attrs: Tuple[str, ...] = (), **kw: Any
606 ) -> Iterable[ExternallyTraversible]: ...
608 def _clone(self, **kw: Any) -> Self:
609 """clone this element"""
610 raise NotImplementedError()
612 def _copy_internals(
613 self, *, omit_attrs: Tuple[str, ...] = (), **kw: Any
614 ) -> None:
615 """Reassign internal elements to be clones of themselves.
617 Called during a copy-and-traverse operation on newly
618 shallow-copied elements to create a deep copy.
620 The given clone function should be used, which may be applying
621 additional transformations to the element (i.e. replacement
622 traversal, cloned traversal, annotations).
624 """
625 raise NotImplementedError()
628_ET = TypeVar("_ET", bound=ExternallyTraversible)
630_CE = TypeVar("_CE", bound="ColumnElement[Any]")
632_TraverseCallableType = Callable[[_ET], None]
635class _CloneCallableType(Protocol):
636 def __call__(self, element: _ET, **kw: Any) -> _ET: ...
639class _TraverseTransformCallableType(Protocol[_ET]):
640 def __call__(self, element: _ET, **kw: Any) -> Optional[_ET]: ...
643_ExtT = TypeVar("_ExtT", bound="ExternalTraversal")
646class ExternalTraversal(util.MemoizedSlots):
647 """Base class for visitor objects which can traverse externally using
648 the :func:`.visitors.traverse` function.
650 Direct usage of the :func:`.visitors.traverse` function is usually
651 preferred.
653 """
655 __slots__ = ("_visitor_dict", "_next")
657 __traverse_options__: Dict[str, Any] = {}
658 _next: Optional[ExternalTraversal]
660 def traverse_single(self, obj: Visitable, **kw: Any) -> Any:
661 for v in self.visitor_iterator:
662 meth = getattr(v, "visit_%s" % obj.__visit_name__, None)
663 if meth:
664 return meth(obj, **kw)
666 def iterate(
667 self, obj: Optional[ExternallyTraversible]
668 ) -> Iterator[ExternallyTraversible]:
669 """Traverse the given expression structure, returning an iterator
670 of all elements.
672 """
673 return iterate(obj, self.__traverse_options__)
675 @overload
676 def traverse(self, obj: Literal[None]) -> None: ...
678 @overload
679 def traverse(
680 self, obj: ExternallyTraversible
681 ) -> ExternallyTraversible: ...
683 def traverse(
684 self, obj: Optional[ExternallyTraversible]
685 ) -> Optional[ExternallyTraversible]:
686 """Traverse and visit the given expression structure."""
688 return traverse(obj, self.__traverse_options__, self._visitor_dict)
690 def _memoized_attr__visitor_dict(
691 self,
692 ) -> Dict[str, _TraverseCallableType[Any]]:
693 visitors = {}
695 for name in dir(self):
696 if name.startswith("visit_"):
697 visitors[name[6:]] = getattr(self, name)
698 return visitors
700 @property
701 def visitor_iterator(self) -> Iterator[ExternalTraversal]:
702 """Iterate through this visitor and each 'chained' visitor."""
704 v: Optional[ExternalTraversal] = self
705 while v:
706 yield v
707 v = getattr(v, "_next", None)
709 def chain(self: _ExtT, visitor: ExternalTraversal) -> _ExtT:
710 """'Chain' an additional ExternalTraversal onto this ExternalTraversal
712 The chained visitor will receive all visit events after this one.
714 """
715 tail = list(self.visitor_iterator)[-1]
716 tail._next = visitor
717 return self
720class CloningExternalTraversal(ExternalTraversal):
721 """Base class for visitor objects which can traverse using
722 the :func:`.visitors.cloned_traverse` function.
724 Direct usage of the :func:`.visitors.cloned_traverse` function is usually
725 preferred.
728 """
730 __slots__ = ()
732 def copy_and_process(
733 self, list_: List[ExternallyTraversible]
734 ) -> List[ExternallyTraversible]:
735 """Apply cloned traversal to the given list of elements, and return
736 the new list.
738 """
739 return [self.traverse(x) for x in list_]
741 @overload
742 def traverse(self, obj: Literal[None]) -> None: ...
744 @overload
745 def traverse(
746 self, obj: ExternallyTraversible
747 ) -> ExternallyTraversible: ...
749 def traverse(
750 self, obj: Optional[ExternallyTraversible]
751 ) -> Optional[ExternallyTraversible]:
752 """Traverse and visit the given expression structure."""
754 return cloned_traverse(
755 obj, self.__traverse_options__, self._visitor_dict
756 )
759class ReplacingExternalTraversal(CloningExternalTraversal):
760 """Base class for visitor objects which can traverse using
761 the :func:`.visitors.replacement_traverse` function.
763 Direct usage of the :func:`.visitors.replacement_traverse` function is
764 usually preferred.
766 """
768 __slots__ = ()
770 def replace(
771 self, elem: ExternallyTraversible
772 ) -> Optional[ExternallyTraversible]:
773 """Receive pre-copied elements during a cloning traversal.
775 If the method returns a new element, the element is used
776 instead of creating a simple copy of the element. Traversal
777 will halt on the newly returned element if it is re-encountered.
778 """
779 return None
781 @overload
782 def traverse(self, obj: Literal[None]) -> None: ...
784 @overload
785 def traverse(
786 self, obj: ExternallyTraversible
787 ) -> ExternallyTraversible: ...
789 def traverse(
790 self, obj: Optional[ExternallyTraversible]
791 ) -> Optional[ExternallyTraversible]:
792 """Traverse and visit the given expression structure."""
794 def replace(
795 element: ExternallyTraversible,
796 **kw: Any,
797 ) -> Optional[ExternallyTraversible]:
798 for v in self.visitor_iterator:
799 e = cast(ReplacingExternalTraversal, v).replace(element)
800 if e is not None:
801 return e
803 return None
805 return replacement_traverse(obj, self.__traverse_options__, replace)
808# backwards compatibility
809Traversible = Visitable
811ClauseVisitor = ExternalTraversal
812CloningVisitor = CloningExternalTraversal
813ReplacingCloningVisitor = ReplacingExternalTraversal
816def iterate(
817 obj: Optional[ExternallyTraversible],
818 opts: Mapping[str, Any] = util.EMPTY_DICT,
819) -> Iterator[ExternallyTraversible]:
820 r"""Traverse the given expression structure, returning an iterator.
822 Traversal is configured to be breadth-first.
824 The central API feature used by the :func:`.visitors.iterate`
825 function is the
826 :meth:`_expression.ClauseElement.get_children` method of
827 :class:`_expression.ClauseElement` objects. This method should return all
828 the :class:`_expression.ClauseElement` objects which are associated with a
829 particular :class:`_expression.ClauseElement` object. For example, a
830 :class:`.Case` structure will refer to a series of
831 :class:`_expression.ColumnElement` objects within its "whens" and "else\_"
832 member variables.
834 :param obj: :class:`_expression.ClauseElement` structure to be traversed
836 :param opts: dictionary of iteration options. This dictionary is usually
837 empty in modern usage.
839 """
840 if obj is None:
841 return
843 yield obj
844 children = obj.get_children(**opts)
846 if not children:
847 return
849 stack = deque([children])
850 while stack:
851 t_iterator = stack.popleft()
852 for t in t_iterator:
853 yield t
854 stack.append(t.get_children(**opts))
857@overload
858def traverse_using(
859 iterator: Iterable[ExternallyTraversible],
860 obj: Literal[None],
861 visitors: Mapping[str, _TraverseCallableType[Any]],
862) -> None: ...
865@overload
866def traverse_using(
867 iterator: Iterable[ExternallyTraversible],
868 obj: ExternallyTraversible,
869 visitors: Mapping[str, _TraverseCallableType[Any]],
870) -> ExternallyTraversible: ...
873def traverse_using(
874 iterator: Iterable[ExternallyTraversible],
875 obj: Optional[ExternallyTraversible],
876 visitors: Mapping[str, _TraverseCallableType[Any]],
877) -> Optional[ExternallyTraversible]:
878 """Visit the given expression structure using the given iterator of
879 objects.
881 :func:`.visitors.traverse_using` is usually called internally as the result
882 of the :func:`.visitors.traverse` function.
884 :param iterator: an iterable or sequence which will yield
885 :class:`_expression.ClauseElement`
886 structures; the iterator is assumed to be the
887 product of the :func:`.visitors.iterate` function.
889 :param obj: the :class:`_expression.ClauseElement`
890 that was used as the target of the
891 :func:`.iterate` function.
893 :param visitors: dictionary of visit functions. See :func:`.traverse`
894 for details on this dictionary.
896 .. seealso::
898 :func:`.traverse`
901 """
902 for target in iterator:
903 meth = visitors.get(target.__visit_name__, None)
904 if meth:
905 meth(target)
906 return obj
909@overload
910def traverse(
911 obj: Literal[None],
912 opts: Mapping[str, Any],
913 visitors: Mapping[str, _TraverseCallableType[Any]],
914) -> None: ...
917@overload
918def traverse(
919 obj: ExternallyTraversible,
920 opts: Mapping[str, Any],
921 visitors: Mapping[str, _TraverseCallableType[Any]],
922) -> ExternallyTraversible: ...
925def traverse(
926 obj: Optional[ExternallyTraversible],
927 opts: Mapping[str, Any],
928 visitors: Mapping[str, _TraverseCallableType[Any]],
929) -> Optional[ExternallyTraversible]:
930 """Traverse and visit the given expression structure using the default
931 iterator.
933 e.g.::
935 from sqlalchemy.sql import visitors
937 stmt = select(some_table).where(some_table.c.foo == "bar")
940 def visit_bindparam(bind_param):
941 print("found bound value: %s" % bind_param.value)
944 visitors.traverse(stmt, {}, {"bindparam": visit_bindparam})
946 The iteration of objects uses the :func:`.visitors.iterate` function,
947 which does a breadth-first traversal using a stack.
949 :param obj: :class:`_expression.ClauseElement` structure to be traversed
951 :param opts: dictionary of iteration options. This dictionary is usually
952 empty in modern usage.
954 :param visitors: dictionary of visit functions. The dictionary should
955 have strings as keys, each of which would correspond to the
956 ``__visit_name__`` of a particular kind of SQL expression object, and
957 callable functions as values, each of which represents a visitor function
958 for that kind of object.
960 """
961 return traverse_using(iterate(obj, opts), obj, visitors)
964@overload
965def cloned_traverse(
966 obj: Literal[None],
967 opts: Mapping[str, Any],
968 visitors: Mapping[str, _TraverseCallableType[Any]],
969) -> None: ...
972# a bit of controversy here, as the clone of the lead element
973# *could* in theory replace with an entirely different kind of element.
974# however this is really not how cloned_traverse is ever used internally
975# at least.
976@overload
977def cloned_traverse(
978 obj: _ET,
979 opts: Mapping[str, Any],
980 visitors: Mapping[str, _TraverseCallableType[Any]],
981) -> _ET: ...
984def cloned_traverse(
985 obj: Optional[ExternallyTraversible],
986 opts: Mapping[str, Any],
987 visitors: Mapping[str, _TraverseCallableType[Any]],
988) -> Optional[ExternallyTraversible]:
989 """Clone the given expression structure, allowing modifications by
990 visitors for mutable objects.
992 Traversal usage is the same as that of :func:`.visitors.traverse`.
993 The visitor functions present in the ``visitors`` dictionary may also
994 modify the internals of the given structure as the traversal proceeds.
996 The :func:`.cloned_traverse` function does **not** provide objects that are
997 part of the :class:`.Immutable` interface to the visit methods (this
998 primarily includes :class:`.ColumnClause`, :class:`.Column`,
999 :class:`.TableClause` and :class:`.Table` objects). As this traversal is
1000 only intended to allow in-place mutation of objects, :class:`.Immutable`
1001 objects are skipped. The :meth:`.Immutable._clone` method is still called
1002 on each object to allow for objects to replace themselves with a different
1003 object based on a clone of their sub-internals (e.g. a
1004 :class:`.ColumnClause` that clones its subquery to return a new
1005 :class:`.ColumnClause`).
1007 .. versionchanged:: 2.0 The :func:`.cloned_traverse` function omits
1008 objects that are part of the :class:`.Immutable` interface.
1010 The central API feature used by the :func:`.visitors.cloned_traverse`
1011 and :func:`.visitors.replacement_traverse` functions, in addition to the
1012 :meth:`_expression.ClauseElement.get_children`
1013 function that is used to achieve
1014 the iteration, is the :meth:`_expression.ClauseElement._copy_internals`
1015 method.
1016 For a :class:`_expression.ClauseElement`
1017 structure to support cloning and replacement
1018 traversals correctly, it needs to be able to pass a cloning function into
1019 its internal members in order to make copies of them.
1021 .. seealso::
1023 :func:`.visitors.traverse`
1025 :func:`.visitors.replacement_traverse`
1027 """
1029 cloned: Dict[int, ExternallyTraversible] = {}
1030 stop_on = set(opts.get("stop_on", []))
1032 def deferred_copy_internals(
1033 obj: ExternallyTraversible,
1034 ) -> ExternallyTraversible:
1035 return cloned_traverse(obj, opts, visitors)
1037 def clone(elem: ExternallyTraversible, **kw: Any) -> ExternallyTraversible:
1038 if elem in stop_on:
1039 return elem
1040 else:
1041 if id(elem) not in cloned:
1042 if "replace" in kw:
1043 newelem = cast(
1044 Optional[ExternallyTraversible], kw["replace"](elem)
1045 )
1046 if newelem is not None:
1047 cloned[id(elem)] = newelem
1048 return newelem
1050 # the _clone method for immutable normally returns "self".
1051 # however, the method is still allowed to return a
1052 # different object altogether; ColumnClause._clone() will
1053 # based on options clone the subquery to which it is associated
1054 # and return the new corresponding column.
1055 cloned[id(elem)] = newelem = elem._clone(clone=clone, **kw)
1056 newelem._copy_internals(clone=clone, **kw)
1058 # however, visit methods which are tasked with in-place
1059 # mutation of the object should not get access to the immutable
1060 # object.
1061 if not elem._is_immutable:
1062 meth = visitors.get(newelem.__visit_name__, None)
1063 if meth:
1064 meth(newelem)
1065 return cloned[id(elem)]
1067 if obj is not None:
1068 obj = clone(
1069 obj, deferred_copy_internals=deferred_copy_internals, **opts
1070 )
1071 clone = None # type: ignore[assignment] # remove gc cycles
1072 return obj
1075@overload
1076def replacement_traverse(
1077 obj: Literal[None],
1078 opts: Mapping[str, Any],
1079 replace: _TraverseTransformCallableType[Any],
1080) -> None: ...
1083@overload
1084def replacement_traverse(
1085 obj: _CE,
1086 opts: Mapping[str, Any],
1087 replace: _TraverseTransformCallableType[Any],
1088) -> _CE: ...
1091@overload
1092def replacement_traverse(
1093 obj: ExternallyTraversible,
1094 opts: Mapping[str, Any],
1095 replace: _TraverseTransformCallableType[Any],
1096) -> ExternallyTraversible: ...
1099def replacement_traverse(
1100 obj: Optional[ExternallyTraversible],
1101 opts: Mapping[str, Any],
1102 replace: _TraverseTransformCallableType[Any],
1103) -> Optional[ExternallyTraversible]:
1104 """Clone the given expression structure, allowing element
1105 replacement by a given replacement function.
1107 This function is very similar to the :func:`.visitors.cloned_traverse`
1108 function, except instead of being passed a dictionary of visitors, all
1109 elements are unconditionally passed into the given replace function.
1110 The replace function then has the option to return an entirely new object
1111 which will replace the one given. If it returns ``None``, then the object
1112 is kept in place.
1114 The difference in usage between :func:`.visitors.cloned_traverse` and
1115 :func:`.visitors.replacement_traverse` is that in the former case, an
1116 already-cloned object is passed to the visitor function, and the visitor
1117 function can then manipulate the internal state of the object.
1118 In the case of the latter, the visitor function should only return an
1119 entirely different object, or do nothing.
1121 The use case for :func:`.visitors.replacement_traverse` is that of
1122 replacing a FROM clause inside of a SQL structure with a different one,
1123 as is a common use case within the ORM.
1125 """
1127 cloned = {}
1128 stop_on = {id(x) for x in opts.get("stop_on", [])}
1130 def deferred_copy_internals(
1131 obj: ExternallyTraversible,
1132 ) -> ExternallyTraversible:
1133 return replacement_traverse(obj, opts, replace)
1135 def clone(elem: ExternallyTraversible, **kw: Any) -> ExternallyTraversible:
1136 if (
1137 id(elem) in stop_on
1138 or "no_replacement_traverse" in elem._annotations
1139 ):
1140 return elem
1141 else:
1142 newelem = replace(elem)
1143 if newelem is not None:
1144 stop_on.add(id(newelem))
1145 return newelem # type: ignore
1146 else:
1147 # base "already seen" on id(), not hash, so that we don't
1148 # replace an Annotated element with its non-annotated one, and
1149 # vice versa
1150 id_elem = id(elem)
1151 if id_elem not in cloned:
1152 if "replace" in kw:
1153 newelem = kw["replace"](elem)
1154 if newelem is not None:
1155 cloned[id_elem] = newelem
1156 return newelem # type: ignore
1158 cloned[id_elem] = newelem = elem._clone(**kw)
1159 newelem._copy_internals(clone=clone, **kw)
1160 return cloned[id_elem] # type: ignore
1162 if obj is not None:
1163 obj = clone(
1164 obj, deferred_copy_internals=deferred_copy_internals, **opts
1165 )
1166 clone = None # type: ignore[assignment] # remove gc cycles
1167 return obj