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"""Convert parse tree to AST.
5
6This module converts the parse tree to the AST we use for code generation. The
7main entry point is OrderedModule, which gets passed the parser
8representation of a mojom file. When called it's assumed that all imports have
9already been parsed and converted to ASTs before.
10"""
11
12import itertools
13import os
14import re
15import sys
16
17from mojom.generate import generator
18from mojom.generate import module as mojom
19from mojom.parse import ast
20
21
22def _IsStrOrUnicode(x):
23  if sys.version_info[0] < 3:
24    return isinstance(x, (unicode, str))
25  return isinstance(x, str)
26
27
28def _DuplicateName(values):
29  """Returns the 'mojom_name' of the first entry in |values| whose 'mojom_name'
30  has already been encountered. If there are no duplicates, returns None."""
31  names = set()
32  for value in values:
33    if value.mojom_name in names:
34      return value.mojom_name
35    names.add(value.mojom_name)
36  return None
37
38
39def _ElemsOfType(elems, elem_type, scope):
40  """Find all elements of the given type.
41
42  Args:
43    elems: {Sequence[Any]} Sequence of elems.
44    elem_type: {Type[C]} Extract all elems of this type.
45    scope: {str} The name of the surrounding scope (e.g. struct
46        definition). Used in error messages.
47
48  Returns:
49    {List[C]} All elems of matching type.
50  """
51  assert isinstance(elem_type, type)
52  result = [elem for elem in elems if isinstance(elem, elem_type)]
53  duplicate_name = _DuplicateName(result)
54  if duplicate_name:
55    raise Exception('Names in mojom must be unique within a scope. The name '
56                    '"%s" is used more than once within the scope "%s".' %
57                    (duplicate_name, scope))
58  return result
59
60
61def _ProcessElements(scope, elements, operations_by_type):
62  """Iterates over the given elements, running a function from
63  operations_by_type for any element that matches a key in that dict. The scope
64  is the name of the surrounding scope, such as a filename or struct name, used
65  only in error messages."""
66  names_in_this_scope = set()
67  for element in elements:
68    # pylint: disable=unidiomatic-typecheck
69    element_type = type(element)
70    if element_type in operations_by_type:
71      if element.mojom_name in names_in_this_scope:
72        raise Exception('Names must be unique within a scope. The name "%s" is '
73                        'used more than once within the scope "%s".' %
74                        (duplicate_name, scope))
75      operations_by_type[element_type](element)
76
77
78def _MapKind(kind):
79  map_to_kind = {
80      'bool': 'b',
81      'int8': 'i8',
82      'int16': 'i16',
83      'int32': 'i32',
84      'int64': 'i64',
85      'uint8': 'u8',
86      'uint16': 'u16',
87      'uint32': 'u32',
88      'uint64': 'u64',
89      'float': 'f',
90      'double': 'd',
91      'string': 's',
92      'handle': 'h',
93      'handle<data_pipe_consumer>': 'h:d:c',
94      'handle<data_pipe_producer>': 'h:d:p',
95      'handle<message_pipe>': 'h:m',
96      'handle<shared_buffer>': 'h:s',
97      'handle<platform>': 'h:p'
98  }
99  if kind.endswith('?'):
100    base_kind = _MapKind(kind[0:-1])
101    # NOTE: This doesn't rule out enum types. Those will be detected later, when
102    # cross-reference is established.
103    reference_kinds = ('m', 's', 'h', 'a', 'r', 'x', 'asso', 'rmt', 'rcv',
104                       'rma', 'rca')
105    if re.split('[^a-z]', base_kind, 1)[0] not in reference_kinds:
106      raise Exception('A type (spec "%s") cannot be made nullable' % base_kind)
107    return '?' + base_kind
108  if kind.endswith('}'):
109    lbracket = kind.rfind('{')
110    value = kind[0:lbracket]
111    return 'm[' + _MapKind(kind[lbracket + 1:-1]) + '][' + _MapKind(value) + ']'
112  if kind.endswith(']'):
113    lbracket = kind.rfind('[')
114    typename = kind[0:lbracket]
115    return 'a' + kind[lbracket + 1:-1] + ':' + _MapKind(typename)
116  if kind.endswith('&'):
117    return 'r:' + _MapKind(kind[0:-1])
118  if kind.startswith('asso<'):
119    assert kind.endswith('>')
120    return 'asso:' + _MapKind(kind[5:-1])
121  if kind.startswith('rmt<'):
122    assert kind.endswith('>')
123    return 'rmt:' + _MapKind(kind[4:-1])
124  if kind.startswith('rcv<'):
125    assert kind.endswith('>')
126    return 'rcv:' + _MapKind(kind[4:-1])
127  if kind.startswith('rma<'):
128    assert kind.endswith('>')
129    return 'rma:' + _MapKind(kind[4:-1])
130  if kind.startswith('rca<'):
131    assert kind.endswith('>')
132    return 'rca:' + _MapKind(kind[4:-1])
133  if kind in map_to_kind:
134    return map_to_kind[kind]
135  return 'x:' + kind
136
137
138def _AttributeListToDict(attribute_list):
139  if attribute_list is None:
140    return None
141  assert isinstance(attribute_list, ast.AttributeList)
142  # TODO(vtl): Check for duplicate keys here.
143  return dict(
144      [(attribute.key, attribute.value) for attribute in attribute_list])
145
146
147builtin_values = frozenset([
148    "double.INFINITY", "double.NEGATIVE_INFINITY", "double.NAN",
149    "float.INFINITY", "float.NEGATIVE_INFINITY", "float.NAN"
150])
151
152
153def _IsBuiltinValue(value):
154  return value in builtin_values
155
156
157def _LookupKind(kinds, spec, scope):
158  """Tries to find which Kind a spec refers to, given the scope in which its
159  referenced. Starts checking from the narrowest scope to most general. For
160  example, given a struct field like
161    Foo.Bar x;
162  Foo.Bar could refer to the type 'Bar' in the 'Foo' namespace, or an inner
163  type 'Bar' in the struct 'Foo' in the current namespace.
164
165  |scope| is a tuple that looks like (namespace, struct/interface), referring
166  to the location where the type is referenced."""
167  if spec.startswith('x:'):
168    mojom_name = spec[2:]
169    for i in range(len(scope), -1, -1):
170      test_spec = 'x:'
171      if i > 0:
172        test_spec += '.'.join(scope[:i]) + '.'
173      test_spec += mojom_name
174      kind = kinds.get(test_spec)
175      if kind:
176        return kind
177
178  return kinds.get(spec)
179
180
181def _GetScopeForKind(module, kind):
182  """For a given kind, returns a tuple of progressively more specific names
183  used to qualify the kind. For example if kind is an enum named Bar nested in a
184  struct Foo within module 'foo', this would return ('foo', 'Foo', 'Bar')"""
185  if isinstance(kind, mojom.Enum) and kind.parent_kind:
186    # Enums may be nested in other kinds.
187    return _GetScopeForKind(module, kind.parent_kind) + (kind.mojom_name, )
188
189  module_fragment = (module.mojom_namespace, ) if module.mojom_namespace else ()
190  kind_fragment = (kind.mojom_name, ) if kind else ()
191  return module_fragment + kind_fragment
192
193
194def _LookupValueInScope(module, kind, identifier):
195  """Given a kind and an identifier, this attempts to resolve the given
196  identifier to a concrete NamedValue within the scope of the given kind."""
197  scope = _GetScopeForKind(module, kind)
198  for i in reversed(range(len(scope) + 1)):
199    qualified_name = '.'.join(scope[:i] + (identifier, ))
200    value = module.values.get(qualified_name)
201    if value:
202      return value
203  return None
204
205
206def _LookupValue(module, parent_kind, implied_kind, ast_leaf_node):
207  """Resolves a leaf node in the form ('IDENTIFIER', 'x') to a constant value
208  identified by 'x' in some mojom definition. parent_kind is used as context
209  when resolving the identifier. If the given leaf node is not an IDENTIFIER
210  (e.g. already a constant value), it is returned as-is.
211
212  If implied_kind is provided, the parsed identifier may also be resolved within
213  its scope as fallback. This can be useful for more concise value references
214  when assigning enum-typed constants or field values."""
215  if not isinstance(ast_leaf_node, tuple) or ast_leaf_node[0] != 'IDENTIFIER':
216    return ast_leaf_node
217
218  # First look for a known user-defined identifier to resolve this within the
219  # enclosing scope.
220  identifier = ast_leaf_node[1]
221
222  value = _LookupValueInScope(module, parent_kind, identifier)
223  if value:
224    return value
225
226  # Next look in the scope of implied_kind, if provided.
227  value = (implied_kind and implied_kind.module and _LookupValueInScope(
228      implied_kind.module, implied_kind, identifier))
229  if value:
230    return value
231
232  # Fall back on defined builtin symbols
233  if _IsBuiltinValue(identifier):
234    return mojom.BuiltinValue(identifier)
235
236  raise ValueError('Unknown identifier %s' % identifier)
237
238
239def _Kind(kinds, spec, scope):
240  """Convert a type name into a mojom.Kind object.
241
242  As a side-effect this function adds the result to 'kinds'.
243
244  Args:
245    kinds: {Dict[str, mojom.Kind]} All known kinds up to this point, indexed by
246        their names.
247    spec: {str} A name uniquely identifying a type.
248    scope: {Tuple[str, str]} A tuple that looks like (namespace,
249        struct/interface), referring to the location where the type is
250        referenced.
251
252  Returns:
253    {mojom.Kind} The type corresponding to 'spec'.
254  """
255  kind = _LookupKind(kinds, spec, scope)
256  if kind:
257    return kind
258
259  if spec.startswith('?'):
260    kind = _Kind(kinds, spec[1:], scope).MakeNullableKind()
261  elif spec.startswith('a:'):
262    kind = mojom.Array(_Kind(kinds, spec[2:], scope))
263  elif spec.startswith('asso:'):
264    inner_kind = _Kind(kinds, spec[5:], scope)
265    if isinstance(inner_kind, mojom.InterfaceRequest):
266      kind = mojom.AssociatedInterfaceRequest(inner_kind)
267    else:
268      kind = mojom.AssociatedInterface(inner_kind)
269  elif spec.startswith('a'):
270    colon = spec.find(':')
271    length = int(spec[1:colon])
272    kind = mojom.Array(_Kind(kinds, spec[colon + 1:], scope), length)
273  elif spec.startswith('r:'):
274    kind = mojom.InterfaceRequest(_Kind(kinds, spec[2:], scope))
275  elif spec.startswith('rmt:'):
276    kind = mojom.PendingRemote(_Kind(kinds, spec[4:], scope))
277  elif spec.startswith('rcv:'):
278    kind = mojom.PendingReceiver(_Kind(kinds, spec[4:], scope))
279  elif spec.startswith('rma:'):
280    kind = mojom.PendingAssociatedRemote(_Kind(kinds, spec[4:], scope))
281  elif spec.startswith('rca:'):
282    kind = mojom.PendingAssociatedReceiver(_Kind(kinds, spec[4:], scope))
283  elif spec.startswith('m['):
284    # Isolate the two types from their brackets.
285
286    # It is not allowed to use map as key, so there shouldn't be nested ']'s
287    # inside the key type spec.
288    key_end = spec.find(']')
289    assert key_end != -1 and key_end < len(spec) - 1
290    assert spec[key_end + 1] == '[' and spec[-1] == ']'
291
292    first_kind = spec[2:key_end]
293    second_kind = spec[key_end + 2:-1]
294
295    kind = mojom.Map(
296        _Kind(kinds, first_kind, scope), _Kind(kinds, second_kind, scope))
297  else:
298    kind = mojom.Kind(spec)
299
300  kinds[spec] = kind
301  return kind
302
303
304def _Import(module, import_module):
305  # Copy the struct kinds from our imports into the current module.
306  importable_kinds = (mojom.Struct, mojom.Union, mojom.Enum, mojom.Interface)
307  for kind in import_module.kinds.values():
308    if (isinstance(kind, importable_kinds)
309        and kind.module.path == import_module.path):
310      module.kinds[kind.spec] = kind
311  # Ditto for values.
312  for value in import_module.values.values():
313    if value.module.path == import_module.path:
314      module.values[value.GetSpec()] = value
315
316  return import_module
317
318
319def _Struct(module, parsed_struct):
320  """
321  Args:
322    module: {mojom.Module} Module currently being constructed.
323    parsed_struct: {ast.Struct} Parsed struct.
324
325  Returns:
326    {mojom.Struct} AST struct.
327  """
328  struct = mojom.Struct(module=module)
329  struct.mojom_name = parsed_struct.mojom_name
330  struct.native_only = parsed_struct.body is None
331  struct.spec = 'x:' + module.GetNamespacePrefix() + struct.mojom_name
332  module.kinds[struct.spec] = struct
333  struct.enums = []
334  struct.constants = []
335  struct.fields_data = []
336  if not struct.native_only:
337    _ProcessElements(
338        parsed_struct.mojom_name, parsed_struct.body, {
339            ast.Enum:
340            lambda enum: struct.enums.append(_Enum(module, enum, struct)),
341            ast.Const:
342            lambda const: struct.constants.append(
343                _Constant(module, const, struct)),
344            ast.StructField:
345            struct.fields_data.append,
346        })
347
348  struct.attributes = _AttributeListToDict(parsed_struct.attribute_list)
349
350  # Enforce that a [Native] attribute is set to make native-only struct
351  # declarations more explicit.
352  if struct.native_only:
353    if not struct.attributes or not struct.attributes.get('Native', False):
354      raise Exception("Native-only struct declarations must include a " +
355                      "Native attribute.")
356
357  if struct.attributes and struct.attributes.get('CustomSerializer', False):
358    struct.custom_serializer = True
359
360  return struct
361
362
363def _Union(module, parsed_union):
364  """
365  Args:
366    module: {mojom.Module} Module currently being constructed.
367    parsed_union: {ast.Union} Parsed union.
368
369  Returns:
370    {mojom.Union} AST union.
371  """
372  union = mojom.Union(module=module)
373  union.mojom_name = parsed_union.mojom_name
374  union.spec = 'x:' + module.GetNamespacePrefix() + union.mojom_name
375  module.kinds[union.spec] = union
376  # Stash fields parsed_union here temporarily.
377  union.fields_data = []
378  _ProcessElements(parsed_union.mojom_name, parsed_union.body,
379                   {ast.UnionField: union.fields_data.append})
380  union.attributes = _AttributeListToDict(parsed_union.attribute_list)
381  return union
382
383
384def _StructField(module, parsed_field, struct):
385  """
386  Args:
387    module: {mojom.Module} Module currently being constructed.
388    parsed_field: {ast.StructField} Parsed struct field.
389    struct: {mojom.Struct} Struct this field belongs to.
390
391  Returns:
392    {mojom.StructField} AST struct field.
393  """
394  field = mojom.StructField()
395  field.mojom_name = parsed_field.mojom_name
396  field.kind = _Kind(module.kinds, _MapKind(parsed_field.typename),
397                     (module.mojom_namespace, struct.mojom_name))
398  field.ordinal = parsed_field.ordinal.value if parsed_field.ordinal else None
399  field.default = _LookupValue(module, struct, field.kind,
400                               parsed_field.default_value)
401  field.attributes = _AttributeListToDict(parsed_field.attribute_list)
402  return field
403
404
405def _UnionField(module, parsed_field, union):
406  """
407  Args:
408    module: {mojom.Module} Module currently being constructed.
409    parsed_field: {ast.UnionField} Parsed union field.
410    union: {mojom.Union} Union this fields belong to.
411
412  Returns:
413    {mojom.UnionField} AST union.
414  """
415  field = mojom.UnionField()
416  field.mojom_name = parsed_field.mojom_name
417  field.kind = _Kind(module.kinds, _MapKind(parsed_field.typename),
418                     (module.mojom_namespace, union.mojom_name))
419  field.ordinal = parsed_field.ordinal.value if parsed_field.ordinal else None
420  field.default = None
421  field.attributes = _AttributeListToDict(parsed_field.attribute_list)
422  return field
423
424
425def _Parameter(module, parsed_param, interface):
426  """
427  Args:
428    module: {mojom.Module} Module currently being constructed.
429    parsed_param: {ast.Parameter} Parsed parameter.
430    union: {mojom.Interface} Interface this parameter belongs to.
431
432  Returns:
433    {mojom.Parameter} AST parameter.
434  """
435  parameter = mojom.Parameter()
436  parameter.mojom_name = parsed_param.mojom_name
437  parameter.kind = _Kind(module.kinds, _MapKind(parsed_param.typename),
438                         (module.mojom_namespace, interface.mojom_name))
439  parameter.ordinal = (parsed_param.ordinal.value
440                       if parsed_param.ordinal else None)
441  parameter.default = None  # TODO(tibell): We never have these. Remove field?
442  parameter.attributes = _AttributeListToDict(parsed_param.attribute_list)
443  return parameter
444
445
446def _Method(module, parsed_method, interface):
447  """
448  Args:
449    module: {mojom.Module} Module currently being constructed.
450    parsed_method: {ast.Method} Parsed method.
451    interface: {mojom.Interface} Interface this method belongs to.
452
453  Returns:
454    {mojom.Method} AST method.
455  """
456  method = mojom.Method(
457      interface,
458      parsed_method.mojom_name,
459      ordinal=parsed_method.ordinal.value if parsed_method.ordinal else None)
460  method.parameters = list(
461      map(lambda parameter: _Parameter(module, parameter, interface),
462          parsed_method.parameter_list))
463  if parsed_method.response_parameter_list is not None:
464    method.response_parameters = list(
465        map(lambda parameter: _Parameter(module, parameter, interface),
466            parsed_method.response_parameter_list))
467  method.attributes = _AttributeListToDict(parsed_method.attribute_list)
468
469  # Enforce that only methods with response can have a [Sync] attribute.
470  if method.sync and method.response_parameters is None:
471    raise Exception("Only methods with response can include a [Sync] "
472                    "attribute. If no response parameters are needed, you "
473                    "could use an empty response parameter list, i.e., "
474                    "\"=> ()\".")
475
476  return method
477
478
479def _Interface(module, parsed_iface):
480  """
481  Args:
482    module: {mojom.Module} Module currently being constructed.
483    parsed_iface: {ast.Interface} Parsed interface.
484
485  Returns:
486    {mojom.Interface} AST interface.
487  """
488  interface = mojom.Interface(module=module)
489  interface.mojom_name = parsed_iface.mojom_name
490  interface.spec = 'x:' + module.GetNamespacePrefix() + interface.mojom_name
491  module.kinds[interface.spec] = interface
492  interface.attributes = _AttributeListToDict(parsed_iface.attribute_list)
493  interface.enums = []
494  interface.constants = []
495  interface.methods_data = []
496  _ProcessElements(
497      parsed_iface.mojom_name, parsed_iface.body, {
498          ast.Enum:
499          lambda enum: interface.enums.append(_Enum(module, enum, interface)),
500          ast.Const:
501          lambda const: interface.constants.append(
502              _Constant(module, const, interface)),
503          ast.Method:
504          interface.methods_data.append,
505      })
506  return interface
507
508
509def _EnumField(module, enum, parsed_field):
510  """
511  Args:
512    module: {mojom.Module} Module currently being constructed.
513    enum: {mojom.Enum} Enum this field belongs to.
514    parsed_field: {ast.EnumValue} Parsed enum value.
515
516  Returns:
517    {mojom.EnumField} AST enum field.
518  """
519  field = mojom.EnumField()
520  field.mojom_name = parsed_field.mojom_name
521  field.value = _LookupValue(module, enum, None, parsed_field.value)
522  field.attributes = _AttributeListToDict(parsed_field.attribute_list)
523  value = mojom.EnumValue(module, enum, field)
524  module.values[value.GetSpec()] = value
525  return field
526
527
528def _ResolveNumericEnumValues(enum):
529  """
530  Given a reference to a mojom.Enum, resolves and assigns the numeric value of
531  each field, and also computes the min_value and max_value of the enum.
532  """
533
534  # map of <mojom_name> -> integral value
535  prev_value = -1
536  min_value = None
537  max_value = None
538  for field in enum.fields:
539    # This enum value is +1 the previous enum value (e.g: BEGIN).
540    if field.value is None:
541      prev_value += 1
542
543    # Integral value (e.g: BEGIN = -0x1).
544    elif _IsStrOrUnicode(field.value):
545      prev_value = int(field.value, 0)
546
547    # Reference to a previous enum value (e.g: INIT = BEGIN).
548    elif isinstance(field.value, mojom.EnumValue):
549      prev_value = field.value.field.numeric_value
550    elif isinstance(field.value, mojom.ConstantValue):
551      constant = field.value.constant
552      kind = constant.kind
553      if not mojom.IsIntegralKind(kind) or mojom.IsBoolKind(kind):
554        raise ValueError('Enum values must be integers. %s is not an integer.' %
555                         constant.mojom_name)
556      prev_value = int(constant.value, 0)
557    else:
558      raise Exception('Unresolved enum value for %s' % field.value.GetSpec())
559
560    #resolved_enum_values[field.mojom_name] = prev_value
561    field.numeric_value = prev_value
562    if min_value is None or prev_value < min_value:
563      min_value = prev_value
564    if max_value is None or prev_value > max_value:
565      max_value = prev_value
566
567  enum.min_value = min_value
568  enum.max_value = max_value
569
570
571def _Enum(module, parsed_enum, parent_kind):
572  """
573  Args:
574    module: {mojom.Module} Module currently being constructed.
575    parsed_enum: {ast.Enum} Parsed enum.
576
577  Returns:
578    {mojom.Enum} AST enum.
579  """
580  enum = mojom.Enum(module=module)
581  enum.mojom_name = parsed_enum.mojom_name
582  enum.native_only = parsed_enum.enum_value_list is None
583  mojom_name = enum.mojom_name
584  if parent_kind:
585    mojom_name = parent_kind.mojom_name + '.' + mojom_name
586  enum.spec = 'x:%s.%s' % (module.mojom_namespace, mojom_name)
587  enum.parent_kind = parent_kind
588  enum.attributes = _AttributeListToDict(parsed_enum.attribute_list)
589
590  if not enum.native_only:
591    enum.fields = list(
592        map(lambda field: _EnumField(module, enum, field),
593            parsed_enum.enum_value_list))
594    _ResolveNumericEnumValues(enum)
595
596  module.kinds[enum.spec] = enum
597
598  # Enforce that a [Native] attribute is set to make native-only enum
599  # declarations more explicit.
600  if enum.native_only:
601    if not enum.attributes or not enum.attributes.get('Native', False):
602      raise Exception("Native-only enum declarations must include a " +
603                      "Native attribute.")
604
605  return enum
606
607
608def _Constant(module, parsed_const, parent_kind):
609  """
610  Args:
611    module: {mojom.Module} Module currently being constructed.
612    parsed_const: {ast.Const} Parsed constant.
613
614  Returns:
615    {mojom.Constant} AST constant.
616  """
617  constant = mojom.Constant()
618  constant.mojom_name = parsed_const.mojom_name
619  if parent_kind:
620    scope = (module.mojom_namespace, parent_kind.mojom_name)
621  else:
622    scope = (module.mojom_namespace, )
623  # TODO(mpcomplete): maybe we should only support POD kinds.
624  constant.kind = _Kind(module.kinds, _MapKind(parsed_const.typename), scope)
625  constant.parent_kind = parent_kind
626  constant.value = _LookupValue(module, parent_kind, constant.kind,
627                                parsed_const.value)
628
629  # Iteratively resolve this constant reference to a concrete value
630  while isinstance(constant.value, mojom.ConstantValue):
631    constant.value = constant.value.constant.value
632
633  value = mojom.ConstantValue(module, parent_kind, constant)
634  module.values[value.GetSpec()] = value
635  return constant
636
637
638def _CollectReferencedKinds(module, all_defined_kinds):
639  """
640  Takes a {mojom.Module} object and a list of all defined kinds within that
641  module, and enumerates the complete dict of user-defined mojom types
642  (as {mojom.Kind} objects) referenced by the module's own defined kinds (i.e.
643  as types of struct or union or interface parameters. The returned dict is
644  keyed by kind spec.
645  """
646
647  def extract_referenced_user_kinds(kind):
648    if mojom.IsArrayKind(kind):
649      return extract_referenced_user_kinds(kind.kind)
650    if mojom.IsMapKind(kind):
651      return (extract_referenced_user_kinds(kind.key_kind) +
652              extract_referenced_user_kinds(kind.value_kind))
653    if (mojom.IsInterfaceRequestKind(kind) or mojom.IsAssociatedKind(kind)
654        or mojom.IsPendingRemoteKind(kind)
655        or mojom.IsPendingReceiverKind(kind)):
656      return [kind.kind]
657    if mojom.IsStructKind(kind):
658      return [kind]
659    if (mojom.IsInterfaceKind(kind) or mojom.IsEnumKind(kind)
660        or mojom.IsUnionKind(kind)):
661      return [kind]
662    return []
663
664  def sanitize_kind(kind):
665    """Removes nullability from a kind"""
666    if kind.spec.startswith('?'):
667      return _Kind(module.kinds, kind.spec[1:], (module.mojom_namespace, ''))
668    return kind
669
670  referenced_user_kinds = {}
671  for defined_kind in all_defined_kinds:
672    if mojom.IsStructKind(defined_kind) or mojom.IsUnionKind(defined_kind):
673      for field in defined_kind.fields:
674        for referenced_kind in extract_referenced_user_kinds(field.kind):
675          sanitized_kind = sanitize_kind(referenced_kind)
676          referenced_user_kinds[sanitized_kind.spec] = sanitized_kind
677
678  # Also scan for references in parameter lists
679  for interface in module.interfaces:
680    for method in interface.methods:
681      for param in itertools.chain(method.parameters or [],
682                                   method.response_parameters or []):
683        for referenced_kind in extract_referenced_user_kinds(param.kind):
684          sanitized_kind = sanitize_kind(referenced_kind)
685          referenced_user_kinds[sanitized_kind.spec] = sanitized_kind
686
687  return referenced_user_kinds
688
689
690def _AssignDefaultOrdinals(items):
691  """Assigns default ordinal values to a sequence of items if necessary."""
692  next_ordinal = 0
693  for item in items:
694    if item.ordinal is not None:
695      next_ordinal = item.ordinal + 1
696    else:
697      item.ordinal = next_ordinal
698      next_ordinal += 1
699
700
701def _AssertTypeIsStable(kind):
702  """Raises an error if a type is not stable, meaning it is composed of at least
703  one type that is not marked [Stable]."""
704
705  def assertDependencyIsStable(dependency):
706    if (mojom.IsEnumKind(dependency) or mojom.IsStructKind(dependency)
707        or mojom.IsUnionKind(dependency) or mojom.IsInterfaceKind(dependency)):
708      if not dependency.stable:
709        raise Exception(
710            '%s is marked [Stable] but cannot be stable because it depends on '
711            '%s, which is not marked [Stable].' %
712            (kind.mojom_name, dependency.mojom_name))
713    elif mojom.IsArrayKind(dependency) or mojom.IsAnyInterfaceKind(dependency):
714      assertDependencyIsStable(dependency.kind)
715    elif mojom.IsMapKind(dependency):
716      assertDependencyIsStable(dependency.key_kind)
717      assertDependencyIsStable(dependency.value_kind)
718
719  if mojom.IsStructKind(kind) or mojom.IsUnionKind(kind):
720    for field in kind.fields:
721      assertDependencyIsStable(field.kind)
722  elif mojom.IsInterfaceKind(kind):
723    for method in kind.methods:
724      for param in method.param_struct.fields:
725        assertDependencyIsStable(param.kind)
726      if method.response_param_struct:
727        for response_param in method.response_param_struct.fields:
728          assertDependencyIsStable(response_param.kind)
729
730
731def _Module(tree, path, imports):
732  """
733  Args:
734    tree: {ast.Mojom} The parse tree.
735    path: {str} The path to the mojom file.
736    imports: {Dict[str, mojom.Module]} Mapping from filenames, as they appear in
737        the import list, to already processed modules. Used to process imports.
738
739  Returns:
740    {mojom.Module} An AST for the mojom.
741  """
742  module = mojom.Module(path=path)
743  module.kinds = {}
744  for kind in mojom.PRIMITIVES:
745    module.kinds[kind.spec] = kind
746
747  module.values = {}
748
749  module.mojom_namespace = tree.module.mojom_namespace[1] if tree.module else ''
750  # Imports must come first, because they add to module.kinds which is used
751  # by by the others.
752  module.imports = [
753      _Import(module, imports[imp.import_filename]) for imp in tree.import_list
754  ]
755  if tree.module and tree.module.attribute_list:
756    assert isinstance(tree.module.attribute_list, ast.AttributeList)
757    # TODO(vtl): Check for duplicate keys here.
758    module.attributes = dict((attribute.key, attribute.value)
759                             for attribute in tree.module.attribute_list)
760
761  filename = os.path.basename(path)
762  # First pass collects kinds.
763  module.constants = []
764  module.enums = []
765  module.structs = []
766  module.unions = []
767  module.interfaces = []
768  _ProcessElements(
769      filename, tree.definition_list, {
770          ast.Const:
771          lambda const: module.constants.append(_Constant(module, const, None)),
772          ast.Enum:
773          lambda enum: module.enums.append(_Enum(module, enum, None)),
774          ast.Struct:
775          lambda struct: module.structs.append(_Struct(module, struct)),
776          ast.Union:
777          lambda union: module.unions.append(_Union(module, union)),
778          ast.Interface:
779          lambda interface: module.interfaces.append(
780              _Interface(module, interface)),
781      })
782
783  # Second pass expands fields and methods. This allows fields and parameters
784  # to refer to kinds defined anywhere in the mojom.
785  all_defined_kinds = {}
786  for struct in module.structs:
787    struct.fields = list(
788        map(lambda field: _StructField(module, field, struct),
789            struct.fields_data))
790    _AssignDefaultOrdinals(struct.fields)
791    del struct.fields_data
792    all_defined_kinds[struct.spec] = struct
793    for enum in struct.enums:
794      all_defined_kinds[enum.spec] = enum
795
796  for union in module.unions:
797    union.fields = list(
798        map(lambda field: _UnionField(module, field, union), union.fields_data))
799    _AssignDefaultOrdinals(union.fields)
800    del union.fields_data
801    all_defined_kinds[union.spec] = union
802
803  for interface in module.interfaces:
804    interface.methods = list(
805        map(lambda method: _Method(module, method, interface),
806            interface.methods_data))
807    _AssignDefaultOrdinals(interface.methods)
808    del interface.methods_data
809    all_defined_kinds[interface.spec] = interface
810    for enum in interface.enums:
811      all_defined_kinds[enum.spec] = enum
812  for enum in module.enums:
813    all_defined_kinds[enum.spec] = enum
814
815  all_referenced_kinds = _CollectReferencedKinds(module,
816                                                 all_defined_kinds.values())
817  imported_kind_specs = set(all_referenced_kinds.keys()).difference(
818      set(all_defined_kinds.keys()))
819  module.imported_kinds = dict(
820      (spec, all_referenced_kinds[spec]) for spec in imported_kind_specs)
821
822  generator.AddComputedData(module)
823  for iface in module.interfaces:
824    for method in iface.methods:
825      if method.param_struct:
826        _AssignDefaultOrdinals(method.param_struct.fields)
827      if method.response_param_struct:
828        _AssignDefaultOrdinals(method.response_param_struct.fields)
829
830  # Ensure that all types marked [Stable] are actually stable. Enums are
831  # automatically OK since they don't depend on other definitions.
832  for kinds in (module.structs, module.unions, module.interfaces):
833    for kind in kinds:
834      if kind.stable:
835        _AssertTypeIsStable(kind)
836
837  return module
838
839
840def OrderedModule(tree, path, imports):
841  """Convert parse tree to AST module.
842
843  Args:
844    tree: {ast.Mojom} The parse tree.
845    path: {str} The path to the mojom file.
846    imports: {Dict[str, mojom.Module]} Mapping from filenames, as they appear in
847        the import list, to already processed modules. Used to process imports.
848
849  Returns:
850    {mojom.Module} An AST for the mojom.
851  """
852  module = _Module(tree, path, imports)
853  return module
854