blob: 7b4e2dc81e20bf6ba641e4cb6fb6a7b7fb3a1a17 [file] [log] [blame]
Jeremy Hylton3e0055f2005-10-20 19:59:25 +00001"""An implementation of the Zephyr Abstract Syntax Definition Language.
2
3See http://asdl.sourceforge.net/ and
Senthil Kumaran2b80fa62010-05-18 13:48:45 +00004http://www.cs.princeton.edu/research/techreps/TR-554-97
Jeremy Hylton3e0055f2005-10-20 19:59:25 +00005
6Only supports top level module decl, not view. I'm guessing that view
7is intended to support the browser and I'm not interested in the
8browser.
Martin v. Löwiseae93b72006-02-28 00:12:47 +00009
10Changes for Python: Add support for module versions
Jeremy Hylton3e0055f2005-10-20 19:59:25 +000011"""
12
Jeremy Hylton3e0055f2005-10-20 19:59:25 +000013import os
Guido van Rossum805365e2007-05-07 22:24:25 +000014import sys
Jeremy Hylton3e0055f2005-10-20 19:59:25 +000015import traceback
16
17import spark
18
Guido van Rossum805365e2007-05-07 22:24:25 +000019def output(string):
20 sys.stdout.write(string + "\n")
21
22
Benjamin Peterson87c8d872009-06-11 22:54:11 +000023class Token(object):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +000024 # spark seems to dispatch in the parser based on a token's
25 # type attribute
26 def __init__(self, type, lineno):
27 self.type = type
28 self.lineno = lineno
29
30 def __str__(self):
31 return self.type
32
33 def __repr__(self):
34 return str(self)
35
36class Id(Token):
37 def __init__(self, value, lineno):
38 self.type = 'Id'
39 self.value = value
40 self.lineno = lineno
41
42 def __str__(self):
43 return self.value
Tim Peters710ab3b2006-02-28 18:30:36 +000044
Martin v. Löwiseae93b72006-02-28 00:12:47 +000045class String(Token):
46 def __init__(self, value, lineno):
47 self.type = 'String'
48 self.value = value
49 self.lineno = lineno
Jeremy Hylton3e0055f2005-10-20 19:59:25 +000050
Guido van Rossum805365e2007-05-07 22:24:25 +000051class ASDLSyntaxError(Exception):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +000052
53 def __init__(self, lineno, token=None, msg=None):
54 self.lineno = lineno
55 self.token = token
56 self.msg = msg
57
58 def __str__(self):
59 if self.msg is None:
60 return "Error at '%s', line %d" % (self.token, self.lineno)
61 else:
62 return "%s, line %d" % (self.msg, self.lineno)
63
64class ASDLScanner(spark.GenericScanner, object):
65
66 def tokenize(self, input):
67 self.rv = []
68 self.lineno = 1
69 super(ASDLScanner, self).tokenize(input)
70 return self.rv
71
72 def t_id(self, s):
73 r"[\w\.]+"
74 # XXX doesn't distinguish upper vs. lower, which is
75 # significant for ASDL.
76 self.rv.append(Id(s, self.lineno))
Tim Peters710ab3b2006-02-28 18:30:36 +000077
Martin v. Löwiseae93b72006-02-28 00:12:47 +000078 def t_string(self, s):
79 r'"[^"]*"'
80 self.rv.append(String(s, self.lineno))
Jeremy Hylton3e0055f2005-10-20 19:59:25 +000081
82 def t_xxx(self, s): # not sure what this production means
83 r"<="
84 self.rv.append(Token(s, self.lineno))
85
86 def t_punctuation(self, s):
87 r"[\{\}\*\=\|\(\)\,\?\:]"
88 self.rv.append(Token(s, self.lineno))
89
90 def t_comment(self, s):
91 r"\-\-[^\n]*"
92 pass
93
94 def t_newline(self, s):
95 r"\n"
96 self.lineno += 1
97
98 def t_whitespace(self, s):
99 r"[ \t]+"
100 pass
101
102 def t_default(self, s):
103 r" . +"
Collin Winter4902e692007-08-30 18:18:27 +0000104 raise ValueError("unmatched input: %r" % s)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000105
106class ASDLParser(spark.GenericParser, object):
107 def __init__(self):
108 super(ASDLParser, self).__init__("module")
109
110 def typestring(self, tok):
111 return tok.type
112
113 def error(self, tok):
114 raise ASDLSyntaxError(tok.lineno, tok)
115
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000116 def p_module_0(self, info):
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000117 " module ::= Id Id version { } "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000118 module, name, version, _0, _1 = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000119 if module.value != "module":
120 raise ASDLSyntaxError(module.lineno,
121 msg="expected 'module', found %s" % module)
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000122 return Module(name, None, version)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000123
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000124 def p_module(self, info):
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000125 " module ::= Id Id version { definitions } "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000126 module, name, version, _0, definitions, _1 = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000127 if module.value != "module":
128 raise ASDLSyntaxError(module.lineno,
129 msg="expected 'module', found %s" % module)
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000130 return Module(name, definitions, version)
Tim Peters710ab3b2006-02-28 18:30:36 +0000131
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000132 def p_version(self, info):
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000133 "version ::= Id String"
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000134 version, V = info
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000135 if version.value != "version":
136 raise ASDLSyntaxError(version.lineno,
Guido van Rossum805365e2007-05-07 22:24:25 +0000137 msg="expected 'version', found %" % version)
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000138 return V
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000139
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000140 def p_definition_0(self, definition):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000141 " definitions ::= definition "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000142 return definition[0]
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000143
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000144 def p_definition_1(self, definitions):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000145 " definitions ::= definition definitions "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000146 return definitions[0] + definitions[1]
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000147
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000148 def p_definition(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000149 " definition ::= Id = type "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000150 id, _, type = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000151 return [Type(id, type)]
152
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000153 def p_type_0(self, product):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000154 " type ::= product "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000155 return product[0]
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000156
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000157 def p_type_1(self, sum):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000158 " type ::= sum "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000159 return Sum(sum[0])
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000160
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000161 def p_type_2(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000162 " type ::= sum Id ( fields ) "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000163 sum, id, _0, attributes, _1 = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000164 if id.value != "attributes":
165 raise ASDLSyntaxError(id.lineno,
166 msg="expected attributes, found %s" % id)
Martin v. Löwis49c5da12006-03-01 22:49:05 +0000167 if attributes:
168 attributes.reverse()
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000169 return Sum(sum, attributes)
170
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000171 def p_product(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000172 " product ::= ( fields ) "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000173 _0, fields, _1 = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000174 # XXX can't I just construct things in the right order?
Tim Peters536cf992005-12-25 23:18:31 +0000175 fields.reverse()
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000176 return Product(fields)
177
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000178 def p_sum_0(self, constructor):
Georg Brandl1f01deb2009-01-03 22:47:39 +0000179 " sum ::= constructor "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000180 return [constructor[0]]
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000181
Neal Norwitzbda355f2008-03-17 18:03:56 +0000182 def p_sum_1(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000183 " sum ::= constructor | sum "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000184 constructor, _, sum = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000185 return [constructor] + sum
186
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000187 def p_sum_2(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000188 " sum ::= constructor | sum "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000189 constructor, _, sum = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000190 return [constructor] + sum
191
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000192 def p_constructor_0(self, id):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000193 " constructor ::= Id "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000194 return Constructor(id[0])
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000195
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000196 def p_constructor_1(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000197 " constructor ::= Id ( fields ) "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000198 id, _0, fields, _1 = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000199 # XXX can't I just construct things in the right order?
Tim Peters536cf992005-12-25 23:18:31 +0000200 fields.reverse()
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000201 return Constructor(id, fields)
202
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000203 def p_fields_0(self, field):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000204 " fields ::= field "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000205 return [field[0]]
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000206
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000207 def p_fields_1(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000208 " fields ::= field , fields "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000209 field, _, fields = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000210 return fields + [field]
211
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000212 def p_field_0(self, type_):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000213 " field ::= Id "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000214 return Field(type_[0])
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000215
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000216 def p_field_1(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000217 " field ::= Id Id "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000218 type, name = info
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000219 return Field(type, name)
220
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000221 def p_field_2(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000222 " field ::= Id * Id "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000223 type, _, name = info
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000224 return Field(type, name, seq=True)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000225
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000226 def p_field_3(self, info):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000227 " field ::= Id ? Id "
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000228 type, _, name = info
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000229 return Field(type, name, opt=True)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000230
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000231 def p_field_4(self, type_):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000232 " field ::= Id * "
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000233 return Field(type_[0], seq=True)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000234
Guido van Rossum1bc535d2007-05-15 18:46:22 +0000235 def p_field_5(self, type_):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000236 " field ::= Id ? "
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000237 return Field(type[0], opt=True)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000238
239builtin_types = ("identifier", "string", "int", "bool", "object")
240
241# below is a collection of classes to capture the AST of an AST :-)
242# not sure if any of the methods are useful yet, but I'm adding them
243# piecemeal as they seem helpful
244
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000245class AST(object):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000246 pass # a marker class
247
248class Module(AST):
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000249 def __init__(self, name, dfns, version):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000250 self.name = name
251 self.dfns = dfns
Martin v. Löwiseae93b72006-02-28 00:12:47 +0000252 self.version = version
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000253 self.types = {} # maps type name to value (from dfns)
254 for type in dfns:
255 self.types[type.name.value] = type.value
256
257 def __repr__(self):
258 return "Module(%s, %s)" % (self.name, self.dfns)
259
260class Type(AST):
261 def __init__(self, name, value):
262 self.name = name
263 self.value = value
264
265 def __repr__(self):
266 return "Type(%s, %s)" % (self.name, self.value)
267
268class Constructor(AST):
269 def __init__(self, name, fields=None):
270 self.name = name
271 self.fields = fields or []
272
273 def __repr__(self):
274 return "Constructor(%s, %s)" % (self.name, self.fields)
275
276class Field(AST):
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000277 def __init__(self, type, name=None, seq=False, opt=False):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000278 self.type = type
279 self.name = name
280 self.seq = seq
281 self.opt = opt
282
283 def __repr__(self):
284 if self.seq:
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000285 extra = ", seq=True"
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000286 elif self.opt:
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000287 extra = ", opt=True"
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000288 else:
289 extra = ""
290 if self.name is None:
291 return "Field(%s%s)" % (self.type, extra)
292 else:
293 return "Field(%s, %s%s)" % (self.type, self.name, extra)
294
295class Sum(AST):
296 def __init__(self, types, attributes=None):
297 self.types = types
298 self.attributes = attributes or []
299
300 def __repr__(self):
301 if self.attributes is None:
302 return "Sum(%s)" % self.types
303 else:
304 return "Sum(%s, %s)" % (self.types, self.attributes)
305
306class Product(AST):
307 def __init__(self, fields):
308 self.fields = fields
309
310 def __repr__(self):
311 return "Product(%s)" % self.fields
312
313class VisitorBase(object):
314
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000315 def __init__(self, skip=False):
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000316 self.cache = {}
317 self.skip = skip
318
319 def visit(self, object, *args):
320 meth = self._dispatch(object)
321 if meth is None:
322 return
323 try:
324 meth(object, *args)
Guido van Rossum805365e2007-05-07 22:24:25 +0000325 except Exception:
Alexandre Vassalottidf6f3fd2009-07-17 05:35:59 +0000326 output("Error visiting" + repr(object))
327 output(str(sys.exc_info()[1]))
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000328 traceback.print_exc()
329 # XXX hack
330 if hasattr(self, 'file'):
331 self.file.flush()
332 os._exit(1)
333
334 def _dispatch(self, object):
335 assert isinstance(object, AST), repr(object)
336 klass = object.__class__
337 meth = self.cache.get(klass)
338 if meth is None:
339 methname = "visit" + klass.__name__
340 if self.skip:
341 meth = getattr(self, methname, None)
342 else:
343 meth = getattr(self, methname)
344 self.cache[klass] = meth
345 return meth
346
347class Check(VisitorBase):
348
349 def __init__(self):
Benjamin Peterson87c8d872009-06-11 22:54:11 +0000350 super(Check, self).__init__(skip=True)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000351 self.cons = {}
352 self.errors = 0
353 self.types = {}
354
355 def visitModule(self, mod):
356 for dfn in mod.dfns:
357 self.visit(dfn)
358
359 def visitType(self, type):
360 self.visit(type.value, str(type.name))
361
362 def visitSum(self, sum, name):
363 for t in sum.types:
364 self.visit(t, name)
365
366 def visitConstructor(self, cons, name):
367 key = str(cons.name)
368 conflict = self.cons.get(key)
369 if conflict is None:
370 self.cons[key] = name
371 else:
Guido van Rossum805365e2007-05-07 22:24:25 +0000372 output("Redefinition of constructor %s" % key)
373 output("Defined in %s and %s" % (conflict, name))
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000374 self.errors += 1
375 for f in cons.fields:
376 self.visit(f, key)
377
378 def visitField(self, field, name):
379 key = str(field.type)
380 l = self.types.setdefault(key, [])
381 l.append(name)
382
383 def visitProduct(self, prod, name):
384 for f in prod.fields:
385 self.visit(f, name)
386
387def check(mod):
388 v = Check()
389 v.visit(mod)
390
391 for t in v.types:
Fred Drake34e4f522006-12-29 04:42:48 +0000392 if t not in mod.types and not t in builtin_types:
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000393 v.errors += 1
394 uses = ", ".join(v.types[t])
Guido van Rossum805365e2007-05-07 22:24:25 +0000395 output("Undefined type %s, used in %s" % (t, uses))
Tim Peters536cf992005-12-25 23:18:31 +0000396
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000397 return not v.errors
398
399def parse(file):
400 scanner = ASDLScanner()
401 parser = ASDLParser()
402
403 buf = open(file).read()
404 tokens = scanner.tokenize(buf)
405 try:
406 return parser.parse(tokens)
Guido van Rossum805365e2007-05-07 22:24:25 +0000407 except ASDLSyntaxError:
Georg Brandl8a732782009-04-12 11:34:13 +0000408 err = sys.exc_info()[1]
409 output(str(err))
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000410 lines = buf.split("\n")
Guido van Rossum805365e2007-05-07 22:24:25 +0000411 output(lines[err.lineno - 1]) # lines starts at 0, files at 1
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000412
413if __name__ == "__main__":
414 import glob
415 import sys
416
417 if len(sys.argv) > 1:
418 files = sys.argv[1:]
419 else:
420 testdir = "tests"
421 files = glob.glob(testdir + "/*.asdl")
Tim Peters536cf992005-12-25 23:18:31 +0000422
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000423 for file in files:
Guido van Rossum805365e2007-05-07 22:24:25 +0000424 output(file)
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000425 mod = parse(file)
Georg Brandl8a732782009-04-12 11:34:13 +0000426 if not mod:
427 break
Guido van Rossum805365e2007-05-07 22:24:25 +0000428 output("module", mod.name)
429 output(len(mod.dfns), "definitions")
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000430 if not check(mod):
Guido van Rossum805365e2007-05-07 22:24:25 +0000431 output("Check failed")
Jeremy Hylton3e0055f2005-10-20 19:59:25 +0000432 else:
433 for dfn in mod.dfns:
Guido van Rossum805365e2007-05-07 22:24:25 +0000434 output(dfn.type)