#!/usr/bin/python
# Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
# for details. All rights reserved. Use of this source code is governed by a
# BSD-style license that can be found in the LICENSE file.

import copy
import database
import logging
import monitored
import multiprocessing
import os
import os.path
import re
import sys
import tempfile
import time
import traceback

import idl_validator

import compiler
import compute_interfaces_info_individual
from compute_interfaces_info_individual import InterfaceInfoCollector
import idl_definitions

from idlnode import *

_logger = logging.getLogger('databasebuilder')

# Used in source annotations to specify the parent interface declaring
# a displaced declaration. The 'via' attribute specifies the parent interface
# which implements a displaced declaration.
_VIA_ANNOTATION_ATTR_NAME = 'via'


class DatabaseBuilderOptions(object):
  """Used in specifying options when importing new interfaces"""

  def __init__(self,
      idl_defines=[],
      source=None, source_attributes={},
      rename_operation_arguments_on_merge=False,
      add_new_interfaces=True,
      obsolete_old_declarations=False,
      logging_level=logging.WARNING):
    """Constructor.
    Args:
      idl_defines -- list of definitions for the idl gcc pre-processor
      source -- the origin of the IDL file, used for annotating the
        database.
      source_attributes -- this map of attributes is used as
        annotation attributes.
      rename_operation_arguments_on_merge -- if True, will rename
        operation arguments when merging using the new name rather
        than the old.
      add_new_interfaces -- when False, if an interface is a new
        addition, it will be ignored.
      obsolete_old_declarations -- when True, if a declaration
        from a certain source is not re-declared, it will be removed.
    """
    self.source = source
    self.source_attributes = source_attributes
    self.idl_defines = idl_defines
    self.rename_operation_arguments_on_merge = \
        rename_operation_arguments_on_merge
    self.add_new_interfaces = add_new_interfaces
    self.obsolete_old_declarations = obsolete_old_declarations
    _logger.setLevel(logging_level)


def format_exception(e):
    exception_list = traceback.format_stack()
    exception_list = exception_list[:-2]
    exception_list.extend(traceback.format_tb(sys.exc_info()[2]))
    exception_list.extend(traceback.format_exception_only(sys.exc_info()[0], sys.exc_info()[1]))

    exception_str = "Traceback (most recent call last):\n"
    exception_str += "".join(exception_list)
    # Removing the last \n
    exception_str = exception_str[:-1]

    return exception_str


# Compile IDL using Blink's IDL compiler.
def _compile_idl_file(build, file_name, import_options):
  try:
    idl_file_fullpath = os.path.realpath(file_name)
    idl_definition = build.idl_compiler.compile_file(idl_file_fullpath)
    return idl_definition
  except Exception as err:
    print 'ERROR: idl_compiler.py: ' + os.path.basename(file_name)
    print err
    print
    print 'Stack Dump:'
    print format_exception(err)

  return 1


# Create the Model (IDLFile) from the new AST of the compiled IDL file.
def _load_idl_file(build, file_name, import_options):
  try:
    # Compute interface name from IDL filename (it's one for one in WebKit).
    name = os.path.splitext(os.path.basename(file_name))[0]

    idl_definition = new_asts[name]
    return IDLFile(idl_definition, file_name)
  except Exception as err:
    print 'ERROR: loading AST from cache: ' + os.path.basename(file_name)
    print err
    print
    print 'Stack Dump:'
    print format_exception(err)

  return 1


# New IDL parser builder.
class Build():
    def __init__(self, provider):
        # TODO(terry): Consider using the generator to do the work today we're
        #              driven by the databasebuilder.  Blink compiler requires
        #              an output directory even though we don't use (yet). Might
        #              use the code generator portion of the new IDL compiler
        #              then we'd have a real output directory. Today we use the
        #              compiler to only create an AST.
        self.output_directory = tempfile.mkdtemp()
        attrib_file = os.path.join('Source', idl_validator.EXTENDED_ATTRIBUTES_FILENAME)
        # Create compiler.
        self.idl_compiler = compiler.IdlCompilerDart(self.output_directory,
                                            attrib_file,
                                            interfaces_info=provider._info_collector.interfaces_info,
                                            only_if_changed=True)

    def format_exception(self, e):
        exception_list = traceback.format_stack()
        exception_list = exception_list[:-2]
        exception_list.extend(traceback.format_tb(sys.exc_info()[2]))
        exception_list.extend(traceback.format_exception_only(sys.exc_info()[0], sys.exc_info()[1]))

        exception_str = "Traceback (most recent call last):\n"
        exception_str += "".join(exception_list)
        # Removing the last \n
        exception_str = exception_str[:-1]

        return exception_str

    def generate_from_idl(self, idl_file):
        try:
            idl_file_fullpath = os.path.realpath(idl_file)
            self.idl_compiler.compile_file(idl_file_fullpath)
        except Exception as err:
            print 'ERROR: idl_compiler.py: ' + os.path.basename(idl_file)
            print err
            print
            print 'Stack Dump:'
            print self.format_exception(err)

            return 1

        return IDLFile(idl_ast, file_name)


class DatabaseBuilder(object):
  def __init__(self, database):
    """DatabaseBuilder is used for importing and merging interfaces into
    the Database"""
    self._info_collector = InterfaceInfoCollector()

    self._database = database
    self._imported_interfaces = []
    self._impl_stmts = []
    self.conditionals_met = set()

    # Spin up the new IDL parser.
    self.build = Build(self)

    # Global typedef to mapping.
    self.global_type_defs = monitored.Dict('databasebuilder.global_type_defs', {
      'Transferable' : 'MessagePort',
    })

  # TODO(terry): Consider keeping richer type information (e.g.,
  #              IdlArrayOrSequenceType from the Blink parser) instead of just
  #              a type name.
  def _resolve_type_defs(self, idl_file):
    for type_node in idl_file.all(IDLType):
      resolved = False
      type_name = type_node.id
      for typedef in self.global_type_defs:
        seq_name_typedef = 'sequence<%s>' % typedef
        if type_name == typedef:
          type_node.id = self.global_type_defs[typedef]
          resolved = True
        elif type_name == seq_name_typedef:
          type_node.id = 'sequence<%s>' % self.global_type_defs[typedef]
          resolved = True
      if not(resolved):
        for typedef in idl_file.typeDefs:
          if type_name == typedef.id:
            type_node.id = typedef.type.id
            resolved = True

  def _strip_ext_attributes(self, idl_file):
    """Strips unuseful extended attributes."""
    for ext_attrs in idl_file.all(IDLExtAttrs):
      # TODO: Decide which attributes are uninteresting.
      pass

  def _rename_types(self, idl_file, import_options):
    """Rename interface and type names with names provided in the
    options. Also clears scopes from scoped names"""

    strip_modules = lambda name: name.split('::')[-1]

    def rename_node(idl_node):
      idl_node.reset_id(strip_modules(idl_node.id))

    def rename_ext_attrs(ext_attrs_node):
      for type_valued_attribute_name in ['DartSupplemental']:
        if type_valued_attribute_name in ext_attrs_node:
          value = ext_attrs_node[type_valued_attribute_name]
          if isinstance(value, str):
            ext_attrs_node[type_valued_attribute_name] = strip_modules(value)

    map(rename_node, idl_file.all(IDLInterface))
    map(rename_node, idl_file.all(IDLType))
    map(rename_ext_attrs, idl_file.all(IDLExtAttrs))

  def _annotate(self, interface, import_options):
    """Adds @ annotations based on the source and source_attributes
    members of import_options."""

    source = import_options.source
    if not source:
      return

    def add_source_annotation(idl_node):
      annotation = IDLAnnotation(
        copy.deepcopy(import_options.source_attributes))
      idl_node.annotations[source] = annotation
      if ((isinstance(idl_node, IDLInterface) or
           isinstance(idl_node, IDLMember)) and
          idl_node.is_fc_suppressed):
        annotation['suppressed'] = None

    add_source_annotation(interface)

    map(add_source_annotation, interface.parents)
    map(add_source_annotation, interface.constants)
    map(add_source_annotation, interface.attributes)
    map(add_source_annotation, interface.operations)

  def _sign(self, node):
    """Computes a unique signature for the node, for merging purposed, by
    concatenating types and names in the declaration."""
    if isinstance(node, IDLType):
      res = node.id
      if res.startswith('unsigned '):
        res = res[len('unsigned '):]
      return res

    res = []
    if isinstance(node, IDLInterface):
      res = ['interface', node.id]
    elif isinstance(node, IDLParentInterface):
      res = ['parent', self._sign(node.type)]
    elif isinstance(node, IDLOperation):
      res = ['op']
      for special in node.specials:
        res.append(special)
      if node.id is not None:
        res.append(node.id)
      for arg in node.arguments:
        res.append(self._sign(arg.type))
      res.append(self._sign(node.type))
    elif isinstance(node, IDLAttribute):
      res = []
      if node.is_read_only:
        res.append('readonly')
      res.append(node.id)
      res.append(self._sign(node.type))
    elif isinstance(node, IDLConstant):
      res = []
      res.append('const')
      res.append(node.id)
      res.append(node.value)
      res.append(self._sign(node.type))
    else:
      raise TypeError("Can't sign input of type %s" % type(node))
    return ':'.join(res)

  def _build_signatures_map(self, idl_node_list):
    """Creates a hash table mapping signatures to idl_nodes for the
    given list of nodes"""
    res = {}
    for idl_node in idl_node_list:
      sig = self._sign(idl_node)
      if sig is None:
        continue
      if sig in res:
        op = res[sig]
        # Only report if the operations that match are either both suppressed
        # or both not suppressed.  Optional args aren't part of type signature
        # for this routine. Suppressing a non-optional type and supplementing
        # with an optional type appear the same.
        if idl_node.is_fc_suppressed == op.is_fc_suppressed:
          raise RuntimeError('Warning: Multiple members have the same '
                           '  signature: "%s"' % sig)
      res[sig] = idl_node
    return res

  def _get_parent_interfaces(self, interface):
    """Return a list of all the parent interfaces of a given interface"""
    res = []

    def recurse(current_interface):
      if current_interface in res:
        return
      res.append(current_interface)
      for parent in current_interface.parents:
        parent_name = parent.type.id
        if self._database.HasInterface(parent_name):
          recurse(self._database.GetInterface(parent_name))

    recurse(interface)
    return res[1:]

  def _merge_ext_attrs(self, old_attrs, new_attrs):
    """Merges two sets of extended attributes.

    Returns: True if old_attrs has changed.
    """
    changed = False
    for (name, value) in new_attrs.items():
      if name in old_attrs and old_attrs[name] == value:
        pass # Identical
      else:
        if name == 'ImplementedAs' and name in old_attrs:
          continue
        old_attrs[name] = value
        changed = True
    return changed

  def _merge_nodes(self, old_list, new_list, import_options):
    """Merges two lists of nodes. Annotates nodes with the source of each
    node.

    Returns:
      True if the old_list has changed.

    Args:
      old_list -- the list to merge into.
      new_list -- list containing more nodes.
      import_options -- controls how merging is done.
    """
    changed = False

    source = import_options.source

    old_signatures_map = self._build_signatures_map(old_list)
    new_signatures_map = self._build_signatures_map(new_list)

    # Merge new items
    for (sig, new_node) in new_signatures_map.items():
      if sig not in old_signatures_map:
        # New node:
        old_list.append(new_node)
        changed = True
      else:
        # Merge old and new nodes:
        old_node = old_signatures_map[sig]
        if (source not in old_node.annotations
            and source in new_node.annotations):
          old_node.annotations[source] = new_node.annotations[source]
          changed = True
        # Maybe rename arguments:
        if isinstance(old_node, IDLOperation):
          for i in range(0, len(old_node.arguments)):
            old_arg = old_node.arguments[i]
            new_arg = new_node.arguments[i]

            old_arg_name = old_arg.id
            new_arg_name = new_arg.id
            if (old_arg_name != new_arg_name
                and (old_arg_name == 'arg'
                     or old_arg_name.endswith('Arg')
                     or import_options.rename_operation_arguments_on_merge)):
              old_node.arguments[i].id = new_arg_name
              changed = True

            if self._merge_ext_attrs(old_arg.ext_attrs, new_arg.ext_attrs):
              changed = True

            # Merge in [Default=Undefined] and DOMString a = null handling in
            # IDL.  The IDL model (IDLArgument) coalesces these two different
            # default value syntaxes into the default_value* models.
            old_default_value = old_arg.default_value
            new_default_value = new_arg.default_value
            old_default_value_is_null = old_arg.default_value_is_null
            new_default_value_is_null = new_arg.default_value_is_null
            if old_default_value != new_default_value:
              old_arg.default_value = new_default_value
              changed = True
            if old_default_value_is_null != new_default_value_is_null:
              old_arg.default_value_is_null = new_default_value_is_null
              changed = True

            # Merge in any optional argument differences.
            old_optional = old_arg.optional
            new_optional = new_arg.optional
            if old_optional != new_optional:
              old_arg.optional = new_optional
              changed = True
        # Maybe merge annotations:
        if (isinstance(old_node, IDLAttribute) or
            isinstance(old_node, IDLOperation)):
          if self._merge_ext_attrs(old_node.ext_attrs, new_node.ext_attrs):
            changed = True

    # Remove annotations on obsolete items from the same source
    if import_options.obsolete_old_declarations:
      for (sig, old_node) in old_signatures_map.items():
        if (source in old_node.annotations
            and sig not in new_signatures_map):
          _logger.warn('%s not available in %s anymore' %
            (sig, source))
          del old_node.annotations[source]
          changed = True

    return changed

  def _merge_interfaces(self, old_interface, new_interface, import_options):
    """Merges the new_interface into the old_interface, annotating the
    interface with the sources of each change."""

    changed = False

    source = import_options.source
    if (source and source not in old_interface.annotations and
        source in new_interface.annotations and
        not new_interface.is_supplemental):
      old_interface.annotations[source] = new_interface.annotations[source]
      changed = True

    def merge_list(what):
      old_list = old_interface.__dict__[what]
      new_list = new_interface.__dict__[what]

      if what != 'parents' and old_interface.id != new_interface.id:
        for node in new_list:
          node.doc_js_interface_name = old_interface.id
          node.ext_attrs['ImplementedBy'] = new_interface.id

      changed = self._merge_nodes(old_list, new_list, import_options)

      # Delete list items with zero remaining annotations.
      if changed and import_options.obsolete_old_declarations:

        def has_annotations(idl_node):
          return len(idl_node.annotations)

        old_interface.__dict__[what] = filter(has_annotations, old_list)

      return changed

    # Smartly merge various declarations:
    if merge_list('parents'):
      changed = True
    if merge_list('constants'):
      changed = True
    if merge_list('attributes'):
      changed = True
    if merge_list('operations'):
      changed = True

    if self._merge_ext_attrs(old_interface.ext_attrs, new_interface.ext_attrs):
      changed = True

    _logger.info('merged interface %s (changed=%s, supplemental=%s)' %
      (old_interface.id, changed, new_interface.is_supplemental))

    return changed

  def _merge_impl_stmt(self, impl_stmt, import_options):
    """Applies "X implements Y" statemetns on the proper places in the
    database"""
    implementor_name = impl_stmt.implementor.id
    implemented_name = impl_stmt.implemented.id
    _logger.info('merging impl stmt %s implements %s' %
                 (implementor_name, implemented_name))

    source = import_options.source
    if self._database.HasInterface(implementor_name):
      interface = self._database.GetInterface(implementor_name)
      if interface.parents is None:
        interface.parents = []
      for parent in interface.parents:
        if parent.type.id == implemented_name:
          if source and source not in parent.annotations:
            parent.annotations[source] = IDLAnnotation(
                import_options.source_attributes)
          return
      # not found, so add new one
      parent = IDLParentInterface(None)
      parent.type = IDLType(implemented_name)
      if source:
        parent.annotations[source] = IDLAnnotation(
            import_options.source_attributes)
      interface.parents.append(parent)

  def merge_imported_interfaces(self):
    """Merges all imported interfaces and loads them into the DB."""
    imported_interfaces = self._imported_interfaces

    # Step 1: Pre process imported interfaces
#    for interface, import_options in imported_interfaces.iteritems():
    for interface, import_options in imported_interfaces:
      self._annotate(interface, import_options)

    # Step 2: Add all new interfaces and merge overlapping ones
    for interface, import_options in imported_interfaces:
      if not interface.is_supplemental:
        if self._database.HasInterface(interface.id):
          old_interface = self._database.GetInterface(interface.id)
          self._merge_interfaces(old_interface, interface, import_options)
        else:
          if import_options.add_new_interfaces:
            self._database.AddInterface(interface)

    # Step 3: Merge in supplemental interfaces
    for interface, import_options in imported_interfaces:
      if interface.is_supplemental:
        target = interface.id
        if self._database.HasInterface(target):
          old_interface = self._database.GetInterface(target)
          self._merge_interfaces(old_interface, interface, import_options)
        else:
          _logger.warning("Supplemental target '%s' not found", target)

    # Step 4: Resolve 'implements' statements
    for impl_stmt, import_options in self._impl_stmts:
      self._merge_impl_stmt(impl_stmt, import_options)

    self._impl_stmts = []
    self._imported_interfaces = []

  def _compute_dart_idl_implements(self, idl_filename):
    full_path = os.path.realpath(idl_filename)

    with open(full_path) as f:
        idl_file_contents = f.read()

    implements_re = (r'^\s*'
                     r'(\w+)\s+'
                     r'implements\s+'
                     r'(\w+)\s*'
                     r';')

    implements_matches = re.finditer(implements_re, idl_file_contents, re.MULTILINE)
    return [match.groups() for match in implements_matches]

  # Compile the IDL file with the Blink compiler and remember each AST for the
  # IDL.
  def _blink_compile_idl_files(self, file_paths, import_options, is_dart_idl):
    if not(is_dart_idl):
      start_time = time.time()

    # Compute information for individual files
    # Information is stored in global variables interfaces_info and
    # partial_interface_files.
      for file_path in file_paths:
        self._info_collector.collect_info(file_path)

      end_time = time.time()
      print 'Compute dependencies %s seconds' % round((end_time - start_time), 2)
    else:
      # Compute the interface_info for dart.idl for implements defined.  This
      # file is special in that more than one interface can exist in this file.
      implement_pairs = self._compute_dart_idl_implements(file_paths[0])

      self._info_collector.interfaces_info['__dart_idl___'] = {
        'implement_pairs': implement_pairs,
      }

    # Parse the IDL files serially.
    start_time = time.time()

    for file_path in file_paths:
      file_path = os.path.normpath(file_path)
      ast = _compile_idl_file(self.build, file_path, import_options)
      self._process_ast(os.path.splitext(os.path.basename(file_path))[0], ast)

    end_time = time.time()
    print 'Compiled %s IDL files in %s seconds' % (len(file_paths),
                                                  round((end_time - start_time), 2))

  def _process_ast(self, filename, ast):
    if len(ast) == 1:
      ast = ast.values()[0]
    else:
      print 'ERROR: Processing AST: ' + os.path.basename(file_name)
    new_asts[filename] = ast

  def import_idl_files(self, file_paths, import_options, is_dart_idl):
    self._blink_compile_idl_files(file_paths, import_options, is_dart_idl)

    start_time = time.time()

    # Parse the IDL files in serial.
    for file_path in file_paths:
      file_path = os.path.normpath(file_path)
      idl_file = _load_idl_file(self.build, file_path, import_options)
      _logger.info('Processing %s' % os.path.splitext(os.path.basename(file_path))[0])
      self._process_idl_file(idl_file, import_options, is_dart_idl)

    end_time = time.time()

    for warning in report_unions_to_any():
      _logger.warning(warning)

    print 'Total %s files %sprocessed in databasebuilder in %s seconds' % \
    (len(file_paths), '', round((end_time - start_time), 2))

  def _process_idl_file(self, idl_file, import_options, dart_idl = False):
    # TODO(terry): strip_ext_attributes on an idl_file does nothing.
    #self._strip_ext_attributes(idl_file)
    self._resolve_type_defs(idl_file)
    self._rename_types(idl_file, import_options)

    def enabled(idl_node):
      return self._is_node_enabled(idl_node, import_options.idl_defines)

    for interface in idl_file.interfaces:
      if not self._is_node_enabled(interface, import_options.idl_defines):
        _logger.info('skipping interface %s (source=%s)'
          % (interface.id, import_options.source))
        continue

      _logger.info('importing interface %s (source=%s file=%s)'
        % (interface.id, import_options.source, os.path.basename(idl_file.filename)))

      interface.attributes = filter(enabled, interface.attributes)
      interface.operations = filter(enabled, interface.operations)
      self._imported_interfaces.append((interface, import_options))

    # If an IDL dictionary then there is no implementsStatements.
    if hasattr(idl_file, 'implementsStatements'):
      for implStmt in idl_file.implementsStatements:
        self._impl_stmts.append((implStmt, import_options))

    for enum in idl_file.enums:
      self._database.AddEnum(enum)

    for dictionary in idl_file.dictionaries:
      self._database.AddDictionary(dictionary)

    # TODO(terry): Hack to remember all typedef unions they're mapped to any
    #              - no type.
    for typedef in idl_file.typeDefs:
      self._database.AddTypeDef(typedef)

  def _is_node_enabled(self, node, idl_defines):
    if not 'Conditional' in node.ext_attrs:
      return True

    def enabled(condition):
      return 'ENABLE_%s' % condition in idl_defines

    conditional = node.ext_attrs['Conditional']
    if conditional.find('&') != -1:
      for condition in conditional.split('&'):
        condition = condition.strip()
        self.conditionals_met.add(condition)
        if not enabled(condition):
          return False
      return True

    for condition in conditional.split('|'):
      condition = condition.strip()
      self.conditionals_met.add(condition)
      if enabled(condition):
        return True
    return False

  def fix_displacements(self, source):
    """E.g. In W3C, something is declared on HTMLDocument but in WebKit
    its on Document, so we need to mark that something in HTMLDocument
    with @WebKit(via=Document). The 'via' attribute specifies the
    parent interface that has the declaration."""

    for interface in self._database.GetInterfaces():
      changed = False

      _logger.info('fixing displacements in %s' % interface.id)

      for parent_interface in self._get_parent_interfaces(interface):
        _logger.info('scanning parent %s of %s' %
          (parent_interface.id, interface.id))

        def fix_nodes(local_list, parent_list):
          changed = False
          parent_signatures_map = self._build_signatures_map(
            parent_list)
          for idl_node in local_list:
            sig = self._sign(idl_node)
            if sig in parent_signatures_map:
              parent_member = parent_signatures_map[sig]
              if (source in parent_member.annotations
                  and source not in idl_node.annotations
                  and _VIA_ANNOTATION_ATTR_NAME
                      not in parent_member.annotations[source]):
                idl_node.annotations[source] = IDLAnnotation(
                    {_VIA_ANNOTATION_ATTR_NAME: parent_interface.id})
                changed = True
          return changed

        changed = fix_nodes(interface.constants,
                  parent_interface.constants) or changed
        changed = fix_nodes(interface.attributes,
                  parent_interface.attributes) or changed
        changed = fix_nodes(interface.operations,
                  parent_interface.operations) or changed
      if changed:
        _logger.info('fixed displaced declarations in %s' %
          interface.id)

  def normalize_annotations(self, sources):
    """Makes the IDLs less verbose by removing annotation attributes
    that are identical to the ones defined at the interface level.

    Args:
      sources -- list of source names to normalize."""
    for interface in self._database.GetInterfaces():
      _logger.debug('normalizing annotations for %s' % interface.id)
      for source in sources:
        if (source not in interface.annotations or
            not interface.annotations[source]):
          continue
        top_level_annotation = interface.annotations[source]

        def normalize(idl_node):
          if (source in idl_node.annotations
              and idl_node.annotations[source]):
            annotation = idl_node.annotations[source]
            for name, value in annotation.items():
              if (name in top_level_annotation
                  and value == top_level_annotation[name]):
                del annotation[name]

        map(normalize, interface.parents)
        map(normalize, interface.constants)
        map(normalize, interface.attributes)
        map(normalize, interface.operations)

  def map_dictionaries(self):
    """Changes the type of operations/constructors arguments from an IDL
       dictionary to a Dictionary.  The IDL dictionary is just an enums of
       strings which are checked at run-time."""
    def dictionary_to_map(type_node):
      if self._database.HasDictionary(type_node.id):
        type_node.dictionary = type_node.id
        type_node.id = 'Dictionary'

    def all_types(node):
      map(dictionary_to_map, node.all(IDLType))

    for interface in self._database.GetInterfaces():
      map(all_types, interface.all(IDLExtAttrFunctionValue))
      map(all_types, interface.attributes)
      map(all_types, interface.operations)

  def fetch_constructor_data(self, options):
    window_interface = self._database.GetInterface('Window')
    for attr in window_interface.attributes:
      type = attr.type.id
      if not type.endswith('Constructor'):
        continue
      type = re.sub('(Constructor)+$', '', type)
      # TODO(antonm): Ideally we'd like to have pristine copy of WebKit IDLs and fetch
      # this information directly from it.  Unfortunately right now database is massaged
      # a lot so it's difficult to maintain necessary information on Window itself.
      interface = self._database.GetInterface(type)
      if 'V8EnabledPerContext' in attr.ext_attrs:
        interface.ext_attrs['synthesizedV8EnabledPerContext'] = \
            attr.ext_attrs['V8EnabledPerContext']
      if 'V8EnabledAtRuntime' in attr.ext_attrs:
        interface.ext_attrs['synthesizedV8EnabledAtRuntime'] = \
            attr.ext_attrs['V8EnabledAtRuntime'] or attr.id

  # Iterate of the database looking for relationships between dictionaries and
  # interfaces marked with NoInterfaceObject.  This mechanism can be used for
  # other IDL analysis.
  def examine_database(self):
    # Contains list of dictionary structure: {'dictionary': dictionary, 'usages': []}
    self._diag_dictionaries = [];
    self._dictionaries_used_types = [];

    # Record any dictionary.
    for dictionary in self._database.GetDictionaries():
      self._diag_dictionaries.append({'dictionary': dictionary, 'usages': []});

    # Contains list of NoInterfaceObject structures: {'no_interface_object': dictionary, 'usages': []}
    self._diag_no_interfaces = [];
    self._no_interfaces_used_types = [];

    # Record any interface with Blink IDL Extended Attribute 'NoInterfaceObject'.
    for interface in self._database.GetInterfaces():
      if interface.is_no_interface_object:
        self._diag_no_interfaces.append({'no_interface_object': interface, 'usages': []});

    for interface in self._database.GetInterfaces():
      self._constructors(interface)
      self._constructors(interface, check_dictionaries=False)

      for attribute in interface.attributes:
        self._attribute_operation(interface, attribute)
        self._attribute_operation(interface, attribute, check_dictionaries=False)

      for operation in interface.operations:
        self._attribute_operation(interface, operation)
        self._attribute_operation(interface, operation, check_dictionaries=False)

    # Report all dictionaries and their usage.
    self._output_examination()
    # Report all interface marked with NoInterfaceObject and their usage.
    self._output_examination(check_dictionaries=False)

    print '\nKey:'
    print '  (READ-ONLY) - read-only attribute has relationship'
    print '  (GET/SET)   - attribute has relationship'
    print '  RETURN      - operation\'s returned value has relationship'
    print '  (ARGUMENT)  - operation\'s argument(s) has relationship'
    print ''
    print '  (New)       - After dictionary name if constructor(s) exist'
    print '  (Ops,Props,New) after a NoInterfaceObject name is defined as:'
    print '    Ops       - number of operations for a NoInterfaceObject'
    print '    Props     - number of properties for a NoInterfaceObject'
    print '    New       - T(#) number constructors for a NoInterfaceObject'
    print '                F no constructors for a NoInterfaceObject'
    print '                e.g., an interface 5 operations, 3 properties and 2'
    print '                      constructors would display (5,3,T(2))'

    print '\n\nExamination Complete\n'

  def _output_examination(self, check_dictionaries=True):
    # Output diagnostics. First columns is Dictionary or NoInterfaceObject e.g.,
    # |  Dictionary  |  Used In Interface  |  Usage Operation/Attribute  |
    print '\n\n'
    title_bar = ['Dictionary', 'Used In Interface', 'Usage Operation/Attribute'] if check_dictionaries \
                else ['NoInterfaceObject (Ops,Props,New)', 'Used In Interface', 'Usage Operation/Attribute']
    self._tabulate_title(title_bar)
    diags = self._diag_dictionaries if check_dictionaries else self._diag_no_interfaces
    for diag in diags:
      if not(check_dictionaries):
        interface = diag['no_interface_object']
        ops_count = len(interface.operations)
        properties_count = len(interface.attributes)
        any_constructors = 'Constructor' in interface.ext_attrs
        constructors = 'T(%s)' % len(interface.ext_attrs['Constructor']) if any_constructors else 'F'
        interface_detail = '%s (%s,%s,%s)' % \
            (diag['no_interface_object'].id,
             ops_count,
             properties_count,
             constructors)
        self._tabulate([interface_detail, '', ''])
      else:
        dictionary = diag['dictionary']
        any_constructors = 'Constructor' in dictionary.ext_attrs
        self._tabulate(['%s%s' % (dictionary.id, ' (New)' if any_constructors else ''), '', ''])
      for usage in diag['usages']:
        detail = ''
        if 'attribute' in usage:
          attribute_type = 'READ-ONLY' if not usage['argument'] else 'GET/SET'
          detail = '(%s) %s' % (attribute_type, usage['attribute'])
        elif 'operation' in usage:
          detail = '%s %s%s' % ('RETURN' if usage['result'] else '',
                                         usage['operation'],
                                         '(ARGUMENT)' if usage['argument'] else '')
        self._tabulate([None, usage['interface'], detail])
      self._tabulate_break()

  # operation_or_attribute either IDLOperation or IDLAttribute if None then
  # its a constructor (IDLExtAttrFunctionValue).
  def _mark_usage(self, interface, operation_or_attribute = None, check_dictionaries=True):
    for diag in self._diag_dictionaries if check_dictionaries else self._diag_no_interfaces:
      for usage in diag['usages']:
        if not usage['interface']:
          usage['interface'] = interface.id
          if isinstance(operation_or_attribute, IDLOperation):
            usage['operation'] = operation_or_attribute.id
            if check_dictionaries:
              usage['result'] = hasattr(operation_or_attribute.type, 'dictionary') and \
                operation_or_attribute.type.dictionary == diag['dictionary'].id
            else:
              usage['result'] = operation_or_attribute.type.id == diag['no_interface_object'].id
            usage['argument'] = False
            for argument in operation_or_attribute.arguments:
              if check_dictionaries:
                arg = hasattr(argument.type, 'dictionary') and argument.type.dictionary == diag['dictionary'].id
              else:
                arg = argument.type.id == diag['no_interface_object'].id
              if arg:
                usage['argument'] = arg
          elif isinstance(operation_or_attribute, IDLAttribute):
            usage['attribute'] = operation_or_attribute.id
            usage['result'] = True
            usage['argument'] = not operation_or_attribute.is_read_only
          elif not operation_or_attribute:
            # Its a constructor only argument is dictionary or interface with NoInterfaceObject.
            usage['operation'] = 'constructor'
            usage['result'] = False
            usage['argument'] = True

  def _remember_usage(self, node, check_dictionaries=True):
    if check_dictionaries:
      used_types = self._dictionaries_used_types
      diag_list = self._diag_dictionaries
      diag_name = 'dictionary'
    else:
      used_types = self._no_interfaces_used_types
      diag_list = self._diag_no_interfaces
      diag_name = 'no_interface_object'

    if len(used_types) > 0:
      normalized_used = list(set(used_types))
      for recorded_id in normalized_used:
        for diag in diag_list:
          if diag[diag_name].id == recorded_id:
            diag['usages'].append({'interface': None, 'node': node})

  # Iterator function to look for any IDLType that is a dictionary then remember
  # that dictionary.
  def _dictionary_used(self, type_node):
    if hasattr(type_node, 'dictionary'):
      dictionary_id = type_node.dictionary
      if self._database.HasDictionary(dictionary_id):
        for diag_dictionary in self._diag_dictionaries:
          if diag_dictionary['dictionary'].id == dictionary_id:
            # Record the dictionary that was referenced.
            self._dictionaries_used_types.append(dictionary_id)
            return

      # If we get to this point, the IDL dictionary was never defined ... oops.
      print 'DIAGNOSE_ERROR: IDL Dictionary %s doesn\'t exist.' % dictionary_id

  # Iterator function to look for any IDLType that is an interface marked with
  # NoInterfaceObject then remember that interface.
  def _no_interface_used(self, type_node):
    if hasattr(type_node, 'id'):
      no_interface_id = type_node.id
      if self._database.HasInterface(no_interface_id):
        no_interface = self._database.GetInterface(no_interface_id)
        if no_interface.is_no_interface_object:
          for diag_no_interface in self._diag_no_interfaces:
            if diag_no_interface['no_interface_object'].id == no_interface_id:
              # Record the interface marked with NoInterfaceObject.
              self._no_interfaces_used_types.append(no_interface_id)
              return

  def _constructors(self, interface, check_dictionaries=True):
    if check_dictionaries:
      self._dictionaries_used_types = []
      constructor_function = self._dictionary_constructor_types
    else:
      self._no_interfaces_used_types = [];
      constructor_function = self._no_interface_constructor_types

    map(constructor_function, interface.all(IDLExtAttrFunctionValue))

    self._mark_usage(interface, check_dictionaries=check_dictionaries)

  # Scan an attribute or operation for a dictionary or interface with NoInterfaceObject
  # reference.  
  def _attribute_operation(self, interface, operation_attribute, check_dictionaries=True):
    if check_dictionaries:
      self._dictionaries_used_types = []
      used = self._dictionary_used
    else:
      self._no_interfaces_used_types = [];
      used = self._no_interface_used

    map(used, operation_attribute.all(IDLType))

    self._remember_usage(operation_attribute, check_dictionaries=check_dictionaries)
    self._mark_usage(interface, operation_attribute, check_dictionaries=check_dictionaries)

  # Iterator function for map to iterate over all constructor types
  # (IDLExtAttrFunctionValue) that have a dictionary reference.
  def _dictionary_constructor_types(self, node):
    self._dictionaries_used_types = []
    map(self._dictionary_used, node.all(IDLType))
    self._remember_usage(node)

  # Iterator function for map to iterate over all constructor types
  # (IDLExtAttrFunctionValue) that reference an interface with NoInterfaceObject.
  def _no_interface_constructor_types(self, node):
    self._no_interfaces_used_types = [];
    map(self._no_interface_used, node.all(IDLType))
    self._remember_usage(node, check_dictionaries=False)

  # Maximum width of each column.
  def _TABULATE_WIDTH(self):
    return 45

  def _tabulate_title(self, row_title):
    title_separator = "=" * self._TABULATE_WIDTH()
    self._tabulate([title_separator, title_separator, title_separator])
    self._tabulate(row_title)
    self._tabulate([title_separator, title_separator, title_separator])

  def _tabulate_break(self):
    break_separator = "-" * self._TABULATE_WIDTH()
    self._tabulate([break_separator, break_separator, break_separator])

  def _tabulate(self, columns):
    """Tabulate a list of columns for a row.  Each item in columns is a column
       value each column will be padded up to _TABULATE_WIDTH.  Each
       column starts/ends with a vertical bar '|' the format a row:

           | columns[0] | columns[1] | columns[2] | ... |
    """
    if len(columns) > 0:
      for column in columns:
        value = '' if not column else column
        sys.stdout.write('|{0:^{1}}'.format(value, self._TABULATE_WIDTH()))
    else:
      sys.stdout.write('|{0:^{1}}'.format('', self._TABULATE_WIDTH()))

    sys.stdout.write('|\n')