Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/lark/visitors.py: 70%

270 statements  

« prev     ^ index     » next       coverage.py v7.3.1, created at 2023-09-25 06:30 +0000

1from typing import TypeVar, Tuple, List, Callable, Generic, Type, Union, Optional, Any, cast 

2from abc import ABC 

3 

4from .utils import combine_alternatives 

5from .tree import Tree, Branch 

6from .exceptions import VisitError, GrammarError 

7from .lexer import Token 

8 

9###{standalone 

10from functools import wraps, update_wrapper 

11from inspect import getmembers, getmro 

12 

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] 

20 

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. 

24 

25 Note: 

26 This feature is disabled when the transformer is provided to Lark 

27 using the ``transformer`` keyword (aka Tree-less LALR mode). 

28 

29 Example: 

30 :: 

31 

32 class T(Transformer): 

33 def ignore_tree(self, children): 

34 return Discard 

35 

36 def IGNORE_TOKEN(self, token): 

37 return Discard 

38 """ 

39 

40 def __repr__(self): 

41 return "lark.visitors.Discard" 

42 

43Discard = _DiscardType() 

44 

45# Transformers 

46 

47class _Decoratable: 

48 "Provides support for decorating methods with @v_args" 

49 

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): 

56 

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 

62 

63 # Skip if v_args already applied (at the function level) 

64 if isinstance(cls.__dict__[name], _VArgsWrapper): 

65 continue 

66 

67 setattr(cls, name, _VArgsWrapper(cls.__dict__[name], visit_wrapper)) 

68 return cls 

69 

70 def __class_getitem__(cls, _): 

71 return cls 

72 

73 

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. 

77 

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. 

80 

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). 

83 

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. 

86 

87 To discard a node, return Discard (``lark.visitors.Discard``). 

88 

89 ``Transformer`` can do anything ``Visitor`` can do, but because it reconstructs the tree, 

90 it is slightly less efficient. 

91 

92 A transformer without methods essentially performs a non-memoized partial deepcopy. 

93 

94 All these classes implement the transformer interface: 

95 

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 

99 

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) 

104 

105 """ 

106 __visit_tokens__ = True # For backwards compatibility 

107 

108 def __init__(self, visit_tokens: bool=True) -> None: 

109 self.__visit_tokens__ = visit_tokens 

110 

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) 

129 

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) 

142 

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 

151 

152 if res is not Discard: 

153 yield res 

154 

155 def _transform_tree(self, tree): 

156 children = list(self._transform_children(tree.children)) 

157 return self._call_userfunc(tree, children) 

158 

159 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T: 

160 "Transform the given tree, and return the final result" 

161 return self._transform_tree(tree) 

162 

163 def __mul__( 

164 self: 'Transformer[_Leaf_T, Tree[_Leaf_U]]', 

165 other: 'Union[Transformer[_Leaf_U, _Return_V], TransformerChain[_Leaf_U, _Return_V,]]' 

166 ) -> 'TransformerChain[_Leaf_T, _Return_V]': 

167 """Chain two transformers together, returning a new transformer. 

168 """ 

169 return TransformerChain(self, other) 

170 

171 def __default__(self, data, children, meta): 

172 """Default function that is called if there is no attribute matching ``data`` 

173 

174 Can be overridden. Defaults to creating a new copy of the tree node (i.e. ``return Tree(data, children, meta)``) 

175 """ 

176 return Tree(data, children, meta) 

177 

178 def __default_token__(self, token): 

179 """Default function that is called if there is no attribute matching ``token.type`` 

180 

181 Can be overridden. Defaults to returning the token as-is. 

182 """ 

183 return token 

184 

185 

186def merge_transformers(base_transformer=None, **transformers_to_merge): 

187 """Merge a collection of transformers into the base_transformer, each into its own 'namespace'. 

188 

189 When called, it will collect the methods from each transformer, and assign them to base_transformer, 

190 with their name prefixed with the given keyword, as ``prefix__methodname``. 

191 

192 This function is especially useful for processing grammars that import other grammars, 

193 thereby creating some of their rules in a 'namespace'. (i.e with a consistent name prefix). 

194 In this case, the key for the transformer should match the name of the imported grammar. 

195 

196 Parameters: 

197 base_transformer (Transformer, optional): The transformer that all other transformers will be added to. 

198 **transformers_to_merge: Keyword arguments, in the form of ``name_prefix = transformer``. 

199 

200 Raises: 

201 AttributeError: In case of a name collision in the merged methods 

202 

203 Example: 

204 :: 

205 

206 class TBase(Transformer): 

207 def start(self, children): 

208 return children[0] + 'bar' 

209 

210 class TImportedGrammar(Transformer): 

211 def foo(self, children): 

212 return "foo" 

213 

214 composed_transformer = merge_transformers(TBase(), imported=TImportedGrammar()) 

215 

216 t = Tree('start', [ Tree('imported__foo', []) ]) 

217 

218 assert composed_transformer.transform(t) == 'foobar' 

219 

220 """ 

221 if base_transformer is None: 

222 base_transformer = Transformer() 

223 for prefix, transformer in transformers_to_merge.items(): 

224 for method_name in dir(transformer): 

225 method = getattr(transformer, method_name) 

226 if not callable(method): 

227 continue 

228 if method_name.startswith("_") or method_name == "transform": 

229 continue 

230 prefixed_method = prefix + "__" + method_name 

231 if hasattr(base_transformer, prefixed_method): 

232 raise AttributeError("Cannot merge: method '%s' appears more than once" % prefixed_method) 

233 

234 setattr(base_transformer, prefixed_method, method) 

235 

236 return base_transformer 

237 

238 

239class InlineTransformer(Transformer): # XXX Deprecated 

240 def _call_userfunc(self, tree, new_children=None): 

241 # Assumes tree is already transformed 

242 children = new_children if new_children is not None else tree.children 

243 try: 

244 f = getattr(self, tree.data) 

245 except AttributeError: 

246 return self.__default__(tree.data, children, tree.meta) 

247 else: 

248 return f(*children) 

249 

250 

251class TransformerChain(Generic[_Leaf_T, _Return_T]): 

252 

253 transformers: 'Tuple[Union[Transformer, TransformerChain], ...]' 

254 

255 def __init__(self, *transformers: 'Union[Transformer, TransformerChain]') -> None: 

256 self.transformers = transformers 

257 

258 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T: 

259 for t in self.transformers: 

260 tree = t.transform(tree) 

261 return cast(_Return_T, tree) 

262 

263 def __mul__( 

264 self: 'TransformerChain[_Leaf_T, Tree[_Leaf_U]]', 

265 other: 'Union[Transformer[_Leaf_U, _Return_V], TransformerChain[_Leaf_U, _Return_V]]' 

266 ) -> 'TransformerChain[_Leaf_T, _Return_V]': 

267 return TransformerChain(*self.transformers + (other,)) 

268 

269 

270class Transformer_InPlace(Transformer): 

271 """Same as Transformer, but non-recursive, and changes the tree in-place instead of returning new instances 

272 

273 Useful for huge trees. Conservative in memory. 

274 """ 

275 def _transform_tree(self, tree): # Cancel recursion 

276 return self._call_userfunc(tree) 

277 

278 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T: 

279 for subtree in tree.iter_subtrees(): 

280 subtree.children = list(self._transform_children(subtree.children)) 

281 

282 return self._transform_tree(tree) 

283 

284 

285class Transformer_NonRecursive(Transformer): 

286 """Same as Transformer but non-recursive. 

287 

288 Like Transformer, it doesn't change the original tree. 

289 

290 Useful for huge trees. 

291 """ 

292 

293 def transform(self, tree: Tree[_Leaf_T]) -> _Return_T: 

294 # Tree to postfix 

295 rev_postfix = [] 

296 q: List[Branch[_Leaf_T]] = [tree] 

297 while q: 

298 t = q.pop() 

299 rev_postfix.append(t) 

300 if isinstance(t, Tree): 

301 q += t.children 

302 

303 # Postfix to tree 

304 stack: List = [] 

305 for x in reversed(rev_postfix): 

306 if isinstance(x, Tree): 

307 size = len(x.children) 

308 if size: 

309 args = stack[-size:] 

310 del stack[-size:] 

311 else: 

312 args = [] 

313 

314 res = self._call_userfunc(x, args) 

315 if res is not Discard: 

316 stack.append(res) 

317 

318 elif self.__visit_tokens__ and isinstance(x, Token): 

319 res = self._call_userfunc_token(x) 

320 if res is not Discard: 

321 stack.append(res) 

322 else: 

323 stack.append(x) 

324 

325 result, = stack # We should have only one tree remaining 

326 # There are no guarantees on the type of the value produced by calling a user func for a 

327 # child will produce. This means type system can't statically know that the final result is 

328 # _Return_T. As a result a cast is required. 

329 return cast(_Return_T, result) 

330 

331 

332class Transformer_InPlaceRecursive(Transformer): 

333 "Same as Transformer, recursive, but changes the tree in-place instead of returning new instances" 

334 def _transform_tree(self, tree): 

335 tree.children = list(self._transform_children(tree.children)) 

336 return self._call_userfunc(tree) 

337 

338 

339# Visitors 

340 

341class VisitorBase: 

342 def _call_userfunc(self, tree): 

343 return getattr(self, tree.data, self.__default__)(tree) 

344 

345 def __default__(self, tree): 

346 """Default function that is called if there is no attribute matching ``tree.data`` 

347 

348 Can be overridden. Defaults to doing nothing. 

349 """ 

350 return tree 

351 

352 def __class_getitem__(cls, _): 

353 return cls 

354 

355 

356class Visitor(VisitorBase, ABC, Generic[_Leaf_T]): 

357 """Tree visitor, non-recursive (can handle huge trees). 

358 

359 Visiting a node calls its methods (provided by the user via inheritance) according to ``tree.data`` 

360 """ 

361 

362 def visit(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]: 

363 "Visits the tree, starting with the leaves and finally the root (bottom-up)" 

364 for subtree in tree.iter_subtrees(): 

365 self._call_userfunc(subtree) 

366 return tree 

367 

368 def visit_topdown(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]: 

369 "Visit the tree, starting at the root, and ending at the leaves (top-down)" 

370 for subtree in tree.iter_subtrees_topdown(): 

371 self._call_userfunc(subtree) 

372 return tree 

373 

374 

375class Visitor_Recursive(VisitorBase, Generic[_Leaf_T]): 

376 """Bottom-up visitor, recursive. 

377 

378 Visiting a node calls its methods (provided by the user via inheritance) according to ``tree.data`` 

379 

380 Slightly faster than the non-recursive version. 

381 """ 

382 

383 def visit(self, tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]: 

384 "Visits the tree, starting with the leaves and finally the root (bottom-up)" 

385 for child in tree.children: 

386 if isinstance(child, Tree): 

387 self.visit(child) 

388 

389 self._call_userfunc(tree) 

390 return tree 

391 

392 def visit_topdown(self,tree: Tree[_Leaf_T]) -> Tree[_Leaf_T]: 

393 "Visit the tree, starting at the root, and ending at the leaves (top-down)" 

394 self._call_userfunc(tree) 

395 

396 for child in tree.children: 

397 if isinstance(child, Tree): 

398 self.visit_topdown(child) 

399 

400 return tree 

401 

402 

403class Interpreter(_Decoratable, ABC, Generic[_Leaf_T, _Return_T]): 

404 """Interpreter walks the tree starting at the root. 

405 

406 Visits the tree, starting with the root and finally the leaves (top-down) 

407 

408 For each tree node, it calls its methods (provided by user via inheritance) according to ``tree.data``. 

409 

410 Unlike ``Transformer`` and ``Visitor``, the Interpreter doesn't automatically visit its sub-branches. 

411 The user has to explicitly call ``visit``, ``visit_children``, or use the ``@visit_children_decor``. 

412 This allows the user to implement branching and loops. 

413 """ 

414 

415 def visit(self, tree: Tree[_Leaf_T]) -> _Return_T: 

416 # There are no guarantees on the type of the value produced by calling a user func for a 

417 # child will produce. So only annotate the public method and use an internal method when 

418 # visiting child trees. 

419 return self._visit_tree(tree) 

420 

421 def _visit_tree(self, tree: Tree[_Leaf_T]): 

422 f = getattr(self, tree.data) 

423 wrapper = getattr(f, 'visit_wrapper', None) 

424 if wrapper is not None: 

425 return f.visit_wrapper(f, tree.data, tree.children, tree.meta) 

426 else: 

427 return f(tree) 

428 

429 def visit_children(self, tree: Tree[_Leaf_T]) -> List: 

430 return [self._visit_tree(child) if isinstance(child, Tree) else child 

431 for child in tree.children] 

432 

433 def __getattr__(self, name): 

434 return self.__default__ 

435 

436 def __default__(self, tree): 

437 return self.visit_children(tree) 

438 

439 

440_InterMethod = Callable[[Type[Interpreter], _Return_T], _R] 

441 

442def visit_children_decor(func: _InterMethod) -> _InterMethod: 

443 "See Interpreter" 

444 @wraps(func) 

445 def inner(cls, tree): 

446 values = cls.visit_children(tree) 

447 return func(cls, values) 

448 return inner 

449 

450# Decorators 

451 

452def _apply_v_args(obj, visit_wrapper): 

453 try: 

454 _apply = obj._apply_v_args 

455 except AttributeError: 

456 return _VArgsWrapper(obj, visit_wrapper) 

457 else: 

458 return _apply(visit_wrapper) 

459 

460 

461class _VArgsWrapper: 

462 """ 

463 A wrapper around a Callable. It delegates `__call__` to the Callable. 

464 If the Callable has a `__get__`, that is also delegate and the resulting function is wrapped. 

465 Otherwise, we use the original function mirroring the behaviour without a __get__. 

466 We also have the visit_wrapper attribute to be used by Transformers. 

467 """ 

468 base_func: Callable 

469 

470 def __init__(self, func: Callable, visit_wrapper: Callable[[Callable, str, list, Any], Any]): 

471 if isinstance(func, _VArgsWrapper): 

472 func = func.base_func 

473 # https://github.com/python/mypy/issues/708 

474 self.base_func = func # type: ignore[assignment] 

475 self.visit_wrapper = visit_wrapper 

476 update_wrapper(self, func) 

477 

478 def __call__(self, *args, **kwargs): 

479 return self.base_func(*args, **kwargs) 

480 

481 def __get__(self, instance, owner=None): 

482 try: 

483 # Use the __get__ attribute of the type instead of the instance 

484 # to fully mirror the behavior of getattr 

485 g = type(self.base_func).__get__ 

486 except AttributeError: 

487 return self 

488 else: 

489 return _VArgsWrapper(g(self.base_func, instance, owner), self.visit_wrapper) 

490 

491 def __set_name__(self, owner, name): 

492 try: 

493 f = type(self.base_func).__set_name__ 

494 except AttributeError: 

495 return 

496 else: 

497 f(self.base_func, owner, name) 

498 

499 

500def _vargs_inline(f, _data, children, _meta): 

501 return f(*children) 

502def _vargs_meta_inline(f, _data, children, meta): 

503 return f(meta, *children) 

504def _vargs_meta(f, _data, children, meta): 

505 return f(meta, children) 

506def _vargs_tree(f, data, children, meta): 

507 return f(Tree(data, children, meta)) 

508 

509 

510def v_args(inline: bool = False, meta: bool = False, tree: bool = False, wrapper: Optional[Callable] = None) -> Callable[[_DECORATED], _DECORATED]: 

511 """A convenience decorator factory for modifying the behavior of user-supplied visitor methods. 

512 

513 By default, callback methods of transformers/visitors accept one argument - a list of the node's children. 

514 

515 ``v_args`` can modify this behavior. When used on a transformer/visitor class definition, 

516 it applies to all the callback methods inside it. 

517 

518 ``v_args`` can be applied to a single method, or to an entire class. When applied to both, 

519 the options given to the method take precedence. 

520 

521 Parameters: 

522 inline (bool, optional): Children are provided as ``*args`` instead of a list argument (not recommended for very long lists). 

523 meta (bool, optional): Provides two arguments: ``meta`` and ``children`` (instead of just the latter) 

524 tree (bool, optional): Provides the entire tree as the argument, instead of the children. 

525 wrapper (function, optional): Provide a function to decorate all methods. 

526 

527 Example: 

528 :: 

529 

530 @v_args(inline=True) 

531 class SolveArith(Transformer): 

532 def add(self, left, right): 

533 return left + right 

534 

535 @v_args(meta=True) 

536 def mul(self, meta, children): 

537 logger.info(f'mul at line {meta.line}') 

538 left, right = children 

539 return left * right 

540 

541 

542 class ReverseNotation(Transformer_InPlace): 

543 @v_args(tree=True) 

544 def tree_node(self, tree): 

545 tree.children = tree.children[::-1] 

546 """ 

547 if tree and (meta or inline): 

548 raise ValueError("Visitor functions cannot combine 'tree' with 'meta' or 'inline'.") 

549 

550 func = None 

551 if meta: 

552 if inline: 

553 func = _vargs_meta_inline 

554 else: 

555 func = _vargs_meta 

556 elif inline: 

557 func = _vargs_inline 

558 elif tree: 

559 func = _vargs_tree 

560 

561 if wrapper is not None: 

562 if func is not None: 

563 raise ValueError("Cannot use 'wrapper' along with 'tree', 'meta' or 'inline'.") 

564 func = wrapper 

565 

566 def _visitor_args_dec(obj): 

567 return _apply_v_args(obj, func) 

568 return _visitor_args_dec 

569 

570 

571###} 

572 

573 

574# --- Visitor Utilities --- 

575 

576class CollapseAmbiguities(Transformer): 

577 """ 

578 Transforms a tree that contains any number of _ambig nodes into a list of trees, 

579 each one containing an unambiguous tree. 

580 

581 The length of the resulting list is the product of the length of all _ambig nodes. 

582 

583 Warning: This may quickly explode for highly ambiguous trees. 

584 

585 """ 

586 def _ambig(self, options): 

587 return sum(options, []) 

588 

589 def __default__(self, data, children_lists, meta): 

590 return [Tree(data, children, meta) for children in combine_alternatives(children_lists)] 

591 

592 def __default_token__(self, t): 

593 return [t]