Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/lark/parse_tree_builder.py: 52%
226 statements
« prev ^ index » next coverage.py v7.3.1, created at 2023-09-25 06:30 +0000
1"""Provides functions for the automatic building and shaping of the parse-tree."""
3from typing import List
5from .exceptions import GrammarError, ConfigurationError
6from .lexer import Token
7from .tree import Tree
8from .visitors import Transformer_InPlace
9from .visitors import _vargs_meta, _vargs_meta_inline
11###{standalone
12from functools import partial, wraps
13from itertools import product
16class ExpandSingleChild:
17 def __init__(self, node_builder):
18 self.node_builder = node_builder
20 def __call__(self, children):
21 if len(children) == 1:
22 return children[0]
23 else:
24 return self.node_builder(children)
28class PropagatePositions:
29 def __init__(self, node_builder, node_filter=None):
30 self.node_builder = node_builder
31 self.node_filter = node_filter
33 def __call__(self, children):
34 res = self.node_builder(children)
36 if isinstance(res, Tree):
37 # Calculate positions while the tree is streaming, according to the rule:
38 # - nodes start at the start of their first child's container,
39 # and end at the end of their last child's container.
40 # Containers are nodes that take up space in text, but have been inlined in the tree.
42 res_meta = res.meta
44 first_meta = self._pp_get_meta(children)
45 if first_meta is not None:
46 if not hasattr(res_meta, 'line'):
47 # meta was already set, probably because the rule has been inlined (e.g. `?rule`)
48 res_meta.line = getattr(first_meta, 'container_line', first_meta.line)
49 res_meta.column = getattr(first_meta, 'container_column', first_meta.column)
50 res_meta.start_pos = getattr(first_meta, 'container_start_pos', first_meta.start_pos)
51 res_meta.empty = False
53 res_meta.container_line = getattr(first_meta, 'container_line', first_meta.line)
54 res_meta.container_column = getattr(first_meta, 'container_column', first_meta.column)
55 res_meta.container_start_pos = getattr(first_meta, 'container_start_pos', first_meta.start_pos)
57 last_meta = self._pp_get_meta(reversed(children))
58 if last_meta is not None:
59 if not hasattr(res_meta, 'end_line'):
60 res_meta.end_line = getattr(last_meta, 'container_end_line', last_meta.end_line)
61 res_meta.end_column = getattr(last_meta, 'container_end_column', last_meta.end_column)
62 res_meta.end_pos = getattr(last_meta, 'container_end_pos', last_meta.end_pos)
63 res_meta.empty = False
65 res_meta.container_end_line = getattr(last_meta, 'container_end_line', last_meta.end_line)
66 res_meta.container_end_column = getattr(last_meta, 'container_end_column', last_meta.end_column)
67 res_meta.container_end_pos = getattr(last_meta, 'container_end_pos', last_meta.end_pos)
69 return res
71 def _pp_get_meta(self, children):
72 for c in children:
73 if self.node_filter is not None and not self.node_filter(c):
74 continue
75 if isinstance(c, Tree):
76 if not c.meta.empty:
77 return c.meta
78 elif isinstance(c, Token):
79 return c
80 elif hasattr(c, '__lark_meta__'):
81 return c.__lark_meta__()
83def make_propagate_positions(option):
84 if callable(option):
85 return partial(PropagatePositions, node_filter=option)
86 elif option is True:
87 return PropagatePositions
88 elif option is False:
89 return None
91 raise ConfigurationError('Invalid option for propagate_positions: %r' % option)
94class ChildFilter:
95 def __init__(self, to_include, append_none, node_builder):
96 self.node_builder = node_builder
97 self.to_include = to_include
98 self.append_none = append_none
100 def __call__(self, children):
101 filtered = []
103 for i, to_expand, add_none in self.to_include:
104 if add_none:
105 filtered += [None] * add_none
106 if to_expand:
107 filtered += children[i].children
108 else:
109 filtered.append(children[i])
111 if self.append_none:
112 filtered += [None] * self.append_none
114 return self.node_builder(filtered)
117class ChildFilterLALR(ChildFilter):
118 """Optimized childfilter for LALR (assumes no duplication in parse tree, so it's safe to change it)"""
120 def __call__(self, children):
121 filtered = []
122 for i, to_expand, add_none in self.to_include:
123 if add_none:
124 filtered += [None] * add_none
125 if to_expand:
126 if filtered:
127 filtered += children[i].children
128 else: # Optimize for left-recursion
129 filtered = children[i].children
130 else:
131 filtered.append(children[i])
133 if self.append_none:
134 filtered += [None] * self.append_none
136 return self.node_builder(filtered)
139class ChildFilterLALR_NoPlaceholders(ChildFilter):
140 "Optimized childfilter for LALR (assumes no duplication in parse tree, so it's safe to change it)"
141 def __init__(self, to_include, node_builder):
142 self.node_builder = node_builder
143 self.to_include = to_include
145 def __call__(self, children):
146 filtered = []
147 for i, to_expand in self.to_include:
148 if to_expand:
149 if filtered:
150 filtered += children[i].children
151 else: # Optimize for left-recursion
152 filtered = children[i].children
153 else:
154 filtered.append(children[i])
155 return self.node_builder(filtered)
158def _should_expand(sym):
159 return not sym.is_term and sym.name.startswith('_')
162def maybe_create_child_filter(expansion, keep_all_tokens, ambiguous, _empty_indices: List[bool]):
163 # Prepare empty_indices as: How many Nones to insert at each index?
164 if _empty_indices:
165 assert _empty_indices.count(False) == len(expansion)
166 s = ''.join(str(int(b)) for b in _empty_indices)
167 empty_indices = [len(ones) for ones in s.split('0')]
168 assert len(empty_indices) == len(expansion)+1, (empty_indices, len(expansion))
169 else:
170 empty_indices = [0] * (len(expansion)+1)
172 to_include = []
173 nones_to_add = 0
174 for i, sym in enumerate(expansion):
175 nones_to_add += empty_indices[i]
176 if keep_all_tokens or not (sym.is_term and sym.filter_out):
177 to_include.append((i, _should_expand(sym), nones_to_add))
178 nones_to_add = 0
180 nones_to_add += empty_indices[len(expansion)]
182 if _empty_indices or len(to_include) < len(expansion) or any(to_expand for i, to_expand,_ in to_include):
183 if _empty_indices or ambiguous:
184 return partial(ChildFilter if ambiguous else ChildFilterLALR, to_include, nones_to_add)
185 else:
186 # LALR without placeholders
187 return partial(ChildFilterLALR_NoPlaceholders, [(i, x) for i,x,_ in to_include])
190class AmbiguousExpander:
191 """Deal with the case where we're expanding children ('_rule') into a parent but the children
192 are ambiguous. i.e. (parent->_ambig->_expand_this_rule). In this case, make the parent itself
193 ambiguous with as many copies as there are ambiguous children, and then copy the ambiguous children
194 into the right parents in the right places, essentially shifting the ambiguity up the tree."""
195 def __init__(self, to_expand, tree_class, node_builder):
196 self.node_builder = node_builder
197 self.tree_class = tree_class
198 self.to_expand = to_expand
200 def __call__(self, children):
201 def _is_ambig_tree(t):
202 return hasattr(t, 'data') and t.data == '_ambig'
204 # -- When we're repeatedly expanding ambiguities we can end up with nested ambiguities.
205 # All children of an _ambig node should be a derivation of that ambig node, hence
206 # it is safe to assume that if we see an _ambig node nested within an ambig node
207 # it is safe to simply expand it into the parent _ambig node as an alternative derivation.
208 ambiguous = []
209 for i, child in enumerate(children):
210 if _is_ambig_tree(child):
211 if i in self.to_expand:
212 ambiguous.append(i)
214 child.expand_kids_by_data('_ambig')
216 if not ambiguous:
217 return self.node_builder(children)
219 expand = [child.children if i in ambiguous else (child,) for i, child in enumerate(children)]
220 return self.tree_class('_ambig', [self.node_builder(list(f)) for f in product(*expand)])
223def maybe_create_ambiguous_expander(tree_class, expansion, keep_all_tokens):
224 to_expand = [i for i, sym in enumerate(expansion)
225 if keep_all_tokens or ((not (sym.is_term and sym.filter_out)) and _should_expand(sym))]
226 if to_expand:
227 return partial(AmbiguousExpander, to_expand, tree_class)
230class AmbiguousIntermediateExpander:
231 """
232 Propagate ambiguous intermediate nodes and their derivations up to the
233 current rule.
235 In general, converts
237 rule
238 _iambig
239 _inter
240 someChildren1
241 ...
242 _inter
243 someChildren2
244 ...
245 someChildren3
246 ...
248 to
250 _ambig
251 rule
252 someChildren1
253 ...
254 someChildren3
255 ...
256 rule
257 someChildren2
258 ...
259 someChildren3
260 ...
261 rule
262 childrenFromNestedIambigs
263 ...
264 someChildren3
265 ...
266 ...
268 propagating up any nested '_iambig' nodes along the way.
269 """
271 def __init__(self, tree_class, node_builder):
272 self.node_builder = node_builder
273 self.tree_class = tree_class
275 def __call__(self, children):
276 def _is_iambig_tree(child):
277 return hasattr(child, 'data') and child.data == '_iambig'
279 def _collapse_iambig(children):
280 """
281 Recursively flatten the derivations of the parent of an '_iambig'
282 node. Returns a list of '_inter' nodes guaranteed not
283 to contain any nested '_iambig' nodes, or None if children does
284 not contain an '_iambig' node.
285 """
287 # Due to the structure of the SPPF,
288 # an '_iambig' node can only appear as the first child
289 if children and _is_iambig_tree(children[0]):
290 iambig_node = children[0]
291 result = []
292 for grandchild in iambig_node.children:
293 collapsed = _collapse_iambig(grandchild.children)
294 if collapsed:
295 for child in collapsed:
296 child.children += children[1:]
297 result += collapsed
298 else:
299 new_tree = self.tree_class('_inter', grandchild.children + children[1:])
300 result.append(new_tree)
301 return result
303 collapsed = _collapse_iambig(children)
304 if collapsed:
305 processed_nodes = [self.node_builder(c.children) for c in collapsed]
306 return self.tree_class('_ambig', processed_nodes)
308 return self.node_builder(children)
312def inplace_transformer(func):
313 @wraps(func)
314 def f(children):
315 # function name in a Transformer is a rule name.
316 tree = Tree(func.__name__, children)
317 return func(tree)
318 return f
321def apply_visit_wrapper(func, name, wrapper):
322 if wrapper is _vargs_meta or wrapper is _vargs_meta_inline:
323 raise NotImplementedError("Meta args not supported for internal transformer")
325 @wraps(func)
326 def f(children):
327 return wrapper(func, name, children, None)
328 return f
331class ParseTreeBuilder:
332 def __init__(self, rules, tree_class, propagate_positions=False, ambiguous=False, maybe_placeholders=False):
333 self.tree_class = tree_class
334 self.propagate_positions = propagate_positions
335 self.ambiguous = ambiguous
336 self.maybe_placeholders = maybe_placeholders
338 self.rule_builders = list(self._init_builders(rules))
340 def _init_builders(self, rules):
341 propagate_positions = make_propagate_positions(self.propagate_positions)
343 for rule in rules:
344 options = rule.options
345 keep_all_tokens = options.keep_all_tokens
346 expand_single_child = options.expand1
348 wrapper_chain = list(filter(None, [
349 (expand_single_child and not rule.alias) and ExpandSingleChild,
350 maybe_create_child_filter(rule.expansion, keep_all_tokens, self.ambiguous, options.empty_indices if self.maybe_placeholders else None),
351 propagate_positions,
352 self.ambiguous and maybe_create_ambiguous_expander(self.tree_class, rule.expansion, keep_all_tokens),
353 self.ambiguous and partial(AmbiguousIntermediateExpander, self.tree_class)
354 ]))
356 yield rule, wrapper_chain
358 def create_callback(self, transformer=None):
359 callbacks = {}
361 default_handler = getattr(transformer, '__default__', None)
362 if default_handler:
363 def default_callback(data, children):
364 return default_handler(data, children, None)
365 else:
366 default_callback = self.tree_class
368 for rule, wrapper_chain in self.rule_builders:
370 user_callback_name = rule.alias or rule.options.template_source or rule.origin.name
371 try:
372 f = getattr(transformer, user_callback_name)
373 wrapper = getattr(f, 'visit_wrapper', None)
374 if wrapper is not None:
375 f = apply_visit_wrapper(f, user_callback_name, wrapper)
376 elif isinstance(transformer, Transformer_InPlace):
377 f = inplace_transformer(f)
378 except AttributeError:
379 f = partial(default_callback, user_callback_name)
381 for w in wrapper_chain:
382 f = w(f)
384 if rule in callbacks:
385 raise GrammarError("Rule '%s' already exists" % (rule,))
387 callbacks[rule] = f
389 return callbacks
391###}