# Copyright (c) 2012 Google Inc. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

# Notes:
#
# This generates makefiles suitable for inclusion into the Android build system
# via an Android.mk file. It is based on make.py, the standard makefile
# generator.
#
# The code below generates a separate .mk file for each target, but
# all are sourced by the top-level GypAndroid.mk.  This means that all
# variables in .mk-files clobber one another, and furthermore that any
# variables set potentially clash with other Android build system variables.
# Try to avoid setting global variables where possible.

import gyp
import gyp.common
import gyp.generator.make as make  # Reuse global functions from make backend.
import os
import re
import subprocess

generator_default_variables = {
  'OS': 'android',
  'EXECUTABLE_PREFIX': '',
  'EXECUTABLE_SUFFIX': '',
  'STATIC_LIB_PREFIX': 'lib',
  'SHARED_LIB_PREFIX': 'lib',
  'STATIC_LIB_SUFFIX': '.a',
  'SHARED_LIB_SUFFIX': '.so',
  'INTERMEDIATE_DIR': '$(gyp_intermediate_dir)',
  'SHARED_INTERMEDIATE_DIR': '$(gyp_shared_intermediate_dir)',
  'PRODUCT_DIR': '$(gyp_shared_intermediate_dir)',
  'SHARED_LIB_DIR': '$(builddir)/lib.$(TOOLSET)',
  'LIB_DIR': '$(obj).$(TOOLSET)',
  'RULE_INPUT_ROOT': '%(INPUT_ROOT)s',  # This gets expanded by Python.
  'RULE_INPUT_DIRNAME': '%(INPUT_DIRNAME)s',  # This gets expanded by Python.
  'RULE_INPUT_PATH': '$(RULE_SOURCES)',
  'RULE_INPUT_EXT': '$(suffix $<)',
  'RULE_INPUT_NAME': '$(notdir $<)',
  'CONFIGURATION_NAME': '$(GYP_CONFIGURATION)',
}

# Make supports multiple toolsets
generator_supports_multiple_toolsets = True


# Generator-specific gyp specs.
generator_additional_non_configuration_keys = [
    # Boolean to declare that this target does not want its name mangled.
    'android_unmangled_name',
]
generator_additional_path_sections = []
generator_extra_sources_for_rules = []


ALL_MODULES_FOOTER = """\
# "gyp_all_modules" is a concatenation of the "gyp_all_modules" targets from
# all the included sub-makefiles. This is just here to clarify.
gyp_all_modules:
"""

header = """\
# This file is generated by gyp; do not edit.

"""

android_standard_include_paths = set([
    # JNI_H_INCLUDE in build/core/binary.mk
    'dalvik/libnativehelper/include/nativehelper',
    # from SRC_HEADERS in build/core/config.mk
    'system/core/include',
    'hardware/libhardware/include',
    'hardware/libhardware_legacy/include',
    'hardware/ril/include',
    'dalvik/libnativehelper/include',
    'frameworks/native/include',
    'frameworks/native/opengl/include',
    'frameworks/base/include',
    'frameworks/base/opengl/include',
    'frameworks/base/native/include',
    'external/skia/include',
    # TARGET_C_INCLUDES in build/core/combo/TARGET_linux-arm.mk
    'bionic/libc/arch-arm/include',
    'bionic/libc/include',
    'bionic/libstdc++/include',
    'bionic/libc/kernel/common',
    'bionic/libc/kernel/arch-arm',
    'bionic/libm/include',
    'bionic/libm/include/arm',
    'bionic/libthread_db/include',
    ])


# Map gyp target types to Android module classes.
MODULE_CLASSES = {
    'static_library': 'STATIC_LIBRARIES',
    'shared_library': 'SHARED_LIBRARIES',
    'executable': 'EXECUTABLES',
}


def IsCPPExtension(ext):
  return make.COMPILABLE_EXTENSIONS.get(ext) == 'cxx'


def Sourceify(path):
  """Convert a path to its source directory form. The Android backend does not
     support options.generator_output, so this function is a noop."""
  return path


# Map from qualified target to path to output.
# For Android, the target of these maps is a tuple ('static', 'modulename'),
# ('dynamic', 'modulename'), or ('path', 'some/path') instead of a string,
# since we link by module.
target_outputs = {}
# Map from qualified target to any linkable output.  A subset
# of target_outputs.  E.g. when mybinary depends on liba, we want to
# include liba in the linker line; when otherbinary depends on
# mybinary, we just want to build mybinary first.
target_link_deps = {}


class AndroidMkWriter(object):
  """AndroidMkWriter packages up the writing of one target-specific Android.mk.

  Its only real entry point is Write(), and is mostly used for namespacing.
  """

  def __init__(self, android_top_dir):
    self.android_top_dir = android_top_dir

  def Write(self, qualified_target, relative_target, base_path, output_filename,
            spec, configs, part_of_all, write_alias_target):
    """The main entry point: writes a .mk file for a single target.

    Arguments:
      qualified_target: target we're generating
      relative_target: qualified target name relative to the root
      base_path: path relative to source root we're building in, used to resolve
                 target-relative paths
      output_filename: output .mk file name to write
      spec, configs: gyp info
      part_of_all: flag indicating this target is part of 'all'
      write_alias_target: flag indicating whether to create short aliases for
                          this target
    """
    gyp.common.EnsureDirExists(output_filename)

    self.fp = open(output_filename, 'w')

    self.fp.write(header)

    self.qualified_target = qualified_target
    self.relative_target = relative_target
    self.path = base_path
    self.target = spec['target_name']
    self.type = spec['type']
    self.toolset = spec['toolset']

    deps, link_deps = self.ComputeDeps(spec)

    # Some of the generation below can add extra output, sources, or
    # link dependencies.  All of the out params of the functions that
    # follow use names like extra_foo.
    extra_outputs = []
    extra_sources = []

    self.android_class = MODULE_CLASSES.get(self.type, 'GYP')
    self.android_module = self.ComputeAndroidModule(spec)
    (self.android_stem, self.android_suffix) = self.ComputeOutputParts(spec)
    self.output = self.output_binary = self.ComputeOutput(spec)

    # Standard header.
    self.WriteLn('include $(CLEAR_VARS)\n')

    # Module class and name.
    self.WriteLn('LOCAL_MODULE_CLASS := ' + self.android_class)
    self.WriteLn('LOCAL_MODULE := ' + self.android_module)
    # Only emit LOCAL_MODULE_STEM if it's different to LOCAL_MODULE.
    # The library module classes fail if the stem is set. ComputeOutputParts
    # makes sure that stem == modulename in these cases.
    if self.android_stem != self.android_module:
      self.WriteLn('LOCAL_MODULE_STEM := ' + self.android_stem)
    self.WriteLn('LOCAL_MODULE_SUFFIX := ' + self.android_suffix)
    self.WriteLn('LOCAL_MODULE_TAGS := optional')
    if self.toolset == 'host':
      self.WriteLn('LOCAL_IS_HOST_MODULE := true')
      self.WriteLn('LOCAL_MULTILIB := $(GYP_HOST_MULTILIB)')
    else:
      self.WriteLn('LOCAL_MODULE_TARGET_ARCH := '
                   '$(TARGET_$(GYP_VAR_PREFIX)ARCH)')

    # Grab output directories; needed for Actions and Rules.
    if self.toolset == 'host':
      self.WriteLn('gyp_intermediate_dir := '
                   '$(call local-intermediates-dir,,$(GYP_HOST_VAR_PREFIX))')
    else:
      self.WriteLn('gyp_intermediate_dir := '
                   '$(call local-intermediates-dir,,$(GYP_VAR_PREFIX))')
    self.WriteLn('gyp_shared_intermediate_dir := '
                 '$(call intermediates-dir-for,GYP,shared,,,$(GYP_VAR_PREFIX))')
    self.WriteLn()

    # List files this target depends on so that actions/rules/copies/sources
    # can depend on the list.
    # TODO: doesn't pull in things through transitive link deps; needed?
    target_dependencies = [x[1] for x in deps if x[0] == 'path']
    self.WriteLn('# Make sure our deps are built first.')
    self.WriteList(target_dependencies, 'GYP_TARGET_DEPENDENCIES',
                   local_pathify=True)

    # Actions must come first, since they can generate more OBJs for use below.
    if 'actions' in spec:
      self.WriteActions(spec['actions'], extra_sources, extra_outputs)

    # Rules must be early like actions.
    if 'rules' in spec:
      self.WriteRules(spec['rules'], extra_sources, extra_outputs)

    if 'copies' in spec:
      self.WriteCopies(spec['copies'], extra_outputs)

    # GYP generated outputs.
    self.WriteList(extra_outputs, 'GYP_GENERATED_OUTPUTS', local_pathify=True)

    # Set LOCAL_ADDITIONAL_DEPENDENCIES so that Android's build rules depend
    # on both our dependency targets and our generated files.
    self.WriteLn('# Make sure our deps and generated files are built first.')
    self.WriteLn('LOCAL_ADDITIONAL_DEPENDENCIES := $(GYP_TARGET_DEPENDENCIES) '
                 '$(GYP_GENERATED_OUTPUTS)')
    self.WriteLn()

    # Sources.
    if spec.get('sources', []) or extra_sources:
      self.WriteSources(spec, configs, extra_sources)

    self.WriteTarget(spec, configs, deps, link_deps, part_of_all,
                     write_alias_target)

    # Update global list of target outputs, used in dependency tracking.
    target_outputs[qualified_target] = ('path', self.output_binary)

    # Update global list of link dependencies.
    if self.type == 'static_library':
      target_link_deps[qualified_target] = ('static', self.android_module)
    elif self.type == 'shared_library':
      target_link_deps[qualified_target] = ('shared', self.android_module)

    self.fp.close()
    return self.android_module


  def WriteActions(self, actions, extra_sources, extra_outputs):
    """Write Makefile code for any 'actions' from the gyp input.

    extra_sources: a list that will be filled in with newly generated source
                   files, if any
    extra_outputs: a list that will be filled in with any outputs of these
                   actions (used to make other pieces dependent on these
                   actions)
    """
    for action in actions:
      name = make.StringToMakefileVariable('%s_%s' % (self.relative_target,
                                                      action['action_name']))
      self.WriteLn('### Rules for action "%s":' % action['action_name'])
      inputs = action['inputs']
      outputs = action['outputs']

      # Build up a list of outputs.
      # Collect the output dirs we'll need.
      dirs = set()
      for out in outputs:
        if not out.startswith('$'):
          print ('WARNING: Action for target "%s" writes output to local path '
                 '"%s".' % (self.target, out))
        dir = os.path.split(out)[0]
        if dir:
          dirs.add(dir)
      if int(action.get('process_outputs_as_sources', False)):
        extra_sources += outputs

      # Prepare the actual command.
      command = gyp.common.EncodePOSIXShellList(action['action'])
      if 'message' in action:
        quiet_cmd = 'Gyp action: %s ($@)' % action['message']
      else:
        quiet_cmd = 'Gyp action: %s ($@)' % name
      if len(dirs) > 0:
        command = 'mkdir -p %s' % ' '.join(dirs) + '; ' + command

      cd_action = 'cd $(gyp_local_path)/%s; ' % self.path
      command = cd_action + command

      # The makefile rules are all relative to the top dir, but the gyp actions
      # are defined relative to their containing dir.  This replaces the gyp_*
      # variables for the action rule with an absolute version so that the
      # output goes in the right place.
      # Only write the gyp_* rules for the "primary" output (:1);
      # it's superfluous for the "extra outputs", and this avoids accidentally
      # writing duplicate dummy rules for those outputs.
      main_output = make.QuoteSpaces(self.LocalPathify(outputs[0]))
      self.WriteLn('%s: gyp_local_path := $(LOCAL_PATH)' % main_output)
      self.WriteLn('%s: gyp_var_prefix := $(GYP_VAR_PREFIX)' % main_output)
      self.WriteLn('%s: gyp_intermediate_dir := '
                   '$(abspath $(gyp_intermediate_dir))' % main_output)
      self.WriteLn('%s: gyp_shared_intermediate_dir := '
                   '$(abspath $(gyp_shared_intermediate_dir))' % main_output)

      # Android's envsetup.sh adds a number of directories to the path including
      # the built host binary directory. This causes actions/rules invoked by
      # gyp to sometimes use these instead of system versions, e.g. bison.
      # The built host binaries may not be suitable, and can cause errors.
      # So, we remove them from the PATH using the ANDROID_BUILD_PATHS variable
      # set by envsetup.
      self.WriteLn('%s: export PATH := $(subst $(ANDROID_BUILD_PATHS),,$(PATH))'
                   % main_output)

      # Don't allow spaces in input/output filenames, but make an exception for
      # filenames which start with '$(' since it's okay for there to be spaces
      # inside of make function/macro invocations.
      for input in inputs:
        if not input.startswith('$(') and ' ' in input:
          raise gyp.common.GypError(
              'Action input filename "%s" in target %s contains a space' %
              (input, self.target))
      for output in outputs:
        if not output.startswith('$(') and ' ' in output:
          raise gyp.common.GypError(
              'Action output filename "%s" in target %s contains a space' %
              (output, self.target))

      self.WriteLn('%s: %s $(GYP_TARGET_DEPENDENCIES)' %
                   (main_output, ' '.join(map(self.LocalPathify, inputs))))
      self.WriteLn('\t@echo "%s"' % quiet_cmd)
      self.WriteLn('\t$(hide)%s\n' % command)
      for output in outputs[1:]:
        # Make each output depend on the main output, with an empty command
        # to force make to notice that the mtime has changed.
        self.WriteLn('%s: %s ;' % (self.LocalPathify(output), main_output))

      extra_outputs += outputs
      self.WriteLn()

    self.WriteLn()


  def WriteRules(self, rules, extra_sources, extra_outputs):
    """Write Makefile code for any 'rules' from the gyp input.

    extra_sources: a list that will be filled in with newly generated source
                   files, if any
    extra_outputs: a list that will be filled in with any outputs of these
                   rules (used to make other pieces dependent on these rules)
    """
    if len(rules) == 0:
      return

    for rule in rules:
      if len(rule.get('rule_sources', [])) == 0:
        continue
      name = make.StringToMakefileVariable('%s_%s' % (self.relative_target,
                                                      rule['rule_name']))
      self.WriteLn('\n### Generated for rule "%s":' % name)
      self.WriteLn('# "%s":' % rule)

      inputs = rule.get('inputs')
      for rule_source in rule.get('rule_sources', []):
        (rule_source_dirname, rule_source_basename) = os.path.split(rule_source)
        (rule_source_root, rule_source_ext) = \
            os.path.splitext(rule_source_basename)

        outputs = [self.ExpandInputRoot(out, rule_source_root,
                                        rule_source_dirname)
                   for out in rule['outputs']]

        dirs = set()
        for out in outputs:
          if not out.startswith('$'):
            print ('WARNING: Rule for target %s writes output to local path %s'
                   % (self.target, out))
          dir = os.path.dirname(out)
          if dir:
            dirs.add(dir)
        extra_outputs += outputs
        if int(rule.get('process_outputs_as_sources', False)):
          extra_sources.extend(outputs)

        components = []
        for component in rule['action']:
          component = self.ExpandInputRoot(component, rule_source_root,
                                           rule_source_dirname)
          if '$(RULE_SOURCES)' in component:
            component = component.replace('$(RULE_SOURCES)',
                                          rule_source)
          components.append(component)

        command = gyp.common.EncodePOSIXShellList(components)
        cd_action = 'cd $(gyp_local_path)/%s; ' % self.path
        command = cd_action + command
        if dirs:
          command = 'mkdir -p %s' % ' '.join(dirs) + '; ' + command

        # We set up a rule to build the first output, and then set up
        # a rule for each additional output to depend on the first.
        outputs = map(self.LocalPathify, outputs)
        main_output = outputs[0]
        self.WriteLn('%s: gyp_local_path := $(LOCAL_PATH)' % main_output)
        self.WriteLn('%s: gyp_var_prefix := $(GYP_VAR_PREFIX)' % main_output)
        self.WriteLn('%s: gyp_intermediate_dir := '
                     '$(abspath $(gyp_intermediate_dir))' % main_output)
        self.WriteLn('%s: gyp_shared_intermediate_dir := '
                     '$(abspath $(gyp_shared_intermediate_dir))' % main_output)

        # See explanation in WriteActions.
        self.WriteLn('%s: export PATH := '
                     '$(subst $(ANDROID_BUILD_PATHS),,$(PATH))' % main_output)

        main_output_deps = self.LocalPathify(rule_source)
        if inputs:
          main_output_deps += ' '
          main_output_deps += ' '.join([self.LocalPathify(f) for f in inputs])

        self.WriteLn('%s: %s $(GYP_TARGET_DEPENDENCIES)' %
                     (main_output, main_output_deps))
        self.WriteLn('\t%s\n' % command)
        for output in outputs[1:]:
          # Make each output depend on the main output, with an empty command
          # to force make to notice that the mtime has changed.
          self.WriteLn('%s: %s ;' % (output, main_output))
        self.WriteLn()

    self.WriteLn()


  def WriteCopies(self, copies, extra_outputs):
    """Write Makefile code for any 'copies' from the gyp input.

    extra_outputs: a list that will be filled in with any outputs of this action
                   (used to make other pieces dependent on this action)
    """
    self.WriteLn('### Generated for copy rule.')

    variable = make.StringToMakefileVariable(self.relative_target + '_copies')
    outputs = []
    for copy in copies:
      for path in copy['files']:
        # The Android build system does not allow generation of files into the
        # source tree. The destination should start with a variable, which will
        # typically be $(gyp_intermediate_dir) or
        # $(gyp_shared_intermediate_dir). Note that we can't use an assertion
        # because some of the gyp tests depend on this.
        if not copy['destination'].startswith('$'):
          print ('WARNING: Copy rule for target %s writes output to '
                 'local path %s' % (self.target, copy['destination']))

        # LocalPathify() calls normpath, stripping trailing slashes.
        path = Sourceify(self.LocalPathify(path))
        filename = os.path.split(path)[1]
        output = Sourceify(self.LocalPathify(os.path.join(copy['destination'],
                                                          filename)))

        self.WriteLn('%s: %s $(GYP_TARGET_DEPENDENCIES) | $(ACP)' %
                     (output, path))
        self.WriteLn('\t@echo Copying: $@')
        self.WriteLn('\t$(hide) mkdir -p $(dir $@)')
        self.WriteLn('\t$(hide) $(ACP) -rpf $< $@')
        self.WriteLn()
        outputs.append(output)
    self.WriteLn('%s = %s' % (variable,
                              ' '.join(map(make.QuoteSpaces, outputs))))
    extra_outputs.append('$(%s)' % variable)
    self.WriteLn()


  def WriteSourceFlags(self, spec, configs):
    """Write out the flags and include paths used to compile source files for
    the current target.

    Args:
      spec, configs: input from gyp.
    """
    for configname, config in sorted(configs.iteritems()):
      extracted_includes = []

      self.WriteLn('\n# Flags passed to both C and C++ files.')
      cflags, includes_from_cflags = self.ExtractIncludesFromCFlags(
          config.get('cflags', []) + config.get('cflags_c', []))
      extracted_includes.extend(includes_from_cflags)
      self.WriteList(cflags, 'MY_CFLAGS_%s' % configname)

      self.WriteList(config.get('defines'), 'MY_DEFS_%s' % configname,
                     prefix='-D', quoter=make.EscapeCppDefine)

      self.WriteLn('\n# Include paths placed before CFLAGS/CPPFLAGS')
      includes = list(config.get('include_dirs', []))
      includes.extend(extracted_includes)
      includes = map(Sourceify, map(self.LocalPathify, includes))
      includes = self.NormalizeIncludePaths(includes)
      self.WriteList(includes, 'LOCAL_C_INCLUDES_%s' % configname)

      self.WriteLn('\n# Flags passed to only C++ (and not C) files.')
      self.WriteList(config.get('cflags_cc'), 'LOCAL_CPPFLAGS_%s' % configname)

    self.WriteLn('\nLOCAL_CFLAGS := $(MY_CFLAGS_$(GYP_CONFIGURATION)) '
                 '$(MY_DEFS_$(GYP_CONFIGURATION))')
    # Undefine ANDROID for host modules
    # TODO: the source code should not use macro ANDROID to tell if it's host
    # or target module.
    if self.toolset == 'host':
      self.WriteLn('# Undefine ANDROID for host modules')
      self.WriteLn('LOCAL_CFLAGS += -UANDROID')
    self.WriteLn('LOCAL_C_INCLUDES := $(GYP_COPIED_SOURCE_ORIGIN_DIRS) '
                                     '$(LOCAL_C_INCLUDES_$(GYP_CONFIGURATION))')
    self.WriteLn('LOCAL_CPPFLAGS := $(LOCAL_CPPFLAGS_$(GYP_CONFIGURATION))')
    # Android uses separate flags for assembly file invocations, but gyp expects
    # the same CFLAGS to be applied:
    self.WriteLn('LOCAL_ASFLAGS := $(LOCAL_CFLAGS)')


  def WriteSources(self, spec, configs, extra_sources):
    """Write Makefile code for any 'sources' from the gyp input.
    These are source files necessary to build the current target.
    We need to handle shared_intermediate directory source files as
    a special case by copying them to the intermediate directory and
    treating them as a genereated sources. Otherwise the Android build
    rules won't pick them up.

    Args:
      spec, configs: input from gyp.
      extra_sources: Sources generated from Actions or Rules.
    """
    sources = filter(make.Compilable, spec.get('sources', []))
    generated_not_sources = [x for x in extra_sources if not make.Compilable(x)]
    extra_sources = filter(make.Compilable, extra_sources)

    # Determine and output the C++ extension used by these sources.
    # We simply find the first C++ file and use that extension.
    all_sources = sources + extra_sources
    local_cpp_extension = '.cpp'
    for source in all_sources:
      (root, ext) = os.path.splitext(source)
      if IsCPPExtension(ext):
        local_cpp_extension = ext
        break
    if local_cpp_extension != '.cpp':
      self.WriteLn('LOCAL_CPP_EXTENSION := %s' % local_cpp_extension)

    # We need to move any non-generated sources that are coming from the
    # shared intermediate directory out of LOCAL_SRC_FILES and put them
    # into LOCAL_GENERATED_SOURCES. We also need to move over any C++ files
    # that don't match our local_cpp_extension, since Android will only
    # generate Makefile rules for a single LOCAL_CPP_EXTENSION.
    local_files = []
    for source in sources:
      (root, ext) = os.path.splitext(source)
      if '$(gyp_shared_intermediate_dir)' in source:
        extra_sources.append(source)
      elif '$(gyp_intermediate_dir)' in source:
        extra_sources.append(source)
      elif IsCPPExtension(ext) and ext != local_cpp_extension:
        extra_sources.append(source)
      else:
        local_files.append(os.path.normpath(os.path.join(self.path, source)))

    # For any generated source, if it is coming from the shared intermediate
    # directory then we add a Make rule to copy them to the local intermediate
    # directory first. This is because the Android LOCAL_GENERATED_SOURCES
    # must be in the local module intermediate directory for the compile rules
    # to work properly. If the file has the wrong C++ extension, then we add
    # a rule to copy that to intermediates and use the new version.
    final_generated_sources = []
    # If a source file gets copied, we still need to add the orginal source
    # directory as header search path, for GCC searches headers in the
    # directory that contains the source file by default.
    origin_src_dirs = []
    for source in extra_sources:
      local_file = source
      if not '$(gyp_intermediate_dir)/' in local_file:
        basename = os.path.basename(local_file)
        local_file = '$(gyp_intermediate_dir)/' + basename
      (root, ext) = os.path.splitext(local_file)
      if IsCPPExtension(ext) and ext != local_cpp_extension:
        local_file = root + local_cpp_extension
      if local_file != source:
        self.WriteLn('%s: %s' % (local_file, self.LocalPathify(source)))
        self.WriteLn('\tmkdir -p $(@D); cp $< $@')
        origin_src_dirs.append(os.path.dirname(source))
      final_generated_sources.append(local_file)

    # We add back in all of the non-compilable stuff to make sure that the
    # make rules have dependencies on them.
    final_generated_sources.extend(generated_not_sources)
    self.WriteList(final_generated_sources, 'LOCAL_GENERATED_SOURCES')

    origin_src_dirs = gyp.common.uniquer(origin_src_dirs)
    origin_src_dirs = map(Sourceify, map(self.LocalPathify, origin_src_dirs))
    self.WriteList(origin_src_dirs, 'GYP_COPIED_SOURCE_ORIGIN_DIRS')

    self.WriteList(local_files, 'LOCAL_SRC_FILES')

    # Write out the flags used to compile the source; this must be done last
    # so that GYP_COPIED_SOURCE_ORIGIN_DIRS can be used as an include path.
    self.WriteSourceFlags(spec, configs)


  def ComputeAndroidModule(self, spec):
    """Return the Android module name used for a gyp spec.

    We use the complete qualified target name to avoid collisions between
    duplicate targets in different directories. We also add a suffix to
    distinguish gyp-generated module names.
    """

    if int(spec.get('android_unmangled_name', 0)):
      assert self.type != 'shared_library' or self.target.startswith('lib')
      return self.target

    if self.type == 'shared_library':
      # For reasons of convention, the Android build system requires that all
      # shared library modules are named 'libfoo' when generating -l flags.
      prefix = 'lib_'
    else:
      prefix = ''

    if spec['toolset'] == 'host':
      suffix = '_$(TARGET_$(GYP_VAR_PREFIX)ARCH)_host_gyp'
    else:
      suffix = '_gyp'

    if self.path:
      middle = make.StringToMakefileVariable('%s_%s' % (self.path, self.target))
    else:
      middle = make.StringToMakefileVariable(self.target)

    return ''.join([prefix, middle, suffix])


  def ComputeOutputParts(self, spec):
    """Return the 'output basename' of a gyp spec, split into filename + ext.

    Android libraries must be named the same thing as their module name,
    otherwise the linker can't find them, so product_name and so on must be
    ignored if we are building a library, and the "lib" prepending is
    not done for Android.
    """
    assert self.type != 'loadable_module' # TODO: not supported?

    target = spec['target_name']
    target_prefix = ''
    target_ext = ''
    if self.type == 'static_library':
      target = self.ComputeAndroidModule(spec)
      target_ext = '.a'
    elif self.type == 'shared_library':
      target = self.ComputeAndroidModule(spec)
      target_ext = '.so'
    elif self.type == 'none':
      target_ext = '.stamp'
    elif self.type != 'executable':
      print ("ERROR: What output file should be generated?",
             "type", self.type, "target", target)

    if self.type != 'static_library' and self.type != 'shared_library':
      target_prefix = spec.get('product_prefix', target_prefix)
      target = spec.get('product_name', target)
      product_ext = spec.get('product_extension')
      if product_ext:
        target_ext = '.' + product_ext

    target_stem = target_prefix + target
    return (target_stem, target_ext)


  def ComputeOutputBasename(self, spec):
    """Return the 'output basename' of a gyp spec.

    E.g., the loadable module 'foobar' in directory 'baz' will produce
      'libfoobar.so'
    """
    return ''.join(self.ComputeOutputParts(spec))


  def ComputeOutput(self, spec):
    """Return the 'output' (full output path) of a gyp spec.

    E.g., the loadable module 'foobar' in directory 'baz' will produce
      '$(obj)/baz/libfoobar.so'
    """
    if self.type == 'executable':
      # We install host executables into shared_intermediate_dir so they can be
      # run by gyp rules that refer to PRODUCT_DIR.
      path = '$(gyp_shared_intermediate_dir)'
    elif self.type == 'shared_library':
      if self.toolset == 'host':
        path = '$($(GYP_HOST_VAR_PREFIX)HOST_OUT_INTERMEDIATE_LIBRARIES)'
      else:
        path = '$($(GYP_VAR_PREFIX)TARGET_OUT_INTERMEDIATE_LIBRARIES)'
    else:
      # Other targets just get built into their intermediate dir.
      if self.toolset == 'host':
        path = ('$(call intermediates-dir-for,%s,%s,true,,'
                '$(GYP_HOST_VAR_PREFIX))' % (self.android_class,
                                             self.android_module))
      else:
        path = ('$(call intermediates-dir-for,%s,%s,,,$(GYP_VAR_PREFIX))'
                % (self.android_class, self.android_module))

    assert spec.get('product_dir') is None # TODO: not supported?
    return os.path.join(path, self.ComputeOutputBasename(spec))

  def NormalizeIncludePaths(self, include_paths):
    """ Normalize include_paths.
    Convert absolute paths to relative to the Android top directory;
    filter out include paths that are already brought in by the Android build
    system.

    Args:
      include_paths: A list of unprocessed include paths.
    Returns:
      A list of normalized include paths.
    """
    normalized = []
    for path in include_paths:
      if path[0] == '/':
        path = gyp.common.RelativePath(path, self.android_top_dir)

      # Filter out the Android standard search path.
      if path not in android_standard_include_paths:
        normalized.append(path)
    return normalized

  def ExtractIncludesFromCFlags(self, cflags):
    """Extract includes "-I..." out from cflags

    Args:
      cflags: A list of compiler flags, which may be mixed with "-I.."
    Returns:
      A tuple of lists: (clean_clfags, include_paths). "-I.." is trimmed.
    """
    clean_cflags = []
    include_paths = []
    for flag in cflags:
      if flag.startswith('-I'):
        include_paths.append(flag[2:])
      else:
        clean_cflags.append(flag)

    return (clean_cflags, include_paths)

  def ComputeAndroidLibraryModuleNames(self, libraries):
    """Compute the Android module names from libraries, ie spec.get('libraries')

    Args:
      libraries: the value of spec.get('libraries')
    Returns:
      A tuple (static_lib_modules, dynamic_lib_modules)
    """
    static_lib_modules = []
    dynamic_lib_modules = []
    for libs in libraries:
      # Libs can have multiple words.
      for lib in libs.split():
        # Filter the system libraries, which are added by default by the Android
        # build system.
        if (lib == '-lc' or lib == '-lstdc++' or lib == '-lm' or
            lib.endswith('libgcc.a')):
          continue
        match = re.search(r'([^/]+)\.a$', lib)
        if match:
          static_lib_modules.append(match.group(1))
          continue
        match = re.search(r'([^/]+)\.so$', lib)
        if match:
          dynamic_lib_modules.append(match.group(1))
          continue
        # "-lstlport" -> libstlport
        if lib.startswith('-l'):
          if lib.endswith('_static'):
            static_lib_modules.append('lib' + lib[2:])
          else:
            dynamic_lib_modules.append('lib' + lib[2:])
    return (static_lib_modules, dynamic_lib_modules)


  def ComputeDeps(self, spec):
    """Compute the dependencies of a gyp spec.

    Returns a tuple (deps, link_deps), where each is a list of
    filenames that will need to be put in front of make for either
    building (deps) or linking (link_deps).
    """
    deps = []
    link_deps = []
    if 'dependencies' in spec:
      deps.extend([target_outputs[dep] for dep in spec['dependencies']
                   if target_outputs[dep]])
      for dep in spec['dependencies']:
        if dep in target_link_deps:
          link_deps.append(target_link_deps[dep])
      deps.extend(link_deps)
    return (gyp.common.uniquer(deps), gyp.common.uniquer(link_deps))


  def WriteTargetFlags(self, spec, configs, link_deps):
    """Write Makefile code to specify the link flags and library dependencies.

    spec, configs: input from gyp.
    link_deps: link dependency list; see ComputeDeps()
    """
    for configname, config in sorted(configs.iteritems()):
      ldflags = list(config.get('ldflags', []))
      self.WriteLn('')
      self.WriteList(ldflags, 'LOCAL_LDFLAGS_%s' % configname)
    self.WriteLn('\nLOCAL_LDFLAGS := $(LOCAL_LDFLAGS_$(GYP_CONFIGURATION))')

    # Libraries (i.e. -lfoo)
    libraries = gyp.common.uniquer(spec.get('libraries', []))
    static_libs, dynamic_libs = self.ComputeAndroidLibraryModuleNames(
        libraries)

    # Link dependencies (i.e. libfoo.a, libfoo.so)
    static_link_deps = [x[1] for x in link_deps if x[0] == 'static']
    shared_link_deps = [x[1] for x in link_deps if x[0] == 'shared']
    self.WriteLn('')
    self.WriteList(static_libs + static_link_deps,
                   'LOCAL_STATIC_LIBRARIES')
    self.WriteLn('# Enable grouping to fix circular references')
    self.WriteLn('LOCAL_GROUP_STATIC_LIBRARIES := true')
    self.WriteLn('')
    self.WriteList(dynamic_libs + shared_link_deps,
                   'LOCAL_SHARED_LIBRARIES')


  def WriteTarget(self, spec, configs, deps, link_deps, part_of_all,
                  write_alias_target):
    """Write Makefile code to produce the final target of the gyp spec.

    spec, configs: input from gyp.
    deps, link_deps: dependency lists; see ComputeDeps()
    part_of_all: flag indicating this target is part of 'all'
    write_alias_target: flag indicating whether to create short aliases for this
                        target
    """
    self.WriteLn('### Rules for final target.')

    if self.type != 'none':
      self.WriteTargetFlags(spec, configs, link_deps)

    # Add to the set of targets which represent the gyp 'all' target. We use the
    # name 'gyp_all_modules' as the Android build system doesn't allow the use
    # of the Make target 'all' and because 'all_modules' is the equivalent of
    # the Make target 'all' on Android.
    if part_of_all and write_alias_target:
      self.WriteLn('# Add target alias to "gyp_all_modules" target.')
      self.WriteLn('.PHONY: gyp_all_modules')
      self.WriteLn('gyp_all_modules: %s' % self.android_module)
      self.WriteLn('')

    # Add an alias from the gyp target name to the Android module name. This
    # simplifies manual builds of the target, and is required by the test
    # framework.
    if self.target != self.android_module and write_alias_target:
      self.WriteLn('# Alias gyp target name.')
      self.WriteLn('.PHONY: %s' % self.target)
      self.WriteLn('%s: %s' % (self.target, self.android_module))
      self.WriteLn('')

    # Add the command to trigger build of the target type depending
    # on the toolset. Ex: BUILD_STATIC_LIBRARY vs. BUILD_HOST_STATIC_LIBRARY
    # NOTE: This has to come last!
    modifier = ''
    if self.toolset == 'host':
      modifier = 'HOST_'
    if self.type == 'static_library':
      self.WriteLn('include $(BUILD_%sSTATIC_LIBRARY)' % modifier)
    elif self.type == 'shared_library':
      self.WriteLn('LOCAL_PRELINK_MODULE := false')
      self.WriteLn('include $(BUILD_%sSHARED_LIBRARY)' % modifier)
    elif self.type == 'executable':
      # Executables are for build and test purposes only, so they're installed
      # to a directory that doesn't get included in the system image.
      self.WriteLn('LOCAL_MODULE_PATH := $(gyp_shared_intermediate_dir)')
      self.WriteLn('include $(BUILD_%sEXECUTABLE)' % modifier)
    else:
      self.WriteLn('LOCAL_MODULE_PATH := $(PRODUCT_OUT)/gyp_stamp')
      self.WriteLn('LOCAL_UNINSTALLABLE_MODULE := true')
      if self.toolset == 'target':
        self.WriteLn('LOCAL_2ND_ARCH_VAR_PREFIX := $(GYP_VAR_PREFIX)')
      else:
        self.WriteLn('LOCAL_2ND_ARCH_VAR_PREFIX := $(GYP_HOST_VAR_PREFIX)')
      self.WriteLn()
      self.WriteLn('include $(BUILD_SYSTEM)/base_rules.mk')
      self.WriteLn()
      self.WriteLn('$(LOCAL_BUILT_MODULE): $(LOCAL_ADDITIONAL_DEPENDENCIES)')
      self.WriteLn('\t$(hide) echo "Gyp timestamp: $@"')
      self.WriteLn('\t$(hide) mkdir -p $(dir $@)')
      self.WriteLn('\t$(hide) touch $@')
      self.WriteLn()
      self.WriteLn('LOCAL_2ND_ARCH_VAR_PREFIX :=')


  def WriteList(self, value_list, variable=None, prefix='',
                quoter=make.QuoteIfNecessary, local_pathify=False):
    """Write a variable definition that is a list of values.

    E.g. WriteList(['a','b'], 'foo', prefix='blah') writes out
         foo = blaha blahb
    but in a pretty-printed style.
    """
    values = ''
    if value_list:
      value_list = [quoter(prefix + l) for l in value_list]
      if local_pathify:
        value_list = [self.LocalPathify(l) for l in value_list]
      values = ' \\\n\t' + ' \\\n\t'.join(value_list)
    self.fp.write('%s :=%s\n\n' % (variable, values))


  def WriteLn(self, text=''):
    self.fp.write(text + '\n')


  def LocalPathify(self, path):
    """Convert a subdirectory-relative path into a normalized path which starts
    with the make variable $(LOCAL_PATH) (i.e. the top of the project tree).
    Absolute paths, or paths that contain variables, are just normalized."""
    if '$(' in path or os.path.isabs(path):
      # path is not a file in the project tree in this case, but calling
      # normpath is still important for trimming trailing slashes.
      return os.path.normpath(path)
    local_path = os.path.join('$(LOCAL_PATH)', self.path, path)
    local_path = os.path.normpath(local_path)
    # Check that normalizing the path didn't ../ itself out of $(LOCAL_PATH)
    # - i.e. that the resulting path is still inside the project tree. The
    # path may legitimately have ended up containing just $(LOCAL_PATH), though,
    # so we don't look for a slash.
    assert local_path.startswith('$(LOCAL_PATH)'), (
           'Path %s attempts to escape from gyp path %s !)' % (path, self.path))
    return local_path


  def ExpandInputRoot(self, template, expansion, dirname):
    if '%(INPUT_ROOT)s' not in template and '%(INPUT_DIRNAME)s' not in template:
      return template
    path = template % {
        'INPUT_ROOT': expansion,
        'INPUT_DIRNAME': dirname,
        }
    return os.path.normpath(path)


def PerformBuild(data, configurations, params):
  # The android backend only supports the default configuration.
  options = params['options']
  makefile = os.path.abspath(os.path.join(options.toplevel_dir,
                                          'GypAndroid.mk'))
  env = dict(os.environ)
  env['ONE_SHOT_MAKEFILE'] = makefile
  arguments = ['make', '-C', os.environ['ANDROID_BUILD_TOP'], 'gyp_all_modules']
  print 'Building: %s' % arguments
  subprocess.check_call(arguments, env=env)


def GenerateOutput(target_list, target_dicts, data, params):
  options = params['options']
  generator_flags = params.get('generator_flags', {})
  builddir_name = generator_flags.get('output_dir', 'out')
  limit_to_target_all = generator_flags.get('limit_to_target_all', False)
  write_alias_targets = generator_flags.get('write_alias_targets', True)
  android_top_dir = os.environ.get('ANDROID_BUILD_TOP')
  assert android_top_dir, '$ANDROID_BUILD_TOP not set; you need to run lunch.'

  def CalculateMakefilePath(build_file, base_name):
    """Determine where to write a Makefile for a given gyp file."""
    # Paths in gyp files are relative to the .gyp file, but we want
    # paths relative to the source root for the master makefile.  Grab
    # the path of the .gyp file as the base to relativize against.
    # E.g. "foo/bar" when we're constructing targets for "foo/bar/baz.gyp".
    base_path = gyp.common.RelativePath(os.path.dirname(build_file),
                                        options.depth)
    # We write the file in the base_path directory.
    output_file = os.path.join(options.depth, base_path, base_name)
    assert not options.generator_output, (
        'The Android backend does not support options.generator_output.')
    base_path = gyp.common.RelativePath(os.path.dirname(build_file),
                                        options.toplevel_dir)
    return base_path, output_file

  # TODO:  search for the first non-'Default' target.  This can go
  # away when we add verification that all targets have the
  # necessary configurations.
  default_configuration = None
  toolsets = set([target_dicts[target]['toolset'] for target in target_list])
  for target in target_list:
    spec = target_dicts[target]
    if spec['default_configuration'] != 'Default':
      default_configuration = spec['default_configuration']
      break
  if not default_configuration:
    default_configuration = 'Default'

  srcdir = '.'
  makefile_name = 'GypAndroid' + options.suffix + '.mk'
  makefile_path = os.path.join(options.toplevel_dir, makefile_name)
  assert not options.generator_output, (
      'The Android backend does not support options.generator_output.')
  gyp.common.EnsureDirExists(makefile_path)
  root_makefile = open(makefile_path, 'w')

  root_makefile.write(header)

  # We set LOCAL_PATH just once, here, to the top of the project tree. This
  # allows all the other paths we use to be relative to the Android.mk file,
  # as the Android build system expects.
  root_makefile.write('\nLOCAL_PATH := $(call my-dir)\n')

  # Find the list of targets that derive from the gyp file(s) being built.
  needed_targets = set()
  for build_file in params['build_files']:
    for target in gyp.common.AllTargets(target_list, target_dicts, build_file):
      needed_targets.add(target)

  build_files = set()
  include_list = set()
  android_modules = {}
  for qualified_target in target_list:
    build_file, target, toolset = gyp.common.ParseQualifiedTarget(
        qualified_target)
    relative_build_file = gyp.common.RelativePath(build_file,
                                                  options.toplevel_dir)
    build_files.add(relative_build_file)
    included_files = data[build_file]['included_files']
    for included_file in included_files:
      # The included_files entries are relative to the dir of the build file
      # that included them, so we have to undo that and then make them relative
      # to the root dir.
      relative_include_file = gyp.common.RelativePath(
          gyp.common.UnrelativePath(included_file, build_file),
          options.toplevel_dir)
      abs_include_file = os.path.abspath(relative_include_file)
      # If the include file is from the ~/.gyp dir, we should use absolute path
      # so that relocating the src dir doesn't break the path.
      if (params['home_dot_gyp'] and
          abs_include_file.startswith(params['home_dot_gyp'])):
        build_files.add(abs_include_file)
      else:
        build_files.add(relative_include_file)

    base_path, output_file = CalculateMakefilePath(build_file,
        target + '.' + toolset + options.suffix + '.mk')

    spec = target_dicts[qualified_target]
    configs = spec['configurations']

    part_of_all = (qualified_target in needed_targets and
                   not int(spec.get('suppress_wildcard', False)))
    if limit_to_target_all and not part_of_all:
      continue

    relative_target = gyp.common.QualifiedTarget(relative_build_file, target,
                                                 toolset)
    writer = AndroidMkWriter(android_top_dir)
    android_module = writer.Write(qualified_target, relative_target, base_path,
                                  output_file, spec, configs,
                                  part_of_all=part_of_all,
                                  write_alias_target=write_alias_targets)
    if android_module in android_modules:
      print ('ERROR: Android module names must be unique. The following '
             'targets both generate Android module name %s.\n  %s\n  %s' %
             (android_module, android_modules[android_module],
              qualified_target))
      return
    android_modules[android_module] = qualified_target

    # Our root_makefile lives at the source root.  Compute the relative path
    # from there to the output_file for including.
    mkfile_rel_path = gyp.common.RelativePath(output_file,
                                              os.path.dirname(makefile_path))
    include_list.add(mkfile_rel_path)

  root_makefile.write('GYP_CONFIGURATION ?= %s\n' % default_configuration)
  root_makefile.write('GYP_VAR_PREFIX ?=\n')
  root_makefile.write('GYP_HOST_VAR_PREFIX ?=\n')
  root_makefile.write('GYP_HOST_MULTILIB ?=\n')

  # Write out the sorted list of includes.
  root_makefile.write('\n')
  for include_file in sorted(include_list):
    root_makefile.write('include $(LOCAL_PATH)/' + include_file + '\n')
  root_makefile.write('\n')

  if write_alias_targets:
    root_makefile.write(ALL_MODULES_FOOTER)

  root_makefile.close()