Python code coverage for Lib/lib2to3/btm_utils.py

#	count	content
1	n/a	"Utility functions used by the btm_matcher module"
2	n/a
3	n/a	from . import pytree
4	n/a	from .pgen2 import grammar, token
5	n/a	from .pygram import pattern_symbols, python_symbols
6	n/a
7	n/a	syms = pattern_symbols
8	n/a	pysyms = python_symbols
9	n/a	tokens = grammar.opmap
10	n/a	token_labels = token
11	n/a
12	n/a	TYPE_ANY = -1
13	n/a	TYPE_ALTERNATIVES = -2
14	n/a	TYPE_GROUP = -3
15	n/a
16	n/a	class MinNode(object):
17	n/a	"""This class serves as an intermediate representation of the
18	n/a	pattern tree during the conversion to sets of leaf-to-root
19	n/a	subpatterns"""
20	n/a
21	n/a	def __init__(self, type=None, name=None):
22	n/a	self.type = type
23	n/a	self.name = name
24	n/a	self.children = []
25	n/a	self.leaf = False
26	n/a	self.parent = None
27	n/a	self.alternatives = []
28	n/a	self.group = []
29	n/a
30	n/a	def __repr__(self):
31	n/a	return str(self.type) + ' ' + str(self.name)
32	n/a
33	n/a	def leaf_to_root(self):
34	n/a	"""Internal method. Returns a characteristic path of the
35	n/a	pattern tree. This method must be run for all leaves until the
36	n/a	linear subpatterns are merged into a single"""
37	n/a	node = self
38	n/a	subp = []
39	n/a	while node:
40	n/a	if node.type == TYPE_ALTERNATIVES:
41	n/a	node.alternatives.append(subp)
42	n/a	if len(node.alternatives) == len(node.children):
43	n/a	#last alternative
44	n/a	subp = [tuple(node.alternatives)]
45	n/a	node.alternatives = []
46	n/a	node = node.parent
47	n/a	continue
48	n/a	else:
49	n/a	node = node.parent
50	n/a	subp = None
51	n/a	break
52	n/a
53	n/a	if node.type == TYPE_GROUP:
54	n/a	node.group.append(subp)
55	n/a	#probably should check the number of leaves
56	n/a	if len(node.group) == len(node.children):
57	n/a	subp = get_characteristic_subpattern(node.group)
58	n/a	node.group = []
59	n/a	node = node.parent
60	n/a	continue
61	n/a	else:
62	n/a	node = node.parent
63	n/a	subp = None
64	n/a	break
65	n/a
66	n/a	if node.type == token_labels.NAME and node.name:
67	n/a	#in case of type=name, use the name instead
68	n/a	subp.append(node.name)
69	n/a	else:
70	n/a	subp.append(node.type)
71	n/a
72	n/a	node = node.parent
73	n/a	return subp
74	n/a
75	n/a	def get_linear_subpattern(self):
76	n/a	"""Drives the leaf_to_root method. The reason that
77	n/a	leaf_to_root must be run multiple times is because we need to
78	n/a	reject 'group' matches; for example the alternative form
79	n/a	(a \| b c) creates a group [b c] that needs to be matched. Since
80	n/a	matching multiple linear patterns overcomes the automaton's
81	n/a	capabilities, leaf_to_root merges each group into a single
82	n/a	choice based on 'characteristic'ity,
83	n/a
84	n/a	i.e. (a\|b c) -> (a\|b) if b more characteristic than c
85	n/a
86	n/a	Returns: The most 'characteristic'(as defined by
87	n/a	get_characteristic_subpattern) path for the compiled pattern
88	n/a	tree.
89	n/a	"""
90	n/a
91	n/a	for l in self.leaves():
92	n/a	subp = l.leaf_to_root()
93	n/a	if subp:
94	n/a	return subp
95	n/a
96	n/a	def leaves(self):
97	n/a	"Generator that returns the leaves of the tree"
98	n/a	for child in self.children:
99	n/a	yield from child.leaves()
100	n/a	if not self.children:
101	n/a	yield self
102	n/a
103	n/a	def reduce_tree(node, parent=None):
104	n/a	"""
105	n/a	Internal function. Reduces a compiled pattern tree to an
106	n/a	intermediate representation suitable for feeding the
107	n/a	automaton. This also trims off any optional pattern elements(like
108	n/a	[a], a*).
109	n/a	"""
110	n/a
111	n/a	new_node = None
112	n/a	#switch on the node type
113	n/a	if node.type == syms.Matcher:
114	n/a	#skip
115	n/a	node = node.children[0]
116	n/a
117	n/a	if node.type == syms.Alternatives :
118	n/a	#2 cases
119	n/a	if len(node.children) <= 2:
120	n/a	#just a single 'Alternative', skip this node
121	n/a	new_node = reduce_tree(node.children[0], parent)
122	n/a	else:
123	n/a	#real alternatives
124	n/a	new_node = MinNode(type=TYPE_ALTERNATIVES)
125	n/a	#skip odd children('\|' tokens)
126	n/a	for child in node.children:
127	n/a	if node.children.index(child)%2:
128	n/a	continue
129	n/a	reduced = reduce_tree(child, new_node)
130	n/a	if reduced is not None:
131	n/a	new_node.children.append(reduced)
132	n/a	elif node.type == syms.Alternative:
133	n/a	if len(node.children) > 1:
134	n/a
135	n/a	new_node = MinNode(type=TYPE_GROUP)
136	n/a	for child in node.children:
137	n/a	reduced = reduce_tree(child, new_node)
138	n/a	if reduced:
139	n/a	new_node.children.append(reduced)
140	n/a	if not new_node.children:
141	n/a	# delete the group if all of the children were reduced to None
142	n/a	new_node = None
143	n/a
144	n/a	else:
145	n/a	new_node = reduce_tree(node.children[0], parent)
146	n/a
147	n/a	elif node.type == syms.Unit:
148	n/a	if (isinstance(node.children[0], pytree.Leaf) and
149	n/a	node.children[0].value == '('):
150	n/a	#skip parentheses
151	n/a	return reduce_tree(node.children[1], parent)
152	n/a	if ((isinstance(node.children[0], pytree.Leaf) and
153	n/a	node.children[0].value == '[')
154	n/a	or
155	n/a	(len(node.children)>1 and
156	n/a	hasattr(node.children[1], "value") and
157	n/a	node.children[1].value == '[')):
158	n/a	#skip whole unit if its optional
159	n/a	return None
160	n/a
161	n/a	leaf = True
162	n/a	details_node = None
163	n/a	alternatives_node = None
164	n/a	has_repeater = False
165	n/a	repeater_node = None
166	n/a	has_variable_name = False
167	n/a
168	n/a	for child in node.children:
169	n/a	if child.type == syms.Details:
170	n/a	leaf = False
171	n/a	details_node = child
172	n/a	elif child.type == syms.Repeater:
173	n/a	has_repeater = True
174	n/a	repeater_node = child
175	n/a	elif child.type == syms.Alternatives:
176	n/a	alternatives_node = child
177	n/a	if hasattr(child, 'value') and child.value == '=': # variable name
178	n/a	has_variable_name = True
179	n/a
180	n/a	#skip variable name
181	n/a	if has_variable_name:
182	n/a	#skip variable name, '='
183	n/a	name_leaf = node.children[2]
184	n/a	if hasattr(name_leaf, 'value') and name_leaf.value == '(':
185	n/a	# skip parenthesis
186	n/a	name_leaf = node.children[3]
187	n/a	else:
188	n/a	name_leaf = node.children[0]
189	n/a
190	n/a	#set node type
191	n/a	if name_leaf.type == token_labels.NAME:
192	n/a	#(python) non-name or wildcard
193	n/a	if name_leaf.value == 'any':
194	n/a	new_node = MinNode(type=TYPE_ANY)
195	n/a	else:
196	n/a	if hasattr(token_labels, name_leaf.value):
197	n/a	new_node = MinNode(type=getattr(token_labels, name_leaf.value))
198	n/a	else:
199	n/a	new_node = MinNode(type=getattr(pysyms, name_leaf.value))
200	n/a
201	n/a	elif name_leaf.type == token_labels.STRING:
202	n/a	#(python) name or character; remove the apostrophes from
203	n/a	#the string value
204	n/a	name = name_leaf.value.strip("'")
205	n/a	if name in tokens:
206	n/a	new_node = MinNode(type=tokens[name])
207	n/a	else:
208	n/a	new_node = MinNode(type=token_labels.NAME, name=name)
209	n/a	elif name_leaf.type == syms.Alternatives:
210	n/a	new_node = reduce_tree(alternatives_node, parent)
211	n/a
212	n/a	#handle repeaters
213	n/a	if has_repeater:
214	n/a	if repeater_node.children[0].value == '*':
215	n/a	#reduce to None
216	n/a	new_node = None
217	n/a	elif repeater_node.children[0].value == '+':
218	n/a	#reduce to a single occurrence i.e. do nothing
219	n/a	pass
220	n/a	else:
221	n/a	#TODO: handle {min, max} repeaters
222	n/a	raise NotImplementedError
223	n/a	pass
224	n/a
225	n/a	#add children
226	n/a	if details_node and new_node is not None:
227	n/a	for child in details_node.children[1:-1]:
228	n/a	#skip '<', '>' markers
229	n/a	reduced = reduce_tree(child, new_node)
230	n/a	if reduced is not None:
231	n/a	new_node.children.append(reduced)
232	n/a	if new_node:
233	n/a	new_node.parent = parent
234	n/a	return new_node
235	n/a
236	n/a
237	n/a	def get_characteristic_subpattern(subpatterns):
238	n/a	"""Picks the most characteristic from a list of linear patterns
239	n/a	Current order used is:
240	n/a	names > common_names > common_chars
241	n/a	"""
242	n/a	if not isinstance(subpatterns, list):
243	n/a	return subpatterns
244	n/a	if len(subpatterns)==1:
245	n/a	return subpatterns[0]
246	n/a
247	n/a	# first pick out the ones containing variable names
248	n/a	subpatterns_with_names = []
249	n/a	subpatterns_with_common_names = []
250	n/a	common_names = ['in', 'for', 'if' , 'not', 'None']
251	n/a	subpatterns_with_common_chars = []
252	n/a	common_chars = "[]().,:"
253	n/a	for subpattern in subpatterns:
254	n/a	if any(rec_test(subpattern, lambda x: type(x) is str)):
255	n/a	if any(rec_test(subpattern,
256	n/a	lambda x: isinstance(x, str) and x in common_chars)):
257	n/a	subpatterns_with_common_chars.append(subpattern)
258	n/a	elif any(rec_test(subpattern,
259	n/a	lambda x: isinstance(x, str) and x in common_names)):
260	n/a	subpatterns_with_common_names.append(subpattern)
261	n/a
262	n/a	else:
263	n/a	subpatterns_with_names.append(subpattern)
264	n/a
265	n/a	if subpatterns_with_names:
266	n/a	subpatterns = subpatterns_with_names
267	n/a	elif subpatterns_with_common_names:
268	n/a	subpatterns = subpatterns_with_common_names
269	n/a	elif subpatterns_with_common_chars:
270	n/a	subpatterns = subpatterns_with_common_chars
271	n/a	# of the remaining subpatterns pick out the longest one
272	n/a	return max(subpatterns, key=len)
273	n/a
274	n/a	def rec_test(sequence, test_func):
275	n/a	"""Tests test_func on all items of sequence and items of included
276	n/a	sub-iterables"""
277	n/a	for x in sequence:
278	n/a	if isinstance(x, (list, tuple)):
279	n/a	yield from rec_test(x, test_func)
280	n/a	else:
281	n/a	yield test_func(x)