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