Python code coverage for Lib/lib2to3/pytree.py

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