// Copyright 2015 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.query2;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Ascii;
import com.google.common.base.Function;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.base.Throwables;
import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSet.Builder;
import com.google.common.collect.Iterables;
import com.google.common.collect.Maps;
import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;
import com.google.common.util.concurrent.AsyncFunction;
import com.google.common.util.concurrent.Futures;
import com.google.common.util.concurrent.ListenableFuture;
import com.google.common.util.concurrent.ListeningExecutorService;
import com.google.common.util.concurrent.MoreExecutors;
import com.google.common.util.concurrent.ThreadFactoryBuilder;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.cmdline.TargetParsingException;
import com.google.devtools.build.lib.cmdline.TargetPattern;
import com.google.devtools.build.lib.collect.CompactHashSet;
import com.google.devtools.build.lib.concurrent.BlockingStack;
import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.events.DelegatingEventHandler;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.EventKind;
import com.google.devtools.build.lib.events.ExtendedEventHandler;
import com.google.devtools.build.lib.graph.Digraph;
import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
import com.google.devtools.build.lib.packages.DependencyFilter;
import com.google.devtools.build.lib.packages.NoSuchPackageException;
import com.google.devtools.build.lib.packages.NoSuchTargetException;
import com.google.devtools.build.lib.packages.NoSuchThingException;
import com.google.devtools.build.lib.packages.Package;
import com.google.devtools.build.lib.packages.Rule;
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
import com.google.devtools.build.lib.profiler.AutoProfiler;
import com.google.devtools.build.lib.query2.engine.AllRdepsFunction;
import com.google.devtools.build.lib.query2.engine.Callback;
import com.google.devtools.build.lib.query2.engine.FunctionExpression;
import com.google.devtools.build.lib.query2.engine.KeyExtractor;
import com.google.devtools.build.lib.query2.engine.MinDepthUniquifier;
import com.google.devtools.build.lib.query2.engine.OutputFormatterCallback;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskCallable;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture;
import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
import com.google.devtools.build.lib.query2.engine.QueryException;
import com.google.devtools.build.lib.query2.engine.QueryExpression;
import com.google.devtools.build.lib.query2.engine.QueryExpressionMapper;
import com.google.devtools.build.lib.query2.engine.QueryUtil.MinDepthUniquifierImpl;
import com.google.devtools.build.lib.query2.engine.QueryUtil.UniquifierImpl;
import com.google.devtools.build.lib.query2.engine.RdepsFunction;
import com.google.devtools.build.lib.query2.engine.StreamableQueryEnvironment;
import com.google.devtools.build.lib.query2.engine.TargetLiteral;
import com.google.devtools.build.lib.query2.engine.ThreadSafeOutputFormatterCallback;
import com.google.devtools.build.lib.query2.engine.Uniquifier;
import com.google.devtools.build.lib.query2.engine.VariableContext;
import com.google.devtools.build.lib.skyframe.BlacklistedPackagePrefixesValue;
import com.google.devtools.build.lib.skyframe.ContainingPackageLookupFunction;
import com.google.devtools.build.lib.skyframe.FileValue;
import com.google.devtools.build.lib.skyframe.GraphBackedRecursivePackageProvider;
import com.google.devtools.build.lib.skyframe.PackageLookupValue;
import com.google.devtools.build.lib.skyframe.PackageValue;
import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternsFunction;
import com.google.devtools.build.lib.skyframe.RecursivePackageProviderBackedTargetPatternResolver;
import com.google.devtools.build.lib.skyframe.SkyFunctions;
import com.google.devtools.build.lib.skyframe.TargetPatternValue;
import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
import com.google.devtools.build.lib.skyframe.TransitiveTraversalValue;
import com.google.devtools.build.lib.util.Pair;
import com.google.devtools.build.lib.util.Preconditions;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.RootedPath;
import com.google.devtools.build.skyframe.EvaluationResult;
import com.google.devtools.build.skyframe.InterruptibleSupplier;
import com.google.devtools.build.skyframe.SkyFunctionName;
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.build.skyframe.WalkableGraph;
import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.RejectedExecutionException;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.annotation.Nullable;
/**
* {@link AbstractBlazeQueryEnvironment} that introspects the Skyframe graph to find forward and
* reverse edges. Results obtained by calling {@link #evaluateQuery} are not guaranteed to be in any
* particular order. As well, this class eagerly loads the full transitive closure of targets, even
* if the full closure isn't needed.
*
*
This class has concurrent implementations of the
* {@link QueryTaskFuture}/{@link QueryTaskCallable} helper methods. The combination of this and the
* asynchronous evaluation model yields parallel query evaluation.
*/
public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment
implements StreamableQueryEnvironment {
// 10k is likely a good balance between using batch efficiently and not blowing up memory.
// TODO(janakr): Unify with RecursivePackageProviderBackedTargetPatternResolver's constant.
static final int BATCH_CALLBACK_SIZE = 10000;
protected static final int DEFAULT_THREAD_COUNT = Runtime.getRuntime().availableProcessors();
private static final int MAX_QUERY_EXPRESSION_LOG_CHARS = 1000;
private static final Logger LOG = Logger.getLogger(SkyQueryEnvironment.class.getName());
private final BlazeTargetAccessor accessor = new BlazeTargetAccessor(this);
protected final int loadingPhaseThreads;
protected final WalkableGraphFactory graphFactory;
protected final ImmutableList universeScope;
protected boolean blockUniverseEvaluationErrors;
protected ExtendedEventHandler universeEvalEventHandler;
protected final String parserPrefix;
protected final PathPackageLocator pkgPath;
private final int queryEvaluationParallelismLevel;
// The following fields are set in the #beforeEvaluateQuery method.
private MultisetSemaphore packageSemaphore;
protected WalkableGraph graph;
private InterruptibleSupplier> blacklistPatternsSupplier;
private GraphBackedRecursivePackageProvider graphBackedRecursivePackageProvider;
private ListeningExecutorService executor;
private RecursivePackageProviderBackedTargetPatternResolver resolver;
private final SkyKey universeKey;
private final ImmutableList universeTargetPatternKeys;
public SkyQueryEnvironment(
boolean keepGoing,
int loadingPhaseThreads,
ExtendedEventHandler eventHandler,
Set settings,
Iterable extraFunctions,
String parserPrefix,
WalkableGraphFactory graphFactory,
List universeScope,
PathPackageLocator pkgPath,
boolean blockUniverseEvaluationErrors) {
this(
keepGoing,
loadingPhaseThreads,
// SkyQueryEnvironment operates on a prepopulated Skyframe graph. Therefore, query
// evaluation is completely CPU-bound.
/*queryEvaluationParallelismLevel=*/ DEFAULT_THREAD_COUNT,
eventHandler,
settings,
extraFunctions,
parserPrefix,
graphFactory,
universeScope,
pkgPath,
blockUniverseEvaluationErrors);
}
protected SkyQueryEnvironment(
boolean keepGoing,
int loadingPhaseThreads,
int queryEvaluationParallelismLevel,
ExtendedEventHandler eventHandler,
Set settings,
Iterable extraFunctions,
String parserPrefix,
WalkableGraphFactory graphFactory,
List universeScope,
PathPackageLocator pkgPath,
boolean blockUniverseEvaluationErrors) {
super(
keepGoing,
/*strictScope=*/ true,
/*labelFilter=*/ Rule.ALL_LABELS,
eventHandler,
settings,
extraFunctions);
this.loadingPhaseThreads = loadingPhaseThreads;
this.graphFactory = graphFactory;
this.pkgPath = pkgPath;
this.universeScope = ImmutableList.copyOf(Preconditions.checkNotNull(universeScope));
this.parserPrefix = parserPrefix;
Preconditions.checkState(
!universeScope.isEmpty(), "No queries can be performed with an empty universe");
this.queryEvaluationParallelismLevel = queryEvaluationParallelismLevel;
this.universeKey = graphFactory.getUniverseKey(universeScope, parserPrefix);
this.blockUniverseEvaluationErrors = blockUniverseEvaluationErrors;
this.universeEvalEventHandler =
this.blockUniverseEvaluationErrors
? new ErrorBlockingForwardingEventHandler(this.eventHandler)
: this.eventHandler;
this.universeTargetPatternKeys =
PrepareDepsOfPatternsFunction.getTargetPatternKeys(
PrepareDepsOfPatternsFunction.getSkyKeys(universeKey, eventHandler));
}
private void beforeEvaluateQuery() throws InterruptedException {
if (graph == null || !graphFactory.isUpToDate(universeKey)) {
// If this environment is uninitialized or the graph factory needs to evaluate, do so. We
// assume here that this environment cannot be initialized-but-stale if the factory is up
// to date.
EvaluationResult result;
try (AutoProfiler p = AutoProfiler.logged("evaluation and walkable graph", LOG)) {
result =
graphFactory.prepareAndGet(universeKey, loadingPhaseThreads, universeEvalEventHandler);
}
checkEvaluationResult(result);
packageSemaphore = makeFreshPackageMultisetSemaphore();
graph = result.getWalkableGraph();
blacklistPatternsSupplier = InterruptibleSupplier.Memoize.of(new BlacklistSupplier(graph));
graphBackedRecursivePackageProvider =
new GraphBackedRecursivePackageProvider(graph, universeTargetPatternKeys, pkgPath);
}
if (executor == null) {
executor = MoreExecutors.listeningDecorator(
new ThreadPoolExecutor(
/*corePoolSize=*/ queryEvaluationParallelismLevel,
/*maximumPoolSize=*/ queryEvaluationParallelismLevel,
/*keepAliveTime=*/ 1,
/*units=*/ TimeUnit.SECONDS,
/*workQueue=*/ new BlockingStack(),
new ThreadFactoryBuilder().setNameFormat("QueryEnvironment %d").build()));
}
resolver =
new RecursivePackageProviderBackedTargetPatternResolver(
graphBackedRecursivePackageProvider,
eventHandler,
TargetPatternEvaluator.DEFAULT_FILTERING_POLICY,
packageSemaphore);
}
protected MultisetSemaphore makeFreshPackageMultisetSemaphore() {
return MultisetSemaphore.unbounded();
}
@ThreadSafe
public MultisetSemaphore getPackageMultisetSemaphore() {
return packageSemaphore;
}
/**
* The {@link EvaluationResult} is from the evaluation of a single PrepareDepsOfPatterns node. We
* expect to see either a single successfully evaluated value or a cycle in the result.
*/
private void checkEvaluationResult(EvaluationResult result) {
Collection values = result.values();
if (!values.isEmpty()) {
Preconditions.checkState(
values.size() == 1,
"Universe query \"%s\" returned multiple values unexpectedly (%s values in result)",
universeScope,
values.size());
Preconditions.checkNotNull(result.get(universeKey), result);
} else {
// No values in the result, so there must be an error. We expect the error to be a cycle.
boolean foundCycle = !Iterables.isEmpty(result.getError().getCycleInfo());
Preconditions.checkState(
foundCycle,
"Universe query \"%s\" failed with non-cycle error: %s",
universeScope,
result.getError());
}
}
/**
* A {@link QueryExpressionMapper} that transforms each occurrence of an expression of the form
* {@literal 'rdeps(, )'} to {@literal 'allrdeps()'}. The latter is more
* efficient.
*/
protected static class RdepsToAllRdepsQueryExpressionMapper extends QueryExpressionMapper {
protected final TargetPattern.Parser targetPatternParser;
private final String absoluteUniverseScopePattern;
protected RdepsToAllRdepsQueryExpressionMapper(
TargetPattern.Parser targetPatternParser,
String universeScopePattern) {
this.targetPatternParser = targetPatternParser;
this.absoluteUniverseScopePattern = targetPatternParser.absolutize(universeScopePattern);
}
@Override
public QueryExpression map(FunctionExpression functionExpression) {
if (functionExpression.getFunction().getName().equals(new RdepsFunction().getName())) {
List args = functionExpression.getArgs();
QueryExpression universeExpression = args.get(0).getExpression();
if (universeExpression instanceof TargetLiteral) {
TargetLiteral literalUniverseExpression = (TargetLiteral) universeExpression;
String absolutizedUniverseExpression =
targetPatternParser.absolutize(literalUniverseExpression.getPattern());
if (absolutizedUniverseExpression.equals(absoluteUniverseScopePattern)) {
List argsTail = args.subList(1, functionExpression.getArgs().size());
return new FunctionExpression(new AllRdepsFunction(), argsTail);
}
}
}
return super.map(functionExpression);
}
}
@Override
public final QueryExpression transformParsedQuery(QueryExpression queryExpression) {
QueryExpressionMapper mapper = getQueryExpressionMapper();
QueryExpression transformedQueryExpression = queryExpression.getMapped(mapper);
LOG.info(String.format(
"transformed query [%s] to [%s]",
Ascii.truncate(
queryExpression.toString(), MAX_QUERY_EXPRESSION_LOG_CHARS, "[truncated]"),
Ascii.truncate(
transformedQueryExpression.toString(), MAX_QUERY_EXPRESSION_LOG_CHARS, "[truncated]")));
return transformedQueryExpression;
}
protected QueryExpressionMapper getQueryExpressionMapper() {
if (universeScope.size() != 1) {
return QueryExpressionMapper.identity();
}
TargetPattern.Parser targetPatternParser = new TargetPattern.Parser(parserPrefix);
String universeScopePattern = Iterables.getOnlyElement(universeScope);
return new RdepsToAllRdepsQueryExpressionMapper(targetPatternParser, universeScopePattern);
}
@Override
protected void evalTopLevelInternal(
QueryExpression expr, OutputFormatterCallback callback)
throws QueryException, InterruptedException {
Throwable throwableToThrow = null;
try {
super.evalTopLevelInternal(expr, callback);
} catch (Throwable throwable) {
throwableToThrow = throwable;
} finally {
if (throwableToThrow != null) {
LOG.log(
Level.INFO,
"About to shutdown query threadpool because of throwable",
throwableToThrow);
// Force termination of remaining tasks if evaluation failed abruptly (e.g. was
// interrupted). We don't want to leave any dangling threads running tasks.
executor.shutdownNow();
executor.awaitTermination(Long.MAX_VALUE, TimeUnit.MILLISECONDS);
// Signal that executor must be recreated on the next invocation.
executor = null;
Throwables.propagateIfPossible(
throwableToThrow, QueryException.class, InterruptedException.class);
}
}
}
@Override
public QueryEvalResult evaluateQuery(
QueryExpression expr, ThreadSafeOutputFormatterCallback callback)
throws QueryException, InterruptedException, IOException {
// Some errors are reported as QueryExceptions and others as ERROR events (if --keep_going). The
// result is set to have an error iff there were errors emitted during the query, so we reset
// errors here.
eventHandler.resetErrors();
beforeEvaluateQuery();
// SkyQueryEnvironment batches callback invocations using a BatchStreamedCallback, created here
// so that there's one per top-level evaluateQuery call. The batch size is large enough that
// per-call costs of calling the original callback are amortized over a good number of targets,
// and small enough that holding a batch of targets in memory doesn't risk an OOM error.
//
// This flushes the batched callback prior to constructing the QueryEvalResult in the unlikely
// case of a race between the original callback and the eventHandler.
BatchStreamedCallback batchCallback = new BatchStreamedCallback(callback, BATCH_CALLBACK_SIZE);
return super.evaluateQuery(expr, batchCallback);
}
private Map> targetifyValues(
Map> input) throws InterruptedException {
return targetifyValues(
input,
makePackageKeyToTargetKeyMap(ImmutableSet.copyOf(Iterables.concat(input.values()))));
}
private Map> targetifyValues(
Map> input,
Multimap packageKeyToTargetKeyMap) throws InterruptedException {
ImmutableMap.Builder> result = ImmutableMap.builder();
Map allTargets =
makeTargetsFromPackageKeyToTargetKeyMap(packageKeyToTargetKeyMap);
for (Map.Entry> entry : input.entrySet()) {
Iterable skyKeys = entry.getValue();
Set targets = CompactHashSet.createWithExpectedSize(Iterables.size(skyKeys));
for (SkyKey key : skyKeys) {
Target target = allTargets.get(key);
if (target != null) {
targets.add(target);
}
}
result.put(entry.getKey(), targets);
}
return result.build();
}
private Map> targetifyKeys(Map> input)
throws InterruptedException {
Map targets = makeTargetsFromSkyKeys(input.keySet());
ImmutableMap.Builder> resultBuilder = ImmutableMap.builder();
for (Map.Entry> entry : input.entrySet()) {
SkyKey key = entry.getKey();
Target target = targets.get(key);
if (target != null) {
resultBuilder.put(target, entry.getValue());
}
}
return resultBuilder.build();
}
private Map> targetifyKeysAndValues(
Map> input) throws InterruptedException {
return targetifyKeys(targetifyValues(input));
}
private Map> getRawFwdDeps(Iterable targets)
throws InterruptedException {
return targetifyKeysAndValues(graph.getDirectDeps(makeTransitiveTraversalKeys(targets)));
}
private Map> getRawReverseDeps(
Iterable transitiveTraversalKeys) throws InterruptedException {
return targetifyValues(graph.getReverseDeps(transitiveTraversalKeys));
}
private Set