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