frameworkIncludePaths;
private final PathFragment outputPathFragment;
private final Root absoluteRoot;
/**
* Scanner-scoped cache of inclusions with their resolved files and include path entries. This
* cache is specific to a given pair of search paths, and is thus scanner-local.
*
* Each inclusion (name+type+context) is associated with its resolved file here, thus saving
* redundant path searches. The second entry of the pair is the include path entry on which the
* file was found.
*/
private final InclusionCache inclusionCache;
private final PathExistenceCache pathCache;
private final ExecutorService includePool;
// We are using this Random just for shuffling, so keep the order deterministic by hardcoding
// the seed.
private static final Random CONSTANT_SEED_RANDOM = new Random(88);
/**
* Constructs a new IncludeScanner
*
* @param cache externally scoped cache of file-path to inclusion-set mappings
* @param pathCache include path existence cache
* @param quoteIncludePaths the list of quote search path dirs (-iquote)
* @param includePaths the list of all other non-framework search path dirs (-I and -isystem)
* @param frameworkIncludePaths the list of framework other search path dirs (-F)
*/
LegacyIncludeScanner(
IncludeParser parser,
ExecutorService includePool,
ConcurrentMap>> cache,
PathExistenceCache pathCache,
List quoteIncludePaths,
List includePaths,
List frameworkIncludePaths,
Path outputPath,
Path execRoot,
ArtifactFactory artifactFactory,
Supplier spawnIncludeScannerSupplier) {
this.parser = parser;
this.includePool = includePool;
this.fileParseCache = cache;
this.pathCache = pathCache;
this.artifactFactory = Preconditions.checkNotNull(artifactFactory);
this.spawnIncludeScannerSupplier = spawnIncludeScannerSupplier;
this.quoteIncludePaths =
ImmutableList.builder()
.addAll(quoteIncludePaths)
.addAll(includePaths)
.build();
this.quoteIncludePathsFrameworkIndex = quoteIncludePaths.size();
this.includePaths = ImmutableList.copyOf(includePaths);
this.frameworkIncludePaths = ImmutableList.copyOf(frameworkIncludePaths);
this.inclusionCache = new InclusionCache();
this.execRoot = execRoot;
this.outputPathFragment = outputPath.relativeTo(execRoot);
this.absoluteRoot = Root.absoluteRoot(execRoot.getFileSystem());
}
/**
* Locates an included file relative to the including file. The result is not cacheable.
*
* @param inclusion the inclusion to locate
* @param includer the including file
* @return the resolved Path, or null if no file could be found
*/
@Nullable
private Artifact locateRelative(
Inclusion inclusion,
IncludeScanningHeaderData headerData,
Artifact includer,
PathFragment parent) {
if (inclusion.kind != Kind.QUOTE) {
return null;
}
PathFragment name = inclusion.pathFragment;
// The most effective way to see that something is not a relative inclusion is to see whether
// the include statement starts with a directory (has a '/') and whether that directory exists.
// We only do this for source files as we never match generated files against the file system.
if (includer.isSourceArtifact() && !name.containsUplevelReferences()) {
String firstSegment = name.getSegment(0);
// Specifically avoiding a call to segmentCount() here as that would scan the entire path.
if (firstSegment.length() < name.getPathString().length()
&& !pathCache.directoryExists(parent.getRelative(firstSegment))) {
return null;
}
}
PathFragment execPath = parent.getRelative(name);
if (!isFile(execPath, name, includer.isSourceArtifact(), headerData)) {
return null;
}
PathFragment parentDirectory = includer.getRootRelativePath().getParentDirectory();
PathFragment rootRelativePath = parentDirectory.getRelative(name);
if (rootRelativePath.containsUplevelReferences()) {
// An include cannot break out of a (package path) root via a relative inclusion. It should
// also not break out of the root and then come back into it -- who knows what hardcoded
// directory names there are in it.
return null;
}
Artifact header = headerData.getHeaderArtifact(execPath);
if (header != null) {
return header;
}
ArtifactRoot root = includer.getRoot();
Artifact sourceArtifact =
artifactFactory.resolveSourceArtifactWithAncestor(name, parent, root, RepositoryName.MAIN);
if (sourceArtifact == null) {
// If the name had up-level references, this path may not be under any package. Otherwise,
// we must have gotten an artifact, since it should be under the same package as the
// including artifact.
Preconditions.checkState(
name.containsUplevelReferences(), "%s %s %s %s", name, parent, rootRelativePath, root);
}
return sourceArtifact;
}
/** Returns whether the given path exists in the filesystem. */
private boolean isFile(
PathFragment execPath,
PathFragment includeAsWritten,
boolean isSource,
IncludeScanningHeaderData headerData) {
if (isOutputFile(execPath)) {
return headerData.isDeclaredHeader(execPath);
}
// TODO(djasper): This code path cannot be hit with isSource being false. Verify and add
// Preconditions check.
if (isSource && !execPath.isAbsolute() && execPath.endsWith(includeAsWritten)) {
// Verify that the directory of execPath exists as an optimization. Most includes are relative
// to the workspace and we'd like to avoid stat'ing every such include relative to every
// include path. If testing whether "a/b/c.h" is a file beneath the include path "e/f/",
// verify that "e/f/a" and "e/f/a/b" are valid directories (and cache the result).
int execPathSegments = execPath.segmentCount();
int nameSegments = includeAsWritten.segmentCount();
for (int i = execPathSegments - nameSegments + 1; i < execPathSegments; i++) {
if (!pathCache.directoryExists(execPath.subFragment(0, i))) {
return false;
}
}
}
// Shortcut: If this is a declared header, it's bound to exist.
if (headerData.isDeclaredHeader(execPath)) {
return true;
}
return pathCache.fileExists(execPath, isSource);
}
@Override
public final void processAsync(
Artifact mainSource,
Collection sources,
IncludeScanningHeaderData includeScanningHeaderData,
List cmdlineIncludes,
Set includes,
ActionExecutionMetadata actionExecutionMetadata,
ActionExecutionContext actionExecutionContext,
Artifact grepIncludes)
throws IOException, NoSuchPackageException, ExecException, InterruptedException {
SkyFunction.Environment env = actionExecutionContext.getEnvironmentForDiscoveringInputs();
ImmutableSet pathHints;
if (parser.getHints() == null) {
pathHints = ImmutableSet.of();
} else {
pathHints = parser.getHints().getPathLevelHintedInclusions(quoteIncludePaths, env);
if (env.valuesMissing()) {
return;
}
Preconditions.checkNotNull(pathHints, "Null path hints for %s", quoteIncludePaths);
}
IncludeVisitor visitor =
new IncludeVisitor(
actionExecutionMetadata,
actionExecutionContext,
grepIncludes,
includeScanningHeaderData);
try {
visitor.processInternal(mainSource, sources, cmdlineIncludes, includes, pathHints);
} catch (MissingDepExecException e) {
// This happens when a skyframe restart is necessary. Callers are responsible for checking
// env.valuesMissing() as per this method's contract, so we can just ignore the exception.
if (!env.valuesMissing()) {
throw new IllegalStateException("Missing dep without skyframe request", e);
}
}
}
private static void checkForInterrupt(String operation, Object source)
throws InterruptedException {
// We require passing in the operation and the source Path / Artifact to avoid intermediate
// String operations. The include scanner is performance critical and this showed up in a
// profiler.
if (Thread.currentThread().isInterrupted()) {
throw new InterruptedException(
"Include scanning interrupted while " + operation + " " + source);
}
}
private boolean isIllegalOutputFile(
PathFragment includeFile, IncludeScanningHeaderData headerData) {
return isOutputFile(includeFile) && !headerData.isDeclaredHeader(includeFile);
}
private boolean isOutputFile(PathFragment path) {
return path.startsWith(outputPathFragment);
}
/**
* Implements a potentially parallel traversal over source files using a thread pool shared across
* different IncludeScanner instances.
*/
private class IncludeVisitor extends AbstractQueueVisitor {
private final ActionExecutionMetadata actionExecutionMetadata;
private final ActionExecutionContext actionExecutionContext;
private final Artifact grepIncludes;
private final IncludeScanningHeaderData headerData;
/** The set of all processed inclusions, to avoid processing duplicate inclusions. */
private final Set visitedInclusions = Sets.newConcurrentHashSet();
IncludeVisitor(
ActionExecutionMetadata actionExecutionMetadata,
ActionExecutionContext actionExecutionContext,
Artifact grepIncludes,
IncludeScanningHeaderData headerData) {
super(
includePool,
ExecutorOwnership.SHARED,
ExceptionHandlingMode.FAIL_FAST,
ErrorClassifier.DEFAULT);
this.actionExecutionMetadata = actionExecutionMetadata;
this.actionExecutionContext = actionExecutionContext;
this.grepIncludes = grepIncludes;
this.headerData = headerData;
}
void processInternal(
Artifact mainSource,
Collection sources,
List cmdlineIncludes,
Set includes,
ImmutableSet pathHints)
throws InterruptedException, IOException, ExecException {
try {
// Process cmd line includes, if specified.
if (mainSource != null && !cmdlineIncludes.isEmpty()) {
processCmdlineIncludes(mainSource, cmdlineIncludes, includes);
sync();
}
processBulkAsync(sources, includes);
sync();
// Process include hints
// TODO(ulfjack): Make this code go away. Use the new hinted inclusions instead.
Hints hints = parser.getHints();
if (hints != null) {
// Follow "path" hints.
processBulkAsync(pathHints, includes);
// Follow "file" hints for the primary sources.
for (Artifact source : sources) {
processFileLevelHintsAsync(hints, source, includes);
}
sync();
// Follow "file" hints for all included headers, transitively.
Set frontier = includes;
while (!frontier.isEmpty()) {
Set adjacent = Sets.newConcurrentHashSet();
for (Artifact include : frontier) {
processFileLevelHintsAsync(hints, include, adjacent);
}
sync();
// Keep novel nodes as the next frontier.
for (Iterator iter = adjacent.iterator(); iter.hasNext(); ) {
if (!includes.add(iter.next())) {
iter.remove();
}
}
frontier = adjacent;
}
}
} catch (IOException | InterruptedException | ExecException e) {
// Careful: Do not leak visitation threads if we have an exception in the initial thread.
sync();
throw e;
}
}
/** Block for the completion of all outstanding visitations. */
private void sync() throws IOException, ExecException, InterruptedException {
try {
super.awaitQuiescence(true);
} catch (InterruptedException e) {
throw new InterruptedException("Interrupted during include visitation");
} catch (IORuntimeException e) {
throw e.getCauseIOException();
} catch (ExecRuntimeException e) {
throw e.getRealCause();
} catch (InterruptedRuntimeException e) {
throw e.getRealCause();
}
}
/**
* Processes a given file for includes and populates the provided set with the visited includes.
*
* @param source the file to process
* @param contextPathPos the position on the include path where the containing file was found,
* or -1 for top-level inclusions
* @param contextKind the kind how the containing file was included, or null for top-level
* inclusions
* @param visited the set to receive the files that are transitively included by {@code source}
*/
private void process(
final Artifact source, int contextPathPos, Kind contextKind, Set visited)
throws IOException, ExecException, InterruptedException {
checkForInterrupt("processing", source);
Collection inclusions = null;
while (inclusions == null) {
SettableFuture> future = SettableFuture.create();
Future> previous = fileParseCache.putIfAbsent(source, future);
if (previous == null) {
previous = future;
try {
future.set(
parser.extractInclusions(
source,
actionExecutionMetadata,
actionExecutionContext,
grepIncludes,
spawnIncludeScannerSupplier.get(),
isOutputFile(source.getExecPath())));
} catch (Throwable t) {
fileParseCache.remove(source);
future.setException(t);
throw t;
}
}
try {
inclusions = Preconditions.checkNotNull(previous.get(), source);
} catch (ExecutionException e) {
// An exception occured when some other thread tried to load the same file that we are
// waiting for. If this is a MissingDepExecException, we have to simply retry as otherwise
// we'd end up in an unexpected state (not requesting any deps, but claiming that there
// are missing ones). For other exceptions, this might not be necessary but is safe to do
// and reduces complexity.
}
}
// Shuffle the inclusions to get better parallelism. See b/62200470.
List shuffledInclusions = new ArrayList<>(inclusions);
Collections.shuffle(shuffledInclusions, CONSTANT_SEED_RANDOM);
// For each inclusion: get or locate its target file & recursively process
IncludeScannerHelper helper =
new IncludeScannerHelper(includePaths, quoteIncludePaths, source);
PathFragment parent = source.getExecPath().getParentDirectory();
for (Inclusion inclusion : shuffledInclusions) {
findAndProcess(
helper.createInclusionWithContext(inclusion, contextPathPos, contextKind),
source,
parent,
visited);
}
}
/**
* Same as {@link #process}, but executes asynchronously if the #include lines of {@code source}
* haven't been extracted yet. For sources that have already been extracted, just continue
* walking them in the current thread. The overhead of scheduling this on other threads is
* larger than the gain in concurrency. The only really slow operation is the (possibly remote)
* extraction of includes.
*/
private void processAsyncIfNotExtracted(
final Artifact source, int contextPathPos, Kind contextKind, Set visited)
throws IOException, ExecException, InterruptedException {
ListenableFuture> cacheResult = fileParseCache.get(source);
if (cacheResult != null) {
process(source, contextPathPos, contextKind, visited);
} else {
super.execute(
() -> {
try (SilentCloseable ignored =
actionExecutionContext.getThreadStateReceiverForMetrics().started()) {
process(source, contextPathPos, contextKind, visited);
} catch (IOException e) {
throw new IORuntimeException(e);
} catch (ExecException e) {
throw new ExecRuntimeException(e);
} catch (InterruptedException e) {
throw new InterruptedRuntimeException(e);
}
});
}
}
/** Visits an inclusion starting from a source file. */
private void findAndProcess(
InclusionWithContext inclusion, Artifact source, PathFragment parent, Set visited)
throws IOException, ExecException, InterruptedException {
// Try to find the included file relative to the file that contains the inclusion. Relative
// inclusions are handled like the first entry on the quote include path
Artifact includeFile = locateRelative(inclusion.getInclusion(), headerData, source, parent);
int contextPathPos = 0;
Kind contextKind = null;
checkForInterrupt("visiting", source);
// If nothing has been found, get an inclusion from the cache. This will automatically search
// on the include paths and populate the cache if necessary.
if (includeFile == null) {
LocateOnPathResult result = inclusionCache.lookup(inclusion, headerData);
includeFile = result.path;
contextPathPos = result.includePosition;
contextKind = inclusion.getContextKind();
}
// Recursively process the found file (if not yet done).
if (includeFile != null
&& !isIllegalOutputFile(includeFile.getExecPath(), headerData)
&& headerData.isLegalHeader(includeFile)
&& visitedInclusions.add(
new ArtifactWithInclusionContext(includeFile, contextKind, contextPathPos))) {
visited.add(includeFile);
if (headerData.isModularHeader(includeFile)) {
return;
}
processAsyncIfNotExtracted(includeFile, contextPathPos, contextKind, visited);
}
}
/**
* Processes a given list of includes for a given base file and populates the provided set with
* the visited includes
*
* @param source the source file used as a reference for finding includes
* @param includes the list of -include option strings to locate and process
* @param visited the set of files that are transitively included by {@code includes} to
* populate
*/
private void processCmdlineIncludes(
Artifact source, List includes, Set visited)
throws IOException, ExecException, InterruptedException {
PathFragment parent = source.getExecPath().getParentDirectory();
for (String incl : includes) {
InclusionWithContext inclusion = new InclusionWithContext(incl, Kind.QUOTE);
findAndProcess(inclusion, source, parent, visited);
}
}
/**
* Processes a bunch sources asynchronously and adds them and their included files to the
* provided set.
*
* @param sources the files to process and add to the set
* @param visited the set to receive the files that are transitively included by {@code sources}
*/
private void processBulkAsync(Collection sources, final Set visited)
throws IOException, ExecException, InterruptedException {
for (final Artifact source : sources) {
// TODO(djasper): This looks suspicious. We should only stop based on visitedInclusions.
if (!visited.add(source)) {
continue;
}
processAsyncIfNotExtracted(source, /*contextPathPos=*/ -1, /*contextKind=*/ null, visited);
}
}
private void processFileLevelHintsAsync(
final Hints hints, final Artifact include, final Set alsoVisited) {
Collection sources = hints.getFileLevelHintedInclusionsLegacy(include);
// Early-out if there's nothing to do to avoid enqueuing a closure
if (sources.isEmpty()) {
return;
}
super.execute(
() -> {
try (SilentCloseable ignored =
actionExecutionContext.getThreadStateReceiverForMetrics().started()) {
processBulkAsync(sources, alsoVisited);
} catch (IOException e) {
throw new IORuntimeException(e);
} catch (ExecException e) {
throw new ExecRuntimeException(e);
} catch (InterruptedException e) {
throw new InterruptedRuntimeException(e);
}
});
}
}
private static final class ExecRuntimeException extends RuntimeException {
private final ExecException cause;
ExecRuntimeException(ExecException e) {
super(e);
this.cause = e;
}
public ExecException getRealCause() {
return cause;
}
}
private static final class InterruptedRuntimeException extends RuntimeException {
private final InterruptedException cause;
InterruptedRuntimeException(InterruptedException e) {
super(e);
this.cause = e;
}
public InterruptedException getRealCause() {
return cause;
}
}
}