blob: ffad7447a93b485a95a82cf7c63498013e7edefc [file] [log] [blame]
# Copyright 2013 The Chromium Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
"""Convert parse tree to AST.
This module converts the parse tree to the AST we use for code generation. The
main entry point is OrderedModule, which gets passed the parser
representation of a mojom file. When called it's assumed that all imports have
already been parsed and converted to ASTs before.
import copy
import re
import module as mojom
from mojom.parse import ast
def _DuplicateName(values):
"""Returns the 'name' of the first entry in |values| whose 'name' has already
been encountered. If there are no duplicates, returns None."""
names = set()
for value in values:
if in names:
return None
def _ElemsOfType(elems, elem_type, scope):
"""Find all elements of the given type.
elems: {Sequence[Any]} Sequence of elems.
elem_type: {Type[C]} Extract all elems of this type.
scope: {str} The name of the surrounding scope (e.g. struct
definition). Used in error messages.
{List[C]} All elems of matching type.
assert isinstance(elem_type, type)
result = [elem for elem in elems if isinstance(elem, elem_type)]
duplicate_name = _DuplicateName(result)
if duplicate_name:
raise Exception('Names in mojom must be unique within a scope. The name '
'"%s" is used more than once within the scope "%s".' %
(duplicate_name, scope))
return result
def _MapKind(kind):
map_to_kind = {'bool': 'b',
'int8': 'i8',
'int16': 'i16',
'int32': 'i32',
'int64': 'i64',
'uint8': 'u8',
'uint16': 'u16',
'uint32': 'u32',
'uint64': 'u64',
'float': 'f',
'double': 'd',
'string': 's',
'handle': 'h',
'handle<data_pipe_consumer>': 'h:d:c',
'handle<data_pipe_producer>': 'h:d:p',
'handle<message_pipe>': 'h:m',
'handle<shared_buffer>': 'h:s'}
if kind.endswith('?'):
base_kind = _MapKind(kind[0:-1])
# NOTE: This doesn't rule out enum types. Those will be detected later, when
# cross-reference is established.
reference_kinds = ('m', 's', 'h', 'a', 'r', 'x', 'asso')
if re.split('[^a-z]', base_kind, 1)[0] not in reference_kinds:
raise Exception(
'A type (spec "%s") cannot be made nullable' % base_kind)
return '?' + base_kind
if kind.endswith('}'):
lbracket = kind.rfind('{')
value = kind[0:lbracket]
return 'm[' + _MapKind(kind[lbracket+1:-1]) + '][' + _MapKind(value) + ']'
if kind.endswith(']'):
lbracket = kind.rfind('[')
typename = kind[0:lbracket]
return 'a' + kind[lbracket+1:-1] + ':' + _MapKind(typename)
if kind.endswith('&'):
return 'r:' + _MapKind(kind[0:-1])
if kind.startswith('asso<'):
assert kind.endswith('>')
return 'asso:' + _MapKind(kind[5:-1])
if kind in map_to_kind:
return map_to_kind[kind]
return 'x:' + kind
def _AttributeListToDict(attribute_list):
if attribute_list is None:
return None
assert isinstance(attribute_list, ast.AttributeList)
# TODO(vtl): Check for duplicate keys here.
return dict([(attribute.key, attribute.value)
for attribute in attribute_list])
builtin_values = frozenset([
def _IsBuiltinValue(value):
return value in builtin_values
def _LookupKind(kinds, spec, scope):
"""Tries to find which Kind a spec refers to, given the scope in which its
referenced. Starts checking from the narrowest scope to most general. For
example, given a struct field like
Foo.Bar x;
Foo.Bar could refer to the type 'Bar' in the 'Foo' namespace, or an inner
type 'Bar' in the struct 'Foo' in the current namespace.
|scope| is a tuple that looks like (namespace, struct/interface), referring
to the location where the type is referenced."""
if spec.startswith('x:'):
name = spec[2:]
for i in xrange(len(scope), -1, -1):
test_spec = 'x:'
if i > 0:
test_spec += '.'.join(scope[:i]) + '.'
test_spec += name
kind = kinds.get(test_spec)
if kind:
return kind
return kinds.get(spec)
def _LookupValue(values, name, scope, kind):
"""Like LookupKind, but for constant values."""
# If the type is an enum, the value can be specified as a qualified name, in
# which case the form EnumName.ENUM_VALUE must be used. We use the presence
# of a '.' in the requested name to identify this. Otherwise, we prepend the
# enum name.
if isinstance(kind, mojom.Enum) and '.' not in name:
name = '%s.%s' % (kind.spec.split(':', 1)[1], name)
for i in reversed(xrange(len(scope) + 1)):
test_spec = '.'.join(scope[:i])
if test_spec:
test_spec += '.'
test_spec += name
value = values.get(test_spec)
if value:
return value
return values.get(name)
def _FixupExpression(module, value, scope, kind):
"""Translates an IDENTIFIER into a built-in value or structured NamedValue
if isinstance(value, tuple) and value[0] == 'IDENTIFIER':
# Allow user defined values to shadow builtins.
result = _LookupValue(module.values, value[1], scope, kind)
if result:
if isinstance(result, tuple):
raise Exception('Unable to resolve expression: %r' % value[1])
return result
if _IsBuiltinValue(value[1]):
return mojom.BuiltinValue(value[1])
return value
def _Kind(kinds, spec, scope):
"""Convert a type name into a mojom.Kind object.
As a side-effect this function adds the result to 'kinds'.
kinds: {Dict[str, mojom.Kind]} All known kinds up to this point, indexed by
their names.
spec: {str} A name uniquely identifying a type.
scope: {Tuple[str, str]} A tuple that looks like (namespace,
struct/interface), referring to the location where the type is
{mojom.Kind} The type corresponding to 'spec'.
kind = _LookupKind(kinds, spec, scope)
if kind:
return kind
if spec.startswith('?'):
kind = _Kind(kinds, spec[1:], scope).MakeNullableKind()
elif spec.startswith('a:'):
kind = mojom.Array(_Kind(kinds, spec[2:], scope))
elif spec.startswith('asso:'):
inner_kind = _Kind(kinds, spec[5:], scope)
if isinstance(inner_kind, mojom.InterfaceRequest):
kind = mojom.AssociatedInterfaceRequest(inner_kind)
kind = mojom.AssociatedInterface(inner_kind)
elif spec.startswith('a'):
colon = spec.find(':')
length = int(spec[1:colon])
kind = mojom.Array(_Kind(kinds, spec[colon+1:], scope), length)
elif spec.startswith('r:'):
kind = mojom.InterfaceRequest(_Kind(kinds, spec[2:], scope))
elif spec.startswith('m['):
# Isolate the two types from their brackets.
# It is not allowed to use map as key, so there shouldn't be nested ']'s
# inside the key type spec.
key_end = spec.find(']')
assert key_end != -1 and key_end < len(spec) - 1
assert spec[key_end+1] == '[' and spec[-1] == ']'
first_kind = spec[2:key_end]
second_kind = spec[key_end+2:-1]
kind = mojom.Map(_Kind(kinds, first_kind, scope),
_Kind(kinds, second_kind, scope))
kind = mojom.Kind(spec)
kinds[spec] = kind
return kind
def _KindFromImport(original_kind, imported_from):
"""Used with 'import module' - clones the kind imported from the given
module's namespace. Only used with Structs, Unions, Interfaces and Enums."""
kind = copy.copy(original_kind)
# |shared_definition| is used to store various properties (see
# |AddSharedProperty()| in, including |imported_from|. We don't
# want the copy to share these with the original, so copy it if necessary.
if hasattr(original_kind, 'shared_definition'):
kind.shared_definition = copy.copy(original_kind.shared_definition)
kind.imported_from = imported_from
return kind
def _Import(module, import_module):
import_item = {}
import_item['module_name'] =
import_item['namespace'] = import_module.namespace
import_item['module'] = import_module
# Copy the struct kinds from our imports into the current module.
importable_kinds = (mojom.Struct, mojom.Union, mojom.Enum, mojom.Interface)
for kind in import_module.kinds.itervalues():
if (isinstance(kind, importable_kinds) and
kind.imported_from is None):
kind = _KindFromImport(kind, import_item)
module.kinds[kind.spec] = kind
# Ditto for values.
for value in import_module.values.itervalues():
if value.imported_from is None:
# Values don't have shared definitions (since they're not nullable), so no
# need to do anything special.
value = copy.copy(value)
value.imported_from = import_item
module.values[value.GetSpec()] = value
return import_item
def _Struct(module, parsed_struct):
module: {mojom.Module} Module currently being constructed.
parsed_struct: {ast.Struct} Parsed struct.
{mojom.Struct} AST struct.
struct = mojom.Struct(module=module) =
struct.native_only = parsed_struct.body is None
struct.spec = 'x:' + module.namespace + '.' +
module.kinds[struct.spec] = struct
if struct.native_only:
struct.enums = []
struct.constants = []
struct.fields_data = []
struct.enums = map(
lambda enum: _Enum(module, enum, struct),
_ElemsOfType(parsed_struct.body, ast.Enum,
struct.constants = map(
lambda constant: _Constant(module, constant, struct),
_ElemsOfType(parsed_struct.body, ast.Const,
# Stash fields parsed_struct here temporarily.
struct.fields_data = _ElemsOfType(
parsed_struct.body, ast.StructField,
struct.attributes = _AttributeListToDict(parsed_struct.attribute_list)
# Enforce that a [Native] attribute is set to make native-only struct
# declarations more explicit.
if struct.native_only:
if not struct.attributes or not struct.attributes.get('Native', False):
raise Exception("Native-only struct declarations must include a " +
"Native attribute.")
return struct
def _Union(module, parsed_union):
module: {mojom.Module} Module currently being constructed.
parsed_union: {ast.Union} Parsed union.
{mojom.Union} AST union.
union = mojom.Union(module=module) =
union.spec = 'x:' + module.namespace + '.' +
module.kinds[union.spec] = union
# Stash fields parsed_union here temporarily.
union.fields_data = _ElemsOfType(
parsed_union.body, ast.UnionField,
union.attributes = _AttributeListToDict(parsed_union.attribute_list)
return union
def _StructField(module, parsed_field, struct):
module: {mojom.Module} Module currently being constructed.
parsed_field: {ast.StructField} Parsed struct field.
struct: {mojom.Struct} Struct this field belongs to.
{mojom.StructField} AST struct field.
field = mojom.StructField() =
field.kind = _Kind(
module.kinds, _MapKind(parsed_field.typename),
field.ordinal = parsed_field.ordinal.value if parsed_field.ordinal else None
field.default = _FixupExpression(
module, parsed_field.default_value, (module.namespace,,
field.attributes = _AttributeListToDict(parsed_field.attribute_list)
return field
def _UnionField(module, parsed_field, union):
module: {mojom.Module} Module currently being constructed.
parsed_field: {ast.UnionField} Parsed union field.
union: {mojom.Union} Union this fields belong to.
{mojom.UnionField} AST union.
field = mojom.UnionField() =
field.kind = _Kind(
module.kinds, _MapKind(parsed_field.typename),
field.ordinal = parsed_field.ordinal.value if parsed_field.ordinal else None
field.default = _FixupExpression(
module, None, (module.namespace,, field.kind)
field.attributes = _AttributeListToDict(parsed_field.attribute_list)
return field
def _Parameter(module, parsed_param, interface):
module: {mojom.Module} Module currently being constructed.
parsed_param: {ast.Parameter} Parsed parameter.
union: {mojom.Interface} Interface this parameter belongs to.
{mojom.Parameter} AST parameter.
parameter = mojom.Parameter() =
parameter.kind = _Kind(
module.kinds, _MapKind(parsed_param.typename),
parameter.ordinal = (
parsed_param.ordinal.value if parsed_param.ordinal else None)
parameter.default = None # TODO(tibell): We never have these. Remove field?
parameter.attributes = _AttributeListToDict(parsed_param.attribute_list)
return parameter
def _Method(module, parsed_method, interface):
module: {mojom.Module} Module currently being constructed.
parsed_method: {ast.Method} Parsed method.
interface: {mojom.Interface} Interface this method belongs to.
{mojom.Method} AST method.
method = mojom.Method(
ordinal=parsed_method.ordinal.value if parsed_method.ordinal else None)
method.parameters = map(
lambda parameter: _Parameter(module, parameter, interface),
if parsed_method.response_parameter_list is not None:
method.response_parameters = map(
lambda parameter: _Parameter(module, parameter, interface),
method.attributes = _AttributeListToDict(parsed_method.attribute_list)
# Enforce that only methods with response can have a [Sync] attribute.
if method.sync and method.response_parameters is None:
raise Exception("Only methods with response can include a [Sync] "
"attribute. If no response parameters are needed, you "
"could use an empty response parameter list, i.e., "
"\"=> ()\".")
return method
def _Interface(module, parsed_iface):
module: {mojom.Module} Module currently being constructed.
parsed_iface: {ast.Interface} Parsed interface.
{mojom.Interface} AST interface.
interface = mojom.Interface(module=module) =
interface.spec = 'x:' + module.namespace + '.' +
module.kinds[interface.spec] = interface
interface.enums = map(
lambda enum: _Enum(module, enum, interface),
_ElemsOfType(parsed_iface.body, ast.Enum,
interface.constants = map(
lambda constant: _Constant(module, constant, interface),
_ElemsOfType(parsed_iface.body, ast.Const,
# Stash methods parsed_iface here temporarily.
interface.methods_data = _ElemsOfType(
parsed_iface.body, ast.Method,
interface.attributes = _AttributeListToDict(parsed_iface.attribute_list)
return interface
def _EnumField(module, enum, parsed_field, parent_kind):
module: {mojom.Module} Module currently being constructed.
enum: {mojom.Enum} Enum this field belongs to.
parsed_field: {ast.EnumValue} Parsed enum value.
parent_kind: {mojom.Kind} The enclosing type.
{mojom.EnumField} AST enum field.
field = mojom.EnumField() =
# TODO(mpcomplete): FixupExpression should be done in the second pass,
# so constants and enums can refer to each other.
# TODO(mpcomplete): But then, what if constants are initialized to an enum? Or
# vice versa?
if parent_kind:
field.value = _FixupExpression(
module, parsed_field.value, (module.namespace,, enum)
field.value = _FixupExpression(
module, parsed_field.value, (module.namespace, ), enum)
field.attributes = _AttributeListToDict(parsed_field.attribute_list)
value = mojom.EnumValue(module, enum, field)
module.values[value.GetSpec()] = value
return field
def _ResolveNumericEnumValues(enum_fields):
Given a reference to a list of mojom.EnumField, resolves and assigns their
values to EnumField.numeric_value.
# map of <name> -> integral value
resolved_enum_values = {}
prev_value = -1
for field in enum_fields:
# This enum value is +1 the previous enum value (e.g: BEGIN).
if field.value is None:
prev_value += 1
# Integral value (e.g: BEGIN = -0x1).
elif type(field.value) is str:
prev_value = int(field.value, 0)
# Reference to a previous enum value (e.g: INIT = BEGIN).
elif type(field.value) is mojom.EnumValue:
prev_value = resolved_enum_values[]
raise Exception("Unresolved enum value.")
resolved_enum_values[] = prev_value
field.numeric_value = prev_value
def _Enum(module, parsed_enum, parent_kind):
module: {mojom.Module} Module currently being constructed.
parsed_enum: {ast.Enum} Parsed enum.
{mojom.Enum} AST enum.
enum = mojom.Enum(module=module) =
enum.native_only = parsed_enum.enum_value_list is None
name =
if parent_kind:
name = + '.' + name
enum.spec = 'x:%s.%s' % (module.namespace, name)
enum.parent_kind = parent_kind
enum.attributes = _AttributeListToDict(parsed_enum.attribute_list)
if enum.native_only:
enum.fields = []
enum.fields = map(
lambda field: _EnumField(module, enum, field, parent_kind),
module.kinds[enum.spec] = enum
# Enforce that a [Native] attribute is set to make native-only enum
# declarations more explicit.
if enum.native_only:
if not enum.attributes or not enum.attributes.get('Native', False):
raise Exception("Native-only enum declarations must include a " +
"Native attribute.")
return enum
def _Constant(module, parsed_const, parent_kind):
module: {mojom.Module} Module currently being constructed.
parsed_const: {ast.Const} Parsed constant.
{mojom.Constant} AST constant.
constant = mojom.Constant() =
if parent_kind:
scope = (module.namespace,
scope = (module.namespace, )
# TODO(mpcomplete): maybe we should only support POD kinds.
constant.kind = _Kind(module.kinds, _MapKind(parsed_const.typename), scope)
constant.parent_kind = parent_kind
constant.value = _FixupExpression(module, parsed_const.value, scope, None)
value = mojom.ConstantValue(module, parent_kind, constant)
module.values[value.GetSpec()] = value
return constant
def _Module(tree, name, imports):
tree: {ast.Mojom} The parse tree.
name: {str} The mojom filename, excluding the path.
imports: {Dict[str, mojom.Module]} Mapping from filenames, as they appear in
the import list, to already processed modules. Used to process imports.
{mojom.Module} An AST for the mojom.
module = mojom.Module()
module.kinds = {}
for kind in mojom.PRIMITIVES:
module.kinds[kind.spec] = kind
module.values = {} = name
module.namespace =[1] if tree.module else ''
# Imports must come first, because they add to module.kinds which is used
# by by the others.
module.imports = [
_Import(module, imports[imp.import_filename])
for imp in tree.import_list]
if tree.module and tree.module.attribute_list:
assert isinstance(tree.module.attribute_list, ast.AttributeList)
# TODO(vtl): Check for duplicate keys here.
module.attributes = dict((attribute.key, attribute.value)
for attribute in tree.module.attribute_list)
# First pass collects kinds.
module.enums = map(
lambda enum: _Enum(module, enum, None),
_ElemsOfType(tree.definition_list, ast.Enum, name))
module.structs = map(
lambda struct: _Struct(module, struct),
_ElemsOfType(tree.definition_list, ast.Struct, name))
module.unions = map(
lambda union: _Union(module, union),
_ElemsOfType(tree.definition_list, ast.Union, name))
module.interfaces = map(
lambda interface: _Interface(module, interface),
_ElemsOfType(tree.definition_list, ast.Interface, name))
module.constants = map(
lambda constant: _Constant(module, constant, None),
_ElemsOfType(tree.definition_list, ast.Const, name))
# Second pass expands fields and methods. This allows fields and parameters
# to refer to kinds defined anywhere in the mojom.
for struct in module.structs:
struct.fields = map(lambda field:
_StructField(module, field, struct), struct.fields_data)
del struct.fields_data
for union in module.unions:
union.fields = map(lambda field:
_UnionField(module, field, union), union.fields_data)
del union.fields_data
for interface in module.interfaces:
interface.methods = map(lambda method:
_Method(module, method, interface), interface.methods_data)
del interface.methods_data
return module
def OrderedModule(tree, name, imports):
"""Convert parse tree to AST module.
tree: {ast.Mojom} The parse tree.
name: {str} The mojom filename, excluding the path.
imports: {Dict[str, mojom.Module]} Mapping from filenames, as they appear in
the import list, to already processed modules. Used to process imports.
{mojom.Module} An AST for the mojom.
module = _Module(tree, name, imports)
for interface in module.interfaces:
next_ordinal = 0
for method in interface.methods:
if method.ordinal is None:
method.ordinal = next_ordinal
next_ordinal = method.ordinal + 1
return module