Makes the analyzer output the set of targets needing a build

pylib/gyp/generator/analyzer.py

 # Copyright (c) 2014 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.
 
 """
 This script is intended for use as a GYP_GENERATOR. It takes as input (by way of
 the generator flag config_path) the path of a json file that dictates the files
 and targets to search for. The following keys are supported:
 files: list of paths (relative) of the files to search for.
 targets: list of targets to search for. The target names are unqualified.
+ignore_targets: list of targets not to include in effected_targets. If a target

[scottmg, 2014/08/15 19:44:45]

All the 'effected/Effected's should be 'affected/Affected'.

[sky, 2014/08/15 19:58:12]

I *knew* I would get that wrong;)

+  that any of these targets depend on is modified the target won't be output.
+  These targets will be output if they contained one of the supplied file names.

[scottmg, 2014/08/15 21:30:24]

so, if there's a target in ignored_targets, and something in that target changes
it _will_ be output?

[sky, 2014/08/15 22:39:37]

Ya, sorry, this is all rather complex. Consider the All target in build/all.gyp.
It depends upon mojo.gyp:* . Lets say you modified a mojo/spy/spy.cc, which is
in the target mojo.gyp:mojo_spy. Since All depends upon mojo.gyp:* it depends
upon mojo.gyp:mojo_spy. And since mojo_spy has been modified this means we need
to compile both mojo_spy and the All target. The All target doesn't contain any
files, so we don't want to trigger compiling it. This is what the ignore_targets
are for. With All in ignore_targets All won't be added to affected_targets,
unless it has a source that matched the set of files specified.

I thought perhaps I could key off the build_type. That is, instead of
ignore_targets key off a build_type of None. But I couldn't convince myself that
was right. Some build_types of None have actions, and it seems like if such a
target depends upon a matched target then it needs to be built.

 
 The following is output:
 error: only supplied if there is an error.
 warning: only supplied if there is a warning.
 targets: the set of targets passed in via targets that either directly or
-  indirectly depend upon the set of paths supplied in files.
-status: indicates if any of the supplied files matched at least one target.
+  indirectly depend upon the set of paths supplied in files. This is not output
+effected_targets: minimal set of targets that directly depend on the changed
+  files. The output from this could be passed into a compile step to build the
+  minimal set of targets that are effected by the set of changed files.
+status: outputs one of three values: none of the supplied files were found,
+  one of the include files changed so that it should be assumed everything
+  changed (in this case targets and effected_targets are not output) or at
+  least one file was found.
 
 If the generator flag analyzer_output_path is specified, output is written
 there. Otherwise output is written to stdout.
 """
 
 import gyp.common
 import gyp.ninja_syntax as ninja_syntax
 import json
 import os
 import posixpath
 import sys
 
 debug = False
 
 found_dependency_string = 'Found dependency'
 no_dependency_string = 'No dependencies'
+# Status when it should be assumed that everything has changed.
+all_changed_string = 'Found dependency (all)'
 
 # MatchStatus is used indicate if and how a target depends upon the supplied
 # sources.
-# The target's sources contain one of the supplied paths.
 MATCH_STATUS_MATCHES = 1
 # The target has a dependency on another target that contains one of the
 # supplied paths.
 MATCH_STATUS_MATCHES_BY_DEPENDENCY = 2
 # The target's sources weren't in the supplied paths and none of the target's
 # dependencies depend upon a target that matched.
 MATCH_STATUS_DOESNT_MATCH = 3
 # The target doesn't contain the source, but the dependent targets have not yet
 # been visited to determine a more specific status yet.
 MATCH_STATUS_TBD = 4
@@ skipping 103 matching lines @@
                                 results)
   if 'rules' in target_dict:
     for rule in target_dict['rules']:
       _ExtractSourcesFromAction(rule, base_path, base_path_components, results)
 
   return results
 
 
 class Target(object):
   """Holds information about a particular target:
-  deps: set of the names of direct dependent targets.
-  match_staus: one of the MatchStatus values"""
-  def __init__(self):
+  deps: set of Targets this Target depends upon. This is not recursive, only the
+    direct dependent Targets.
+  match_staus: one of the MatchStatus values.
+  back_deps: set of Targets that have a dependency on this Target.
+  visited: used during iteration to indicate whether we've visited this target.
+    This is used for two iterations, once in building the set of Targets and
+    again in _GetEffectedTargets().
+  name: fully qualified name of the target."""
+  def __init__(self, name):
     self.deps = set()
     self.match_status = MATCH_STATUS_TBD
+    self.back_deps = set()
+    self.visited = False
+    self.name = name
 
 
 class Config(object):
   """Details what we're looking for
   files: set of files to search for
-  targets: see file description for details"""
+  targets: see file description for details.
+  ignore_targets: see file description for details"""
   def __init__(self):
     self.files = []
-    self.targets = []
+    self.targets = set()
+    self.ignore_targets = set()
 
   def Init(self, params):
     """Initializes Config. This is a separate method as it raises an exception
     if there is a parse error."""
     generator_flags = params.get('generator_flags', {})
     config_path = generator_flags.get('config_path', None)
     if not config_path:
       return
     try:
       f = open(config_path, 'r')
       config = json.load(f)
       f.close()
     except IOError:
       raise Exception('Unable to open file ' + config_path)
     except ValueError as e:
       raise Exception('Unable to parse config file ' + config_path + str(e))
     if not isinstance(config, dict):
       raise Exception('config_path must be a JSON file containing a dictionary')
     self.files = config.get('files', [])
-    # Coalesce duplicates
-    self.targets = list(set(config.get('targets', [])))
+    # Convert to sets so that we remove duplicates.
+    self.targets = set(config.get('targets', []))
+    self.ignore_targets = set(config.get('ignore_targets', []))
 
 
 def _WasBuildFileModified(build_file, data, files):
   """Returns true if the build file |build_file| is either in |files| or
   one of the files included by |build_file| is in |files|."""
   if _ToGypPath(build_file) in files:
     if debug:
       print 'gyp file modified', build_file
     return True
 
   # First element of included_files is the file itself.
   if len(data[build_file]['included_files']) <= 1:
     return False
 
   for include_file in data[build_file]['included_files'][1:]:
     # |included_files| are relative to the directory of the |build_file|.
     rel_include_file = \
         _ToGypPath(gyp.common.UnrelativePath(include_file, build_file))
     if rel_include_file in files:
       if debug:
         print 'included gyp file modified, gyp_file=', build_file, \
             'included file=', rel_include_file
       return True
   return False
 
 
-def _GenerateTargets(data, target_list, target_dicts, toplevel_dir, files):
-  """Generates a dictionary with the key the name of a target and the value a
-  Target. |toplevel_dir| is the root of the source tree. If the sources of
-  a target match that of |files|, then |target.matched| is set to True.
-  This returns a tuple of the dictionary and whether at least one target's
-  sources listed one of the paths in |files|."""
+def _GenerateTargets(data, target_list, target_dicts, toplevel_dir, files,
+                     build_files):
+  """Returns a tuple of the following:
+  . A dictionary mapping from fully qualified name to Target.
+  . A list of the targets that have a source file in |files|.
+  . Set of root Targets reachable from the the files |build_files|.
+  This sets the |match_status| of the targets that contain any of the source
+  files in |files| to MATCH_STATUS_MATCHES.
+  |toplevel_dir| is the root of the source tree."""
+  # Maps from target name to Target.
   targets = {}
 
+  # Targets that matched.
+  matching_targets = []
+
   # Queue of targets to visit.
   targets_to_visit = target_list[:]
 
-  matched = False
-
   # Maps from build file to a boolean indicating whether the build file is in
   # |files|.
   build_file_in_files = {}
 
+  # Root targets across all files.
+  roots = set()
+
+  # Set of Targets in |build_files|.
+  build_file_targets = set()
+
   while len(targets_to_visit) > 0:
     target_name = targets_to_visit.pop()
-    if target_name in targets:
+    if not target_name in targets:
+      target = Target(target_name)
+      targets[target_name] = target
+      roots.add(target)
+    elif targets[target_name].visited:
       continue
+    else:
+      target = targets[target_name]
 
-    target = Target()
-    targets[target_name] = target
+    target.visited = True
 
     build_file = gyp.common.ParseQualifiedTarget(target_name)[0]
     if not build_file in build_file_in_files:
       build_file_in_files[build_file] = \
           _WasBuildFileModified(build_file, data, files)
 
+    if build_file in build_files:
+      build_file_targets.add(target)
+
     # If a build file (or any of its included files) is modified we assume all
     # targets in the file are modified.
     if build_file_in_files[build_file]:
+      print 'matching target from modified build file', target_name
       target.match_status = MATCH_STATUS_MATCHES
-      matched = True
+      matching_targets.append(target)
     else:
       sources = _ExtractSources(target_name, target_dicts[target_name],
                                 toplevel_dir)
       for source in sources:
         if source in files:
+          print 'target', target_name, 'matches', source
           target.match_status = MATCH_STATUS_MATCHES
-          matched = True
+          matching_targets.append(target)
           break
 
+    # Add dependencies to visit as well as updating back pointers for deps.
     for dep in target_dicts[target_name].get('dependencies', []):
-      targets[target_name].deps.add(dep)
       targets_to_visit.append(dep)
 
-  return targets, matched
+      if not dep in targets:
+        dep_target = Target(dep)
+        targets[dep] = dep_target
+      else:
+        dep_target = targets[dep]
+        roots.discard(dep_target)
+
+      target.deps.add(dep_target)
+      dep_target.back_deps.add(target)
+
+  return targets, matching_targets, roots & build_file_targets
 
 
-def _GetUnqualifiedToQualifiedMapping(all_targets, to_find):
-  """Returns a mapping (dictionary) from unqualified name to qualified name for
-  all the targets in |to_find|."""
+def _GetUnqualifiedToTargetMapping(all_targets, to_find):
+  """Returns a mapping (dictionary) from unqualified name to Target for all the
+  Targets in |to_find|."""
   result = {}
   if not to_find:
     return result
   to_find = set(to_find)
   for target_name in all_targets.keys():
     extracted = gyp.common.ParseQualifiedTarget(target_name)
     if len(extracted) > 1 and extracted[1] in to_find:
       to_find.remove(extracted[1])
-      result[extracted[1]] = target_name
+      result[extracted[1]] = all_targets[target_name]
       if not to_find:
         return result
   return result
 
 
-def _DoesTargetDependOn(target, all_targets):
+def _DoesTargetDependOn(target):
   """Returns true if |target| or any of its dependencies matches the supplied
   set of paths. This updates |matches| of the Targets as it recurses.
-  target: the Target to look for.
-  all_targets: mapping from target name to Target.
-  matching_targets: set of targets looking for."""
+  target: the Target to look for."""
   if target.match_status == MATCH_STATUS_DOESNT_MATCH:
     return False
   if target.match_status == MATCH_STATUS_MATCHES or \
       target.match_status == MATCH_STATUS_MATCHES_BY_DEPENDENCY:
     return True
-  for dep_name in target.deps:
-    dep_target = all_targets[dep_name]
-    if _DoesTargetDependOn(dep_target, all_targets):
-      dep_target.match_status = MATCH_STATUS_MATCHES_BY_DEPENDENCY
+  for dep in target.deps:
+    if _DoesTargetDependOn(dep):
+      target.match_status = MATCH_STATUS_MATCHES_BY_DEPENDENCY
       return True
-    dep_target.match_status = MATCH_STATUS_DOESNT_MATCH
+  target.match_status = MATCH_STATUS_DOESNT_MATCH
   return False
 
 
-def _GetTargetsDependingOn(all_targets, possible_targets):
-  """Returns the list of targets in |possible_targets| that depend (either
-  directly on indirectly) on the matched files.
-  all_targets: mapping from target name to Target.
+def _GetTargetsDependingOn(possible_targets):
+  """Returns the list of Targets in |possible_targets| that depend (either
+  directly on indirectly) on the matched targets.
   possible_targets: targets to search from."""
   found = []
   for target in possible_targets:
-    if _DoesTargetDependOn(all_targets[target], all_targets):
-      # possible_targets was initially unqualified, keep it unqualified.
-      found.append(gyp.common.ParseQualifiedTarget(target)[1])
+    if _DoesTargetDependOn(target):
+      found.append(target)
   return found
 
 
+def _RemoveTargetsThatDependOn(target, targets):
+  """Removes |target| from |targets|. If |targets| is not empty recurses through
+  descendants."""
+  if target in targets:
+    targets.remove(target)
+    return len(targets) == 0
+
+  if target.visited or target.match_status == MATCH_STATUS_DOESNT_MATCH:
+    return False
+
+  for child_target in target.deps:
+    if _RemoveTargetsThatDependOn(child_target, targets):
+      return True
+
+  return False
+
+
+def _AddFirstModified(target, result):
+  """Adds |target| to |result| if it matches, otherwise recursively descends
+  through children doing the same.
+  |result|: targets that match are added here. Once a target matches none of its
+            dependencies are considered."""
+  if target.visited:
+    return
+
+  if target.match_status == MATCH_STATUS_MATCHES or \
+      target.match_status == MATCH_STATUS_MATCHES_BY_DEPENDENCY:
+    # Because of iteration order it is possible for |target| to depend on other
+    # targets in |result|. Prune them.
+    if result:
+      _RemoveTargetsThatDependOn(target, result)
+    result.add(target)
+    target.visited = True
+    return
+
+  target.visited = True
+
+  if target.match_status == MATCH_STATUS_DOESNT_MATCH:
+    return
+
+  for child_target in target.deps:
+    _AddFirstModified(child_target, result)
+
+
+def _MarkVisitedAndMatches(target):
+  """Marks |target| as visited and matches (assuming it isn't already), and
+  recurses through dependencies. Does nothing if already |target| has already
+  been visited."""
+  if target.visited:
+    return
+
+  target.visited = True
+
+  if target.match_status != MATCH_STATUS_MATCHES:
+    target.match_status = MATCH_STATUS_MATCHES_BY_DEPENDENCY
+
+  for child_target in target.deps:
+    _MarkVisitedAndMatches(child_target)
+
+
+def _MarkDepsVisitedAndMatches(target, ignore):
+  """Marks all the |deps| of |target| that are not in |ignore| as visited and
+  matches. See _MarkVisitedAndMatches() for details."""
+  for child_target in target.deps:
+    if child_target not in ignore:
+      _MarkVisitedAndMatches(child_target)
+
+
+def _GetEffectedTargets(matching_targets, matched_search_targets, roots,
+                        ignore_targets):
+  """Returns the set of Targets that directly depend on |matching_targets| and
+  have not yet matched one of the supplied targets.
+  matched_search_targets: set of targets passed in (by way of config) that
+                          matched a dependency.
+  roots: set of root targets in the build files to search from.
+  ignore_targets: see file description for details."""
+  # This function strives to minimize the set of targets it returns. For example
+  # if A and B are in matching_targets, but B depends upon A then we only need
+  # return A for both to be compiled.
+  #
+  # When we get here all the Targets have their |visited| state set to False.
+  # As not all Targets may have been visited the |match_status| may still be
+  # TBD for many. For example, if B depends on A and A matched, then B's state
+  # may still be TBD. We need to ensure the match_status is set correctly so
+  # then when we resurse from the root targets we don't attempt to include
+  # a Target that would be included by way of another Targets depedendencies.
+
+  # First step, visit the search targets, recursively marking all of their
+  # descendants as visited and matching.
+  for target in matched_search_targets:
+    _MarkDepsVisitedAndMatches(target, set())
+
+  # For all the targets that contained matching files we need to mark any of
+  # their dependencies as visited and matching. Similarly any targets that
+  # depend on |matching_targets| needs to be marked as matching as well. We have
+  # to take care not to mark the |matching_targets| (or the |ignore_targets|)
+  # visited, otherwise we won't add it to the result later on.
+  for target in matching_targets:
+    _MarkDepsVisitedAndMatches(target, set())
+    ignore_plus_target = set(ignore_targets)
+    ignore_plus_target.add(target)
+    for back_dep_target in target.back_deps:
+      if back_dep_target not in ignore_targets:
+        back_dep_target.match_status = MATCH_STATUS_MATCHES_BY_DEPENDENCY
+        _MarkDepsVisitedAndMatches(back_dep_target, ignore_plus_target)
+
+  # Reset the status of any in |ignore_targets| that match by way of a
+  # dependency. This way we won't incorrectly pull them in again (they may have
+  # matched by dependency). We don't reset those that matched explicitly as they
+  # have to be compiled.
+  for target in ignore_targets:
+    if target.match_status == MATCH_STATUS_MATCHES_BY_DEPENDENCY:
+      target.match_status = MATCH_STATUS_TBD
+
+  # Finally we can search down from the root Targets adding the first Targets
+  # that match.
+  result = set()
+  for root in roots:
+    _AddFirstModified(root, result)
+
+  return result
+
+
 def _WriteOutput(params, **values):
   """Writes the output, either to stdout or a file is specified."""
   output_path = params.get('generator_flags', {}).get(
       'analyzer_output_path', None)
   if not output_path:
     print json.dumps(values)
     return
   try:
     f = open(output_path, 'w')
     f.write(json.dumps(values) + '\n')
     f.close()
   except IOError as e:
     print 'Error writing to output file', output_path, str(e)
 
 
+def _WasIncludeFileModified(params, files):
+  """Returns true if one of the files in |files| is in the set of included
+  files."""
+  if params['options'].includes:
+    for include in params['options'].includes:
+      if _ToGypPath(include) in files:
+        print 'Include file modified, assuming all changed', include
+        return True
+  return False
+
+
+def _NamesNotIn(names, mapping):
+  """Returns a list of the values in |names| that are not in |mapping|."""
+  return [name for name in names if name not in mapping]
+
+
+def _LookupTargets(names, mapping):
+  """Returns a list of the mapping[name] for each value in |names| that is in
+  |mapping|."""
+  return [mapping[name] for name in names if name in mapping]
+
+
 def CalculateVariables(default_variables, params):
   """Calculate additional variables for use in the build (called by gyp)."""
   flavor = gyp.common.GetFlavor(params)
   if flavor == 'mac':
     default_variables.setdefault('OS', 'mac')
   elif flavor == 'win':
     default_variables.setdefault('OS', 'win')
     # Copy additional generator configuration data from VS, which is shared
     # by the Windows Ninja generator.
     import gyp.generator.msvs as msvs_generator
@@ skipping 16 matching lines @@
   try:
     config.Init(params)
     if not config.files:
       raise Exception('Must specify files to analyze via config_path generator '
                       'flag')
 
     toplevel_dir = _ToGypPath(os.path.abspath(params['options'].toplevel_dir))
     if debug:
       print 'toplevel_dir', toplevel_dir
 
-    matched = False
-    matched_include = False
+    if _WasIncludeFileModified(params, config.files):
+      result_dict = { 'status': all_changed_string }
+      _WriteOutput(params, **result_dict)
+      return
 
-    # If one of the modified files is an include file then everything is
-    # affected.
-    if params['options'].includes:
-      for include in params['options'].includes:
-        if _ToGypPath(include) in config.files:
-          if debug:
-            print 'include path modified', include
-          matched_include = True
-          matched = True
-          break
-
-    if not matched:
-      all_targets, matched = _GenerateTargets(data, target_list, target_dicts,
-                                              toplevel_dir,
-                                              frozenset(config.files))
+    all_targets, matching_targets, roots = _GenerateTargets(
+      data, target_list, target_dicts, toplevel_dir, frozenset(config.files),
+      params['build_files'])
 
     warning = None
-    if matched_include:
-      output_targets = config.targets
-    elif matched:
-      unqualified_mapping = _GetUnqualifiedToQualifiedMapping(
-          all_targets, config.targets)
-      if len(unqualified_mapping) != len(config.targets):
-        not_found = []
-        for target in config.targets:
-          if not target in unqualified_mapping:
-            not_found.append(target)
-        warning = 'Unable to find all targets: ' + str(not_found)
-      qualified_targets = []
-      for target in config.targets:
-        if target in unqualified_mapping:
-          qualified_targets.append(unqualified_mapping[target])
-      output_targets = _GetTargetsDependingOn(all_targets, qualified_targets)
+    combined_targets = config.targets | config.ignore_targets
+    unqualified_mapping = _GetUnqualifiedToTargetMapping(all_targets,
+                                                         combined_targets)
+    if len(unqualified_mapping) != len(combined_targets):
+      not_found = _NamesNotIn(combined_targets, unqualified_mapping)
+      warning = 'Unable to find all targets: ' + str(not_found)
+
+    if matching_targets:
+      search_targets = _LookupTargets(config.targets, unqualified_mapping)
+      ignore_targets = _LookupTargets(config.ignore_targets,
+                                      unqualified_mapping)
+
+      matched_search_targets = _GetTargetsDependingOn(search_targets)
+      # Reset the visited status for _GetEffectedTargets.
+      for target in all_targets.itervalues():
+        target.visited = False
+      effected_targets = _GetEffectedTargets(matching_targets,
+                                             matched_search_targets, roots,
+                                             ignore_targets)
+      matched_search_targets = [gyp.common.ParseQualifiedTarget(target.name)[1]
+                              for target in matched_search_targets]
+      effected_targets = [gyp.common.ParseQualifiedTarget(target.name)[1]
+                          for target in effected_targets]
     else:
-      output_targets = []
+      matched_search_targets = []
+      effected_targets = []
 
-    result_dict = { 'targets': output_targets,
-                    'status': found_dependency_string if matched else
-                              no_dependency_string }
+    result_dict = { 'targets': matched_search_targets,
+                    'status': found_dependency_string if matching_targets else
+                              no_dependency_string,
+                    'effected_targets': effected_targets}
     if warning:
       result_dict['warning'] = warning
     _WriteOutput(params, **result_dict)
 
   except Exception as e:
     _WriteOutput(params, error=str(e))