Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/lark/visitors.py: 71%
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_FUNC = Callable[..., _Return_T]
19_DECORATED = Union[_FUNC, type]
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 # There are no guarantees on the type of the value produced by calling a user func for a
421 # child will produce. So only annotate the public method and use an internal method when
422 # visiting child trees.
423 return self._visit_tree(tree)
425 def _visit_tree(self, tree: Tree[_Leaf_T]):
426 f = getattr(self, tree.data)
427 wrapper = getattr(f, 'visit_wrapper', None)
428 if wrapper is not None:
429 return f.visit_wrapper(f, tree.data, tree.children, tree.meta)
430 else:
431 return f(tree)
433 def visit_children(self, tree: Tree[_Leaf_T]) -> List:
434 return [self._visit_tree(child) if isinstance(child, Tree) else child
435 for child in tree.children]
437 def __getattr__(self, name):
438 return self.__default__
440 def __default__(self, tree):
441 return self.visit_children(tree)
444_InterMethod = Callable[[Type[Interpreter], _Return_T], _R]
446def visit_children_decor(func: _InterMethod) -> _InterMethod:
447 "See Interpreter"
448 @wraps(func)
449 def inner(cls, tree):
450 values = cls.visit_children(tree)
451 return func(cls, values)
452 return inner
454# Decorators
456def _apply_v_args(obj, visit_wrapper):
457 try:
458 _apply = obj._apply_v_args
459 except AttributeError:
460 return _VArgsWrapper(obj, visit_wrapper)
461 else:
462 return _apply(visit_wrapper)
465class _VArgsWrapper:
466 """
467 A wrapper around a Callable. It delegates `__call__` to the Callable.
468 If the Callable has a `__get__`, that is also delegate and the resulting function is wrapped.
469 Otherwise, we use the original function mirroring the behaviour without a __get__.
470 We also have the visit_wrapper attribute to be used by Transformers.
471 """
472 base_func: Callable
474 def __init__(self, func: Callable, visit_wrapper: Callable[[Callable, str, list, Any], Any]):
475 if isinstance(func, _VArgsWrapper):
476 func = func.base_func
477 self.base_func = func
478 self.visit_wrapper = visit_wrapper
479 update_wrapper(self, func)
481 def __call__(self, *args, **kwargs):
482 return self.base_func(*args, **kwargs)
484 def __get__(self, instance, owner=None):
485 try:
486 # Use the __get__ attribute of the type instead of the instance
487 # to fully mirror the behavior of getattr
488 g = type(self.base_func).__get__
489 except AttributeError:
490 return self
491 else:
492 return _VArgsWrapper(g(self.base_func, instance, owner), self.visit_wrapper)
494 def __set_name__(self, owner, name):
495 try:
496 f = type(self.base_func).__set_name__
497 except AttributeError:
498 return
499 else:
500 f(self.base_func, owner, name)
503def _vargs_inline(f, _data, children, _meta):
504 return f(*children)
505def _vargs_meta_inline(f, _data, children, meta):
506 return f(meta, *children)
507def _vargs_meta(f, _data, children, meta):
508 return f(meta, children)
509def _vargs_tree(f, data, children, meta):
510 return f(Tree(data, children, meta))
513def v_args(inline: bool = False, meta: bool = False, tree: bool = False, wrapper: Optional[Callable] = None) -> Callable[[_DECORATED], _DECORATED]:
514 """A convenience decorator factory for modifying the behavior of user-supplied callback methods of ``Transformer`` classes.
516 By default, transformer callback methods accept one argument - a list of the node's children.
518 ``v_args`` can modify this behavior. When used on a ``Transformer`` class definition, it applies to
519 all the callback methods inside it.
521 ``v_args`` can be applied to a single method, or to an entire class. When applied to both,
522 the options given to the method take precedence.
524 Parameters:
525 inline (bool, optional): Children are provided as ``*args`` instead of a list argument (not recommended for very long lists).
526 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).
527 tree (bool, optional): Provides the entire tree as the argument, instead of the children.
528 wrapper (function, optional): Provide a function to decorate all methods.
530 Example:
531 ::
533 @v_args(inline=True)
534 class SolveArith(Transformer):
535 def add(self, left, right):
536 return left + right
538 @v_args(meta=True)
539 def mul(self, meta, children):
540 logger.info(f'mul at line {meta.line}')
541 left, right = children
542 return left * right
545 class ReverseNotation(Transformer_InPlace):
546 @v_args(tree=True)
547 def tree_node(self, tree):
548 tree.children = tree.children[::-1]
549 """
550 if tree and (meta or inline):
551 raise ValueError("Visitor functions cannot combine 'tree' with 'meta' or 'inline'.")
553 func = None
554 if meta:
555 if inline:
556 func = _vargs_meta_inline
557 else:
558 func = _vargs_meta
559 elif inline:
560 func = _vargs_inline
561 elif tree:
562 func = _vargs_tree
564 if wrapper is not None:
565 if func is not None:
566 raise ValueError("Cannot use 'wrapper' along with 'tree', 'meta' or 'inline'.")
567 func = wrapper
569 def _visitor_args_dec(obj):
570 return _apply_v_args(obj, func)
571 return _visitor_args_dec
574###}
577# --- Visitor Utilities ---
579class CollapseAmbiguities(Transformer):
580 """
581 Transforms a tree that contains any number of _ambig nodes into a list of trees,
582 each one containing an unambiguous tree.
584 The length of the resulting list is the product of the length of all _ambig nodes.
586 Warning: This may quickly explode for highly ambiguous trees.
588 """
589 def _ambig(self, options):
590 return sum(options, [])
592 def __default__(self, data, children_lists, meta):
593 return [Tree(data, children, meta) for children in combine_alternatives(children_lists)]
595 def __default_token__(self, t):
596 return [t]