Switch the label visitation algorithm have the query environment filter the label deps instead.
Also rename some references to TTVs by the more general term Label to refer to targets in the build graph.
PiperOrigin-RevId: 280185323
diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractTargetOuputtingVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractTargetOuputtingVisitor.java
index e9ad01b..10fdba3 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/AbstractTargetOuputtingVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractTargetOuputtingVisitor.java
@@ -20,12 +20,16 @@
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
+import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.query2.ParallelVisitorUtils.ParallelQueryVisitor;
import com.google.devtools.build.lib.query2.engine.Callback;
import com.google.devtools.build.lib.query2.engine.QueryException;
import com.google.devtools.build.skyframe.SkyKey;
import java.util.Collection;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
/**
* Helper class to traverse a visitation graph where the outputs are {@link Target}s and there is a
@@ -49,8 +53,24 @@
@Override
protected Iterable<Target> outputKeysToOutputValues(Iterable<SkyKey> targetKeys)
throws InterruptedException {
- return env.getTargets(Iterables.transform(targetKeys, SkyQueryEnvironment.SKYKEY_TO_LABEL))
- .values();
+ Map<Label, Target> targets =
+ env.getTargets(Iterables.transform(targetKeys, SkyQueryEnvironment.SKYKEY_TO_LABEL));
+ checkForMissingTargets(targetKeys, targets);
+ return targets.values();
+ }
+
+ private void checkForMissingTargets(Iterable<SkyKey> targetKeys, Map<Label, Target> targets) {
+ Set<SkyKey> missingTargets = new HashSet<>();
+ Set<Label> keysFound = targets.keySet();
+ for (SkyKey key : targetKeys) {
+ if (!keysFound.contains(key)) {
+ missingTargets.add(key);
+ }
+ }
+ if (!missingTargets.isEmpty()) {
+ env.getEventHandler()
+ .handle(Event.warn("Targets were missing from graph: " + missingTargets));
+ }
}
@Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractUnfilteredTTVDTCVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractUnfilteredLabelDTCVisitor.java
similarity index 61%
rename from src/main/java/com/google/devtools/build/lib/query2/AbstractUnfilteredTTVDTCVisitor.java
rename to src/main/java/com/google/devtools/build/lib/query2/AbstractUnfilteredLabelDTCVisitor.java
index b178a2d..5845dca 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/AbstractUnfilteredTTVDTCVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractUnfilteredLabelDTCVisitor.java
@@ -14,21 +14,21 @@
package com.google.devtools.build.lib.query2;
import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
-import com.google.common.collect.Multimap;
import com.google.devtools.build.lib.query2.engine.Callback;
import com.google.devtools.build.lib.query2.engine.Uniquifier;
import com.google.devtools.build.skyframe.SkyKey;
+import java.util.Map;
/**
- * Helper class for visiting the TTV-only DTC of some given TTV keys, via BFS following all
- * TTV->TTV dep edges. Disallowed edge filtering is *not* performed.
+ * Helper class for visiting the label-only DTC of some given label keys, via BFS following all
+ * target label -> target label dep edges. Disallowed edge filtering is *not* performed.
*/
-public abstract class AbstractUnfilteredTTVDTCVisitor<T> extends AbstractSkyKeyParallelVisitor<T> {
+public abstract class AbstractUnfilteredLabelDTCVisitor<T>
+ extends AbstractSkyKeyParallelVisitor<T> {
protected final SkyQueryEnvironment env;
- protected AbstractUnfilteredTTVDTCVisitor(
+ protected AbstractUnfilteredLabelDTCVisitor(
SkyQueryEnvironment env,
Uniquifier<SkyKey> uniquifier,
int processResultsBatchSize,
@@ -43,21 +43,16 @@
}
@Override
- protected Visit getVisitResult(Iterable<SkyKey> ttvKeys) throws InterruptedException {
- Multimap<SkyKey, SkyKey> deps = env.getUnfilteredDirectDepsOfSkyKeys(ttvKeys);
- return new Visit(
- /*keysToUseForResult=*/ deps.keySet(),
- /*keysToVisit=*/ deps.values()
- .stream()
- .filter(SkyQueryEnvironment.IS_TTV)
- .collect(ImmutableList.toImmutableList()));
+ protected Visit getVisitResult(Iterable<SkyKey> labelKeys) throws InterruptedException {
+ Map<SkyKey, Iterable<SkyKey>> depsMap = env.getFwdDepLabels(labelKeys);
+ return new Visit(labelKeys, Iterables.concat(depsMap.values()));
}
@Override
protected Iterable<SkyKey> preprocessInitialVisit(Iterable<SkyKey> visitationKeys) {
- // ParallelTargetVisitorCallback passes in TTV keys.
+ // ParallelTargetVisitorCallback passes in labels.
Preconditions.checkState(
- Iterables.all(visitationKeys, SkyQueryEnvironment.IS_TTV), visitationKeys);
+ Iterables.all(visitationKeys, SkyQueryEnvironment.IS_LABEL), visitationKeys);
return visitationKeys;
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/DepsUnboundedVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/DepsUnboundedVisitor.java
index e2eeb5f..1451cc4 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/DepsUnboundedVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/DepsUnboundedVisitor.java
@@ -13,16 +13,11 @@
// limitations under the License.
package com.google.devtools.build.lib.query2;
-import static com.google.devtools.build.lib.query2.SkyQueryEnvironment.IS_TTV;
-import static com.google.devtools.build.lib.query2.SkyQueryEnvironment.SKYKEY_TO_LABEL;
-
-import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Multimap;
-import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
-import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.query2.ParallelVisitorUtils.ParallelQueryVisitor;
import com.google.devtools.build.lib.query2.ParallelVisitorUtils.QueryVisitorFactory;
@@ -31,7 +26,6 @@
import com.google.devtools.build.lib.query2.engine.QueryExpressionContext;
import com.google.devtools.build.lib.query2.engine.Uniquifier;
import com.google.devtools.build.skyframe.SkyKey;
-import java.util.Map;
import java.util.Set;
/**
@@ -124,22 +118,8 @@
/*keysToVisit=*/ depsAsSkyKeys);
}
- // We need to explicitly check that all requested TTVs are actually in the graph.
- Map<SkyKey, Iterable<SkyKey>> depMap = env.graph.getDirectDeps(keys);
- checkIfMissingTargets(keys, depMap);
- Iterable<SkyKey> deps = Iterables.filter(Iterables.concat(depMap.values()), IS_TTV);
- return new Visit(keys, deps);
- }
-
- private void checkIfMissingTargets(Iterable<SkyKey> keys, Map<SkyKey, Iterable<SkyKey>> depMap) {
- if (depMap.size() != Iterables.size(keys)) {
- Iterable<Label> missingTargets =
- Iterables.transform(
- Iterables.filter(keys, Predicates.not(Predicates.in(depMap.keySet()))),
- SKYKEY_TO_LABEL);
- env.getEventHandler()
- .handle(Event.warn("Targets were missing from graph: " + missingTargets));
- }
+ return new Visit(
+ keys, ImmutableSet.copyOf(Iterables.concat(env.getFwdDepLabels(keys).values())));
}
@Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java b/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java
index de2a3d1..dbc4354 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/ParallelSkyQueryUtils.java
@@ -111,8 +111,8 @@
new ThreadSafeAggregateAllSkyKeysCallback(concurrencyLevel);
return env.execute(
() -> {
- UnfilteredSkyKeyTTVDTCVisitor visitor =
- new UnfilteredSkyKeyTTVDTCVisitor.Factory(
+ UnfilteredSkyKeyLabelDTCVisitor visitor =
+ new UnfilteredSkyKeyLabelDTCVisitor.Factory(
env,
env.createSkyKeyUniquifier(),
processResultsBatchSize,
diff --git a/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java
index 8b672ee..020bdeb 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java
@@ -117,7 +117,7 @@
SkyKey rdep = entry.getKey();
int depthOfRdepOfRdep = shallowestRdepDepthMap.get(rdep) + 1;
Streams.stream(entry.getValue())
- .filter(Predicates.and(SkyQueryEnvironment.IS_TTV, universe))
+ .filter(Predicates.and(SkyQueryEnvironment.IS_LABEL, universe))
.forEachOrdered(
rdepOfRdep -> {
depAndRdepAtDepthsToVisitBuilder.add(
diff --git a/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java
index eecf12d..3cb7b6e 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java
@@ -113,7 +113,7 @@
Iterables.transform(
Iterables.filter(
reverseDepsEntry.getValue(),
- Predicates.and(SkyQueryEnvironment.IS_TTV, unfilteredUniverse)),
+ Predicates.and(SkyQueryEnvironment.IS_LABEL, unfilteredUniverse)),
rdep -> new DepAndRdep(reverseDepsEntry.getKey(), rdep))));
return new Visit(
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index b42dd40..e14cdad 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -27,7 +27,6 @@
import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableMultimap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Maps;
@@ -452,8 +451,8 @@
return super.evaluateQuery(expr, batchCallback);
}
- private Map<SkyKey, Collection<Target>> targetifyValues(
- Map<SkyKey, ? extends Iterable<SkyKey>> input) throws InterruptedException {
+ Map<SkyKey, Collection<Target>> targetifyValues(Map<SkyKey, ? extends Iterable<SkyKey>> input)
+ throws InterruptedException {
return targetifyValues(
input,
makePackageKeyToTargetKeyMap(ImmutableSet.copyOf(Iterables.concat(input.values()))));
@@ -522,12 +521,10 @@
for (Target target : targets) {
targetsByKey.put(TARGET_TO_SKY_KEY.apply(target), target);
}
- Map<SkyKey, Collection<Target>> directDeps = targetifyValues(
- graph.getDirectDeps(targetsByKey.keySet()));
+ Map<SkyKey, Collection<Target>> directDeps =
+ targetifyValues(getFwdDepLabels(targetsByKey.keySet()));
if (targetsByKey.keySet().size() != directDeps.keySet().size()) {
- Iterable<Label> missingTargets = Iterables.transform(
- Sets.difference(targetsByKey.keySet(), directDeps.keySet()),
- SKYKEY_TO_LABEL);
+ Iterable<SkyKey> missingTargets = Sets.difference(targetsByKey.keySet(), directDeps.keySet());
eventHandler.handle(Event.warn("Targets were missing from graph: " + missingTargets));
}
ThreadSafeMutableSet<Target> result = createThreadSafeMutableSet();
@@ -537,29 +534,28 @@
return result;
}
- /**
- * Returns deps in the form of {@link SkyKey}s.
- *
- * <p>The implementation of this method does not filter out deps due to disallowed edges,
- * therefore callers are responsible for doing the right thing themselves.
- */
- public Multimap<SkyKey, SkyKey> getUnfilteredDirectDepsOfSkyKeys(Iterable<SkyKey> keys)
+ /** Returns the target dependencies' {@link Label}s of the passed in target {@code Label}s. */
+ protected Map<SkyKey, Iterable<SkyKey>> getFwdDepLabels(Iterable<SkyKey> targetLabels)
throws InterruptedException {
- ImmutableMultimap.Builder<SkyKey, SkyKey> builder = ImmutableMultimap.builder();
- graph.getDirectDeps(keys).forEach(builder::putAll);
- return builder.build();
+ Preconditions.checkState(
+ Iterables.all(targetLabels, IS_LABEL), "Expected all labels: %s", targetLabels);
+ return graph.getDirectDeps(targetLabels).entrySet().stream()
+ .collect(
+ ImmutableMap.toImmutableMap(
+ Map.Entry::getKey, entry -> Iterables.filter(entry.getValue(), IS_LABEL)));
}
@Override
public Collection<Target> getReverseDeps(
Iterable<Target> targets, QueryExpressionContext<Target> context)
throws InterruptedException {
- return getReverseDepsOfTransitiveTraversalKeys(Iterables.transform(targets, TARGET_TO_SKY_KEY));
+ return getReverseDepsOfLabels(Iterables.transform(targets, Target::getLabel));
}
- private Collection<Target> getReverseDepsOfTransitiveTraversalKeys(
- Iterable<SkyKey> transitiveTraversalKeys) throws InterruptedException {
- Map<SkyKey, Collection<Target>> rawReverseDeps = getRawReverseDeps(transitiveTraversalKeys);
+ protected Collection<Target> getReverseDepsOfLabels(Iterable<Label> targetLabels)
+ throws InterruptedException {
+ Map<SkyKey, Collection<Target>> rawReverseDeps =
+ getRawReverseDeps(Iterables.transform(targetLabels, label -> label));
return processRawReverseDeps(rawReverseDeps);
}
@@ -986,14 +982,17 @@
Iterables.filter(transitiveTraversalKeys, Predicates.not(Predicates.in(successfulKeys)));
Set<Map.Entry<SkyKey, Exception>> errorEntries =
graph.getMissingAndExceptions(unsuccessfulKeys).entrySet();
+ Set<SkyKey> missingKeys = new HashSet<>();
for (Map.Entry<SkyKey, Exception> entry : errorEntries) {
if (entry.getValue() == null) {
- // Targets may be in the graph because they are not in the universe or depend on cycles.
- eventHandler.handle(Event.warn(entry.getKey().argument() + " does not exist in graph"));
+ missingKeys.add((SkyKey) entry.getKey().argument());
} else {
errorMessagesBuilder.add(entry.getValue().getMessage());
}
}
+ if (!missingKeys.isEmpty()) {
+ eventHandler.handle(Event.warn("Targets were missing from graph: " + missingKeys));
+ }
// Lastly, report all found errors.
ImmutableList<String> errorMessages = errorMessagesBuilder.build();
@@ -1014,11 +1013,11 @@
return eventHandler;
}
- public static final Predicate<SkyKey> IS_TTV =
+ public static final Predicate<SkyKey> IS_LABEL =
SkyFunctionName.functionIs(Label.TRANSITIVE_TRAVERSAL);
public static final Function<SkyKey, Label> SKYKEY_TO_LABEL =
- skyKey -> IS_TTV.apply(skyKey) ? (Label) skyKey.argument() : null;
+ skyKey -> IS_LABEL.apply(skyKey) ? (Label) skyKey.argument() : null;
static final Function<SkyKey, PackageIdentifier> PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER =
skyKey -> (PackageIdentifier) skyKey.argument();
diff --git a/src/main/java/com/google/devtools/build/lib/query2/UnfilteredSkyKeyTTVDTCVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/UnfilteredSkyKeyLabelDTCVisitor.java
similarity index 90%
rename from src/main/java/com/google/devtools/build/lib/query2/UnfilteredSkyKeyTTVDTCVisitor.java
rename to src/main/java/com/google/devtools/build/lib/query2/UnfilteredSkyKeyLabelDTCVisitor.java
index 16f7113..f5dbea8 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/UnfilteredSkyKeyTTVDTCVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/UnfilteredSkyKeyLabelDTCVisitor.java
@@ -23,8 +23,8 @@
* Helper class for visiting the TTV-only DTC of some given TTV keys, and feeding those TTVs to a
* callback.
*/
-class UnfilteredSkyKeyTTVDTCVisitor extends AbstractUnfilteredTTVDTCVisitor<SkyKey> {
- private UnfilteredSkyKeyTTVDTCVisitor(
+class UnfilteredSkyKeyLabelDTCVisitor extends AbstractUnfilteredLabelDTCVisitor<SkyKey> {
+ private UnfilteredSkyKeyLabelDTCVisitor(
SkyQueryEnvironment env,
Uniquifier<SkyKey> uniquifier,
int processResultsBatchSize,
@@ -59,8 +59,8 @@
}
@Override
- public UnfilteredSkyKeyTTVDTCVisitor create() {
- return new UnfilteredSkyKeyTTVDTCVisitor(
+ public UnfilteredSkyKeyLabelDTCVisitor create() {
+ return new UnfilteredSkyKeyLabelDTCVisitor(
env, uniquifier, processResultsBatchSize, aggregateAllCallback);
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 5a874e1..71ccc8c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -535,7 +535,7 @@
map.put(SkyFunctions.PACKAGE_ERROR_MESSAGE, new PackageErrorMessageFunction());
map.put(SkyFunctions.TARGET_PATTERN_ERROR, new TargetPatternErrorFunction());
map.put(SkyFunctions.TRANSITIVE_TARGET, new TransitiveTargetFunction(ruleClassProvider));
- map.put(Label.TRANSITIVE_TRAVERSAL, new TransitiveTraversalFunction());
+ map.put(Label.TRANSITIVE_TRAVERSAL, getTransitiveTraversalFunction());
map.put(
SkyFunctions.CONFIGURED_TARGET,
new ConfiguredTargetFunction(
@@ -617,6 +617,10 @@
return ImmutableMap.copyOf(map);
}
+ protected SkyFunction getTransitiveTraversalFunction() {
+ return new TransitiveTraversalFunction();
+ }
+
protected boolean traverseTestSuites() {
return false;
}
