Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/lark/visitors.py: 70%
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
1from typing import TypeVar, Tuple, List, Callable, Generic, Type, Union, Optional, Any, cast
2from abc import ABC
4from .utils import combine_alternatives
5from .tree import Tree, Branch
6from .exceptions import VisitError, GrammarError
7from .lexer import Token
9###{standalone
10from functools import wraps, update_wrapper
11from inspect import getmembers, getmro
13_Return_T = TypeVar('_Return_T')
14_Return_V = TypeVar('_Return_V')
15_Leaf_T = TypeVar('_Leaf_T')
16_Leaf_U = TypeVar('_Leaf_U')
17_R = TypeVar('_R')
18_DECORATED = Union[Callable[..., _Return_T], Type[_Return_T]]
19_DECORATOR = Callable[[_DECORATED[_Return_T]], _DECORATED[_Return_T]]
21class _DiscardType:
22 """When the Discard value is returned from a transformer callback,
23 that node is discarded and won't appear in the parent.
25 Note:
26 This feature is disabled when the transformer is provided to Lark
27 using the ``transformer`` keyword (aka Tree-less LALR mode).
29 Example:
30 ::
32 class T(Transformer):
33 def ignore_tree(self, children):
34 return Discard
36 def IGNORE_TOKEN(self, token):
37 return Discard
38 """
40 def __repr__(self):
41 return "lark.visitors.Discard"
43Discard = _DiscardType()
45# Transformers
47class _Decoratable:
48 "Provides support for decorating methods with @v_args"
50 @classmethod
51 def _apply_v_args(cls, visit_wrapper):
52 mro = getmro(cls)
53 assert mro[0] is cls
54 libmembers = {name for _cls in mro[1:] for name, _ in getmembers(_cls)}
55 for name, value in getmembers(cls):
57 # Make sure the function isn't inherited (unless it's overwritten)
58 if name.startswith('_') or (name in libmembers and name not in cls.__dict__):
59 continue
60 if not callable(value):
61 continue
63 # Skip if v_args already applied (at the function level)
64 if isinstance(cls.__dict__[name], _VArgsWrapper):
65 continue
67 setattr(cls, name, _VArgsWrapper(cls.__dict__[name], visit_wrapper))
68 return cls
70 def __class_getitem__(cls, _):
71 return cls
74class Transformer(_Decoratable, ABC, Generic[_Leaf_T, _Return_T]):
75 """Transformers work bottom-up (or depth-first), starting with visiting the leaves and working
76 their way up until ending at the root of the tree.
78 For each node visited, the transformer will call the appropriate method (callbacks), according to the
79 node's ``data``, and use the returned value to replace the node, thereby creating a new tree structure.
81 Transformers can be used to implement map & reduce patterns. Because nodes are reduced from leaf to root,
82 at any point the callbacks may assume the children have already been transformed (if applicable).
84 If the transformer cannot find a method with the right name, it will instead call ``__default__``, which by
85 default creates a copy of the node.
87 To discard a node, return Discard (``lark.visitors.Discard``).
89 ``Transformer`` can do anything ``Visitor`` can do, but because it reconstructs the tree,
90 it is slightly less efficient.
92 A transformer without methods essentially performs a non-memoized partial deepcopy.
94 All these classes implement the transformer interface:
96 - ``Transformer`` - Recursively transforms the tree. This is the one you probably want.
97 - ``Transformer_InPlace`` - Non-recursive. Changes the tree in-place instead of returning new instances
98 - ``Transformer_InPlaceRecursive`` - Recursive. Changes the tree in-place instead of returning new instances
100 Parameters:
101 visit_tokens (bool, optional): Should the transformer visit tokens in addition to rules.
102 Setting this to ``False`` is slightly faster. Defaults to ``True``.
103 (For processing ignored tokens, use the ``lexer_callbacks`` options)
105 """
106 __visit_tokens__ = True # For backwards compatibility
108 def __init__(self, visit_tokens: bool=True) -> None:
109 self.__visit_tokens__ = visit_tokens
111 def _call_userfunc(self, tree, new_children=None):
112 # Assumes tree is already transformed
113 children = new_children if new_children is not None else tree.children
114 try:
115 f = getattr(self, tree.data)
116 except AttributeError:
117 return self.__default__(tree.data, children, tree.meta)
118 else:
119 try:
120 wrapper = getattr(f, 'visit_wrapper', None)
121 if wrapper is not None:
122 return f.visit_wrapper(f, tree.data, children, tree.meta)
123 else:
124 return f(children)
125 except GrammarError:
126 raise
127 except Exception as e:
128 raise VisitError(tree.data, tree, e)
130 def _call_userfunc_token(self, token):
131 try:
132 f = getattr(self, token.type)
133 except AttributeError:
134 return self.__default_token__(token)
135 else:
136 try:
137 return f(token)
138 except GrammarError:
139 raise
140 except Exception as e:
141 raise VisitError(token.type, token, e)
143 def _transform_children(self, children):
144 for c in children:
145 if isinstance(c, Tree):
146 res = self._transform_tree(c)
147 elif self.__visit_tokens__ and isinstance(c, Token):
148 res = self._call_userfunc_token(c)
149 else:
150 res = c
152 if res is not Discard:
153 yield res
155 def _transform_tree(self, tree):
156 children = list(self._transform_children(tree.children))
157 return self._call_userfunc(tree, children)
159 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T:
160 "Transform the given tree, and return the final result"
161 res = list(self._transform_children([tree]))
162 if not res:
163 return None # type: ignore[return-value]
164 assert len(res) == 1
165 return res[0]
167 def __mul__(
168 self: 'Transformer[_Leaf_T, Tree[_Leaf_U]]',
169 other: 'Union[Transformer[_Leaf_U, _Return_V], TransformerChain[_Leaf_U, _Return_V,]]'
170 ) -> 'TransformerChain[_Leaf_T, _Return_V]':
171 """Chain two transformers together, returning a new transformer.
172 """
173 return TransformerChain(self, other)
175 def __default__(self, data, children, meta):
176 """Default function that is called if there is no attribute matching ``data``
178 Can be overridden. Defaults to creating a new copy of the tree node (i.e. ``return Tree(data, children, meta)``)
179 """
180 return Tree(data, children, meta)
182 def __default_token__(self, token):
183 """Default function that is called if there is no attribute matching ``token.type``
185 Can be overridden. Defaults to returning the token as-is.
186 """
187 return token
190def merge_transformers(base_transformer=None, **transformers_to_merge):
191 """Merge a collection of transformers into the base_transformer, each into its own 'namespace'.
193 When called, it will collect the methods from each transformer, and assign them to base_transformer,
194 with their name prefixed with the given keyword, as ``prefix__methodname``.
196 This function is especially useful for processing grammars that import other grammars,
197 thereby creating some of their rules in a 'namespace'. (i.e with a consistent name prefix).
198 In this case, the key for the transformer should match the name of the imported grammar.
200 Parameters:
201 base_transformer (Transformer, optional): The transformer that all other transformers will be added to.
202 **transformers_to_merge: Keyword arguments, in the form of ``name_prefix = transformer``.
204 Raises:
205 AttributeError: In case of a name collision in the merged methods
207 Example:
208 ::
210 class TBase(Transformer):
211 def start(self, children):
212 return children[0] + 'bar'
214 class TImportedGrammar(Transformer):
215 def foo(self, children):
216 return "foo"
218 composed_transformer = merge_transformers(TBase(), imported=TImportedGrammar())
220 t = Tree('start', [ Tree('imported__foo', []) ])
222 assert composed_transformer.transform(t) == 'foobar'
224 """
225 if base_transformer is None:
226 base_transformer = Transformer()
227 for prefix, transformer in transformers_to_merge.items():
228 for method_name in dir(transformer):
229 method = getattr(transformer, method_name)
230 if not callable(method):
231 continue
232 if method_name.startswith("_") or method_name == "transform":
233 continue
234 prefixed_method = prefix + "__" + method_name
235 if hasattr(base_transformer, prefixed_method):
236 raise AttributeError("Cannot merge: method '%s' appears more than once" % prefixed_method)
238 setattr(base_transformer, prefixed_method, method)
240 return base_transformer
243class InlineTransformer(Transformer): # XXX Deprecated
244 def _call_userfunc(self, tree, new_children=None):
245 # Assumes tree is already transformed
246 children = new_children if new_children is not None else tree.children
247 try:
248 f = getattr(self, tree.data)
249 except AttributeError:
250 return self.__default__(tree.data, children, tree.meta)
251 else:
252 return f(*children)
255class TransformerChain(Generic[_Leaf_T, _Return_T]):
257 transformers: 'Tuple[Union[Transformer, TransformerChain], ...]'
259 def __init__(self, *transformers: 'Union[Transformer, TransformerChain]') -> None:
260 self.transformers = transformers
262 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T:
263 for t in self.transformers:
264 tree = t.transform(tree)
265 return cast(_Return_T, tree)
267 def __mul__(
268 self: 'TransformerChain[_Leaf_T, Tree[_Leaf_U]]',
269 other: 'Union[Transformer[_Leaf_U, _Return_V], TransformerChain[_Leaf_U, _Return_V]]'
270 ) -> 'TransformerChain[_Leaf_T, _Return_V]':
271 return TransformerChain(*self.transformers + (other,))
274class Transformer_InPlace(Transformer[_Leaf_T, _Return_T]):
275 """Same as Transformer, but non-recursive, and changes the tree in-place instead of returning new instances
277 Useful for huge trees. Conservative in memory.
278 """
279 def _transform_tree(self, tree): # Cancel recursion
280 return self._call_userfunc(tree)
282 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T:
283 for subtree in tree.iter_subtrees():
284 subtree.children = list(self._transform_children(subtree.children))
286 return self._transform_tree(tree)
289class Transformer_NonRecursive(Transformer[_Leaf_T, _Return_T]):
290 """Same as Transformer but non-recursive.
292 Like Transformer, it doesn't change the original tree.
294 Useful for huge trees.
295 """
297 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T:
298 # Tree to postfix
299 rev_postfix = []
300 q: List[Branch[_Leaf_T]] = [tree]
301 while q:
302 t = q.pop()
303 rev_postfix.append(t)
304 if isinstance(t, Tree):
305 q += t.children
307 # Postfix to tree
308 stack: List = []
309 for x in reversed(rev_postfix):
310 if isinstance(x, Tree):
311 size = len(x.children)
312 if size:
313 args = stack[-size:]
314 del stack[-size:]
315 else:
316 args = []
318 res = self._call_userfunc(x, args)
319 if res is not Discard:
320 stack.append(res)
322 elif self.__visit_tokens__ and isinstance(x, Token):
323 res = self._call_userfunc_token(x)
324 if res is not Discard:
325 stack.append(res)
326 else:
327 stack.append(x)
329 result, = stack # We should have only one tree remaining
330 # There are no guarantees on the type of the value produced by calling a user func for a
331 # child will produce. This means type system can't statically know that the final result is
332 # _Return_T. As a result a cast is required.
333 return cast(_Return_T, result)
336class Transformer_InPlaceRecursive(Transformer[_Leaf_T, _Return_T]):
337 "Same as Transformer, recursive, but changes the tree in-place instead of returning new instances"
338 def _transform_tree(self, tree):
339 tree.children = list(self._transform_children(tree.children))
340 return self._call_userfunc(tree)
343# Visitors
345class VisitorBase:
346 def _call_userfunc(self, tree):
347 return getattr(self, tree.data, self.__default__)(tree)
349 def __default__(self, tree):
350 """Default function that is called if there is no attribute matching ``tree.data``
352 Can be overridden. Defaults to doing nothing.
353 """
354 return tree
356 def __class_getitem__(cls, _):
357 return cls
360class Visitor(VisitorBase, ABC, Generic[_Leaf_T]):
361 """Tree visitor, non-recursive (can handle huge trees).
363 Visiting a node calls its methods (provided by the user via inheritance) according to ``tree.data``
364 """
366 def visit(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
367 "Visits the tree, starting with the leaves and finally the root (bottom-up)"
368 for subtree in tree.iter_subtrees():
369 self._call_userfunc(subtree)
370 return tree
372 def visit_topdown(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
373 "Visit the tree, starting at the root, and ending at the leaves (top-down)"
374 for subtree in tree.iter_subtrees_topdown():
375 self._call_userfunc(subtree)
376 return tree
379class Visitor_Recursive(VisitorBase, Generic[_Leaf_T]):
380 """Bottom-up visitor, recursive.
382 Visiting a node calls its methods (provided by the user via inheritance) according to ``tree.data``
384 Slightly faster than the non-recursive version.
385 """
387 def visit(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
388 "Visits the tree, starting with the leaves and finally the root (bottom-up)"
389 for child in tree.children:
390 if isinstance(child, Tree):
391 self.visit(child)
393 self._call_userfunc(tree)
394 return tree
396 def visit_topdown(self,tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
397 "Visit the tree, starting at the root, and ending at the leaves (top-down)"
398 self._call_userfunc(tree)
400 for child in tree.children:
401 if isinstance(child, Tree):
402 self.visit_topdown(child)
404 return tree
407class Interpreter(_Decoratable, ABC, Generic[_Leaf_T, _Return_T]):
408 """Interpreter walks the tree starting at the root.
410 Visits the tree, starting with the root and finally the leaves (top-down)
412 For each tree node, it calls its methods (provided by user via inheritance) according to ``tree.data``.
414 Unlike ``Transformer`` and ``Visitor``, the Interpreter doesn't automatically visit its sub-branches.
415 The user has to explicitly call ``visit``, ``visit_children``, or use the ``@visit_children_decor``.
416 This allows the user to implement branching and loops.
417 """
419 def visit(self, tree: Tree[_Leaf_T]) -> _Return_T:
420 "Visit the tree, starting with the root and finally the leaves (top-down)."
421 # There are no guarantees on the type of the value produced by calling a user func for a
422 # child will produce. So only annotate the public method and use an internal method when
423 # visiting child trees.
424 return self._visit_tree(tree)
426 def _visit_tree(self, tree: Tree[_Leaf_T]):
427 f = getattr(self, tree.data)
428 wrapper = getattr(f, 'visit_wrapper', None)
429 if wrapper is not None:
430 return f.visit_wrapper(f, tree.data, tree.children, tree.meta)
431 else:
432 return f(tree)
434 def visit_children(self, tree: Tree[_Leaf_T]) -> List:
435 "Visit all the children of this tree and return the results as a list."
436 return [
437 self._visit_tree(child)
438 if isinstance(child, Tree)
439 else child
440 for child in tree.children
441 ]
443 def __getattr__(self, name):
444 return self.__default__
446 def __default__(self, tree):
447 """
448 Default function that is called if there is no attribute matching ``tree.data``.
450 Can be overridden. Defaults to visiting all the tree's children.
451 """
452 return self.visit_children(tree)
455_InterMethod = Callable[[Type[Interpreter], _Return_T], _R]
457def visit_children_decor(func: _InterMethod) -> _InterMethod:
458 """
459 A wrapper around Interpreter methods. It makes the wrapped node method automatically visit the
460 node's children before proceeding with the logic you have defined for that node.
462 Example:
463 ::
465 class ProcessQuery(Interpreter):
466 @visit_children_decor
467 def query(self, tree):
468 pass
469 """
470 @wraps(func)
471 def inner(cls, tree):
472 if not isinstance(cls, Interpreter):
473 raise TypeError("visit_children_decor can only be applied to Interpreter methods.")
474 values = cls.visit_children(tree)
475 return func(cls, values)
476 return inner
478# Decorators
480def _apply_v_args(obj, visit_wrapper):
481 try:
482 _apply = obj._apply_v_args
483 except AttributeError:
484 return _VArgsWrapper(obj, visit_wrapper)
485 else:
486 return _apply(visit_wrapper)
489class _VArgsWrapper:
490 """
491 A wrapper around a Callable. It delegates `__call__` to the Callable.
492 If the Callable has a `__get__`, that is also delegate and the resulting function is wrapped.
493 Otherwise, we use the original function mirroring the behaviour without a __get__.
494 We also have the visit_wrapper attribute to be used by Transformers.
495 """
496 base_func: Callable
498 def __init__(self, func: Callable, visit_wrapper: Callable[[Callable, str, list, Any], Any]):
499 if isinstance(func, _VArgsWrapper):
500 func = func.base_func
501 self.base_func = func
502 self.visit_wrapper = visit_wrapper
503 update_wrapper(self, func)
505 def __call__(self, *args, **kwargs):
506 return self.base_func(*args, **kwargs)
508 def __get__(self, instance, owner=None):
509 try:
510 # Use the __get__ attribute of the type instead of the instance
511 # to fully mirror the behavior of getattr
512 g = type(self.base_func).__get__
513 except AttributeError:
514 return self
515 else:
516 return _VArgsWrapper(g(self.base_func, instance, owner), self.visit_wrapper)
518 def __set_name__(self, owner, name):
519 try:
520 f = type(self.base_func).__set_name__
521 except AttributeError:
522 return
523 else:
524 f(self.base_func, owner, name)
527def _vargs_inline(f, _data, children, _meta):
528 return f(*children)
529def _vargs_meta_inline(f, _data, children, meta):
530 return f(meta, *children)
531def _vargs_meta(f, _data, children, meta):
532 return f(meta, children)
533def _vargs_tree(f, data, children, meta):
534 return f(Tree(data, children, meta))
537def v_args(inline: bool = False, meta: bool = False, tree: bool = False, wrapper: Optional[Callable] = None) -> _DECORATOR:
538 """A convenience decorator factory for modifying the behavior of user-supplied callback methods
539 of ``Transformer`` or ``Interpreter`` classes.
541 By default, the callback methods for these classes accept one argument - a list of the node's children.
543 ``v_args`` can modify this behavior. When used on the class definition, it applies to
544 all the callback methods inside it.
546 ``v_args`` can be applied to a single method, or to an entire class. When applied to both,
547 the options given to the method take precedence.
549 Parameters:
550 inline (bool, optional): Children are provided as ``*args`` instead of a list argument (not recommended for very long lists).
551 meta (bool, optional): Provides two arguments: ``meta`` and ``children`` (instead of just the latter); ``meta`` isn't available for transformers supplied to Lark using the ``transformer`` parameter (aka internal transformers).
552 tree (bool, optional): Provides the entire tree as the argument, instead of the children.
553 wrapper (function, optional): Provide a function to decorate all methods.
555 Example:
556 ::
558 @v_args(inline=True)
559 class SolveArith(Transformer):
560 def add(self, left, right):
561 return left + right
563 @v_args(meta=True)
564 def mul(self, meta, children):
565 logger.info(f'mul at line {meta.line}')
566 left, right = children
567 return left * right
570 class ReverseNotation(Transformer_InPlace):
571 @v_args(tree=True)
572 def tree_node(self, tree):
573 tree.children = tree.children[::-1]
574 """
575 if tree and (meta or inline):
576 raise ValueError("Visitor functions cannot combine 'tree' with 'meta' or 'inline'.")
578 func = None
579 if meta:
580 if inline:
581 func = _vargs_meta_inline
582 else:
583 func = _vargs_meta
584 elif inline:
585 func = _vargs_inline
586 elif tree:
587 func = _vargs_tree
589 if wrapper is not None:
590 if func is not None:
591 raise ValueError("Cannot use 'wrapper' along with 'tree', 'meta' or 'inline'.")
592 func = wrapper
594 def _visitor_args_dec(obj):
595 return _apply_v_args(obj, func)
596 return _visitor_args_dec
599###}
602# --- Visitor Utilities ---
604class CollapseAmbiguities(Transformer):
605 """
606 Transforms a tree that contains any number of _ambig nodes into a list of trees,
607 each one containing an unambiguous tree.
609 The length of the resulting list is the product of the length of all _ambig nodes.
611 Warning: This may quickly explode for highly ambiguous trees.
613 """
614 def _ambig(self, options):
615 return sum(options, [])
617 def __default__(self, data, children_lists, meta):
618 return [Tree(data, children, meta) for children in combine_alternatives(children_lists)]
620 def __default_token__(self, t):
621 return [t]