| 1 | """front_end.py: Lexer and parser for the ASDL schema language."""
|
| 2 | from __future__ import print_function
|
| 3 |
|
| 4 | import re
|
| 5 |
|
| 6 | from asdl import ast
|
| 7 | from asdl.ast import (AST, Use, Module, TypeDecl, Constructor, Field, Sum,
|
| 8 | SimpleSum, Product)
|
| 9 | from asdl.util import log
|
| 10 |
|
| 11 | _ = log
|
| 12 |
|
| 13 | _KEYWORDS = ['use', 'module', 'generate']
|
| 14 |
|
| 15 | _TOKENS = [
|
| 16 | ('Keyword', ''),
|
| 17 | ('Name', ''),
|
| 18 |
|
| 19 | # For operators, the string matters
|
| 20 | ('Equals', '='),
|
| 21 | ('Comma', ','),
|
| 22 | ('Question', '?'),
|
| 23 | ('Pipe', '|'),
|
| 24 | ('Asterisk', '*'),
|
| 25 | ('LParen', '('),
|
| 26 | ('RParen', ')'),
|
| 27 | ('LBrace', '{'),
|
| 28 | ('RBrace', '}'),
|
| 29 | ('Percent', '%'),
|
| 30 |
|
| 31 | # Oils addition for parameterized types.
|
| 32 | ('LBracket', '['),
|
| 33 | ('RBracket', ']'),
|
| 34 |
|
| 35 | # - Start with Dict[string, bool].
|
| 36 | # - List[string] is an alias for string*
|
| 37 | #
|
| 38 | # statically typed: Dict and List
|
| 39 | # dynamically typed: dict and list
|
| 40 | ]
|
| 41 |
|
| 42 | _TOKEN_STR = [name for name, _ in _TOKENS] # integer -> string like LParen
|
| 43 | _TOKEN_INT = {} # string like '(' -> integer
|
| 44 |
|
| 45 |
|
| 46 | class TokenKind(object):
|
| 47 | """ASDL tokens.
|
| 48 |
|
| 49 | TokenKind.LBrace = 5, etc.
|
| 50 | """
|
| 51 | pass
|
| 52 |
|
| 53 |
|
| 54 | for i, (name, val) in enumerate(_TOKENS):
|
| 55 | setattr(TokenKind, name, i)
|
| 56 | _TOKEN_INT[val] = i
|
| 57 |
|
| 58 |
|
| 59 | class Token(object):
|
| 60 |
|
| 61 | def __init__(self, kind, value, lineno):
|
| 62 | self.kind = kind
|
| 63 | self.value = value
|
| 64 | self.lineno = lineno
|
| 65 |
|
| 66 |
|
| 67 | class ASDLSyntaxError(Exception):
|
| 68 |
|
| 69 | def __init__(self, msg, lineno=None):
|
| 70 | self.msg = msg
|
| 71 | self.lineno = lineno or '<unknown>'
|
| 72 |
|
| 73 | def __str__(self):
|
| 74 | return 'Syntax error on line {0.lineno}: {0.msg}'.format(self)
|
| 75 |
|
| 76 |
|
| 77 | def _Tokenize(f):
|
| 78 | """Tokenize the given buffer.
|
| 79 |
|
| 80 | Yield Token objects.
|
| 81 | """
|
| 82 | for lineno, line in enumerate(f, 1):
|
| 83 | for m in re.finditer(r'\s*(\w+|--.*|#.*|.)', line.strip()):
|
| 84 | c = m.group(1)
|
| 85 | if c in _KEYWORDS:
|
| 86 | yield Token(TokenKind.Keyword, c, lineno)
|
| 87 |
|
| 88 | elif c[0].isalpha():
|
| 89 | yield Token(TokenKind.Name, c, lineno)
|
| 90 |
|
| 91 | elif c.startswith('--') or c.startswith('#'):
|
| 92 | # ASDL comments start with --
|
| 93 | # Added # comments like Python and shell
|
| 94 | break
|
| 95 |
|
| 96 | else:
|
| 97 | # Operators
|
| 98 | try:
|
| 99 | op_kind = _TOKEN_INT[c]
|
| 100 | except KeyError:
|
| 101 | raise ASDLSyntaxError('Invalid operator %s' % c, lineno)
|
| 102 | yield Token(op_kind, c, lineno)
|
| 103 |
|
| 104 |
|
| 105 | def _SumIsSimple(variant_list):
|
| 106 | """Return True if a sum is a simple.
|
| 107 |
|
| 108 | A sum is simple if its types have no fields, e.g. unaryop = Invert |
|
| 109 | Not | UAdd | USub
|
| 110 | """
|
| 111 | for t in variant_list:
|
| 112 | if t.fields or t.shared_type:
|
| 113 | return False
|
| 114 | return True
|
| 115 |
|
| 116 |
|
| 117 | _CODE_GEN_OPTIONS = [
|
| 118 | 'no_namespace_suffix', # Id.Foo instead of Id_e.Foo
|
| 119 | 'integers', # integer builtin_i instead of strongly typed builtin_e
|
| 120 | 'uint16', # like integers, but use uint16_t instead
|
| 121 | 'bit_set', # not implemented: 1 << n instead of n
|
| 122 |
|
| 123 | # probably don't need this
|
| 124 | # 'common_synthetic_field:left_tok',
|
| 125 |
|
| 126 | # Put this type, and transitive closure of types it references, in the
|
| 127 | # unique "first class variant" namespace, and generate type reflection.
|
| 128 | 'reflect_all_types',
|
| 129 |
|
| 130 | # Squeeze and Freeze, with the number of bits as a option Hm the headers
|
| 131 | # here still need type reflection. Probably OK.
|
| 132 | 'mirror_all_types:16',
|
| 133 | ]
|
| 134 |
|
| 135 |
|
| 136 | class ASDLParser(object):
|
| 137 | """Parser for ASDL files.
|
| 138 |
|
| 139 | Create, then call the parse method on a buffer containing ASDL. This
|
| 140 | is a simple recursive descent parser that uses _Tokenize for the
|
| 141 | lexing.
|
| 142 | """
|
| 143 |
|
| 144 | def __init__(self):
|
| 145 | self._tokenizer = None
|
| 146 | self.cur_token = None
|
| 147 |
|
| 148 | def parse(self, f):
|
| 149 | """Parse the ASDL in the file and return an AST with a Module root."""
|
| 150 | self._tokenizer = _Tokenize(f)
|
| 151 | self._advance()
|
| 152 | return self._parse_module()
|
| 153 |
|
| 154 | def _parse_module(self):
|
| 155 | """
|
| 156 | type_decl : NAME (':' NAME) '=' compound_type
|
| 157 | module : 'module' NAME '{' use* type_decl* '}'
|
| 158 |
|
| 159 | We added:
|
| 160 | : for code gen options
|
| 161 | use for imports
|
| 162 |
|
| 163 | alloc_members =
|
| 164 | List
|
| 165 | | Dict
|
| 166 | | Struct
|
| 167 | generate [bit_set]
|
| 168 |
|
| 169 | -- color::Red, not color_e::Red or color_i::Red
|
| 170 | color = Red | Green
|
| 171 | generate [integers, no_sum_suffix]
|
| 172 | """
|
| 173 | if not self._at_keyword('module'):
|
| 174 | raise ASDLSyntaxError(
|
| 175 | 'Expected "module" (found {})'.format(self.cur_token.value),
|
| 176 | self.cur_token.lineno)
|
| 177 | self._advance()
|
| 178 | name = self._match(TokenKind.Name)
|
| 179 | self._match(TokenKind.LBrace)
|
| 180 |
|
| 181 | uses = []
|
| 182 | while self._at_keyword('use'):
|
| 183 | uses.append(self._parse_use())
|
| 184 |
|
| 185 | defs = []
|
| 186 | while self.cur_token.kind == TokenKind.Name:
|
| 187 | typename = self._advance()
|
| 188 | self._match(TokenKind.Equals)
|
| 189 | type_ = self._parse_compound_type()
|
| 190 | defs.append(TypeDecl(typename, type_))
|
| 191 |
|
| 192 | self._match(TokenKind.RBrace)
|
| 193 | return Module(name, uses, defs)
|
| 194 |
|
| 195 | def _parse_use(self):
|
| 196 | """Use: 'use' NAME+ '{' NAME+ '}'.
|
| 197 |
|
| 198 | example: use frontend syntax { Token }
|
| 199 |
|
| 200 | This means frontend/syntax.asdl.h :: Token
|
| 201 | """
|
| 202 | self._advance() # past 'use'
|
| 203 | module_parts = []
|
| 204 | while self.cur_token.kind == TokenKind.Name:
|
| 205 | part = self._advance()
|
| 206 | module_parts.append(part)
|
| 207 |
|
| 208 | self._match(TokenKind.LBrace)
|
| 209 |
|
| 210 | type_names = []
|
| 211 | while self.cur_token.kind == TokenKind.Name:
|
| 212 | t = self._advance()
|
| 213 | type_names.append(t)
|
| 214 | if self.cur_token.kind == TokenKind.RParen:
|
| 215 | break
|
| 216 | elif self.cur_token.kind == TokenKind.Comma:
|
| 217 | self._advance()
|
| 218 |
|
| 219 | self._match(TokenKind.RBrace)
|
| 220 | #print('MOD %s' % module_parts)
|
| 221 | return Use(module_parts, type_names)
|
| 222 |
|
| 223 | def _parse_compound_type(self):
|
| 224 | """Constructor : NAME fields? | NAME '%' NAME # shared variant.
|
| 225 |
|
| 226 | compound_type : product
|
| 227 | | constructor ('|' constructor)*
|
| 228 | """
|
| 229 | if self.cur_token.kind == TokenKind.LParen:
|
| 230 | # If we see a (, it's a product
|
| 231 | return self._parse_product()
|
| 232 | else:
|
| 233 | # Otherwise it's a sum. Look for ConstructorId
|
| 234 | sumlist = []
|
| 235 | while True:
|
| 236 | cons_name = self._match(TokenKind.Name)
|
| 237 |
|
| 238 | shared_type = None
|
| 239 | fields = None
|
| 240 | if self.cur_token.kind == TokenKind.LParen:
|
| 241 | fields = self._parse_fields()
|
| 242 | elif self.cur_token.kind == TokenKind.Percent:
|
| 243 | self._advance()
|
| 244 | shared_type = self._match(TokenKind.Name)
|
| 245 | else:
|
| 246 | pass
|
| 247 |
|
| 248 | cons = Constructor(cons_name, shared_type, fields)
|
| 249 | sumlist.append(cons)
|
| 250 |
|
| 251 | if self.cur_token.kind != TokenKind.Pipe:
|
| 252 | break
|
| 253 | self._advance()
|
| 254 | generate = self._parse_optional_generate()
|
| 255 |
|
| 256 | # Additional validation
|
| 257 | if generate is not None:
|
| 258 | for g in generate:
|
| 259 | if g not in _CODE_GEN_OPTIONS:
|
| 260 | raise ASDLSyntaxError('Invalid code gen option %r' % g,
|
| 261 | self.cur_token.lineno)
|
| 262 |
|
| 263 | if _SumIsSimple(sumlist):
|
| 264 | return SimpleSum(sumlist, generate)
|
| 265 | else:
|
| 266 | return Sum(sumlist, generate)
|
| 267 |
|
| 268 | def _parse_type_expr(self):
|
| 269 | """One or two params:
|
| 270 |
|
| 271 | type_params : '[' type_expr ( ',' type_expr )* ']'
|
| 272 |
|
| 273 | type_expr : NAME type_params? (''?' | '*')? # allow one suffix
|
| 274 |
|
| 275 | NAME is validated against Optional, List, Dict afterward
|
| 276 | """
|
| 277 | type_name = self._match(TokenKind.Name)
|
| 278 |
|
| 279 | # Accept Python-like naming!
|
| 280 | if type_name == 'str':
|
| 281 | type_name = 'string'
|
| 282 |
|
| 283 | children = []
|
| 284 | if self.cur_token.kind == TokenKind.LBracket:
|
| 285 | self._advance()
|
| 286 | children.append(self._parse_type_expr())
|
| 287 | if self.cur_token.kind == TokenKind.Comma:
|
| 288 | self._advance()
|
| 289 | children.append(self._parse_type_expr())
|
| 290 |
|
| 291 | self._match(TokenKind.RBracket)
|
| 292 |
|
| 293 | if type_name in ('List', 'Optional'):
|
| 294 | if len(children) != 1:
|
| 295 | raise ASDLSyntaxError(
|
| 296 | 'Expected 1 type param to {}'.format(type_name),
|
| 297 | self.cur_token.lineno)
|
| 298 | elif type_name == 'Dict':
|
| 299 | if len(children) != 2:
|
| 300 | raise ASDLSyntaxError(
|
| 301 | 'Expected 2 type params to {}'.format(type_name),
|
| 302 | self.cur_token.lineno)
|
| 303 | else:
|
| 304 | if len(children) != 0:
|
| 305 | raise ASDLSyntaxError(
|
| 306 | 'Expected zero type params to {}'.format(type_name),
|
| 307 | self.cur_token.lineno)
|
| 308 |
|
| 309 | if len(children):
|
| 310 | typ = ast.ParameterizedType(type_name, children)
|
| 311 | else:
|
| 312 | typ = ast.NamedType(type_name)
|
| 313 |
|
| 314 | if self.cur_token.kind == TokenKind.Asterisk:
|
| 315 | # string* is equivalent to List[string]
|
| 316 | typ = ast.ParameterizedType('List', [typ])
|
| 317 | self._advance()
|
| 318 |
|
| 319 | elif self.cur_token.kind == TokenKind.Question:
|
| 320 | # string* is equivalent to Optional[string]
|
| 321 | typ = ast.ParameterizedType('Optional', [typ])
|
| 322 | self._advance()
|
| 323 |
|
| 324 | return typ
|
| 325 |
|
| 326 | def _parse_fields(self):
|
| 327 | """fields_inner: type_expr NAME ( ',' type_expr NAME )* ','?
|
| 328 |
|
| 329 | fields : '(' fields_inner? ')'
|
| 330 |
|
| 331 | Name Quantifier? should be changed to typename.
|
| 332 | """
|
| 333 | fields = []
|
| 334 | self._match(TokenKind.LParen)
|
| 335 | while self.cur_token.kind == TokenKind.Name:
|
| 336 | typ = self._parse_type_expr()
|
| 337 | field_name = self._match(TokenKind.Name)
|
| 338 |
|
| 339 | fields.append(Field(typ, field_name))
|
| 340 |
|
| 341 | if self.cur_token.kind == TokenKind.RParen:
|
| 342 | break
|
| 343 | elif self.cur_token.kind == TokenKind.Comma:
|
| 344 | self._advance()
|
| 345 |
|
| 346 | self._match(TokenKind.RParen)
|
| 347 | return fields
|
| 348 |
|
| 349 | def _parse_list(self):
|
| 350 | """list_inner: NAME ( ',' NAME )* ','?
|
| 351 |
|
| 352 | list : '[' list_inner? ']'
|
| 353 | """
|
| 354 | generate = []
|
| 355 | self._match(TokenKind.LBracket)
|
| 356 | while self.cur_token.kind == TokenKind.Name:
|
| 357 | name = self._match(TokenKind.Name)
|
| 358 |
|
| 359 | generate.append(name)
|
| 360 |
|
| 361 | if self.cur_token.kind == TokenKind.RBracket:
|
| 362 | break
|
| 363 | elif self.cur_token.kind == TokenKind.Comma:
|
| 364 | self._advance()
|
| 365 |
|
| 366 | self._match(TokenKind.RBracket)
|
| 367 | return generate
|
| 368 |
|
| 369 | def _parse_optional_generate(self):
|
| 370 | """Attributes = 'generate' list."""
|
| 371 | if self._at_keyword('generate'):
|
| 372 | self._advance()
|
| 373 | return self._parse_list()
|
| 374 | else:
|
| 375 | return None
|
| 376 |
|
| 377 | def _parse_product(self):
|
| 378 | """Product: fields attributes?"""
|
| 379 | return Product(self._parse_fields())
|
| 380 |
|
| 381 | def _advance(self):
|
| 382 | """Return current token; read next token into self.cur_token."""
|
| 383 | cur_val = None if self.cur_token is None else self.cur_token.value
|
| 384 | try:
|
| 385 | self.cur_token = next(self._tokenizer)
|
| 386 | except StopIteration:
|
| 387 | self.cur_token = None
|
| 388 | return cur_val
|
| 389 |
|
| 390 | def _match(self, kind):
|
| 391 | """The 'match' primitive of RD parsers.
|
| 392 |
|
| 393 | * Verifies that the current token is of the given kind (kind can
|
| 394 | be a tuple, in which the kind must match one of its members).
|
| 395 | * Returns the value of the current token
|
| 396 | * Reads in the next token
|
| 397 |
|
| 398 | Args:
|
| 399 | kind: A TokenKind, or a tuple of TokenKind
|
| 400 | """
|
| 401 | if self.cur_token.kind == kind:
|
| 402 | value = self.cur_token.value
|
| 403 | self._advance()
|
| 404 | return value
|
| 405 | else:
|
| 406 | raise ASDLSyntaxError(
|
| 407 | 'Expected token {}, got {}'.format(_TOKEN_STR[kind],
|
| 408 | self.cur_token.value),
|
| 409 | self.cur_token.lineno)
|
| 410 |
|
| 411 | def _at_keyword(self, keyword):
|
| 412 | return (self.cur_token.kind == TokenKind.Keyword and
|
| 413 | self.cur_token.value == keyword)
|
| 414 |
|
| 415 |
|
| 416 | _PRIMITIVE_TYPES = [
|
| 417 | 'string',
|
| 418 | 'int',
|
| 419 | 'uint16', # used for Token length - should we generalize this?
|
| 420 | 'BigInt',
|
| 421 | 'float',
|
| 422 | 'bool',
|
| 423 |
|
| 424 | # 'any' is used for value.{BuiltinProc,BuiltinFunc}, to cast from class
|
| 425 | # type
|
| 426 | 'any',
|
| 427 | ]
|
| 428 |
|
| 429 |
|
| 430 | def _ResolveType(typ, type_lookup):
|
| 431 | # type: (AST, dict) -> None
|
| 432 | """Recursively attach a 'resolved' field to AST nodes."""
|
| 433 | if isinstance(typ, ast.NamedType):
|
| 434 | if typ.name not in _PRIMITIVE_TYPES:
|
| 435 | ast_node = type_lookup.get(typ.name)
|
| 436 | if ast_node is None:
|
| 437 | raise ASDLSyntaxError("Couldn't find type %r" % typ.name)
|
| 438 | typ.resolved = ast_node
|
| 439 |
|
| 440 | elif isinstance(typ, ast.ParameterizedType):
|
| 441 | for child in typ.children:
|
| 442 | _ResolveType(child, type_lookup)
|
| 443 |
|
| 444 | if typ.type_name == 'Optional':
|
| 445 | child = typ.children[0]
|
| 446 | if isinstance(child, ast.NamedType):
|
| 447 | if child.name in _PRIMITIVE_TYPES and child.name != 'string':
|
| 448 | raise ASDLSyntaxError(
|
| 449 | 'Optional primitive type {} not allowed'.format(
|
| 450 | child.name))
|
| 451 |
|
| 452 | if child.resolved and isinstance(child.resolved,
|
| 453 | ast.SimpleSum):
|
| 454 | raise ASDLSyntaxError(
|
| 455 | 'Optional simple sum type {} not allowed'.format(
|
| 456 | child.name))
|
| 457 |
|
| 458 | else:
|
| 459 | raise AssertionError()
|
| 460 |
|
| 461 |
|
| 462 | def _ResolveFields(field_ast_nodes, type_lookup):
|
| 463 | """
|
| 464 | Args:
|
| 465 | type_lookup: Populated by name resolution
|
| 466 | """
|
| 467 | for field in field_ast_nodes:
|
| 468 | _ResolveType(field.typ, type_lookup)
|
| 469 |
|
| 470 |
|
| 471 | def _ResolveModule(module, app_types):
|
| 472 | """Name resolution for NamedType."""
|
| 473 | # Types that fields are declared with: int, id, word_part, etc.
|
| 474 | # Fields are NOT declared with Constructor names.
|
| 475 | type_lookup = dict(app_types)
|
| 476 |
|
| 477 | # Note: we don't actually load the type, and instead leave that to MyPy /
|
| 478 | # C++. A consequence of this is TypeNameHeuristic().
|
| 479 | for u in module.uses:
|
| 480 | for type_name in u.type_names:
|
| 481 | type_lookup[type_name] = u # type: ast.Use()
|
| 482 |
|
| 483 | # NOTE: We need two passes because types can be mutually recursive, e.g.
|
| 484 | # asdl/arith.asdl.
|
| 485 |
|
| 486 | # First pass: collect declared types and make entries for them.
|
| 487 | for d in module.dfns:
|
| 488 | type_lookup[d.name] = d.value
|
| 489 |
|
| 490 | # Second pass: add NamedType.resolved field
|
| 491 | for d in module.dfns:
|
| 492 | ast_node = d.value
|
| 493 | if isinstance(ast_node, ast.Product):
|
| 494 | #log('fields %s', ast_node.fields)
|
| 495 | _ResolveFields(ast_node.fields, type_lookup)
|
| 496 |
|
| 497 | elif isinstance(ast_node, ast.Sum):
|
| 498 | for cons in ast_node.types:
|
| 499 | _ResolveFields(cons.fields, type_lookup)
|
| 500 |
|
| 501 | else:
|
| 502 | raise AssertionError(ast_node)
|
| 503 |
|
| 504 |
|
| 505 | def LoadSchema(f, app_types, verbose=False):
|
| 506 | """Returns an AST for the schema."""
|
| 507 | p = ASDLParser()
|
| 508 | schema_ast = p.parse(f)
|
| 509 | if verbose:
|
| 510 | import sys
|
| 511 | schema_ast.Print(sys.stdout, 0)
|
| 512 |
|
| 513 | # Make sure all the names are valid
|
| 514 | _ResolveModule(schema_ast, app_types)
|
| 515 | return schema_ast
|