Python code coverage for Parser/asdl.py

#	count	content
1	n/a	#-------------------------------------------------------------------------------
2	n/a	# Parser for ASDL [1] definition files. Reads in an ASDL description and parses
3	n/a	# it into an AST that describes it.
4	n/a	#
5	n/a	# The EBNF we're parsing here: Figure 1 of the paper [1]. Extended to support
6	n/a	# modules and attributes after a product. Words starting with Capital letters
7	n/a	# are terminals. Literal tokens are in "double quotes". Others are
8	n/a	# non-terminals. Id is either TokenId or ConstructorId.
9	n/a	#
10	n/a	# module ::= "module" Id "{" [definitions] "}"
11	n/a	# definitions ::= { TypeId "=" type }
12	n/a	# type ::= product \| sum
13	n/a	# product ::= fields ["attributes" fields]
14	n/a	# fields ::= "(" { field, "," } field ")"
15	n/a	# field ::= TypeId ["?" \| "*"] [Id]
16	n/a	# sum ::= constructor { "\|" constructor } ["attributes" fields]
17	n/a	# constructor ::= ConstructorId [fields]
18	n/a	#
19	n/a	# [1] "The Zephyr Abstract Syntax Description Language" by Wang, et. al. See
20	n/a	# http://asdl.sourceforge.net/
21	n/a	#-------------------------------------------------------------------------------
22	n/a	from collections import namedtuple
23	n/a	import re
24	n/a
25	n/a	__all__ = [
26	n/a	'builtin_types', 'parse', 'AST', 'Module', 'Type', 'Constructor',
27	n/a	'Field', 'Sum', 'Product', 'VisitorBase', 'Check', 'check']
28	n/a
29	n/a	# The following classes define nodes into which the ASDL description is parsed.
30	n/a	# Note: this is a "meta-AST". ASDL files (such as Python.asdl) describe the AST
31	n/a	# structure used by a programming language. But ASDL files themselves need to be
32	n/a	# parsed. This module parses ASDL files and uses a simple AST to represent them.
33	n/a	# See the EBNF at the top of the file to understand the logical connection
34	n/a	# between the various node types.
35	n/a
36	n/a	builtin_types = {'identifier', 'string', 'bytes', 'int', 'object', 'singleton',
37	n/a	'constant'}
38	n/a
39	n/a	class AST:
40	n/a	def __repr__(self):
41	n/a	raise NotImplementedError
42	n/a
43	n/a	class Module(AST):
44	n/a	def __init__(self, name, dfns):
45	n/a	self.name = name
46	n/a	self.dfns = dfns
47	n/a	self.types = {type.name: type.value for type in dfns}
48	n/a
49	n/a	def __repr__(self):
50	n/a	return 'Module({0.name}, {0.dfns})'.format(self)
51	n/a
52	n/a	class Type(AST):
53	n/a	def __init__(self, name, value):
54	n/a	self.name = name
55	n/a	self.value = value
56	n/a
57	n/a	def __repr__(self):
58	n/a	return 'Type({0.name}, {0.value})'.format(self)
59	n/a
60	n/a	class Constructor(AST):
61	n/a	def __init__(self, name, fields=None):
62	n/a	self.name = name
63	n/a	self.fields = fields or []
64	n/a
65	n/a	def __repr__(self):
66	n/a	return 'Constructor({0.name}, {0.fields})'.format(self)
67	n/a
68	n/a	class Field(AST):
69	n/a	def __init__(self, type, name=None, seq=False, opt=False):
70	n/a	self.type = type
71	n/a	self.name = name
72	n/a	self.seq = seq
73	n/a	self.opt = opt
74	n/a
75	n/a	def __repr__(self):
76	n/a	if self.seq:
77	n/a	extra = ", seq=True"
78	n/a	elif self.opt:
79	n/a	extra = ", opt=True"
80	n/a	else:
81	n/a	extra = ""
82	n/a	if self.name is None:
83	n/a	return 'Field({0.type}{1})'.format(self, extra)
84	n/a	else:
85	n/a	return 'Field({0.type}, {0.name}{1})'.format(self, extra)
86	n/a
87	n/a	class Sum(AST):
88	n/a	def __init__(self, types, attributes=None):
89	n/a	self.types = types
90	n/a	self.attributes = attributes or []
91	n/a
92	n/a	def __repr__(self):
93	n/a	if self.attributes:
94	n/a	return 'Sum({0.types}, {0.attributes})'.format(self)
95	n/a	else:
96	n/a	return 'Sum({0.types})'.format(self)
97	n/a
98	n/a	class Product(AST):
99	n/a	def __init__(self, fields, attributes=None):
100	n/a	self.fields = fields
101	n/a	self.attributes = attributes or []
102	n/a
103	n/a	def __repr__(self):
104	n/a	if self.attributes:
105	n/a	return 'Product({0.fields}, {0.attributes})'.format(self)
106	n/a	else:
107	n/a	return 'Product({0.fields})'.format(self)
108	n/a
109	n/a	# A generic visitor for the meta-AST that describes ASDL. This can be used by
110	n/a	# emitters. Note that this visitor does not provide a generic visit method, so a
111	n/a	# subclass needs to define visit methods from visitModule to as deep as the
112	n/a	# interesting node.
113	n/a	# We also define a Check visitor that makes sure the parsed ASDL is well-formed.
114	n/a
115	n/a	class VisitorBase(object):
116	n/a	"""Generic tree visitor for ASTs."""
117	n/a	def __init__(self):
118	n/a	self.cache = {}
119	n/a
120	n/a	def visit(self, obj, *args):
121	n/a	klass = obj.__class__
122	n/a	meth = self.cache.get(klass)
123	n/a	if meth is None:
124	n/a	methname = "visit" + klass.__name__
125	n/a	meth = getattr(self, methname, None)
126	n/a	self.cache[klass] = meth
127	n/a	if meth:
128	n/a	try:
129	n/a	meth(obj, *args)
130	n/a	except Exception as e:
131	n/a	print("Error visiting %r: %s" % (obj, e))
132	n/a	raise
133	n/a
134	n/a	class Check(VisitorBase):
135	n/a	"""A visitor that checks a parsed ASDL tree for correctness.
136	n/a
137	n/a	Errors are printed and accumulated.
138	n/a	"""
139	n/a	def __init__(self):
140	n/a	super(Check, self).__init__()
141	n/a	self.cons = {}
142	n/a	self.errors = 0
143	n/a	self.types = {}
144	n/a
145	n/a	def visitModule(self, mod):
146	n/a	for dfn in mod.dfns:
147	n/a	self.visit(dfn)
148	n/a
149	n/a	def visitType(self, type):
150	n/a	self.visit(type.value, str(type.name))
151	n/a
152	n/a	def visitSum(self, sum, name):
153	n/a	for t in sum.types:
154	n/a	self.visit(t, name)
155	n/a
156	n/a	def visitConstructor(self, cons, name):
157	n/a	key = str(cons.name)
158	n/a	conflict = self.cons.get(key)
159	n/a	if conflict is None:
160	n/a	self.cons[key] = name
161	n/a	else:
162	n/a	print('Redefinition of constructor {}'.format(key))
163	n/a	print('Defined in {} and {}'.format(conflict, name))
164	n/a	self.errors += 1
165	n/a	for f in cons.fields:
166	n/a	self.visit(f, key)
167	n/a
168	n/a	def visitField(self, field, name):
169	n/a	key = str(field.type)
170	n/a	l = self.types.setdefault(key, [])
171	n/a	l.append(name)
172	n/a
173	n/a	def visitProduct(self, prod, name):
174	n/a	for f in prod.fields:
175	n/a	self.visit(f, name)
176	n/a
177	n/a	def check(mod):
178	n/a	"""Check the parsed ASDL tree for correctness.
179	n/a
180	n/a	Return True if success. For failure, the errors are printed out and False
181	n/a	is returned.
182	n/a	"""
183	n/a	v = Check()
184	n/a	v.visit(mod)
185	n/a
186	n/a	for t in v.types:
187	n/a	if t not in mod.types and not t in builtin_types:
188	n/a	v.errors += 1
189	n/a	uses = ", ".join(v.types[t])
190	n/a	print('Undefined type {}, used in {}'.format(t, uses))
191	n/a	return not v.errors
192	n/a
193	n/a	# The ASDL parser itself comes next. The only interesting external interface
194	n/a	# here is the top-level parse function.
195	n/a
196	n/a	def parse(filename):
197	n/a	"""Parse ASDL from the given file and return a Module node describing it."""
198	n/a	with open(filename) as f:
199	n/a	parser = ASDLParser()
200	n/a	return parser.parse(f.read())
201	n/a
202	n/a	# Types for describing tokens in an ASDL specification.
203	n/a	class TokenKind:
204	n/a	"""TokenKind is provides a scope for enumerated token kinds."""
205	n/a	(ConstructorId, TypeId, Equals, Comma, Question, Pipe, Asterisk,
206	n/a	LParen, RParen, LBrace, RBrace) = range(11)
207	n/a
208	n/a	operator_table = {
209	n/a	'=': Equals, ',': Comma, '?': Question, '\|': Pipe, '(': LParen,
210	n/a	')': RParen, '*': Asterisk, '{': LBrace, '}': RBrace}
211	n/a
212	n/a	Token = namedtuple('Token', 'kind value lineno')
213	n/a
214	n/a	class ASDLSyntaxError(Exception):
215	n/a	def __init__(self, msg, lineno=None):
216	n/a	self.msg = msg
217	n/a	self.lineno = lineno or '<unknown>'
218	n/a
219	n/a	def __str__(self):
220	n/a	return 'Syntax error on line {0.lineno}: {0.msg}'.format(self)
221	n/a
222	n/a	def tokenize_asdl(buf):
223	n/a	"""Tokenize the given buffer. Yield Token objects."""
224	n/a	for lineno, line in enumerate(buf.splitlines(), 1):
225	n/a	for m in re.finditer(r'\s(\w+\|--.\|.)', line.strip()):
226	n/a	c = m.group(1)
227	n/a	if c[0].isalpha():
228	n/a	# Some kind of identifier
229	n/a	if c[0].isupper():
230	n/a	yield Token(TokenKind.ConstructorId, c, lineno)
231	n/a	else:
232	n/a	yield Token(TokenKind.TypeId, c, lineno)
233	n/a	elif c[:2] == '--':
234	n/a	# Comment
235	n/a	break
236	n/a	else:
237	n/a	# Operators
238	n/a	try:
239	n/a	op_kind = TokenKind.operator_table[c]
240	n/a	except KeyError:
241	n/a	raise ASDLSyntaxError('Invalid operator %s' % c, lineno)
242	n/a	yield Token(op_kind, c, lineno)
243	n/a
244	n/a	class ASDLParser:
245	n/a	"""Parser for ASDL files.
246	n/a
247	n/a	Create, then call the parse method on a buffer containing ASDL.
248	n/a	This is a simple recursive descent parser that uses tokenize_asdl for the
249	n/a	lexing.
250	n/a	"""
251	n/a	def __init__(self):
252	n/a	self._tokenizer = None
253	n/a	self.cur_token = None
254	n/a
255	n/a	def parse(self, buf):
256	n/a	"""Parse the ASDL in the buffer and return an AST with a Module root.
257	n/a	"""
258	n/a	self._tokenizer = tokenize_asdl(buf)
259	n/a	self._advance()
260	n/a	return self._parse_module()
261	n/a
262	n/a	def _parse_module(self):
263	n/a	if self._at_keyword('module'):
264	n/a	self._advance()
265	n/a	else:
266	n/a	raise ASDLSyntaxError(
267	n/a	'Expected "module" (found {})'.format(self.cur_token.value),
268	n/a	self.cur_token.lineno)
269	n/a	name = self._match(self._id_kinds)
270	n/a	self._match(TokenKind.LBrace)
271	n/a	defs = self._parse_definitions()
272	n/a	self._match(TokenKind.RBrace)
273	n/a	return Module(name, defs)
274	n/a
275	n/a	def _parse_definitions(self):
276	n/a	defs = []
277	n/a	while self.cur_token.kind == TokenKind.TypeId:
278	n/a	typename = self._advance()
279	n/a	self._match(TokenKind.Equals)
280	n/a	type = self._parse_type()
281	n/a	defs.append(Type(typename, type))
282	n/a	return defs
283	n/a
284	n/a	def _parse_type(self):
285	n/a	if self.cur_token.kind == TokenKind.LParen:
286	n/a	# If we see a (, it's a product
287	n/a	return self._parse_product()
288	n/a	else:
289	n/a	# Otherwise it's a sum. Look for ConstructorId
290	n/a	sumlist = [Constructor(self._match(TokenKind.ConstructorId),
291	n/a	self._parse_optional_fields())]
292	n/a	while self.cur_token.kind == TokenKind.Pipe:
293	n/a	# More constructors
294	n/a	self._advance()
295	n/a	sumlist.append(Constructor(
296	n/a	self._match(TokenKind.ConstructorId),
297	n/a	self._parse_optional_fields()))
298	n/a	return Sum(sumlist, self._parse_optional_attributes())
299	n/a
300	n/a	def _parse_product(self):
301	n/a	return Product(self._parse_fields(), self._parse_optional_attributes())
302	n/a
303	n/a	def _parse_fields(self):
304	n/a	fields = []
305	n/a	self._match(TokenKind.LParen)
306	n/a	while self.cur_token.kind == TokenKind.TypeId:
307	n/a	typename = self._advance()
308	n/a	is_seq, is_opt = self._parse_optional_field_quantifier()
309	n/a	id = (self._advance() if self.cur_token.kind in self._id_kinds
310	n/a	else None)
311	n/a	fields.append(Field(typename, id, seq=is_seq, opt=is_opt))
312	n/a	if self.cur_token.kind == TokenKind.RParen:
313	n/a	break
314	n/a	elif self.cur_token.kind == TokenKind.Comma:
315	n/a	self._advance()
316	n/a	self._match(TokenKind.RParen)
317	n/a	return fields
318	n/a
319	n/a	def _parse_optional_fields(self):
320	n/a	if self.cur_token.kind == TokenKind.LParen:
321	n/a	return self._parse_fields()
322	n/a	else:
323	n/a	return None
324	n/a
325	n/a	def _parse_optional_attributes(self):
326	n/a	if self._at_keyword('attributes'):
327	n/a	self._advance()
328	n/a	return self._parse_fields()
329	n/a	else:
330	n/a	return None
331	n/a
332	n/a	def _parse_optional_field_quantifier(self):
333	n/a	is_seq, is_opt = False, False
334	n/a	if self.cur_token.kind == TokenKind.Asterisk:
335	n/a	is_seq = True
336	n/a	self._advance()
337	n/a	elif self.cur_token.kind == TokenKind.Question:
338	n/a	is_opt = True
339	n/a	self._advance()
340	n/a	return is_seq, is_opt
341	n/a
342	n/a	def _advance(self):
343	n/a	""" Return the value of the current token and read the next one into
344	n/a	self.cur_token.
345	n/a	"""
346	n/a	cur_val = None if self.cur_token is None else self.cur_token.value
347	n/a	try:
348	n/a	self.cur_token = next(self._tokenizer)
349	n/a	except StopIteration:
350	n/a	self.cur_token = None
351	n/a	return cur_val
352	n/a
353	n/a	_id_kinds = (TokenKind.ConstructorId, TokenKind.TypeId)
354	n/a
355	n/a	def _match(self, kind):
356	n/a	"""The 'match' primitive of RD parsers.
357	n/a
358	n/a	* Verifies that the current token is of the given kind (kind can
359	n/a	be a tuple, in which the kind must match one of its members).
360	n/a	* Returns the value of the current token
361	n/a	* Reads in the next token
362	n/a	"""
363	n/a	if (isinstance(kind, tuple) and self.cur_token.kind in kind or
364	n/a	self.cur_token.kind == kind
365	n/a	):
366	n/a	value = self.cur_token.value
367	n/a	self._advance()
368	n/a	return value
369	n/a	else:
370	n/a	raise ASDLSyntaxError(
371	n/a	'Unmatched {} (found {})'.format(kind, self.cur_token.kind),
372	n/a	self.cur_token.lineno)
373	n/a
374	n/a	def _at_keyword(self, keyword):
375	n/a	return (self.cur_token.kind == TokenKind.TypeId and
376	n/a	self.cur_token.value == keyword)