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