# 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 itertools
import os
import re
import sys

from mojom.generate import generator
from mojom.generate import module as mojom
from mojom.parse import ast


def _IsStrOrUnicode(x):
  if sys.version_info[0] < 3:
    return isinstance(x, (unicode, str))
  return isinstance(x, str)


def _DuplicateName(values):
  """Returns the 'mojom_name' of the first entry in |values| whose 'mojom_name'
  has already been encountered. If there are no duplicates, returns None."""
  names = set()
  for value in values:
    if value.mojom_name in names:
      return value.mojom_name
    names.add(value.mojom_name)
  return None


def _ElemsOfType(elems, elem_type, scope):
  """Find all elements of the given type.

  Args:
    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.

  Returns:
    {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 _ProcessElements(scope, elements, operations_by_type):
  """Iterates over the given elements, running a function from
  operations_by_type for any element that matches a key in that dict. The scope
  is the name of the surrounding scope, such as a filename or struct name, used
  only in error messages."""
  names_in_this_scope = set()
  for element in elements:
    # pylint: disable=unidiomatic-typecheck
    element_type = type(element)
    if element_type in operations_by_type:
      if element.mojom_name in names_in_this_scope:
        raise Exception('Names must be unique within a scope. The name "%s" is '
                        'used more than once within the scope "%s".' %
                        (duplicate_name, scope))
      operations_by_type[element_type](element)


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',
      'handle<platform>': 'h:p'
  }
  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', 'rmt', 'rcv',
                       'rma', 'rca')
    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.startswith('asso<'):
    assert kind.endswith('>')
    return 'asso:' + _MapKind(kind[5:-1])
  if kind.startswith('rmt<'):
    assert kind.endswith('>')
    return 'rmt:' + _MapKind(kind[4:-1])
  if kind.startswith('rcv<'):
    assert kind.endswith('>')
    return 'rcv:' + _MapKind(kind[4:-1])
  if kind.startswith('rma<'):
    assert kind.endswith('>')
    return 'rma:' + _MapKind(kind[4:-1])
  if kind.startswith('rca<'):
    assert kind.endswith('>')
    return 'rca:' + _MapKind(kind[4:-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([
    "double.INFINITY", "double.NEGATIVE_INFINITY", "double.NAN",
    "float.INFINITY", "float.NEGATIVE_INFINITY", "float.NAN"
])


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:'):
    mojom_name = spec[2:]
    for i in range(len(scope), -1, -1):
      test_spec = 'x:'
      if i > 0:
        test_spec += '.'.join(scope[:i]) + '.'
      test_spec += mojom_name
      kind = kinds.get(test_spec)
      if kind:
        return kind

  return kinds.get(spec)


def _GetScopeForKind(module, kind):
  """For a given kind, returns a tuple of progressively more specific names
  used to qualify the kind. For example if kind is an enum named Bar nested in a
  struct Foo within module 'foo', this would return ('foo', 'Foo', 'Bar')"""
  if isinstance(kind, mojom.Enum) and kind.parent_kind:
    # Enums may be nested in other kinds.
    return _GetScopeForKind(module, kind.parent_kind) + (kind.mojom_name, )

  module_fragment = (module.mojom_namespace, ) if module.mojom_namespace else ()
  kind_fragment = (kind.mojom_name, ) if kind else ()
  return module_fragment + kind_fragment


def _LookupValueInScope(module, kind, identifier):
  """Given a kind and an identifier, this attempts to resolve the given
  identifier to a concrete NamedValue within the scope of the given kind."""
  scope = _GetScopeForKind(module, kind)
  for i in reversed(range(len(scope) + 1)):
    qualified_name = '.'.join(scope[:i] + (identifier, ))
    value = module.values.get(qualified_name)
    if value:
      return value
  return None


def _LookupValue(module, parent_kind, implied_kind, ast_leaf_node):
  """Resolves a leaf node in the form ('IDENTIFIER', 'x') to a constant value
  identified by 'x' in some mojom definition. parent_kind is used as context
  when resolving the identifier. If the given leaf node is not an IDENTIFIER
  (e.g. already a constant value), it is returned as-is.

  If implied_kind is provided, the parsed identifier may also be resolved within
  its scope as fallback. This can be useful for more concise value references
  when assigning enum-typed constants or field values."""
  if not isinstance(ast_leaf_node, tuple) or ast_leaf_node[0] != 'IDENTIFIER':
    return ast_leaf_node

  # First look for a known user-defined identifier to resolve this within the
  # enclosing scope.
  identifier = ast_leaf_node[1]

  value = _LookupValueInScope(module, parent_kind, identifier)
  if value:
    return value

  # Next look in the scope of implied_kind, if provided.
  value = (implied_kind and implied_kind.module and _LookupValueInScope(
      implied_kind.module, implied_kind, identifier))
  if value:
    return value

  # Fall back on defined builtin symbols
  if _IsBuiltinValue(identifier):
    return mojom.BuiltinValue(identifier)

  raise ValueError('Unknown identifier %s' % identifier)


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'.

  Args:
    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