1# Copyright 2013 The Chromium Authors. All rights reserved. 2# Use of this source code is governed by a BSD-style license that can be 3# found in the LICENSE file. 4 5"""Convert parse tree to AST. 6 7This module converts the parse tree to the AST we use for code generation. The 8main entry point is OrderedModule, which gets passed the parser 9representation of a mojom file. When called it's assumed that all imports have 10already been parsed and converted to ASTs before. 11""" 12 13import copy 14import re 15 16import module as mojom 17from mojom.parse import ast 18 19def _DuplicateName(values): 20 """Returns the 'name' of the first entry in |values| whose 'name' has already 21 been encountered. If there are no duplicates, returns None.""" 22 names = set() 23 for value in values: 24 if value.name in names: 25 return value.name 26 names.add(value.name) 27 return None 28 29def _ElemsOfType(elems, elem_type, scope): 30 """Find all elements of the given type. 31 32 Args: 33 elems: {Sequence[Any]} Sequence of elems. 34 elem_type: {Type[C]} Extract all elems of this type. 35 scope: {str} The name of the surrounding scope (e.g. struct 36 definition). Used in error messages. 37 38 Returns: 39 {List[C]} All elems of matching type. 40 """ 41 assert isinstance(elem_type, type) 42 result = [elem for elem in elems if isinstance(elem, elem_type)] 43 duplicate_name = _DuplicateName(result) 44 if duplicate_name: 45 raise Exception('Names in mojom must be unique within a scope. The name ' 46 '"%s" is used more than once within the scope "%s".' % 47 (duplicate_name, scope)) 48 return result 49 50def _MapKind(kind): 51 map_to_kind = {'bool': 'b', 52 'int8': 'i8', 53 'int16': 'i16', 54 'int32': 'i32', 55 'int64': 'i64', 56 'uint8': 'u8', 57 'uint16': 'u16', 58 'uint32': 'u32', 59 'uint64': 'u64', 60 'float': 'f', 61 'double': 'd', 62 'string': 's', 63 'handle': 'h', 64 'handle<data_pipe_consumer>': 'h:d:c', 65 'handle<data_pipe_producer>': 'h:d:p', 66 'handle<message_pipe>': 'h:m', 67 'handle<shared_buffer>': 'h:s'} 68 if kind.endswith('?'): 69 base_kind = _MapKind(kind[0:-1]) 70 # NOTE: This doesn't rule out enum types. Those will be detected later, when 71 # cross-reference is established. 72 reference_kinds = ('m', 's', 'h', 'a', 'r', 'x', 'asso') 73 if re.split('[^a-z]', base_kind, 1)[0] not in reference_kinds: 74 raise Exception( 75 'A type (spec "%s") cannot be made nullable' % base_kind) 76 return '?' + base_kind 77 if kind.endswith('}'): 78 lbracket = kind.rfind('{') 79 value = kind[0:lbracket] 80 return 'm[' + _MapKind(kind[lbracket+1:-1]) + '][' + _MapKind(value) + ']' 81 if kind.endswith(']'): 82 lbracket = kind.rfind('[') 83 typename = kind[0:lbracket] 84 return 'a' + kind[lbracket+1:-1] + ':' + _MapKind(typename) 85 if kind.endswith('&'): 86 return 'r:' + _MapKind(kind[0:-1]) 87 if kind.startswith('asso<'): 88 assert kind.endswith('>') 89 return 'asso:' + _MapKind(kind[5:-1]) 90 if kind in map_to_kind: 91 return map_to_kind[kind] 92 return 'x:' + kind 93 94def _AttributeListToDict(attribute_list): 95 if attribute_list is None: 96 return None 97 assert isinstance(attribute_list, ast.AttributeList) 98 # TODO(vtl): Check for duplicate keys here. 99 return dict([(attribute.key, attribute.value) 100 for attribute in attribute_list]) 101 102builtin_values = frozenset([ 103 "double.INFINITY", 104 "double.NEGATIVE_INFINITY", 105 "double.NAN", 106 "float.INFINITY", 107 "float.NEGATIVE_INFINITY", 108 "float.NAN"]) 109 110def _IsBuiltinValue(value): 111 return value in builtin_values 112 113def _LookupKind(kinds, spec, scope): 114 """Tries to find which Kind a spec refers to, given the scope in which its 115 referenced. Starts checking from the narrowest scope to most general. For 116 example, given a struct field like 117 Foo.Bar x; 118 Foo.Bar could refer to the type 'Bar' in the 'Foo' namespace, or an inner 119 type 'Bar' in the struct 'Foo' in the current namespace. 120 121 |scope| is a tuple that looks like (namespace, struct/interface), referring 122 to the location where the type is referenced.""" 123 if spec.startswith('x:'): 124 name = spec[2:] 125 for i in xrange(len(scope), -1, -1): 126 test_spec = 'x:' 127 if i > 0: 128 test_spec += '.'.join(scope[:i]) + '.' 129 test_spec += name 130 kind = kinds.get(test_spec) 131 if kind: 132 return kind 133 134 return kinds.get(spec) 135 136def _LookupValue(values, name, scope, kind): 137 """Like LookupKind, but for constant values.""" 138 # If the type is an enum, the value can be specified as a qualified name, in 139 # which case the form EnumName.ENUM_VALUE must be used. We use the presence 140 # of a '.' in the requested name to identify this. Otherwise, we prepend the 141 # enum name. 142 if isinstance(kind, mojom.Enum) and '.' not in name: 143 name = '%s.%s' % (kind.spec.split(':', 1)[1], name) 144 for i in reversed(xrange(len(scope) + 1)): 145 test_spec = '.'.join(scope[:i]) 146 if test_spec: 147 test_spec += '.' 148 test_spec += name 149 value = values.get(test_spec) 150 if value: 151 return value 152 153 return values.get(name) 154 155def _FixupExpression(module, value, scope, kind): 156 """Translates an IDENTIFIER into a built-in value or structured NamedValue 157 object.""" 158 if isinstance(value, tuple) and value[0] == 'IDENTIFIER': 159 # Allow user defined values to shadow builtins. 160 result = _LookupValue(module.values, value[1], scope, kind) 161 if result: 162 if isinstance(result, tuple): 163 raise Exception('Unable to resolve expression: %r' % value[1]) 164 return result 165 if _IsBuiltinValue(value[1]): 166 return mojom.BuiltinValue(value[1]) 167 return value 168 169def _Kind(kinds, spec, scope): 170 """Convert a type name into a mojom.Kind object. 171 172 As a side-effect this function adds the result to 'kinds'. 173 174 Args: 175 kinds: {Dict[str, mojom.Kind]} All known kinds up to this point, indexed by 176 their names. 177 spec: {str} A name uniquely identifying a type. 178 scope: {Tuple[str, str]} A tuple that looks like (namespace, 179 struct/interface), referring to the location where the type is 180 referenced. 181 182 Returns: 183 {mojom.Kind} The type corresponding to 'spec'. 184 """ 185 kind = _LookupKind(kinds, spec, scope) 186 if kind: 187 return kind 188 189 if spec.startswith('?'): 190 kind = _Kind(kinds, spec[1:], scope).MakeNullableKind() 191 elif spec.startswith('a:'): 192 kind = mojom.Array(_Kind(kinds, spec[2:], scope)) 193 elif spec.startswith('asso:'): 194 inner_kind = _Kind(kinds, spec[5:], scope) 195 if isinstance(inner_kind, mojom.InterfaceRequest): 196 kind = mojom.AssociatedInterfaceRequest(inner_kind) 197 else: 198 kind = mojom.AssociatedInterface(inner_kind) 199 elif spec.startswith('a'): 200 colon = spec.find(':') 201 length = int(spec[1:colon]) 202 kind = mojom.Array(_Kind(kinds, spec[colon+1:], scope), length) 203 elif spec.startswith('r:'): 204 kind = mojom.InterfaceRequest(_Kind(kinds, spec[2:], scope)) 205 elif spec.startswith('m['): 206 # Isolate the two types from their brackets. 207 208 # It is not allowed to use map as key, so there shouldn't be nested ']'s 209 # inside the key type spec. 210 key_end = spec.find(']') 211 assert key_end != -1 and key_end < len(spec) - 1 212 assert spec[key_end+1] == '[' and spec[-1] == ']' 213 214 first_kind = spec[2:key_end] 215 second_kind = spec[key_end+2:-1] 216 217 kind = mojom.Map(_Kind(kinds, first_kind, scope), 218 _Kind(kinds, second_kind, scope)) 219 else: 220 kind = mojom.Kind(spec) 221 222 kinds[spec] = kind 223 return kind 224 225def _KindFromImport(original_kind, imported_from): 226 """Used with 'import module' - clones the kind imported from the given 227 module's namespace. Only used with Structs, Unions, Interfaces and Enums.""" 228 kind = copy.copy(original_kind) 229 # |shared_definition| is used to store various properties (see 230 # |AddSharedProperty()| in module.py), including |imported_from|. We don't 231 # want the copy to share these with the original, so copy it if necessary. 232 if hasattr(original_kind, 'shared_definition'): 233 kind.shared_definition = copy.copy(original_kind.shared_definition) 234 kind.imported_from = imported_from 235 return kind 236 237def _Import(module, import_module): 238 import_item = {} 239 import_item['module_name'] = import_module.name 240 import_item['namespace'] = import_module.namespace 241 import_item['module'] = import_module 242 243 # Copy the struct kinds from our imports into the current module. 244 importable_kinds = (mojom.Struct, mojom.Union, mojom.Enum, mojom.Interface) 245 for kind in import_module.kinds.itervalues(): 246 if (isinstance(kind, importable_kinds) and 247 kind.imported_from is None): 248 kind = _KindFromImport(kind, import_item) 249 module.kinds[kind.spec] = kind 250 # Ditto for values. 251 for value in import_module.values.itervalues(): 252 if value.imported_from is None: 253 # Values don't have shared definitions (since they're not nullable), so no 254 # need to do anything special. 255 value = copy.copy(value) 256 value.imported_from = import_item 257 module.values[value.GetSpec()] = value 258 259 return import_item 260 261def _Struct(module, parsed_struct): 262 """ 263 Args: 264 module: {mojom.Module} Module currently being constructed. 265 parsed_struct: {ast.Struct} Parsed struct. 266 267 Returns: 268 {mojom.Struct} AST struct. 269 """ 270 struct = mojom.Struct(module=module) 271 struct.name = parsed_struct.name 272 struct.native_only = parsed_struct.body is None 273 struct.spec = 'x:' + module.namespace + '.' + struct.name 274 module.kinds[struct.spec] = struct 275 if struct.native_only: 276 struct.enums = [] 277 struct.constants = [] 278 struct.fields_data = [] 279 else: 280 struct.enums = map( 281 lambda enum: _Enum(module, enum, struct), 282 _ElemsOfType(parsed_struct.body, ast.Enum, parsed_struct.name)) 283 struct.constants = map( 284 lambda constant: _Constant(module, constant, struct), 285 _ElemsOfType(parsed_struct.body, ast.Const, parsed_struct.name)) 286 # Stash fields parsed_struct here temporarily. 287 struct.fields_data = _ElemsOfType( 288 parsed_struct.body, ast.StructField, parsed_struct.name) 289 struct.attributes = _AttributeListToDict(parsed_struct.attribute_list) 290 291 # Enforce that a [Native] attribute is set to make native-only struct 292 # declarations more explicit. 293 if struct.native_only: 294 if not struct.attributes or not struct.attributes.get('Native', False): 295 raise Exception("Native-only struct declarations must include a " + 296 "Native attribute.") 297 298 return struct 299 300def _Union(module, parsed_union): 301 """ 302 Args: 303 module: {mojom.Module} Module currently being constructed. 304 parsed_union: {ast.Union} Parsed union. 305 306 Returns: 307 {mojom.Union} AST union. 308 """ 309 union = mojom.Union(module=module) 310 union.name = parsed_union.name 311 union.spec = 'x:' + module.namespace + '.' + union.name 312 module.kinds[union.spec] = union 313 # Stash fields parsed_union here temporarily. 314 union.fields_data = _ElemsOfType( 315 parsed_union.body, ast.UnionField, parsed_union.name) 316 union.attributes = _AttributeListToDict(parsed_union.attribute_list) 317 return union 318 319def _StructField(module, parsed_field, struct): 320 """ 321 Args: 322 module: {mojom.Module} Module currently being constructed. 323 parsed_field: {ast.StructField} Parsed struct field. 324 struct: {mojom.Struct} Struct this field belongs to. 325 326 Returns: 327 {mojom.StructField} AST struct field. 328 """ 329 field = mojom.StructField() 330 field.name = parsed_field.name 331 field.kind = _Kind( 332 module.kinds, _MapKind(parsed_field.typename), 333 (module.namespace, struct.name)) 334 field.ordinal = parsed_field.ordinal.value if parsed_field.ordinal else None 335 field.default = _FixupExpression( 336 module, parsed_field.default_value, (module.namespace, struct.name), 337 field.kind) 338 field.attributes = _AttributeListToDict(parsed_field.attribute_list) 339 return field 340 341def _UnionField(module, parsed_field, union): 342 """ 343 Args: 344 module: {mojom.Module} Module currently being constructed. 345 parsed_field: {ast.UnionField} Parsed union field. 346 union: {mojom.Union} Union this fields belong to. 347 348 Returns: 349 {mojom.UnionField} AST union. 350 """ 351 field = mojom.UnionField() 352 field.name = parsed_field.name 353 field.kind = _Kind( 354 module.kinds, _MapKind(parsed_field.typename), 355 (module.namespace, union.name)) 356 field.ordinal = parsed_field.ordinal.value if parsed_field.ordinal else None 357 field.default = _FixupExpression( 358 module, None, (module.namespace, union.name), field.kind) 359 field.attributes = _AttributeListToDict(parsed_field.attribute_list) 360 return field 361 362def _Parameter(module, parsed_param, interface): 363 """ 364 Args: 365 module: {mojom.Module} Module currently being constructed. 366 parsed_param: {ast.Parameter} Parsed parameter. 367 union: {mojom.Interface} Interface this parameter belongs to. 368 369 Returns: 370 {mojom.Parameter} AST parameter. 371 """ 372 parameter = mojom.Parameter() 373 parameter.name = parsed_param.name 374 parameter.kind = _Kind( 375 module.kinds, _MapKind(parsed_param.typename), 376 (module.namespace, interface.name)) 377 parameter.ordinal = ( 378 parsed_param.ordinal.value if parsed_param.ordinal else None) 379 parameter.default = None # TODO(tibell): We never have these. Remove field? 380 parameter.attributes = _AttributeListToDict(parsed_param.attribute_list) 381 return parameter 382 383def _Method(module, parsed_method, interface): 384 """ 385 Args: 386 module: {mojom.Module} Module currently being constructed. 387 parsed_method: {ast.Method} Parsed method. 388 interface: {mojom.Interface} Interface this method belongs to. 389 390 Returns: 391 {mojom.Method} AST method. 392 """ 393 method = mojom.Method( 394 interface, parsed_method.name, 395 ordinal=parsed_method.ordinal.value if parsed_method.ordinal else None) 396 method.parameters = map( 397 lambda parameter: _Parameter(module, parameter, interface), 398 parsed_method.parameter_list) 399 if parsed_method.response_parameter_list is not None: 400 method.response_parameters = map( 401 lambda parameter: _Parameter(module, parameter, interface), 402 parsed_method.response_parameter_list) 403 method.attributes = _AttributeListToDict(parsed_method.attribute_list) 404 405 # Enforce that only methods with response can have a [Sync] attribute. 406 if method.sync and method.response_parameters is None: 407 raise Exception("Only methods with response can include a [Sync] " 408 "attribute. If no response parameters are needed, you " 409 "could use an empty response parameter list, i.e., " 410 "\"=> ()\".") 411 412 return method 413 414def _Interface(module, parsed_iface): 415 """ 416 Args: 417 module: {mojom.Module} Module currently being constructed. 418 parsed_iface: {ast.Interface} Parsed interface. 419 420 Returns: 421 {mojom.Interface} AST interface. 422 """ 423 interface = mojom.Interface(module=module) 424 interface.name = parsed_iface.name 425 interface.spec = 'x:' + module.namespace + '.' + interface.name 426 module.kinds[interface.spec] = interface 427 interface.enums = map( 428 lambda enum: _Enum(module, enum, interface), 429 _ElemsOfType(parsed_iface.body, ast.Enum, parsed_iface.name)) 430 interface.constants = map( 431 lambda constant: _Constant(module, constant, interface), 432 _ElemsOfType(parsed_iface.body, ast.Const, parsed_iface.name)) 433 # Stash methods parsed_iface here temporarily. 434 interface.methods_data = _ElemsOfType( 435 parsed_iface.body, ast.Method, parsed_iface.name) 436 interface.attributes = _AttributeListToDict(parsed_iface.attribute_list) 437 return interface 438 439def _EnumField(module, enum, parsed_field, parent_kind): 440 """ 441 Args: 442 module: {mojom.Module} Module currently being constructed. 443 enum: {mojom.Enum} Enum this field belongs to. 444 parsed_field: {ast.EnumValue} Parsed enum value. 445 parent_kind: {mojom.Kind} The enclosing type. 446 447 Returns: 448 {mojom.EnumField} AST enum field. 449 """ 450 field = mojom.EnumField() 451 field.name = parsed_field.name 452 # TODO(mpcomplete): FixupExpression should be done in the second pass, 453 # so constants and enums can refer to each other. 454 # TODO(mpcomplete): But then, what if constants are initialized to an enum? Or 455 # vice versa? 456 if parent_kind: 457 field.value = _FixupExpression( 458 module, parsed_field.value, (module.namespace, parent_kind.name), enum) 459 else: 460 field.value = _FixupExpression( 461 module, parsed_field.value, (module.namespace, ), enum) 462 field.attributes = _AttributeListToDict(parsed_field.attribute_list) 463 value = mojom.EnumValue(module, enum, field) 464 module.values[value.GetSpec()] = value 465 return field 466 467def _ResolveNumericEnumValues(enum_fields): 468 """ 469 Given a reference to a list of mojom.EnumField, resolves and assigns their 470 values to EnumField.numeric_value. 471 """ 472 473 # map of <name> -> integral value 474 resolved_enum_values = {} 475 prev_value = -1 476 for field in enum_fields: 477 # This enum value is +1 the previous enum value (e.g: BEGIN). 478 if field.value is None: 479 prev_value += 1 480 481 # Integral value (e.g: BEGIN = -0x1). 482 elif type(field.value) is str: 483 prev_value = int(field.value, 0) 484 485 # Reference to a previous enum value (e.g: INIT = BEGIN). 486 elif type(field.value) is mojom.EnumValue: 487 prev_value = resolved_enum_values[field.value.name] 488 else: 489 raise Exception("Unresolved enum value.") 490 491 resolved_enum_values[field.name] = prev_value 492 field.numeric_value = prev_value 493 494def _Enum(module, parsed_enum, parent_kind): 495 """ 496 Args: 497 module: {mojom.Module} Module currently being constructed. 498 parsed_enum: {ast.Enum} Parsed enum. 499 500 Returns: 501 {mojom.Enum} AST enum. 502 """ 503 enum = mojom.Enum(module=module) 504 enum.name = parsed_enum.name 505 enum.native_only = parsed_enum.enum_value_list is None 506 name = enum.name 507 if parent_kind: 508 name = parent_kind.name + '.' + name 509 enum.spec = 'x:%s.%s' % (module.namespace, name) 510 enum.parent_kind = parent_kind 511 enum.attributes = _AttributeListToDict(parsed_enum.attribute_list) 512 if enum.native_only: 513 enum.fields = [] 514 else: 515 enum.fields = map( 516 lambda field: _EnumField(module, enum, field, parent_kind), 517 parsed_enum.enum_value_list) 518 _ResolveNumericEnumValues(enum.fields) 519 520 module.kinds[enum.spec] = enum 521 522 # Enforce that a [Native] attribute is set to make native-only enum 523 # declarations more explicit. 524 if enum.native_only: 525 if not enum.attributes or not enum.attributes.get('Native', False): 526 raise Exception("Native-only enum declarations must include a " + 527 "Native attribute.") 528 529 return enum 530 531def _Constant(module, parsed_const, parent_kind): 532 """ 533 Args: 534 module: {mojom.Module} Module currently being constructed. 535 parsed_const: {ast.Const} Parsed constant. 536 537 Returns: 538 {mojom.Constant} AST constant. 539 """ 540 constant = mojom.Constant() 541 constant.name = parsed_const.name 542 if parent_kind: 543 scope = (module.namespace, parent_kind.name) 544 else: 545 scope = (module.namespace, ) 546 # TODO(mpcomplete): maybe we should only support POD kinds. 547 constant.kind = _Kind(module.kinds, _MapKind(parsed_const.typename), scope) 548 constant.parent_kind = parent_kind 549 constant.value = _FixupExpression(module, parsed_const.value, scope, None) 550 551 value = mojom.ConstantValue(module, parent_kind, constant) 552 module.values[value.GetSpec()] = value 553 return constant 554 555def _Module(tree, name, imports): 556 """ 557 Args: 558 tree: {ast.Mojom} The parse tree. 559 name: {str} The mojom filename, excluding the path. 560 imports: {Dict[str, mojom.Module]} Mapping from filenames, as they appear in 561 the import list, to already processed modules. Used to process imports. 562 563 Returns: 564 {mojom.Module} An AST for the mojom. 565 """ 566 module = mojom.Module() 567 module.kinds = {} 568 for kind in mojom.PRIMITIVES: 569 module.kinds[kind.spec] = kind 570 571 module.values = {} 572 573 module.name = name 574 module.namespace = tree.module.name[1] if tree.module else '' 575 # Imports must come first, because they add to module.kinds which is used 576 # by by the others. 577 module.imports = [ 578 _Import(module, imports[imp.import_filename]) 579 for imp in tree.import_list] 580 if tree.module and tree.module.attribute_list: 581 assert isinstance(tree.module.attribute_list, ast.AttributeList) 582 # TODO(vtl): Check for duplicate keys here. 583 module.attributes = dict((attribute.key, attribute.value) 584 for attribute in tree.module.attribute_list) 585 586 # First pass collects kinds. 587 module.enums = map( 588 lambda enum: _Enum(module, enum, None), 589 _ElemsOfType(tree.definition_list, ast.Enum, name)) 590 module.structs = map( 591 lambda struct: _Struct(module, struct), 592 _ElemsOfType(tree.definition_list, ast.Struct, name)) 593 module.unions = map( 594 lambda union: _Union(module, union), 595 _ElemsOfType(tree.definition_list, ast.Union, name)) 596 module.interfaces = map( 597 lambda interface: _Interface(module, interface), 598 _ElemsOfType(tree.definition_list, ast.Interface, name)) 599 module.constants = map( 600 lambda constant: _Constant(module, constant, None), 601 _ElemsOfType(tree.definition_list, ast.Const, name)) 602 603 # Second pass expands fields and methods. This allows fields and parameters 604 # to refer to kinds defined anywhere in the mojom. 605 for struct in module.structs: 606 struct.fields = map(lambda field: 607 _StructField(module, field, struct), struct.fields_data) 608 del struct.fields_data 609 for union in module.unions: 610 union.fields = map(lambda field: 611 _UnionField(module, field, union), union.fields_data) 612 del union.fields_data 613 for interface in module.interfaces: 614 interface.methods = map(lambda method: 615 _Method(module, method, interface), interface.methods_data) 616 del interface.methods_data 617 618 return module 619 620def OrderedModule(tree, name, imports): 621 """Convert parse tree to AST module. 622 623 Args: 624 tree: {ast.Mojom} The parse tree. 625 name: {str} The mojom filename, excluding the path. 626 imports: {Dict[str, mojom.Module]} Mapping from filenames, as they appear in 627 the import list, to already processed modules. Used to process imports. 628 629 Returns: 630 {mojom.Module} An AST for the mojom. 631 """ 632 module = _Module(tree, name, imports) 633 for interface in module.interfaces: 634 next_ordinal = 0 635 for method in interface.methods: 636 if method.ordinal is None: 637 method.ordinal = next_ordinal 638 next_ordinal = method.ordinal + 1 639 return module 640