# 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.
from __future__
import print_function
import ast
import gyp.common
import gyp.simple_copy
import multiprocessing
import optparse
import os.path
import re
import shlex
import signal
import subprocess
import sys
import threading
import time
import traceback
from gyp.common
import GypError
from gyp.common
import OrderedSet
# A list of types that are treated as linkable.
linkable_types = [
'executable',
'shared_library',
'loadable_module',
'mac_kernel_extension',
'windows_driver',
]
# A list of sections that contain links to other targets.
dependency_sections = [
'dependencies',
'export_dependent_settings']
# base_path_sections is a list of sections defined by GYP that contain
# pathnames. The generators can provide more keys, the two lists are merged
# into path_sections, but you should call IsPathSection instead of using either
# list directly.
base_path_sections = [
'destination',
'files',
'include_dirs',
'inputs',
'libraries',
'outputs',
'sources',
]
path_sections = set()
# These per-process dictionaries are used to cache build file data when loading
# in parallel mode.
per_process_data = {}
per_process_aux_data = {}
try:
_str_types = (basestring,)
# There's no basestring in python3.
except NameError:
_str_types = (str,)
try:
_int_types = (int, long)
# There's no long in python3.
except NameError:
_int_types = (int,)
# Shortcuts as we use these combos a lot.
_str_int_types = _str_types + _int_types
_str_int_list_types = _str_int_types + (list,)
def IsPathSection(section):
# If section ends in one of the '=+?!' characters, it's applied to a section
# without the trailing characters. '/' is notably absent from this list,
# because there's no way for a regular expression to be treated as a path.
while section
and section[-1:]
in '=+?!':
section = section[:-1]
if section
in path_sections:
return True
# Sections mathing the regexp '_(dir|file|path)s?$' are also
# considered PathSections. Using manual string matching since that
# is much faster than the regexp and this can be called hundreds of
# thousands of times so micro performance matters.
if "_" in section:
tail = section[-6:]
if tail[-1] ==
's':
tail = tail[:-1]
if tail[-5:]
in (
'_file',
'_path'):
return True
return tail[-4:] ==
'_dir'
return False
# base_non_configuration_keys is a list of key names that belong in the target
# itself and should not be propagated into its configurations. It is merged
# with a list that can come from the generator to
# create non_configuration_keys.
base_non_configuration_keys = [
# Sections that must exist inside targets and not configurations.
'actions',
'all_dependent_settings',
'configurations',
'copies',
'default_configuration',
'dependencies',
'dependencies_original',
'direct_dependent_settings',
'libraries',
'postbuilds',
'product_dir',
'product_extension',
'product_name',
'product_prefix',
'rules',
'run_as',
'sources',
'standalone_static_library',
'suppress_wildcard',
'target_name',
'toolset',
'toolsets',
'type',
# Sections that can be found inside targets or configurations, but that
# should not be propagated from targets into their configurations.
'variables',
]
non_configuration_keys = []
# Keys that do not belong inside a configuration dictionary.
invalid_configuration_keys = [
'actions',
'all_dependent_settings',
'configurations',
'dependencies',
'direct_dependent_settings',
'libraries',
'link_settings',
'sources',
'standalone_static_library',
'target_name',
'type',
]
# Controls whether or not the generator supports multiple toolsets.
multiple_toolsets =
False
# Paths for converting filelist paths to output paths: {
# toplevel,
# qualified_output_dir,
# }
generator_filelist_paths =
None
def GetIncludedBuildFiles(build_file_path, aux_data, included=
None):
"""Return a list of all build files included into build_file_path.
The returned list will contain build_file_path
as well
as all other files
that it included, either directly
or indirectly. Note that the list may
contain files that were included into a conditional section that evaluated
to
false and was
not merged into build_file_path
's dict.
aux_data
is a dict containing a key
for each build file
or included build
file. Those keys provide access to dicts whose
"included" keys contain
lists of all other files included by the build file.
included should be left at its default
None value by external callers. It
is used
for recursion.
The returned list will
not contain any duplicate entries. Each build file
in the list will be relative to the current directory.
"""
if included ==
None:
included = []
if build_file_path
in included:
return included
included.append(build_file_path)
for included_build_file
in aux_data[build_file_path].get(
'included', []):
GetIncludedBuildFiles(included_build_file, aux_data, included)
return included
def CheckedEval(file_contents):
"""Return the eval of a gyp file.
The gyp file
is restricted to dictionaries
and lists only,
and
repeated keys are
not allowed.
Note that this
is slower than eval()
is.
"""
syntax_tree = ast.parse(file_contents)
assert isinstance(syntax_tree, ast.Module)
c1 = syntax_tree.body
assert len(c1) == 1
c2 = c1[0]
assert isinstance(c2, ast.Expr)
return CheckNode(c2.value, [])
def CheckNode(node, keypath):
if isinstance(node, ast.Dict):
dict = {}
for key, value
in zip(node.keys, node.values):
assert isinstance(key, ast.Str)
key = key.s
if key
in dict:
raise GypError(
"Key '" + key +
"' repeated at level " +
repr(len(keypath) + 1) +
" with key path '" +
'.'.join(keypath) +
"'")
kp = list(keypath)
# Make a copy of the list for descending this node.
kp.append(key)
dict[key] = CheckNode(value, kp)
return dict
elif isinstance(node, ast.List):
children = []
for index, child
in enumerate(node.elts):
kp = list(keypath)
# Copy list.
kp.append(repr(index))
children.append(CheckNode(child, kp))
return children
elif isinstance(node, ast.Str):
return node.s
else:
raise TypeError(
"Unknown AST node at key path '" +
'.'.join(keypath) +
"': " + repr(node))
def LoadOneBuildFile(build_file_path, data, aux_data, includes,
is_target, check):
if build_file_path
in data:
return data[build_file_path]
if os.path.exists(build_file_path):
build_file_contents = open(build_file_path,
'rb').read().decode(
'utf-8')
else:
raise GypError(
"%s not found (cwd: %s)" % (build_file_path, os.getcwd()))
build_file_data =
None
try:
if check:
build_file_data = CheckedEval(build_file_contents)
else:
build_file_data = eval(build_file_contents, {
'__builtins__':
None},
None)
except SyntaxError
as e:
e.filename = build_file_path
raise
except Exception
as e:
gyp.common.ExceptionAppend(e,
'while reading ' + build_file_path)
raise
if type(build_file_data)
is not dict:
raise GypError(
"%s does not evaluate to a dictionary." % build_file_path)
data[build_file_path] = build_file_data
aux_data[build_file_path] = {}
# Scan for includes and merge them in.
if (
'skip_includes' not in build_file_data
or
not build_file_data[
'skip_includes']):
try:
if is_target:
LoadBuildFileIncludesIntoDict(build_file_data, build_file_path, data,
aux_data, includes, check)
else:
LoadBuildFileIncludesIntoDict(build_file_data, build_file_path, data,
aux_data,
None, check)
except Exception
as e:
gyp.common.ExceptionAppend(e,
'while reading includes of ' + build_file_path)
raise
return build_file_data
def LoadBuildFileIncludesIntoDict(subdict, subdict_path, data, aux_data,
includes, check):
includes_list = []
if includes !=
None:
includes_list.extend(includes)
if 'includes' in subdict:
for include
in subdict[
'includes']:
# "include" is specified relative to subdict_path, so compute the real
# path to include by appending the provided "include" to the directory
# in which subdict_path resides.
relative_include = \
os.path.normpath(os.path.join(os.path.dirname(subdict_path), include))
includes_list.append(relative_include)
# Unhook the includes list, it's no longer needed.
del subdict[
'includes']
# Merge in the included files.
for include
in includes_list:
if not 'included' in aux_data[subdict_path]:
aux_data[subdict_path][
'included'] = []
aux_data[subdict_path][
'included'].append(include)
gyp.DebugOutput(gyp.DEBUG_INCLUDES,
"Loading Included File: '%s'", include)
MergeDicts(subdict,
LoadOneBuildFile(include, data, aux_data,
None,
False, check),
subdict_path, include)
# Recurse into subdictionaries.
for k, v
in subdict.items():
if type(v)
is dict:
LoadBuildFileIncludesIntoDict(v, subdict_path, data, aux_data,
None, check)
elif type(v)
is list:
LoadBuildFileIncludesIntoList(v, subdict_path, data, aux_data,
check)
# This recurses into lists so that it can look for dicts.
def LoadBuildFileIncludesIntoList(sublist, sublist_path, data, aux_data, check):
for item
in sublist:
if type(item)
is dict:
LoadBuildFileIncludesIntoDict(item, sublist_path, data, aux_data,
None, check)
elif type(item)
is list:
LoadBuildFileIncludesIntoList(item, sublist_path, data, aux_data, check)
# Processes toolsets in all the targets. This recurses into condition entries
# since they can contain toolsets as well.
def ProcessToolsetsInDict(data):
if 'targets' in data:
target_list = data[
'targets']
new_target_list = []
for target
in target_list:
# If this target already has an explicit 'toolset', and no 'toolsets'
# list, don't modify it further.
if 'toolset' in target
and 'toolsets' not in target:
new_target_list.append(target)
continue
if multiple_toolsets:
toolsets = target.get(
'toolsets', [
'target'])
else:
toolsets = [
'target']
# Make sure this 'toolsets' definition is only processed once.
if 'toolsets' in target:
del target[
'toolsets']
if len(toolsets) > 0:
# Optimization: only do copies if more than one toolset is specified.
for build
in toolsets[1:]:
new_target = gyp.simple_copy.deepcopy(target)
new_target[
'toolset'] = build
new_target_list.append(new_target)
target[
'toolset'] = toolsets[0]
new_target_list.append(target)
data[
'targets'] = new_target_list
if 'conditions' in data:
for condition
in data[
'conditions']:
if type(condition)
is list:
for condition_dict
in condition[1:]:
if type(condition_dict)
is dict:
ProcessToolsetsInDict(condition_dict)
# TODO(mark): I don't love this name. It just means that it's going to load
# a build file that contains targets and is expected to provide a targets dict
# that contains the targets...
def LoadTargetBuildFile(build_file_path, data, aux_data, variables, includes,
depth, check, load_dependencies):
# If depth is set, predefine the DEPTH variable to be a relative path from
# this build file's directory to the directory identified by depth.
if depth:
# TODO(dglazkov) The backslash/forward-slash replacement at the end is a
# temporary measure. This should really be addressed by keeping all paths
# in POSIX until actual project generation.
d = gyp.common.RelativePath(depth, os.path.dirname(build_file_path))
if d ==
'':
variables[
'DEPTH'] =
'.'
else:
variables[
'DEPTH'] = d.replace(
'\\',
'/')
# The 'target_build_files' key is only set when loading target build files in
# the non-parallel code path, where LoadTargetBuildFile is called
# recursively. In the parallel code path, we don't need to check whether the
# |build_file_path| has already been loaded, because the 'scheduled' set in
# ParallelState guarantees that we never load the same |build_file_path|
# twice.
if 'target_build_files' in data:
if build_file_path
in data[
'target_build_files']:
# Already loaded.
return False
data[
'target_build_files'].add(build_file_path)
gyp.DebugOutput(gyp.DEBUG_INCLUDES,
"Loading Target Build File '%s'", build_file_path)
build_file_data = LoadOneBuildFile(build_file_path, data, aux_data,
includes,
True, check)
# Store DEPTH for later use in generators.
build_file_data[
'_DEPTH'] = depth
# Set up the included_files key indicating which .gyp files contributed to
# this target dict.
if 'included_files' in build_file_data:
raise GypError(build_file_path +
' must not contain included_files key')
included = GetIncludedBuildFiles(build_file_path, aux_data)
build_file_data[
'included_files'] = []
for included_file
in included:
# included_file is relative to the current directory, but it needs to
# be made relative to build_file_path's directory.
included_relative = \
gyp.common.RelativePath(included_file,
os.path.dirname(build_file_path))
build_file_data[
'included_files'].append(included_relative)
# Do a first round of toolsets expansion so that conditions can be defined
# per toolset.
ProcessToolsetsInDict(build_file_data)
# Apply "pre"/"early" variable expansions and condition evaluations.
ProcessVariablesAndConditionsInDict(
build_file_data, PHASE_EARLY, variables, build_file_path)
# Since some toolsets might have been defined conditionally, perform
# a second round of toolsets expansion now.
ProcessToolsetsInDict(build_file_data)
# Look at each project's target_defaults dict, and merge settings into
# targets.
if 'target_defaults' in build_file_data:
if 'targets' not in build_file_data:
raise GypError(
"Unable to find targets in build file %s" %
build_file_path)
index = 0
while index < len(build_file_data[
'targets']):
# This procedure needs to give the impression that target_defaults is
# used as defaults, and the individual targets inherit from that.
# The individual targets need to be merged into the defaults. Make
# a deep copy of the defaults for each target, merge the target dict
# as found in the input file into that copy, and then hook up the
# copy with the target-specific data merged into it as the replacement
# target dict.
old_target_dict = build_file_data[
'targets'][index]
new_target_dict = gyp.simple_copy.deepcopy(
build_file_data[
'target_defaults'])
MergeDicts(new_target_dict, old_target_dict,
build_file_path, build_file_path)
build_file_data[
'targets'][index] = new_target_dict
index += 1
# No longer needed.
del build_file_data[
'target_defaults']
# Look for dependencies. This means that dependency resolution occurs
# after "pre" conditionals and variable expansion, but before "post" -
# in other words, you can't put a "dependencies" section inside a "post"
# conditional within a target.
dependencies = []
if 'targets' in build_file_data:
for target_dict
in build_file_data[
'targets']:
if 'dependencies' not in target_dict:
continue
for dependency
in target_dict[
'dependencies']:
dependencies.append(
gyp.common.ResolveTarget(build_file_path, dependency,
None)[0])
if load_dependencies:
for dependency
in dependencies:
try:
LoadTargetBuildFile(dependency, data, aux_data, variables,
includes, depth, check, load_dependencies)
except Exception
as e:
gyp.common.ExceptionAppend(
e,
'while loading dependencies of %s' % build_file_path)
raise
else:
return (build_file_path, dependencies)
def CallLoadTargetBuildFile(global_flags,
build_file_path, variables,
includes, depth, check,
generator_input_info):
"""Wrapper around LoadTargetBuildFile for parallel processing.
This wrapper
is used when LoadTargetBuildFile
is executed
in
a worker process.
"""
try:
signal.signal(signal.SIGINT, signal.SIG_IGN)
# Apply globals so that the worker process behaves the same.
for key, value
in global_flags.items():
globals()[key] = value
SetGeneratorGlobals(generator_input_info)
result = LoadTargetBuildFile(build_file_path, per_process_data,
per_process_aux_data, variables,
includes, depth, check,
False)
if not result:
return result
(build_file_path, dependencies) = result
# We can safely pop the build_file_data from per_process_data because it
# will never be referenced by this process again, so we don't need to keep
# it in the cache.
build_file_data = per_process_data.pop(build_file_path)
# This gets serialized and sent back to the main process via a pipe.
# It's handled in LoadTargetBuildFileCallback.
return (build_file_path,
build_file_data,
dependencies)
except GypError
as e:
sys.stderr.write(
"gyp: %s\n" % e)
return None
except Exception
as e:
print(
'Exception:', e, file=sys.stderr)
print(traceback.format_exc(), file=sys.stderr)
return None
class ParallelProcessingError(Exception):
pass
class ParallelState(object):
"""Class to keep track of state when processing input files in parallel.
If build files are loaded
in parallel, use this to keep track of
state during farming out
and processing parallel jobs. It
's stored
in a
global so that the callback function can have access to it.
"""
def __init__(self):
# The multiprocessing pool.
self.pool =
None
# The condition variable used to protect this object and notify
# the main loop when there might be more data to process.
self.condition =
None
# The "data" dict that was passed to LoadTargetBuildFileParallel
self.data =
None
# The number of parallel calls outstanding; decremented when a response
# was received.
self.pending = 0
# The set of all build files that have been scheduled, so we don't
# schedule the same one twice.
self.scheduled = set()
# A list of dependency build file paths that haven't been scheduled yet.
self.dependencies = []
# Flag to indicate if there was an error in a child process.
self.error =
False
def LoadTargetBuildFileCallback(self, result):
"""Handle the results of running LoadTargetBuildFile in another process.
"""
self.condition.acquire()
if not result:
self.error =
True
self.condition.notify()
self.condition.release()
return
(build_file_path0, build_file_data0, dependencies0) = result
self.data[build_file_path0] = build_file_data0
self.data[
'target_build_files'].add(build_file_path0)
for new_dependency
in dependencies0:
if new_dependency
not in self.scheduled:
self.scheduled.add(new_dependency)
self.dependencies.append(new_dependency)
self.pending -= 1
self.condition.notify()
self.condition.release()
def LoadTargetBuildFilesParallel(build_files, data, variables, includes, depth,
check, generator_input_info):
parallel_state = ParallelState()
parallel_state.condition = threading.Condition()
# Make copies of the build_files argument that we can modify while working.
parallel_state.dependencies = list(build_files)
parallel_state.scheduled = set(build_files)
parallel_state.pending = 0
parallel_state.data = data
try:
parallel_state.condition.acquire()
while parallel_state.dependencies
or parallel_state.pending:
if parallel_state.error:
break
if not parallel_state.dependencies:
parallel_state.condition.wait()
continue
dependency = parallel_state.dependencies.pop()
parallel_state.pending += 1
global_flags = {
'path_sections': globals()[
'path_sections'],
'non_configuration_keys': globals()[
'non_configuration_keys'],
'multiple_toolsets': globals()[
'multiple_toolsets']}
if not parallel_state.pool:
parallel_state.pool = multiprocessing.Pool(multiprocessing.cpu_count())
parallel_state.pool.apply_async(
CallLoadTargetBuildFile,
args = (global_flags, dependency,
variables, includes, depth, check, generator_input_info),
callback = parallel_state.LoadTargetBuildFileCallback)
except KeyboardInterrupt
as e:
parallel_state.pool.terminate()
raise e
parallel_state.condition.release()
parallel_state.pool.close()
parallel_state.pool.join()
parallel_state.pool =
None
if parallel_state.error:
sys.exit(1)
# Look for the bracket that matches the first bracket seen in a
# string, and return the start and end as a tuple. For example, if
# the input is something like "<(foo <(bar)) blah", then it would
# return (1, 13), indicating the entire string except for the leading
# "<" and trailing " blah".
LBRACKETS= set(
'{[(')
BRACKETS = {
'}':
'{',
']':
'[',
')':
'('}
def FindEnclosingBracketGroup(input_str):
stack = []
start = -1
for index, char
in enumerate(input_str):
if char
in LBRACKETS:
stack.append(char)
if start == -1:
start = index
elif char
in BRACKETS:
if not stack:
return (-1, -1)
if stack.pop() != BRACKETS[char]:
return (-1, -1)
if not stack:
return (start, index + 1)
return (-1, -1)
def IsStrCanonicalInt(string):
"""Returns True if |string| is in its canonical integer form.
The canonical form
is such that str(int(string)) == string.
"""
if isinstance(string, _str_types):
# This function is called a lot so for maximum performance, avoid
# involving regexps which would otherwise make the code much
# shorter. Regexps would need twice the time of this function.
if string:
if string ==
"0":
return True
if string[0] ==
"-":
string = string[1:]
if not string:
return False
if '1' <= string[0] <=
'9':
return string.isdigit()
return False
# This matches things like "<(asdf)", "<!(cmd)", "<!@(cmd)", "<|(list)",
# "<!interpreter(arguments)", "<([list])", and even "<([)" and "<(<())".
# In the last case, the inner "<()" is captured in match['content'].
early_variable_re = re.compile(
r
'(?P(?P<(?:(?:!?@?)|\|)?)'
r
'(?P[-a-zA-Z0-9_.]+)?'
r
'\((?P\s*\[?)'
r
'(?P.*?)(\]?)\))')
# This matches the same as early_variable_re, but with '>' instead of '<'.
late_variable_re = re.compile(
r
'(?P(?P>(?:(?:!?@?)|\|)?)'
r
'(?P[-a-zA-Z0-9_.]+)?'
r
'\((?P\s*\[?)'
r
'(?P.*?)(\]?)\))')
# This matches the same as early_variable_re, but with '^' instead of '<'.
latelate_variable_re = re.compile(
r
'(?P(?P[\^](?:(?:!?@?)|\|)?)'
r
'(?P[-a-zA-Z0-9_.]+)?'
r
'\((?P\s*\[?)'
r
'(?P.*?)(\]?)\))')
# Global cache of results from running commands so they don't have to be run
# more then once.
cached_command_results = {}
def FixupPlatformCommand(cmd):
if sys.platform ==
'win32':
if type(cmd)
is list:
cmd = [re.sub(
'^cat ',
'type ', cmd[0])] + cmd[1:]
else:
cmd = re.sub(
'^cat ',
'type ', cmd)
return cmd
PHASE_EARLY = 0
PHASE_LATE = 1
PHASE_LATELATE = 2
def ExpandVariables(input, phase, variables, build_file):
# Look for the pattern that gets expanded into variables
if phase == PHASE_EARLY:
variable_re = early_variable_re
expansion_symbol =
'<'
elif phase == PHASE_LATE:
variable_re = late_variable_re
expansion_symbol =
'>'
elif phase == PHASE_LATELATE:
variable_re = latelate_variable_re
expansion_symbol =
'^'
else:
assert False
input_str = str(input)
if IsStrCanonicalInt(input_str):
return int(input_str)
# Do a quick scan to determine if an expensive regex search is warranted.
if expansion_symbol
not in input_str:
return input_str
# Get the entire list of matches as a list of MatchObject instances.
# (using findall here would return strings instead of MatchObjects).
matches = list(variable_re.finditer(input_str))
if not matches:
return input_str
output = input_str
# Reverse the list of matches so that replacements are done right-to-left.
# That ensures that earlier replacements won't mess up the string in a
# way that causes later calls to find the earlier substituted text instead
# of what's intended for replacement.
matches.reverse()
for match_group
in matches:
match = match_group.groupdict()
gyp.DebugOutput(gyp.DEBUG_VARIABLES,
"Matches: %r", match)
# match['replace'] is the substring to look for, match['type']
# is the character code for the replacement type (< > <! >! <| >| <@
# >@ <!@ >!@), match['is_array'] contains a '[' for command
# arrays, and match['content'] is the name of the variable (< >)
# or command to run (<! >!). match['command_string'] is an optional
# command string. Currently, only 'pymod_do_main' is supported.
# run_command is true if a ! variant is used.
run_command =
'!' in match[
'type']
command_string = match[
'command_string']
# file_list is true if a | variant is used.
file_list =
'|' in match[
'type']
# Capture these now so we can adjust them later.
replace_start = match_group.start(
'replace')
replace_end = match_group.end(
'replace')
# Find the ending paren, and re-evaluate the contained string.
(c_start, c_end) = FindEnclosingBracketGroup(input_str[replace_start:])
# Adjust the replacement range to match the entire command
# found by FindEnclosingBracketGroup (since the variable_re
# probably doesn't match the entire command if it contained
# nested variables).
replace_end = replace_start + c_end
# Find the "real" replacement, matching the appropriate closing
# paren, and adjust the replacement start and end.
replacement = input_str[replace_start:replace_end]
# Figure out what the contents of the variable parens are.
contents_start = replace_start + c_start + 1
contents_end = replace_end - 1
contents = input_str[contents_start:contents_end]
# Do filter substitution now for <|().
# Admittedly, this is different than the evaluation order in other
# contexts. However, since filtration has no chance to run on <|(),
# this seems like the only obvious way to give them access to filters.
if file_list:
processed_variables = gyp.simple_copy.deepcopy(variables)
ProcessListFiltersInDict(contents, processed_variables)
# Recurse to expand variables in the contents
contents = ExpandVariables(contents, phase,
processed_variables, build_file)
else:
# Recurse to expand variables in the contents
contents = ExpandVariables(contents, phase, variables, build_file)
# Strip off leading/trailing whitespace so that variable matches are
# simpler below (and because they are rarely needed).
contents = contents.strip()
# expand_to_list is true if an @ variant is used. In that case,
# the expansion should result in a list. Note that the caller
# is to be expecting a list in return, and not all callers do
# because not all are working in list context. Also, for list
# expansions, there can be no other text besides the variable
# expansion in the input string.
expand_to_list =
'@' in match[
'type']
and input_str == replacement
if run_command
or file_list:
# Find the build file's directory, so commands can be run or file lists
# generated relative to it.
build_file_dir = os.path.dirname(build_file)
if build_file_dir ==
'' and not file_list:
# If build_file is just a leaf filename indicating a file in the
# current directory, build_file_dir might be an empty string. Set
# it to None to signal to subprocess.Popen that it should run the
# command in the current directory.
build_file_dir =
None
# Support <|(listfile.txt ...) which generates a file
# containing items from a gyp list, generated at gyp time.
# This works around actions/rules which have more inputs than will
# fit on the command line.
if file_list:
if type(contents)
is list:
contents_list = contents
else:
contents_list = contents.split(
' ')
replacement = contents_list[0]
if os.path.isabs(replacement):
raise GypError(
'| cannot handle absolute paths, got "%s"' % replacement)
if not generator_filelist_paths:
path = os.path.join(build_file_dir, replacement)
else:
if os.path.isabs(build_file_dir):
toplevel = generator_filelist_paths[
'toplevel']
rel_build_file_dir = gyp.common.RelativePath(build_file_dir, toplevel)
else:
rel_build_file_dir = build_file_dir
qualified_out_dir = generator_filelist_paths[
'qualified_out_dir']
path = os.path.join(qualified_out_dir, rel_build_file_dir, replacement)
gyp.common.EnsureDirExists(path)
replacement = gyp.common.RelativePath(path, build_file_dir)
f = gyp.common.WriteOnDiff(path)
for i
in contents_list[1:]:
f.write(
'%s\n' % i)
f.close()
elif run_command:
use_shell =
True
if match[
'is_array']:
contents = eval(contents)
use_shell =
False
# Check for a cached value to avoid executing commands, or generating
# file lists more than once. The cache key contains the command to be
# run as well as the directory to run it from, to account for commands
# that depend on their current directory.
# TODO(http://code.google.com/p/gyp/issues/detail?id=111): In theory,
# someone could author a set of GYP files where each time the command
# is invoked it produces different output by design. When the need
# arises, the syntax should be extended to support no caching off a
# command's output so it is run every time.
cache_key = (str(contents), build_file_dir)
cached_value = cached_command_results.get(cache_key,
None)
if cached_value
is None:
gyp.DebugOutput(gyp.DEBUG_VARIABLES,
"Executing command '%s' in directory '%s'",
contents, build_file_dir)
replacement =
''
if command_string ==
'pymod_do_main':
# <!pymod_do_main(modulename param eters) loads |modulename| as a
# python module and then calls that module's DoMain() function,
# passing ["param", "eters"] as a single list argument. For modules
# that don't load quickly, this can be faster than
# <!(python modulename param eters). Do this in |build_file_dir|.
oldwd = os.getcwd()
# Python doesn't like os.open('.'): no fchdir.
if build_file_dir:
# build_file_dir may be None (see above).
os.chdir(build_file_dir)
try:
parsed_contents = shlex.split(contents)
try:
py_module = __import__(parsed_contents[0])
except ImportError
as e:
raise GypError(
"Error importing pymod_do_main"
"module (%s): %s" % (parsed_contents[0], e))
replacement = str(py_module.DoMain(parsed_contents[1:])).rstrip()
finally:
os.chdir(oldwd)
assert replacement !=
None
elif command_string:
raise GypError(
"Unknown command string '%s' in '%s'." %
(command_string, contents))
else:
# Fix up command with platform specific workarounds.
contents = FixupPlatformCommand(contents)
try:
p = subprocess.Popen(contents, shell=use_shell,
stdout=subprocess.PIPE,
stderr=subprocess.PIPE,
stdin=subprocess.PIPE,
cwd=build_file_dir)
except Exception
as e:
raise GypError(
"%s while executing command '%s' in %s" %
(e, contents, build_file))
p_stdout, p_stderr = p.communicate(
'')
if p.wait() != 0
or p_stderr:
p_stderr_decoded = p_stderr.decode(
'utf-8')
sys.stderr.write(p_stderr_decoded)
# Simulate check_call behavior, since check_call only exists
# in python 2.5 and later.
raise GypError(
"Call to '%s' returned exit status %d while in %s." %
(contents, p.returncode, build_file))
replacement = p_stdout.decode(
'utf-8').rstrip()
cached_command_results[cache_key] = replacement
else:
gyp.DebugOutput(gyp.DEBUG_VARIABLES,
"Had cache value for command '%s' in directory '%s'",
contents,build_file_dir)
replacement = cached_value
else:
if not contents
in variables:
if contents[-1]
in [
'!',
'/']:
# In order to allow cross-compiles (nacl) to happen more naturally,
# we will allow references to >(sources/) etc. to resolve to
# and empty list if undefined. This allows actions to:
# 'action!': [
# '>@(_sources!)',
# ],
# 'action/': [
# '>@(_sources/)',
# ],
replacement = []
else:
raise GypError(
'Undefined variable ' + contents +
' in ' + build_file)
else:
replacement = variables[contents]
if type(replacement)
is list:
for item
in replacement:
if not contents[-1] ==
'/' and not isinstance(item, _str_int_types):
raise GypError(
'Variable ' + contents +
' must expand to a string or list of strings; ' +
'list contains a ' +
item.__class__.__name__)
# Run through the list and handle variable expansions in it. Since
# the list is guaranteed not to contain dicts, this won't do anything
# with conditions sections.
ProcessVariablesAndConditionsInList(replacement, phase, variables,
build_file)
elif not isinstance(replacement, _str_int_types):
raise GypError(
'Variable ' + str(contents) +
' must expand to a string or list of strings; ' +
'found a ' + replacement.__class__.__name__)
if expand_to_list:
# Expanding in list context. It's guaranteed that there's only one
# replacement to do in |input_str| and that it's this replacement. See
# above.
if type(replacement)
is list:
# If it's already a list, make a copy.
output = replacement[:]
else:
# Split it the same way sh would split arguments.
output = shlex.split(str(replacement))
else:
# Expanding in string context.
encoded_replacement =
''
if type(replacement)
is list:
# When expanding a list into string context, turn the list items
# into a string in a way that will work with a subprocess call.
#
# TODO(mark): This isn't completely correct. This should
# call a generator-provided function that observes the
# proper list-to-argument quoting rules on a specific
# platform instead of just calling the POSIX encoding
# routine.
encoded_replacement = gyp.common.EncodePOSIXShellList(replacement)
else:
encoded_replacement = replacement
output = output[:replace_start] + str(encoded_replacement) + \
output[replace_end:]
# Prepare for the next match iteration.
input_str = output
if output == input:
gyp.DebugOutput(gyp.DEBUG_VARIABLES,
"Found only identity matches on %r, avoiding infinite "
"recursion.",
output)
else:
# Look for more matches now that we've replaced some, to deal with
# expanding local variables (variables defined in the same
# variables block as this one).
gyp.DebugOutput(gyp.DEBUG_VARIABLES,
"Found output %r, recursing.", output)
if type(output)
is list:
if output
and type(output[0])
is list:
# Leave output alone if it's a list of lists.
# We don't want such lists to be stringified.
pass
else:
new_output = []
for item
in output:
new_output.append(
ExpandVariables(item, phase, variables, build_file))
output = new_output
else:
output = ExpandVariables(output, phase, variables, build_file)
# Convert all strings that are canonically-represented integers into integers.
if type(output)
is list:
for index, outstr
in enumerate(output):
if IsStrCanonicalInt(outstr):
output[index] = int(outstr)
elif IsStrCanonicalInt(output):
output = int(output)
return output
# The same condition is often evaluated over and over again so it
# makes sense to cache as much as possible between evaluations.
cached_conditions_asts = {}
def EvalCondition(condition, conditions_key, phase, variables, build_file):
"""Returns the dict that should be used or None if the result was
that nothing should be used.
"""
if type(condition)
is not list:
raise GypError(conditions_key +
' must be a list')
if len(condition) < 2:
# It's possible that condition[0] won't work in which case this
# attempt will raise its own IndexError. That's probably fine.
raise GypError(conditions_key +
' ' + condition[0] +
' must be at least length 2, not ' + str(len(condition)))
i = 0
result =
None
while i < len(condition):
cond_expr = condition[i]
true_dict = condition[i + 1]
if type(true_dict)
is not dict:
raise GypError(
'{} {} must be followed by a dictionary, not {}'.format(
conditions_key, cond_expr, type(true_dict)))
if len(condition) > i + 2
and type(condition[i + 2])
is dict:
false_dict = condition[i + 2]
i = i + 3
if i != len(condition):
raise GypError(
'{} {} has {} unexpected trailing items'.format(
conditions_key, cond_expr, len(condition) - i))
else:
false_dict =
None
i = i + 2
if result ==
None:
result = EvalSingleCondition(
cond_expr, true_dict, false_dict, phase, variables, build_file)
return result
def EvalSingleCondition(
cond_expr, true_dict, false_dict, phase, variables, build_file):
"""Returns true_dict if cond_expr evaluates to true, and false_dict
otherwise.
"""
# Do expansions on the condition itself. Since the conditon can naturally
# contain variable references without needing to resort to GYP expansion
# syntax, this is of dubious value for variables, but someone might want to
# use a command expansion directly inside a condition.
cond_expr_expanded = ExpandVariables(cond_expr, phase, variables,
build_file)
if not isinstance(cond_expr_expanded, _str_int_types):
raise ValueError(
'Variable expansion in this context permits str and int ' + \
'only, found ' + cond_expr_expanded.__class__.__name__)
try:
if cond_expr_expanded
in cached_conditions_asts:
ast_code = cached_conditions_asts[cond_expr_expanded]
else:
ast_code = compile(cond_expr_expanded,
'',
'eval')
cached_conditions_asts[cond_expr_expanded] = ast_code
if eval(ast_code, {
'__builtins__':
None}, variables):
return true_dict
return false_dict
except SyntaxError
as e:
syntax_error = SyntaxError(
'%s while evaluating condition \'%s\
' in %s '
'at character %d.' %
(str(e.args[0]), e.text, build_file, e.offset),
e.filename, e.lineno, e.offset, e.text)
raise syntax_error
except NameError
as e:
gyp.common.ExceptionAppend(e,
'while evaluating condition \'%s\
' in %s' %
(cond_expr_expanded, build_file))
raise GypError(e)
def ProcessConditionsInDict(the_dict, phase, variables, build_file):
# Process a 'conditions' or 'target_conditions' section in the_dict,
# depending on phase.
# early -> conditions
# late -> target_conditions
# latelate -> no conditions
#
# Each item in a conditions list consists of cond_expr, a string expression
# evaluated as the condition, and true_dict, a dict that will be merged into
# the_dict if cond_expr evaluates to true. Optionally, a third item,
# false_dict, may be present. false_dict is merged into the_dict if
# cond_expr evaluates to false.
#
# Any dict merged into the_dict will be recursively processed for nested
# conditionals and other expansions, also according to phase, immediately
# prior to being merged.
if phase == PHASE_EARLY:
conditions_key =
'conditions'
elif phase == PHASE_LATE:
conditions_key =
'target_conditions'
elif phase == PHASE_LATELATE:
return
else:
assert False
if not conditions_key
in the_dict:
return
conditions_list = the_dict[conditions_key]
# Unhook the conditions list, it's no longer needed.
del the_dict[conditions_key]
for condition
in conditions_list:
merge_dict = EvalCondition(condition, conditions_key, phase, variables,
build_file)
if merge_dict !=
None:
# Expand variables and nested conditinals in the merge_dict before
# merging it.
ProcessVariablesAndConditionsInDict(merge_dict, phase,
variables, build_file)
MergeDicts(the_dict, merge_dict, build_file, build_file)
def LoadAutomaticVariablesFromDict(variables, the_dict):
# Any keys with plain string values in the_dict become automatic variables.
# The variable name is the key name with a "_" character prepended.
for key, value
in the_dict.items():
if isinstance(value, _str_int_list_types):
variables[
'_' + key] = value
def LoadVariablesFromVariablesDict(variables, the_dict, the_dict_key):
# Any keys in the_dict's "variables" dict, if it has one, becomes a
# variable. The variable name is the key name in the "variables" dict.
# Variables that end with the % character are set only if they are unset in
# the variables dict. the_dict_key is the name of the key that accesses
# the_dict in the_dict's parent dict. If the_dict's parent is not a dict
# (it could be a list or it could be parentless because it is a root dict),
# the_dict_key will be None.
for key, value
in the_dict.get(
'variables', {}).items():
if not isinstance(value, _str_int_list_types):
continue
if key.endswith(
'%'):
variable_name = key[:-1]
if variable_name
in variables:
# If the variable is already set, don't set it.
continue
if the_dict_key ==
'variables' and variable_name
in the_dict:
# If the variable is set without a % in the_dict, and the_dict is a
# variables dict (making |variables| a varaibles sub-dict of a
# variables dict), use the_dict's definition.
value = the_dict[variable_name]
else:
variable_name = key
variables[variable_name] = value
def ProcessVariablesAndConditionsInDict(the_dict, phase, variables_in,
build_file, the_dict_key=
None):
"""Handle all variable and command expansion and conditional evaluation.
This function
is the public entry point
for all variable expansions
and
conditional evaluations. The variables_in dictionary will
not be modified
by this function.
"""
# Make a copy of the variables_in dict that can be modified during the
# loading of automatics and the loading of the variables dict.
variables = variables_in.copy()
LoadAutomaticVariablesFromDict(variables, the_dict)
if 'variables' in the_dict:
# Make sure all the local variables are added to the variables
# list before we process them so that you can reference one
# variable from another. They will be fully expanded by recursion
# in ExpandVariables.
for key, value
in the_dict[
'variables'].items():
variables[key] = value
# Handle the associated variables dict first, so that any variable
# references within can be resolved prior to using them as variables.
# Pass a copy of the variables dict to avoid having it be tainted.
# Otherwise, it would have extra automatics added for everything that
# should just be an ordinary variable in this scope.
ProcessVariablesAndConditionsInDict(the_dict[
'variables'], phase,
variables, build_file,
'variables')
LoadVariablesFromVariablesDict(variables, the_dict, the_dict_key)
for key, value
in the_dict.items():
# Skip "variables", which was already processed if present.
if key !=
'variables' and isinstance(value, _str_types):
expanded = ExpandVariables(value, phase, variables, build_file)
if not isinstance(expanded, _str_int_types):
raise ValueError(
'Variable expansion in this context permits str and int ' + \
'only, found ' + expanded.__class__.__name__ +
' for ' + key)
the_dict[key] = expanded
# Variable expansion may have resulted in changes to automatics. Reload.
# TODO(mark): Optimization: only reload if no changes were made.
variables = variables_in.copy()
LoadAutomaticVariablesFromDict(variables, the_dict)
LoadVariablesFromVariablesDict(variables, the_dict, the_dict_key)
# Process conditions in this dict. This is done after variable expansion
# so that conditions may take advantage of expanded variables. For example,
# if the_dict contains:
# {'type': '<(library_type)',
# 'conditions': [['_type=="static_library"', { ... }]]},
# _type, as used in the condition, will only be set to the value of
# library_type if variable expansion is performed before condition
# processing. However, condition processing should occur prior to recursion
# so that variables (both automatic and "variables" dict type) may be
# adjusted by conditions sections, merged into the_dict, and have the
# intended impact on contained dicts.
#
# This arrangement means that a "conditions" section containing a "variables"
# section will only have those variables effective in subdicts, not in
# the_dict. The workaround is to put a "conditions" section within a
# "variables" section. For example:
# {'conditions': [['os=="mac"', {'variables': {'define': 'IS_MAC'}}]],
# 'defines': ['<(define)'],
# 'my_subdict': {'defines': ['<(define)']}},
# will not result in "IS_MAC" being appended to the "defines" list in the
# current scope but would result in it being appended to the "defines" list
# within "my_subdict". By comparison:
# {'variables': {'conditions': [['os=="mac"', {'define': 'IS_MAC'}]]},
# 'defines': ['<(define)'],
# 'my_subdict': {'defines': ['<(define)']}},
# will append "IS_MAC" to both "defines" lists.
# Evaluate conditions sections, allowing variable expansions within them
# as well as nested conditionals. This will process a 'conditions' or
# 'target_conditions' section, perform appropriate merging and recursive
# conditional and variable processing, and then remove the conditions section
# from the_dict if it is present.
ProcessConditionsInDict(the_dict, phase, variables, build_file)
# Conditional processing may have resulted in changes to automatics or the
# variables dict. Reload.
variables = variables_in.copy()
LoadAutomaticVariablesFromDict(variables, the_dict)
LoadVariablesFromVariablesDict(variables, the_dict, the_dict_key)
# Recurse into child dicts, or process child lists which may result in
# further recursion into descendant dicts.
for key, value
in the_dict.items():
# Skip "variables" and string values, which were already processed if
# present.
if key ==
'variables' or isinstance(value, _str_types):
continue
if type(value)
is dict:
# Pass a copy of the variables dict so that subdicts can't influence
# parents.
ProcessVariablesAndConditionsInDict(value, phase, variables,
build_file, key)
elif type(value)
is list:
# The list itself can't influence the variables dict, and
# ProcessVariablesAndConditionsInList will make copies of the variables
# dict if it needs to pass it to something that can influence it. No
# copy is necessary here.
ProcessVariablesAndConditionsInList(value, phase, variables,
build_file)
elif not isinstance(value, _int_types):
raise TypeError(
'Unknown type ' + value.__class__.__name__ + \
' for ' + key)
def ProcessVariablesAndConditionsInList(the_list, phase, variables,
build_file):
# Iterate using an index so that new values can be assigned into the_list.
index = 0
while index < len(the_list):
item = the_list[index]
if type(item)
is dict:
# Make a copy of the variables dict so that it won't influence anything
# outside of its own scope.
ProcessVariablesAndConditionsInDict(item, phase, variables, build_file)
elif type(item)
is list:
ProcessVariablesAndConditionsInList(item, phase, variables, build_file)
elif isinstance(item, _str_types):
expanded = ExpandVariables(item, phase, variables, build_file)
if isinstance(expanded, _str_int_types):
the_list[index] = expanded
elif type(expanded)
is list:
the_list[index:index+1] = expanded
index += len(expanded)
# index now identifies the next item to examine. Continue right now
# without falling into the index increment below.
continue
else:
raise ValueError(
'Variable expansion in this context permits strings and ' + \
'lists only, found ' + expanded.__class__.__name__ +
' at ' + \
index)
elif not isinstance(item, _int_types):
raise TypeError(
'Unknown type ' + item.__class__.__name__ + \
' at index ' + index)
index = index + 1
def BuildTargetsDict(data):
"""Builds a dict mapping fully-qualified target names to their target dicts.
|data|
is a dict mapping loaded build files by pathname relative to the
current directory. Values
in |data| are build file contents.
For each
|data| value
with a
"targets" key, the value of the
"targets" key
is taken
as a list containing target dicts. Each target
's fully-qualified name is
constructed
from the pathname of the build file (|data| key)
and its
"target_name" property. These fully-qualified names are used
as the keys
in the returned dict. These keys provide access to the target dicts,
the dicts
in the
"targets" lists.
"""
targets = {}
for build_file
in data[
'target_build_files']:
for target
in data[build_file].get(
'targets', []):
target_name = gyp.common.QualifiedTarget(build_file,
target[
'target_name'],
target[
'toolset'])
if target_name
in targets:
raise GypError(
'Duplicate target definitions for ' + target_name)
targets[target_name] = target
return targets
def QualifyDependencies(targets):
"""Make dependency links fully-qualified relative to the current directory.
|targets|
is a dict mapping fully-qualified target names to their target
dicts.
For each target
in this dict, keys known to contain dependency
links are examined,
and any dependencies referenced will be rewritten
so that they are fully-qualified
and relative to the current directory.
All rewritten dependencies are suitable
for use
as keys to |targets|
or a
similar dict.
"""
all_dependency_sections = [dep + op
for dep
in dependency_sections
for op
in (
'',
'!',
'/')]
for target, target_dict
in targets.items():
target_build_file = gyp.common.BuildFile(target)
toolset = target_dict[
'toolset']
for dependency_key
in all_dependency_sections:
dependencies = target_dict.get(dependency_key, [])
for index, dep
in enumerate(dependencies):
dep_file, dep_target, dep_toolset = gyp.common.ResolveTarget(
target_build_file, dep, toolset)
if not multiple_toolsets:
# Ignore toolset specification in the dependency if it is specified.
dep_toolset = toolset
dependency = gyp.common.QualifiedTarget(dep_file,
dep_target,
dep_toolset)
dependencies[index] = dependency
# Make sure anything appearing in a list other than "dependencies" also
# appears in the "dependencies" list.
if dependency_key !=
'dependencies' and \
dependency
not in target_dict[
'dependencies']:
raise GypError(
'Found ' + dependency +
' in ' + dependency_key +
' of ' + target +
', but not in dependencies')
def ExpandWildcardDependencies(targets, data):
"""Expands dependencies specified as build_file:*.
For each target
in |targets|, examines sections containing links to other
targets.
If any such section contains a link of the form build_file:*, it
is taken
as a wildcard link,
and is expanded to list each target
in
build_file. The |data| dict provides access to build file dicts.
Any target that does
not wish to be included by wildcard can provide an
optional
"suppress_wildcard" key
in its target dict. When present
and
true, a wildcard dependency link will
not include such targets.
All dependency names, including the keys to |targets|
and the values
in each
dependency list, must be qualified when this function
is called.
"""
for target, target_dict
in targets.items():
toolset = target_dict[
'toolset']
target_build_file = gyp.common.BuildFile(target)
for dependency_key
in dependency_sections:
dependencies = target_dict.get(dependency_key, [])
# Loop this way instead of "for dependency in" or "for index in xrange"
# because the dependencies list will be modified within the loop body.
index = 0
while index < len(dependencies):
(dependency_build_file, dependency_target, dependency_toolset) = \
gyp.common.ParseQualifiedTarget(dependencies[index])
if dependency_target !=
'*' and dependency_toolset !=
'*':
# Not a wildcard. Keep it moving.
index = index + 1
continue
if dependency_build_file == target_build_file:
# It's an error for a target to depend on all other targets in
# the same file, because a target cannot depend on itself.
raise GypError(
'Found wildcard in ' + dependency_key +
' of ' +
target +
' referring to same build file')
# Take the wildcard out and adjust the index so that the next
# dependency in the list will be processed the next time through the
# loop.
del dependencies[index]
index = index - 1
# Loop through the targets in the other build file, adding them to
# this target's list of dependencies in place of the removed
# wildcard.
dependency_target_dicts = data[dependency_build_file][
'targets']
for dependency_target_dict
in dependency_target_dicts:
if int(dependency_target_dict.get(
'suppress_wildcard',
False)):
continue
dependency_target_name = dependency_target_dict[
'target_name']
if (dependency_target !=
'*' and
dependency_target != dependency_target_name):
continue
dependency_target_toolset = dependency_target_dict[
'toolset']
if (dependency_toolset !=
'*' and
dependency_toolset != dependency_target_toolset):
continue
dependency = gyp.common.QualifiedTarget(dependency_build_file,
dependency_target_name,
dependency_target_toolset)
index = index + 1
dependencies.insert(index, dependency)
index = index + 1
def Unify(l):
"""Removes duplicate elements from l, keeping the first element."""
seen = {}
return [seen.setdefault(e, e)
for e
in l
if e
not in seen]
def RemoveDuplicateDependencies(targets):
"""Makes sure every dependency appears only once in all targets's dependency
lists.
"""
for target_name, target_dict
in targets.items():
for dependency_key
in dependency_sections:
dependencies = target_dict.get(dependency_key, [])
if dependencies:
target_dict[dependency_key] = Unify(dependencies)
def Filter(l, item):
"""Removes item from l."""
res = {}
return [res.setdefault(e, e)
for e
in l
if e != item]
def RemoveSelfDependencies(targets):
"""Remove self dependencies from targets that have the prune_self_dependency
variable set.
"""
for target_name, target_dict
in targets.items():
for dependency_key
in dependency_sections:
dependencies = target_dict.get(dependency_key, [])
if dependencies:
for t
in dependencies:
if t == target_name:
if targets[t].get(
'variables', {}).get(
'prune_self_dependency', 0):
target_dict[dependency_key] = Filter(dependencies, target_name)
def RemoveLinkDependenciesFromNoneTargets(targets):
"""Remove dependencies having the 'link_dependency' attribute from the 'none'
targets.
"""
for target_name, target_dict
in targets.items():
for dependency_key
in dependency_sections:
dependencies = target_dict.get(dependency_key, [])
if dependencies:
for t
in dependencies:
if target_dict.get(
'type',
None) ==
'none':
if targets[t].get(
'variables', {}).get(
'link_dependency', 0):
target_dict[dependency_key] = \
Filter(target_dict[dependency_key], t)
class DependencyGraphNode(object):
"""
Attributes:
ref: A reference to an object that this DependencyGraphNode represents.
dependencies: List of DependencyGraphNodes on which this one depends.
dependents: List of DependencyGraphNodes that depend on this one.
"""
class CircularException(GypError):
pass
def __init__(self, ref):
self.ref = ref
self.dependencies = []
self.dependents = []
def __repr__(self):
return '' % self.ref
def FlattenToList(self):
# flat_list is the sorted list of dependencies - actually, the list items
# are the "ref" attributes of DependencyGraphNodes. Every target will
# appear in flat_list after all of its dependencies, and before all of its
# dependents.
flat_list = OrderedSet()
def ExtractNodeRef(node):
"""Extracts the object that the node represents from the given node."""
return node.ref
# in_degree_zeros is the list of DependencyGraphNodes that have no
# dependencies not in flat_list. Initially, it is a copy of the children
# of this node, because when the graph was built, nodes with no
# dependencies were made implicit dependents of the root node.
in_degree_zeros = sorted(self.dependents[:], key=ExtractNodeRef)
while in_degree_zeros:
# Nodes in in_degree_zeros have no dependencies not in flat_list, so they
# can be appended to flat_list. Take these nodes out of in_degree_zeros
# as work progresses, so that the next node to process from the list can
# always be accessed at a consistent position.
node = in_degree_zeros.pop()
flat_list.add(node.ref)
# Look at dependents of the node just added to flat_list. Some of them
# may now belong in in_degree_zeros.
for node_dependent
in sorted(node.dependents, key=ExtractNodeRef):
is_in_degree_zero =
True
# TODO: We want to check through the
# node_dependent.dependencies list but if it's long and we
# always start at the beginning, then we get O(n^2) behaviour.
for node_dependent_dependency
in (sorted(node_dependent.dependencies,
key=ExtractNodeRef)):
if not node_dependent_dependency.ref
in flat_list:
# The dependent one or more dependencies not in flat_list. There
# will be more chances to add it to flat_list when examining
# it again as a dependent of those other dependencies, provided
# that there are no cycles.
is_in_degree_zero =
False
break
if is_in_degree_zero:
# All of the dependent's dependencies are already in flat_list. Add
# it to in_degree_zeros where it will be processed in a future
# iteration of the outer loop.
in_degree_zeros += [node_dependent]
return list(flat_list)
def FindCycles(self):
"""
Returns a list of cycles
in the graph, where each cycle
is its own list.
"""
results = []
visited = set()
def Visit(node, path):
for child
in node.dependents:
if child
in path:
results.append([child] + path[:path.index(child) + 1])
elif not child
in visited:
visited.add(child)
Visit(child, [child] + path)
visited.add(self)
Visit(self, [self])
return results
def DirectDependencies(self, dependencies=
None):
"""Returns a list of just direct dependencies."""
if dependencies ==
None:
dependencies = []
for dependency
in self.dependencies:
# Check for None, corresponding to the root node.
if dependency.ref !=
None and dependency.ref
not in dependencies:
dependencies.append(dependency.ref)
return dependencies
def _AddImportedDependencies(self, targets, dependencies=
None):
"""Given a list of direct dependencies, adds indirect dependencies that
other dependencies have declared to export their settings.
This method does
not operate on self. Rather, it operates on the list
of dependencies
in the |dependencies| argument.
For each dependency
in
that list,
if any declares that it exports the settings of one of its
own dependencies, those dependencies whose settings are
"passed through"
are added to the list.
As new items are added to the list, they too will
be processed, so it
is possible to
import settings through multiple levels
of dependencies.
This method
is not terribly useful on its own, it depends on being
"primed" with a list of direct dependencies such
as one provided by
DirectDependencies. DirectAndImportedDependencies
is intended to be the
public entry point.
"""
if dependencies ==
None:
dependencies = []
index = 0
while index < len(dependencies):
dependency = dependencies[index]
dependency_dict = targets[dependency]
# Add any dependencies whose settings should be imported to the list
# if not already present. Newly-added items will be checked for
# their own imports when the list iteration reaches them.
# Rather than simply appending new items, insert them after the
# dependency that exported them. This is done to more closely match
# the depth-first method used by DeepDependencies.
add_index = 1
for imported_dependency
in \
dependency_dict.get(
'export_dependent_settings', []):
if imported_dependency
not in dependencies:
dependencies.insert(index + add_index, imported_dependency)
add_index = add_index + 1
index = index + 1
return dependencies
def DirectAndImportedDependencies(self, targets, dependencies=
None):
"""Returns a list of a target's direct dependencies and all indirect
dependencies that a dependency has advertised settings should be exported
through the dependency
for.
"""
dependencies = self.DirectDependencies(dependencies)
return self._AddImportedDependencies(targets, dependencies)
def DeepDependencies(self, dependencies=
None):
--> --------------------
--> maximum size reached
--> --------------------
