ยปCore Development>Code coverage>Lib/lib2to3/pytree.py

Python code coverage for Lib/lib2to3/pytree.py

#countcontent
1n/a# Copyright 2006 Google, Inc. All Rights Reserved.
2n/a# Licensed to PSF under a Contributor Agreement.
3n/a
4n/a"""
5n/aPython parse tree definitions.
6n/a
7n/aThis is a very concrete parse tree; we need to keep every token and
8n/aeven the comments and whitespace between tokens.
9n/a
10n/aThere's also a pattern matching implementation here.
11n/a"""
12n/a
13n/a__author__ = "Guido van Rossum <guido@python.org>"
14n/a
15n/aimport sys
16n/afrom io import StringIO
17n/a
18n/aHUGE = 0x7FFFFFFF # maximum repeat count, default max
19n/a
20n/a_type_reprs = {}
21n/adef type_repr(type_num):
22n/a global _type_reprs
23n/a if not _type_reprs:
24n/a from .pygram import python_symbols
25n/a # printing tokens is possible but not as useful
26n/a # from .pgen2 import token // token.__dict__.items():
27n/a for name, val in python_symbols.__dict__.items():
28n/a if type(val) == int: _type_reprs[val] = name
29n/a return _type_reprs.setdefault(type_num, type_num)
30n/a
31n/aclass Base(object):
32n/a
33n/a """
34n/a Abstract base class for Node and Leaf.
35n/a
36n/a This provides some default functionality and boilerplate using the
37n/a template pattern.
38n/a
39n/a A node may be a subnode of at most one parent.
40n/a """
41n/a
42n/a # Default values for instance variables
43n/a type = None # int: token number (< 256) or symbol number (>= 256)
44n/a parent = None # Parent node pointer, or None
45n/a children = () # Tuple of subnodes
46n/a was_changed = False
47n/a was_checked = False
48n/a
49n/a def __new__(cls, *args, **kwds):
50n/a """Constructor that prevents Base from being instantiated."""
51n/a assert cls is not Base, "Cannot instantiate Base"
52n/a return object.__new__(cls)
53n/a
54n/a def __eq__(self, other):
55n/a """
56n/a Compare two nodes for equality.
57n/a
58n/a This calls the method _eq().
59n/a """
60n/a if self.__class__ is not other.__class__:
61n/a return NotImplemented
62n/a return self._eq(other)
63n/a
64n/a __hash__ = None # For Py3 compatibility.
65n/a
66n/a def _eq(self, other):
67n/a """
68n/a Compare two nodes for equality.
69n/a
70n/a This is called by __eq__ and __ne__. It is only called if the two nodes
71n/a have the same type. This must be implemented by the concrete subclass.
72n/a Nodes should be considered equal if they have the same structure,
73n/a ignoring the prefix string and other context information.
74n/a """
75n/a raise NotImplementedError
76n/a
77n/a def clone(self):
78n/a """
79n/a Return a cloned (deep) copy of self.
80n/a
81n/a This must be implemented by the concrete subclass.
82n/a """
83n/a raise NotImplementedError
84n/a
85n/a def post_order(self):
86n/a """
87n/a Return a post-order iterator for the tree.
88n/a
89n/a This must be implemented by the concrete subclass.
90n/a """
91n/a raise NotImplementedError
92n/a
93n/a def pre_order(self):
94n/a """
95n/a Return a pre-order iterator for the tree.
96n/a
97n/a This must be implemented by the concrete subclass.
98n/a """
99n/a raise NotImplementedError
100n/a
101n/a def replace(self, new):
102n/a """Replace this node with a new one in the parent."""
103n/a assert self.parent is not None, str(self)
104n/a assert new is not None
105n/a if not isinstance(new, list):
106n/a new = [new]
107n/a l_children = []
108n/a found = False
109n/a for ch in self.parent.children:
110n/a if ch is self:
111n/a assert not found, (self.parent.children, self, new)
112n/a if new is not None:
113n/a l_children.extend(new)
114n/a found = True
115n/a else:
116n/a l_children.append(ch)
117n/a assert found, (self.children, self, new)
118n/a self.parent.changed()
119n/a self.parent.children = l_children
120n/a for x in new:
121n/a x.parent = self.parent
122n/a self.parent = None
123n/a
124n/a def get_lineno(self):
125n/a """Return the line number which generated the invocant node."""
126n/a node = self
127n/a while not isinstance(node, Leaf):
128n/a if not node.children:
129n/a return
130n/a node = node.children[0]
131n/a return node.lineno
132n/a
133n/a def changed(self):
134n/a if self.parent:
135n/a self.parent.changed()
136n/a self.was_changed = True
137n/a
138n/a def remove(self):
139n/a """
140n/a Remove the node from the tree. Returns the position of the node in its
141n/a parent's children before it was removed.
142n/a """
143n/a if self.parent:
144n/a for i, node in enumerate(self.parent.children):
145n/a if node is self:
146n/a self.parent.changed()
147n/a del self.parent.children[i]
148n/a self.parent = None
149n/a return i
150n/a
151n/a @property
152n/a def next_sibling(self):
153n/a """
154n/a The node immediately following the invocant in their parent's children
155n/a list. If the invocant does not have a next sibling, it is None
156n/a """
157n/a if self.parent is None:
158n/a return None
159n/a
160n/a # Can't use index(); we need to test by identity
161n/a for i, child in enumerate(self.parent.children):
162n/a if child is self:
163n/a try:
164n/a return self.parent.children[i+1]
165n/a except IndexError:
166n/a return None
167n/a
168n/a @property
169n/a def prev_sibling(self):
170n/a """
171n/a The node immediately preceding the invocant in their parent's children
172n/a list. If the invocant does not have a previous sibling, it is None.
173n/a """
174n/a if self.parent is None:
175n/a return None
176n/a
177n/a # Can't use index(); we need to test by identity
178n/a for i, child in enumerate(self.parent.children):
179n/a if child is self:
180n/a if i == 0:
181n/a return None
182n/a return self.parent.children[i-1]
183n/a
184n/a def leaves(self):
185n/a for child in self.children:
186n/a yield from child.leaves()
187n/a
188n/a def depth(self):
189n/a if self.parent is None:
190n/a return 0
191n/a return 1 + self.parent.depth()
192n/a
193n/a def get_suffix(self):
194n/a """
195n/a Return the string immediately following the invocant node. This is
196n/a effectively equivalent to node.next_sibling.prefix
197n/a """
198n/a next_sib = self.next_sibling
199n/a if next_sib is None:
200n/a return ""
201n/a return next_sib.prefix
202n/a
203n/a if sys.version_info < (3, 0):
204n/a def __str__(self):
205n/a return str(self).encode("ascii")
206n/a
207n/aclass Node(Base):
208n/a
209n/a """Concrete implementation for interior nodes."""
210n/a
211n/a def __init__(self,type, children,
212n/a context=None,
213n/a prefix=None,
214n/a fixers_applied=None):
215n/a """
216n/a Initializer.
217n/a
218n/a Takes a type constant (a symbol number >= 256), a sequence of
219n/a child nodes, and an optional context keyword argument.
220n/a
221n/a As a side effect, the parent pointers of the children are updated.
222n/a """
223n/a assert type >= 256, type
224n/a self.type = type
225n/a self.children = list(children)
226n/a for ch in self.children:
227n/a assert ch.parent is None, repr(ch)
228n/a ch.parent = self
229n/a if prefix is not None:
230n/a self.prefix = prefix
231n/a if fixers_applied:
232n/a self.fixers_applied = fixers_applied[:]
233n/a else:
234n/a self.fixers_applied = None
235n/a
236n/a def __repr__(self):
237n/a """Return a canonical string representation."""
238n/a return "%s(%s, %r)" % (self.__class__.__name__,
239n/a type_repr(self.type),
240n/a self.children)
241n/a
242n/a def __unicode__(self):
243n/a """
244n/a Return a pretty string representation.
245n/a
246n/a This reproduces the input source exactly.
247n/a """
248n/a return "".join(map(str, self.children))
249n/a
250n/a if sys.version_info > (3, 0):
251n/a __str__ = __unicode__
252n/a
253n/a def _eq(self, other):
254n/a """Compare two nodes for equality."""
255n/a return (self.type, self.children) == (other.type, other.children)
256n/a
257n/a def clone(self):
258n/a """Return a cloned (deep) copy of self."""
259n/a return Node(self.type, [ch.clone() for ch in self.children],
260n/a fixers_applied=self.fixers_applied)
261n/a
262n/a def post_order(self):
263n/a """Return a post-order iterator for the tree."""
264n/a for child in self.children:
265n/a yield from child.post_order()
266n/a yield self
267n/a
268n/a def pre_order(self):
269n/a """Return a pre-order iterator for the tree."""
270n/a yield self
271n/a for child in self.children:
272n/a yield from child.pre_order()
273n/a
274n/a def _prefix_getter(self):
275n/a """
276n/a The whitespace and comments preceding this node in the input.
277n/a """
278n/a if not self.children:
279n/a return ""
280n/a return self.children[0].prefix
281n/a
282n/a def _prefix_setter(self, prefix):
283n/a if self.children:
284n/a self.children[0].prefix = prefix
285n/a
286n/a prefix = property(_prefix_getter, _prefix_setter)
287n/a
288n/a def set_child(self, i, child):
289n/a """
290n/a Equivalent to 'node.children[i] = child'. This method also sets the
291n/a child's parent attribute appropriately.
292n/a """
293n/a child.parent = self
294n/a self.children[i].parent = None
295n/a self.children[i] = child
296n/a self.changed()
297n/a
298n/a def insert_child(self, i, child):
299n/a """
300n/a Equivalent to 'node.children.insert(i, child)'. This method also sets
301n/a the child's parent attribute appropriately.
302n/a """
303n/a child.parent = self
304n/a self.children.insert(i, child)
305n/a self.changed()
306n/a
307n/a def append_child(self, child):
308n/a """
309n/a Equivalent to 'node.children.append(child)'. This method also sets the
310n/a child's parent attribute appropriately.
311n/a """
312n/a child.parent = self
313n/a self.children.append(child)
314n/a self.changed()
315n/a
316n/a
317n/aclass Leaf(Base):
318n/a
319n/a """Concrete implementation for leaf nodes."""
320n/a
321n/a # Default values for instance variables
322n/a _prefix = "" # Whitespace and comments preceding this token in the input
323n/a lineno = 0 # Line where this token starts in the input
324n/a column = 0 # Column where this token tarts in the input
325n/a
326n/a def __init__(self, type, value,
327n/a context=None,
328n/a prefix=None,
329n/a fixers_applied=[]):
330n/a """
331n/a Initializer.
332n/a
333n/a Takes a type constant (a token number < 256), a string value, and an
334n/a optional context keyword argument.
335n/a """
336n/a assert 0 <= type < 256, type
337n/a if context is not None:
338n/a self._prefix, (self.lineno, self.column) = context
339n/a self.type = type
340n/a self.value = value
341n/a if prefix is not None:
342n/a self._prefix = prefix
343n/a self.fixers_applied = fixers_applied[:]
344n/a
345n/a def __repr__(self):
346n/a """Return a canonical string representation."""
347n/a return "%s(%r, %r)" % (self.__class__.__name__,
348n/a self.type,
349n/a self.value)
350n/a
351n/a def __unicode__(self):
352n/a """
353n/a Return a pretty string representation.
354n/a
355n/a This reproduces the input source exactly.
356n/a """
357n/a return self.prefix + str(self.value)
358n/a
359n/a if sys.version_info > (3, 0):
360n/a __str__ = __unicode__
361n/a
362n/a def _eq(self, other):
363n/a """Compare two nodes for equality."""
364n/a return (self.type, self.value) == (other.type, other.value)
365n/a
366n/a def clone(self):
367n/a """Return a cloned (deep) copy of self."""
368n/a return Leaf(self.type, self.value,
369n/a (self.prefix, (self.lineno, self.column)),
370n/a fixers_applied=self.fixers_applied)
371n/a
372n/a def leaves(self):
373n/a yield self
374n/a
375n/a def post_order(self):
376n/a """Return a post-order iterator for the tree."""
377n/a yield self
378n/a
379n/a def pre_order(self):
380n/a """Return a pre-order iterator for the tree."""
381n/a yield self
382n/a
383n/a def _prefix_getter(self):
384n/a """
385n/a The whitespace and comments preceding this token in the input.
386n/a """
387n/a return self._prefix
388n/a
389n/a def _prefix_setter(self, prefix):
390n/a self.changed()
391n/a self._prefix = prefix
392n/a
393n/a prefix = property(_prefix_getter, _prefix_setter)
394n/a
395n/adef convert(gr, raw_node):
396n/a """
397n/a Convert raw node information to a Node or Leaf instance.
398n/a
399n/a This is passed to the parser driver which calls it whenever a reduction of a
400n/a grammar rule produces a new complete node, so that the tree is build
401n/a strictly bottom-up.
402n/a """
403n/a type, value, context, children = raw_node
404n/a if children or type in gr.number2symbol:
405n/a # If there's exactly one child, return that child instead of
406n/a # creating a new node.
407n/a if len(children) == 1:
408n/a return children[0]
409n/a return Node(type, children, context=context)
410n/a else:
411n/a return Leaf(type, value, context=context)
412n/a
413n/a
414n/aclass BasePattern(object):
415n/a
416n/a """
417n/a A pattern is a tree matching pattern.
418n/a
419n/a It looks for a specific node type (token or symbol), and
420n/a optionally for a specific content.
421n/a
422n/a This is an abstract base class. There are three concrete
423n/a subclasses:
424n/a
425n/a - LeafPattern matches a single leaf node;
426n/a - NodePattern matches a single node (usually non-leaf);
427n/a - WildcardPattern matches a sequence of nodes of variable length.
428n/a """
429n/a
430n/a # Defaults for instance variables
431n/a type = None # Node type (token if < 256, symbol if >= 256)
432n/a content = None # Optional content matching pattern
433n/a name = None # Optional name used to store match in results dict
434n/a
435n/a def __new__(cls, *args, **kwds):
436n/a """Constructor that prevents BasePattern from being instantiated."""
437n/a assert cls is not BasePattern, "Cannot instantiate BasePattern"
438n/a return object.__new__(cls)
439n/a
440n/a def __repr__(self):
441n/a args = [type_repr(self.type), self.content, self.name]
442n/a while args and args[-1] is None:
443n/a del args[-1]
444n/a return "%s(%s)" % (self.__class__.__name__, ", ".join(map(repr, args)))
445n/a
446n/a def optimize(self):
447n/a """
448n/a A subclass can define this as a hook for optimizations.
449n/a
450n/a Returns either self or another node with the same effect.
451n/a """
452n/a return self
453n/a
454n/a def match(self, node, results=None):
455n/a """
456n/a Does this pattern exactly match a node?
457n/a
458n/a Returns True if it matches, False if not.
459n/a
460n/a If results is not None, it must be a dict which will be
461n/a updated with the nodes matching named subpatterns.
462n/a
463n/a Default implementation for non-wildcard patterns.
464n/a """
465n/a if self.type is not None and node.type != self.type:
466n/a return False
467n/a if self.content is not None:
468n/a r = None
469n/a if results is not None:
470n/a r = {}
471n/a if not self._submatch(node, r):
472n/a return False
473n/a if r:
474n/a results.update(r)
475n/a if results is not None and self.name:
476n/a results[self.name] = node
477n/a return True
478n/a
479n/a def match_seq(self, nodes, results=None):
480n/a """
481n/a Does this pattern exactly match a sequence of nodes?
482n/a
483n/a Default implementation for non-wildcard patterns.
484n/a """
485n/a if len(nodes) != 1:
486n/a return False
487n/a return self.match(nodes[0], results)
488n/a
489n/a def generate_matches(self, nodes):
490n/a """
491n/a Generator yielding all matches for this pattern.
492n/a
493n/a Default implementation for non-wildcard patterns.
494n/a """
495n/a r = {}
496n/a if nodes and self.match(nodes[0], r):
497n/a yield 1, r
498n/a
499n/a
500n/aclass LeafPattern(BasePattern):
501n/a
502n/a def __init__(self, type=None, content=None, name=None):
503n/a """
504n/a Initializer. Takes optional type, content, and name.
505n/a
506n/a The type, if given must be a token type (< 256). If not given,
507n/a this matches any *leaf* node; the content may still be required.
508n/a
509n/a The content, if given, must be a string.
510n/a
511n/a If a name is given, the matching node is stored in the results
512n/a dict under that key.
513n/a """
514n/a if type is not None:
515n/a assert 0 <= type < 256, type
516n/a if content is not None:
517n/a assert isinstance(content, str), repr(content)
518n/a self.type = type
519n/a self.content = content
520n/a self.name = name
521n/a
522n/a def match(self, node, results=None):
523n/a """Override match() to insist on a leaf node."""
524n/a if not isinstance(node, Leaf):
525n/a return False
526n/a return BasePattern.match(self, node, results)
527n/a
528n/a def _submatch(self, node, results=None):
529n/a """
530n/a Match the pattern's content to the node's children.
531n/a
532n/a This assumes the node type matches and self.content is not None.
533n/a
534n/a Returns True if it matches, False if not.
535n/a
536n/a If results is not None, it must be a dict which will be
537n/a updated with the nodes matching named subpatterns.
538n/a
539n/a When returning False, the results dict may still be updated.
540n/a """
541n/a return self.content == node.value
542n/a
543n/a
544n/aclass NodePattern(BasePattern):
545n/a
546n/a wildcards = False
547n/a
548n/a def __init__(self, type=None, content=None, name=None):
549n/a """
550n/a Initializer. Takes optional type, content, and name.
551n/a
552n/a The type, if given, must be a symbol type (>= 256). If the
553n/a type is None this matches *any* single node (leaf or not),
554n/a except if content is not None, in which it only matches
555n/a non-leaf nodes that also match the content pattern.
556n/a
557n/a The content, if not None, must be a sequence of Patterns that
558n/a must match the node's children exactly. If the content is
559n/a given, the type must not be None.
560n/a
561n/a If a name is given, the matching node is stored in the results
562n/a dict under that key.
563n/a """
564n/a if type is not None:
565n/a assert type >= 256, type
566n/a if content is not None:
567n/a assert not isinstance(content, str), repr(content)
568n/a content = list(content)
569n/a for i, item in enumerate(content):
570n/a assert isinstance(item, BasePattern), (i, item)
571n/a if isinstance(item, WildcardPattern):
572n/a self.wildcards = True
573n/a self.type = type
574n/a self.content = content
575n/a self.name = name
576n/a
577n/a def _submatch(self, node, results=None):
578n/a """
579n/a Match the pattern's content to the node's children.
580n/a
581n/a This assumes the node type matches and self.content is not None.
582n/a
583n/a Returns True if it matches, False if not.
584n/a
585n/a If results is not None, it must be a dict which will be
586n/a updated with the nodes matching named subpatterns.
587n/a
588n/a When returning False, the results dict may still be updated.
589n/a """
590n/a if self.wildcards:
591n/a for c, r in generate_matches(self.content, node.children):
592n/a if c == len(node.children):
593n/a if results is not None:
594n/a results.update(r)
595n/a return True
596n/a return False
597n/a if len(self.content) != len(node.children):
598n/a return False
599n/a for subpattern, child in zip(self.content, node.children):
600n/a if not subpattern.match(child, results):
601n/a return False
602n/a return True
603n/a
604n/a
605n/aclass WildcardPattern(BasePattern):
606n/a
607n/a """
608n/a A wildcard pattern can match zero or more nodes.
609n/a
610n/a This has all the flexibility needed to implement patterns like:
611n/a
612n/a .* .+ .? .{m,n}
613n/a (a b c | d e | f)
614n/a (...)* (...)+ (...)? (...){m,n}
615n/a
616n/a except it always uses non-greedy matching.
617n/a """
618n/a
619n/a def __init__(self, content=None, min=0, max=HUGE, name=None):
620n/a """
621n/a Initializer.
622n/a
623n/a Args:
624n/a content: optional sequence of subsequences of patterns;
625n/a if absent, matches one node;
626n/a if present, each subsequence is an alternative [*]
627n/a min: optional minimum number of times to match, default 0
628n/a max: optional maximum number of times to match, default HUGE
629n/a name: optional name assigned to this match
630n/a
631n/a [*] Thus, if content is [[a, b, c], [d, e], [f, g, h]] this is
632n/a equivalent to (a b c | d e | f g h); if content is None,
633n/a this is equivalent to '.' in regular expression terms.
634n/a The min and max parameters work as follows:
635n/a min=0, max=maxint: .*
636n/a min=1, max=maxint: .+
637n/a min=0, max=1: .?
638n/a min=1, max=1: .
639n/a If content is not None, replace the dot with the parenthesized
640n/a list of alternatives, e.g. (a b c | d e | f g h)*
641n/a """
642n/a assert 0 <= min <= max <= HUGE, (min, max)
643n/a if content is not None:
644n/a content = tuple(map(tuple, content)) # Protect against alterations
645n/a # Check sanity of alternatives
646n/a assert len(content), repr(content) # Can't have zero alternatives
647n/a for alt in content:
648n/a assert len(alt), repr(alt) # Can have empty alternatives
649n/a self.content = content
650n/a self.min = min
651n/a self.max = max
652n/a self.name = name
653n/a
654n/a def optimize(self):
655n/a """Optimize certain stacked wildcard patterns."""
656n/a subpattern = None
657n/a if (self.content is not None and
658n/a len(self.content) == 1 and len(self.content[0]) == 1):
659n/a subpattern = self.content[0][0]
660n/a if self.min == 1 and self.max == 1:
661n/a if self.content is None:
662n/a return NodePattern(name=self.name)
663n/a if subpattern is not None and self.name == subpattern.name:
664n/a return subpattern.optimize()
665n/a if (self.min <= 1 and isinstance(subpattern, WildcardPattern) and
666n/a subpattern.min <= 1 and self.name == subpattern.name):
667n/a return WildcardPattern(subpattern.content,
668n/a self.min*subpattern.min,
669n/a self.max*subpattern.max,
670n/a subpattern.name)
671n/a return self
672n/a
673n/a def match(self, node, results=None):
674n/a """Does this pattern exactly match a node?"""
675n/a return self.match_seq([node], results)
676n/a
677n/a def match_seq(self, nodes, results=None):
678n/a """Does this pattern exactly match a sequence of nodes?"""
679n/a for c, r in self.generate_matches(nodes):
680n/a if c == len(nodes):
681n/a if results is not None:
682n/a results.update(r)
683n/a if self.name:
684n/a results[self.name] = list(nodes)
685n/a return True
686n/a return False
687n/a
688n/a def generate_matches(self, nodes):
689n/a """
690n/a Generator yielding matches for a sequence of nodes.
691n/a
692n/a Args:
693n/a nodes: sequence of nodes
694n/a
695n/a Yields:
696n/a (count, results) tuples where:
697n/a count: the match comprises nodes[:count];
698n/a results: dict containing named submatches.
699n/a """
700n/a if self.content is None:
701n/a # Shortcut for special case (see __init__.__doc__)
702n/a for count in range(self.min, 1 + min(len(nodes), self.max)):
703n/a r = {}
704n/a if self.name:
705n/a r[self.name] = nodes[:count]
706n/a yield count, r
707n/a elif self.name == "bare_name":
708n/a yield self._bare_name_matches(nodes)
709n/a else:
710n/a # The reason for this is that hitting the recursion limit usually
711n/a # results in some ugly messages about how RuntimeErrors are being
712n/a # ignored. We only have to do this on CPython, though, because other
713n/a # implementations don't have this nasty bug in the first place.
714n/a if hasattr(sys, "getrefcount"):
715n/a save_stderr = sys.stderr
716n/a sys.stderr = StringIO()
717n/a try:
718n/a for count, r in self._recursive_matches(nodes, 0):
719n/a if self.name:
720n/a r[self.name] = nodes[:count]
721n/a yield count, r
722n/a except RuntimeError:
723n/a # We fall back to the iterative pattern matching scheme if the recursive
724n/a # scheme hits the recursion limit.
725n/a for count, r in self._iterative_matches(nodes):
726n/a if self.name:
727n/a r[self.name] = nodes[:count]
728n/a yield count, r
729n/a finally:
730n/a if hasattr(sys, "getrefcount"):
731n/a sys.stderr = save_stderr
732n/a
733n/a def _iterative_matches(self, nodes):
734n/a """Helper to iteratively yield the matches."""
735n/a nodelen = len(nodes)
736n/a if 0 >= self.min:
737n/a yield 0, {}
738n/a
739n/a results = []
740n/a # generate matches that use just one alt from self.content
741n/a for alt in self.content:
742n/a for c, r in generate_matches(alt, nodes):
743n/a yield c, r
744n/a results.append((c, r))
745n/a
746n/a # for each match, iterate down the nodes
747n/a while results:
748n/a new_results = []
749n/a for c0, r0 in results:
750n/a # stop if the entire set of nodes has been matched
751n/a if c0 < nodelen and c0 <= self.max:
752n/a for alt in self.content:
753n/a for c1, r1 in generate_matches(alt, nodes[c0:]):
754n/a if c1 > 0:
755n/a r = {}
756n/a r.update(r0)
757n/a r.update(r1)
758n/a yield c0 + c1, r
759n/a new_results.append((c0 + c1, r))
760n/a results = new_results
761n/a
762n/a def _bare_name_matches(self, nodes):
763n/a """Special optimized matcher for bare_name."""
764n/a count = 0
765n/a r = {}
766n/a done = False
767n/a max = len(nodes)
768n/a while not done and count < max:
769n/a done = True
770n/a for leaf in self.content:
771n/a if leaf[0].match(nodes[count], r):
772n/a count += 1
773n/a done = False
774n/a break
775n/a r[self.name] = nodes[:count]
776n/a return count, r
777n/a
778n/a def _recursive_matches(self, nodes, count):
779n/a """Helper to recursively yield the matches."""
780n/a assert self.content is not None
781n/a if count >= self.min:
782n/a yield 0, {}
783n/a if count < self.max:
784n/a for alt in self.content:
785n/a for c0, r0 in generate_matches(alt, nodes):
786n/a for c1, r1 in self._recursive_matches(nodes[c0:], count+1):
787n/a r = {}
788n/a r.update(r0)
789n/a r.update(r1)
790n/a yield c0 + c1, r
791n/a
792n/a
793n/aclass NegatedPattern(BasePattern):
794n/a
795n/a def __init__(self, content=None):
796n/a """
797n/a Initializer.
798n/a
799n/a The argument is either a pattern or None. If it is None, this
800n/a only matches an empty sequence (effectively '$' in regex
801n/a lingo). If it is not None, this matches whenever the argument
802n/a pattern doesn't have any matches.
803n/a """
804n/a if content is not None:
805n/a assert isinstance(content, BasePattern), repr(content)
806n/a self.content = content
807n/a
808n/a def match(self, node):
809n/a # We never match a node in its entirety
810n/a return False
811n/a
812n/a def match_seq(self, nodes):
813n/a # We only match an empty sequence of nodes in its entirety
814n/a return len(nodes) == 0
815n/a
816n/a def generate_matches(self, nodes):
817n/a if self.content is None:
818n/a # Return a match if there is an empty sequence
819n/a if len(nodes) == 0:
820n/a yield 0, {}
821n/a else:
822n/a # Return a match if the argument pattern has no matches
823n/a for c, r in self.content.generate_matches(nodes):
824n/a return
825n/a yield 0, {}
826n/a
827n/a
828n/adef generate_matches(patterns, nodes):
829n/a """
830n/a Generator yielding matches for a sequence of patterns and nodes.
831n/a
832n/a Args:
833n/a patterns: a sequence of patterns
834n/a nodes: a sequence of nodes
835n/a
836n/a Yields:
837n/a (count, results) tuples where:
838n/a count: the entire sequence of patterns matches nodes[:count];
839n/a results: dict containing named submatches.
840n/a """
841n/a if not patterns:
842n/a yield 0, {}
843n/a else:
844n/a p, rest = patterns[0], patterns[1:]
845n/a for c0, r0 in p.generate_matches(nodes):
846n/a if not rest:
847n/a yield c0, r0
848n/a else:
849n/a for c1, r1 in generate_matches(rest, nodes[c0:]):
850n/a r = {}
851n/a r.update(r0)
852n/a r.update(r1)
853n/a yield c0 + c1, r