Index: pylib/gyp/generator/analyzer.py |
=================================================================== |
--- pylib/gyp/generator/analyzer.py (revision 1965) |
+++ pylib/gyp/generator/analyzer.py (working copy) |
@@ -8,13 +8,22 @@ |
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 affected_targets. If a target |
+ 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. |
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 |
scottmg
2014/08/15 21:30:24
"This is not output"? It looks like it is.
sky
2014/08/15 22:39:37
Removed.
|
+affected_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 affected 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 affected_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. |
@@ -31,10 +40,11 @@ |
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. |
@@ -143,7 +153,7 @@ |
if 'sources' in target_dict: |
_AddSources(target_dict['sources'], base_path, base_path_components, |
results) |
- # Include the inputs from any actions. Any changes to these effect the |
+ # Include the inputs from any actions. Any changes to these affect the |
# resulting output. |
if 'actions' in target_dict: |
for action in target_dict['actions']: |
@@ -158,20 +168,31 @@ |
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. |
scottmg
2014/08/15 21:30:24
match_staus -> match_status
sky
2014/08/15 22:39:37
Done.
|
+ 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 _GetAffectedTargets(). |
+ 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 |
@@ -191,8 +212,9 @@ |
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): |
@@ -219,60 +241,91 @@ |
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 |
scottmg
2014/08/15 21:30:24
this seems duplicated with code at 314, could one
sky
2014/08/15 22:39:37
They are slightly different, but I can indeed shar
|
+ 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) |
-def _GetUnqualifiedToQualifiedMapping(all_targets, to_find): |
- """Returns a mapping (dictionary) from unqualified name to qualified name for |
- all the targets in |to_find|.""" |
+ return targets, matching_targets, roots & build_file_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 |
@@ -281,45 +334,163 @@ |
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 _GetAffectedTargets(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 |
scottmg
2014/08/15 21:30:24
resurse -> recurse
sky
2014/08/15 22:39:37
Done.
|
+ # a Target that would be included by way of another Targets depedendencies. |
scottmg
2014/08/15 21:30:24
dependencies
sky
2014/08/15 22:39:37
Done.
|
+ |
+ # 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) |
scottmg
2014/08/15 21:30:24
sorry, i don't quite understand ignore_targets sti
sky
2014/08/15 22:39:37
Sorry, I missed your earlier WTF. I responded to i
|
+ 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( |
@@ -335,6 +506,28 @@ |
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) |
@@ -371,48 +564,48 @@ |
if debug: |
print 'toplevel_dir', toplevel_dir |
- matched = False |
- matched_include = False |
+ if _WasIncludeFileModified(params, config.files): |
+ result_dict = { 'status': all_changed_string, |
+ 'targets': list(config.targets) } |
+ _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 |
+ all_targets, matching_targets, roots = _GenerateTargets( |
+ data, target_list, target_dicts, toplevel_dir, frozenset(config.files), |
+ params['build_files']) |
- if not matched: |
- all_targets, matched = _GenerateTargets(data, target_list, target_dicts, |
- toplevel_dir, |
- frozenset(config.files)) |
+ warning = None |
+ 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) |
- 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) |
+ 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 _GetAffectedTargets. |
+ for target in all_targets.itervalues(): |
+ target.visited = False |
+ affected_targets = _GetAffectedTargets(matching_targets, |
+ matched_search_targets, roots, |
+ ignore_targets) |
+ matched_search_targets = [gyp.common.ParseQualifiedTarget(target.name)[1] |
+ for target in matched_search_targets] |
+ affected_targets = [gyp.common.ParseQualifiedTarget(target.name)[1] |
+ for target in affected_targets] |
else: |
- output_targets = [] |
+ matched_search_targets = [] |
+ affected_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, |
+ 'affected_targets': affected_targets} |
if warning: |
result_dict['warning'] = warning |
_WriteOutput(params, **result_dict) |