]> git.madduck.net Git - etc/vim.git/blob - blib2to3/pytree.py

madduck's git repository

Every one of the projects in this repository is available at the canonical URL git://git.madduck.net/madduck/pub/<projectpath> — see each project's metadata for the exact URL.

All patches and comments are welcome. Please squash your changes to logical commits before using git-format-patch and git-send-email to patches@git.madduck.net. If you'd read over the Git project's submission guidelines and adhered to them, I'd be especially grateful.

SSH access, as well as push access can be individually arranged.

If you use my repositories frequently, consider adding the following snippet to ~/.gitconfig and using the third clone URL listed for each project:

[url "git://git.madduck.net/madduck/"]
  insteadOf = madduck:

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