Change analyzer to search for build_targets from supplied targets

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.
 
 The following is output:
 error: only supplied if there is an error.
-targets: the set of targets passed in via targets that either directly or
-  indirectly depend upon the set of paths supplied in files.
 build_targets: minimal set of targets that directly depend on the changed
   files and need to be built. The expectation is this set of targets is passed
-  into a build step.
+  into a build step. The returned values are either values in the supplied
+  targets, or have a dependency on one of the supplied targets.
 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 build_targets are not output) or at
   least one file was found.
 invalid_targets: list of supplied targets thare were not found.
 
+Example:
+Consider a graph like the following:
+  A     D
+ / \
+B   C
+A depends upon both B and C, A is of type none and B and C are executables.
+D is an executable, has no dependencies and nothing depends on it.
+If |targets| = ["A"] and files = ["b.cc", "d.cc"] (B depends upon b.cc and D
+depends upon d.cc), then the following is output:
+|build_targets| = ["B"] B must built as it depends upon the changed file b.cc
+and the supplied target A depends upon it. A is not output as a build_target
+as it is of type none with no rules and actions.
+
+Even though the file d.cc, which D depends upon, has changed D is not output
+as none of the supplied targets (A) depend upon D.
+
 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
@@ skipping 217 matching lines @@
     if _ToLocalPath(toplevel_dir, 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 _GetOrCreateTargetByName(targets, target_name):
   """Creates or returns the Target at targets[target_name]. If there is no
-  Target for |target_name| one is created. Returns a tuple of whether a new
-  Target was created and the Target."""
+  Target for |target_name| one is created."""
   if target_name in targets:
-    return False, targets[target_name]
+    return targets[target_name]
   target = Target(target_name)
   targets[target_name] = target
-  return True, target
+  return target
 
 
 def _DoesTargetTypeRequireBuild(target_dict):
   """Returns true if the target type is such that it needs to be built."""
   # If a 'none' target has rules or actions we assume it requires a build.
   return bool(target_dict['type'] != 'none' or
               target_dict.get('actions') or target_dict.get('rules'))
 
 
 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[:]
 
   # 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()
-    created_target, target = _GetOrCreateTargetByName(targets, target_name)
-    if created_target:
-      roots.add(target)
-    elif target.visited:
+    target = _GetOrCreateTargetByName(targets, target_name)
+    if target.visited:
       continue
 
     target.visited = True
     target.requires_build = _DoesTargetTypeRequireBuild(
         target_dicts[target_name])
     target_type = target_dicts[target_name]['type']
     target.is_executable = target_type == 'executable'
     target.is_static_library = target_type == 'static_library'
     target.is_or_has_linked_ancestor = (target_type == 'executable' or
                                         target_type == 'shared_library')
 
     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, toplevel_dir)
 
-    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
       matching_targets.append(target)
     else:
       sources = _ExtractSources(target_name, target_dicts[target_name],
                                 toplevel_dir)
       for source in sources:
         if _ToGypPath(os.path.normpath(source)) in files:
           print 'target', target_name, 'matches', source
           target.match_status = MATCH_STATUS_MATCHES
           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_to_visit.append(dep)
 
-      created_dep_target, dep_target = _GetOrCreateTargetByName(targets, dep)
-      if not created_dep_target:
-        roots.discard(dep_target)
+      dep_target = _GetOrCreateTargetByName(targets, dep)
 
       target.deps.add(dep_target)
       dep_target.back_deps.add(target)
 
-  return targets, matching_targets, roots & build_file_targets
+  return targets, matching_targets
 
 
 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]] = all_targets[target_name]
       if not to_find:
         return result
   return result
 
 
-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."""
-  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 in target.deps:
-    if _DoesTargetDependOn(dep):
-      target.match_status = MATCH_STATUS_MATCHES_BY_DEPENDENCY
-      print '\t', target.name, 'matches by dep', dep.name
-      return True
-  target.match_status = MATCH_STATUS_DOESNT_MATCH
-  return False
-
-
-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 = []
-  print 'Targets that matched by dependency:'
-  for target in possible_targets:
-    if _DoesTargetDependOn(target):
-      found.append(target)
-  return found
-
-
-def _AddBuildTargets(target, roots, add_if_no_ancestor, result):
+def _AddBuildTargets(target, roots, result):
   """Recurses through all targets that depend on |target|, adding all targets
   that need to be built (and are in |roots|) to |result|.
   roots: set of root targets.
-  add_if_no_ancestor: If true and there are no ancestors of |target| then add
-  |target| to |result|. |target| must still be in |roots|.
   result: targets that need to be built are added here."""
   if target.visited:
     return
 
   target.visited = True
-  target.in_roots = not target.back_deps and target in roots
+  target.in_roots = target in roots
 
   for back_dep_target in target.back_deps:
-    _AddBuildTargets(back_dep_target, roots, False, result)
+    _AddBuildTargets(back_dep_target, roots, result)
     target.added_to_compile_targets |= back_dep_target.added_to_compile_targets
     target.in_roots |= back_dep_target.in_roots
     target.is_or_has_linked_ancestor |= (
       back_dep_target.is_or_has_linked_ancestor)
 
   # Always add 'executable' targets. Even though they may be built by other
   # targets that depend upon them it makes detection of what is going to be
   # built easier.
   # And always add static_libraries that have no dependencies on them from
   # linkables. This is necessary as the other dependencies on them may be
   # static libraries themselves, which are not compile time dependencies.
   if target.in_roots and \
         (target.is_executable or
-         (not target.added_to_compile_targets and
-          (add_if_no_ancestor or target.requires_build)) or
-         (target.is_static_library and add_if_no_ancestor and
-          not target.is_or_has_linked_ancestor)):
+         (not target.added_to_compile_targets and target.requires_build) or
+         (target.is_static_library and not target.is_or_has_linked_ancestor)):
     print '\t\tadding to build targets', target.name, 'executable', \
            target.is_executable, 'added_to_compile_targets', \
-           target.added_to_compile_targets, 'add_if_no_ancestor', \
-           add_if_no_ancestor, 'requires_build', target.requires_build, \
-           'is_static_library', target.is_static_library, \
-           'is_or_has_linked_ancestor', target.is_or_has_linked_ancestor
+           target.added_to_compile_targets, 'requires_build', \
+           target.requires_build, 'is_static_library', \
+           target.is_static_library, 'is_or_has_linked_ancestor', \
+           target.is_or_has_linked_ancestor
     result.add(target)
     target.added_to_compile_targets = True
 
 
 def _GetBuildTargets(matching_targets, roots):
   """Returns the set of Targets that require a build.
   matching_targets: targets that changed and need to be built.
   roots: set of root targets in the build files to search from."""
   result = set()
   for target in matching_targets:
     print '\tfinding build targets for match', target.name
-    _AddBuildTargets(target, roots, True, result)
+    _AddBuildTargets(target, roots, result)
   return result
 
 
 def _WriteOutput(params, **values):
   """Writes the output, either to stdout or a file is specified."""
   if 'error' in values:
     print 'Error:', values['error']
   if 'status' in values:
     print values['status']
   if 'targets' in values:
@@ skipping 82 matching lines @@
     toplevel_dir = _ToGypPath(os.path.abspath(params['options'].toplevel_dir))
     if debug:
       print 'toplevel_dir', toplevel_dir
 
     if _WasGypIncludeFileModified(params, config.files):
       result_dict = { 'status': all_changed_string,
                       'targets': list(config.targets) }
       _WriteOutput(params, **result_dict)
       return
 
-    all_targets, matching_targets, roots = _GenerateTargets(
+    all_targets, matching_targets = _GenerateTargets(
       data, target_list, target_dicts, toplevel_dir, frozenset(config.files),
       params['build_files'])
 
-    print 'roots:'
-    for root in roots:
-      print '\t', root.name
-
     unqualified_mapping = _GetUnqualifiedToTargetMapping(all_targets,
                                                          config.targets)
     invalid_targets = None
     if len(unqualified_mapping) != len(config.targets):
       invalid_targets = _NamesNotIn(config.targets, unqualified_mapping)
 
     if matching_targets:
       search_targets = _LookupTargets(config.targets, unqualified_mapping)
       print 'supplied targets'
       for target in config.targets:
         print '\t', target
       print 'expanded supplied targets'
       for target in search_targets:
         print '\t', target.name
-      matched_search_targets = _GetTargetsDependingOn(search_targets)
-      print 'raw matched search targets:'
-      for target in matched_search_targets:
-        print '\t', target.name
       # Reset the visited status for _GetBuildTargets.
       for target in all_targets.itervalues():
         target.visited = False
       print 'Finding build targets'
-      build_targets = _GetBuildTargets(matching_targets, roots)
-      matched_search_targets = [gyp.common.ParseQualifiedTarget(target.name)[1]
-                                for target in matched_search_targets]
+      build_targets = _GetBuildTargets(matching_targets, search_targets)
       build_targets = [gyp.common.ParseQualifiedTarget(target.name)[1]
                        for target in build_targets]
     else:
-      matched_search_targets = []
       build_targets = []
 
-    result_dict = { 'targets': matched_search_targets,
+    # TODO(sky): nuke 'targets'.
+    result_dict = { 'targets': build_targets,
                     'status': found_dependency_string if matching_targets else
                               no_dependency_string,
                     'build_targets': build_targets}
     if invalid_targets:
       result_dict['invalid_targets'] = invalid_targets
     _WriteOutput(params, **result_dict)
 
   except Exception as e:
     _WriteOutput(params, error=str(e))