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