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 if not stack:
330 return None # type: ignore[return-value]
331 result, = stack # We should have only one tree remaining
332 # There are no guarantees on the type of the value produced by calling a user func for a
333 # child will produce. This means type system can't statically know that the final result is
334 # _Return_T. As a result a cast is required.
335 return cast(_Return_T, result)
338class Transformer_InPlaceRecursive(Transformer[_Leaf_T, _Return_T]):
339 "Same as Transformer, recursive, but changes the tree in-place instead of returning new instances"
340 def _transform_tree(self, tree):
341 tree.children = list(self._transform_children(tree.children))
342 return self._call_userfunc(tree)
345# Visitors
347class VisitorBase:
348 def _call_userfunc(self, tree):
349 return getattr(self, tree.data, self.__default__)(tree)
351 def __default__(self, tree):
352 """Default function that is called if there is no attribute matching ``tree.data``
354 Can be overridden. Defaults to doing nothing.
355 """
356 return tree
358 def __class_getitem__(cls, _):
359 return cls
362class Visitor(VisitorBase, ABC, Generic[_Leaf_T]):
363 """Tree visitor, non-recursive (can handle huge trees).
365 Visiting a node calls its methods (provided by the user via inheritance) according to ``tree.data``
366 """
368 def visit(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
369 "Visits the tree, starting with the leaves and finally the root (bottom-up)"
370 for subtree in tree.iter_subtrees():
371 self._call_userfunc(subtree)
372 return tree
374 def visit_topdown(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
375 "Visit the tree, starting at the root, and ending at the leaves (top-down)"
376 for subtree in tree.iter_subtrees_topdown():
377 self._call_userfunc(subtree)
378 return tree
381class Visitor_Recursive(VisitorBase, Generic[_Leaf_T]):
382 """Bottom-up visitor, recursive.
384 Visiting a node calls its methods (provided by the user via inheritance) according to ``tree.data``
386 Slightly faster than the non-recursive version.
387 """
389 def visit(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
390 "Visits the tree, starting with the leaves and finally the root (bottom-up)"
391 for child in tree.children:
392 if isinstance(child, Tree):
393 self.visit(child)
395 self._call_userfunc(tree)
396 return tree
398 def visit_topdown(self,tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]:
399 "Visit the tree, starting at the root, and ending at the leaves (top-down)"
400 self._call_userfunc(tree)
402 for child in tree.children:
403 if isinstance(child, Tree):
404 self.visit_topdown(child)
406 return tree
409class Interpreter(_Decoratable, ABC, Generic[_Leaf_T, _Return_T]):
410 """Interpreter walks the tree starting at the root.
412 Visits the tree, starting with the root and finally the leaves (top-down)
414 For each tree node, it calls its methods (provided by user via inheritance) according to ``tree.data``.
416 Unlike ``Transformer`` and ``Visitor``, the Interpreter doesn't automatically visit its sub-branches.
417 The user has to explicitly call ``visit``, ``visit_children``, or use the ``@visit_children_decor``.
418 This allows the user to implement branching and loops.
419 """
421 def visit(self, tree: Tree[_Leaf_T]) -> _Return_T:
422 "Visit the tree, starting with the root and finally the leaves (top-down)."
423 # There are no guarantees on the type of the value produced by calling a user func for a
424 # child will produce. So only annotate the public method and use an internal method when
425 # visiting child trees.
426 return self._visit_tree(tree)
428 def _visit_tree(self, tree: Tree[_Leaf_T]):
429 f = getattr(self, tree.data)
430 wrapper = getattr(f, 'visit_wrapper', None)
431 if wrapper is not None:
432 return f.visit_wrapper(f, tree.data, tree.children, tree.meta)
433 else:
434 return f(tree)
436 def visit_children(self, tree: Tree[_Leaf_T]) -> List:
437 "Visit all the children of this tree and return the results as a list."
438 return [
439 self._visit_tree(child)
440 if isinstance(child, Tree)
441 else child
442 for child in tree.children
443 ]
445 def __getattr__(self, name):
446 return self.__default__
448 def __default__(self, tree):
449 """
450 Default function that is called if there is no attribute matching ``tree.data``.
452 Can be overridden. Defaults to visiting all the tree's children.
453 """
454 return self.visit_children(tree)
457_InterMethod = Callable[[Type[Interpreter], _Return_T], _R]
459def visit_children_decor(func: _InterMethod) -> _InterMethod:
460 """
461 A wrapper around Interpreter methods. It makes the wrapped node method automatically visit the
462 node's children before proceeding with the logic you have defined for that node.
464 Example:
465 ::
467 class ProcessQuery(Interpreter):
468 @visit_children_decor
469 def query(self, tree):
470 pass
471 """
472 @wraps(func)
473 def inner(cls, tree):
474 if not isinstance(cls, Interpreter):
475 raise TypeError("visit_children_decor can only be applied to Interpreter methods.")
476 values = cls.visit_children(tree)
477 return func(cls, values)
478 return inner
480# Decorators
482def _apply_v_args(obj, visit_wrapper):
483 try:
484 _apply = obj._apply_v_args
485 except AttributeError:
486 return _VArgsWrapper(obj, visit_wrapper)
487 else:
488 return _apply(visit_wrapper)
491class _VArgsWrapper:
492 """
493 A wrapper around a Callable. It delegates `__call__` to the Callable.
494 If the Callable has a `__get__`, that is also delegate and the resulting function is wrapped.
495 Otherwise, we use the original function mirroring the behaviour without a __get__.
496 We also have the visit_wrapper attribute to be used by Transformers.
497 """
498 base_func: Callable
500 def __init__(self, func: Callable, visit_wrapper: Callable[[Callable, str, list, Any], Any]):
501 if isinstance(func, _VArgsWrapper):
502 func = func.base_func
503 self.base_func = func
504 self.visit_wrapper = visit_wrapper
505 update_wrapper(self, func)
507 def __call__(self, *args, **kwargs):
508 return self.base_func(*args, **kwargs)
510 def __get__(self, instance, owner=None):
511 try:
512 # Use the __get__ attribute of the type instead of the instance
513 # to fully mirror the behavior of getattr
514 g = type(self.base_func).__get__
515 except AttributeError:
516 return self
517 else:
518 return _VArgsWrapper(g(self.base_func, instance, owner), self.visit_wrapper)
520 def __set_name__(self, owner, name):
521 try:
522 f = type(self.base_func).__set_name__
523 except AttributeError:
524 return
525 else:
526 f(self.base_func, owner, name)
529def _vargs_inline(f, _data, children, _meta):
530 return f(*children)
531def _vargs_meta_inline(f, _data, children, meta):
532 return f(meta, *children)
533def _vargs_meta(f, _data, children, meta):
534 return f(meta, children)
535def _vargs_tree(f, data, children, meta):
536 return f(Tree(data, children, meta))
539def v_args(inline: bool = False, meta: bool = False, tree: bool = False, wrapper: Optional[Callable] = None) -> _DECORATOR:
540 """A convenience decorator factory for modifying the behavior of user-supplied callback methods
541 of ``Transformer`` or ``Interpreter`` classes.
543 By default, the callback methods for these classes accept one argument - a list of the node's children.
545 ``v_args`` can modify this behavior. When used on the class definition, it applies to
546 all the callback methods inside it.
548 ``v_args`` can be applied to a single method, or to an entire class. When applied to both,
549 the options given to the method take precedence.
551 Parameters:
552 inline (bool, optional): Children are provided as ``*args`` instead of a list argument (not recommended for very long lists).
553 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).
554 tree (bool, optional): Provides the entire tree as the argument, instead of the children.
555 wrapper (function, optional): Provide a function to decorate all methods.
557 Example:
558 ::
560 @v_args(inline=True)
561 class SolveArith(Transformer):
562 def add(self, left, right):
563 return left + right
565 @v_args(meta=True)
566 def mul(self, meta, children):
567 logger.info(f'mul at line {meta.line}')
568 left, right = children
569 return left * right
572 class ReverseNotation(Transformer_InPlace):
573 @v_args(tree=True)
574 def tree_node(self, tree):
575 tree.children = tree.children[::-1]
576 """
577 if tree and (meta or inline):
578 raise ValueError("Visitor functions cannot combine 'tree' with 'meta' or 'inline'.")
580 func = None
581 if meta:
582 if inline:
583 func = _vargs_meta_inline
584 else:
585 func = _vargs_meta
586 elif inline:
587 func = _vargs_inline
588 elif tree:
589 func = _vargs_tree
591 if wrapper is not None:
592 if func is not None:
593 raise ValueError("Cannot use 'wrapper' along with 'tree', 'meta' or 'inline'.")
594 func = wrapper
596 def _visitor_args_dec(obj):
597 return _apply_v_args(obj, func)
598 return _visitor_args_dec
601###}
604# --- Visitor Utilities ---
606class CollapseAmbiguities(Transformer):
607 """
608 Transforms a tree that contains any number of _ambig nodes into a list of trees,
609 each one containing an unambiguous tree.
611 The length of the resulting list is the product of the length of all _ambig nodes.
613 Warning: This may quickly explode for highly ambiguous trees.
615 """
616 def _ambig(self, options):
617 return sum(options, [])
619 def __default__(self, data, children_lists, meta):
620 return [Tree(data, children, meta) for children in combine_alternatives(children_lists)]
622 def __default_token__(self, t):
623 return [t]