Fix crash bug in SkyQuery rdeps when there's a dependency edge filter. RELNOTES: None PiperOrigin-RevId: 206368137
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 c95a653..5ad164c 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
@@ -70,7 +70,7 @@ ParallelVisitor.createParallelVisitorCallback( new RdepsUnboundedVisitor.Factory( env, - /*universe=*/ Predicates.alwaysTrue(), + /*unfilteredUniverse=*/ Predicates.alwaysTrue(), callback, packageSemaphore))); } @@ -97,7 +97,7 @@ static QueryTaskFuture<Void> getRdepsInUniverseUnboundedParallel( SkyQueryEnvironment env, QueryExpression expression, - Predicate<SkyKey> universe, + Predicate<SkyKey> unfilteredUniverse, QueryExpressionContext<Target> context, Callback<Target> callback, MultisetSemaphore<PackageIdentifier> packageSemaphore) { @@ -105,7 +105,8 @@ expression, context, ParallelVisitor.createParallelVisitorCallback( - new RdepsUnboundedVisitor.Factory(env, universe, callback, packageSemaphore))); + new RdepsUnboundedVisitor.Factory( + env, unfilteredUniverse, callback, packageSemaphore))); } static QueryTaskFuture<Predicate<SkyKey>> getDTCSkyKeyPredicateFuture( @@ -126,7 +127,7 @@ () -> { Callback<Target> visitorCallback = ParallelVisitor.createParallelVisitorCallback( - new TransitiveTraversalValueDTCVisitor.Factory( + new UnfilteredTransitiveTraversalValueDTCVisitor.Factory( env, env.createSkyKeyUniquifier(), processResultsBatchSize,
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 d9f1e0f..f376b8d 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
@@ -60,19 +60,19 @@ */ private final Uniquifier<SkyKey> validRdepUniquifier; - private final Predicate<SkyKey> universe; + private final Predicate<SkyKey> unfilteredUniverse; RdepsUnboundedVisitor( SkyQueryEnvironment env, Uniquifier<DepAndRdep> depAndRdepUniquifier, Uniquifier<SkyKey> validRdepUniquifier, - Predicate<SkyKey> universe, + Predicate<SkyKey> unfilteredUniverse, Callback<Target> callback, MultisetSemaphore<PackageIdentifier> packageSemaphore) { super(env, callback, packageSemaphore); this.depAndRdepUniquifier = depAndRdepUniquifier; this.validRdepUniquifier = validRdepUniquifier; - this.universe = universe; + this.unfilteredUniverse = unfilteredUniverse; } /** @@ -85,17 +85,17 @@ private final SkyQueryEnvironment env; private final Uniquifier<DepAndRdep> depAndRdepUniquifier; private final Uniquifier<SkyKey> validRdepUniquifier; - private final Predicate<SkyKey> universe; + private final Predicate<SkyKey> unfilteredUniverse; private final Callback<Target> callback; private final MultisetSemaphore<PackageIdentifier> packageSemaphore; Factory( SkyQueryEnvironment env, - Predicate<SkyKey> universe, + Predicate<SkyKey> unfilteredUniverse, Callback<Target> callback, MultisetSemaphore<PackageIdentifier> packageSemaphore) { this.env = env; - this.universe = universe; + this.unfilteredUniverse = unfilteredUniverse; this.depAndRdepUniquifier = new UniquifierImpl<>(depAndRdep -> depAndRdep); this.validRdepUniquifier = env.createSkyKeyUniquifier(); this.callback = callback; @@ -105,7 +105,12 @@ @Override public ParallelVisitor<DepAndRdep, Target> create() { return new RdepsUnboundedVisitor( - env, depAndRdepUniquifier, validRdepUniquifier, universe, callback, packageSemaphore); + env, + depAndRdepUniquifier, + validRdepUniquifier, + unfilteredUniverse, + callback, + packageSemaphore); } } @@ -161,7 +166,9 @@ ImmutableList<SkyKey> uniqueValidRdeps = uniqueValidRdepsbuilder.build(); // Retrieve the reverse deps as SkyKeys and defer the targetification and filtering to next - // recursive visitation. + // recursive visitation. Because the universe given to us is unfiltered, we definitely still + // need to filter out disallowed edges, but cannot do so before targetification occurs. This + // means we may be wastefully visiting nodes via disallowed edges. ImmutableList.Builder<DepAndRdep> depAndRdepsToVisitBuilder = ImmutableList.builder(); env.graph .getReverseDeps(uniqueValidRdeps) @@ -172,7 +179,7 @@ Iterables.transform( Iterables.filter( reverseDepsEntry.getValue(), - Predicates.and(SkyQueryEnvironment.IS_TTV, universe)), + Predicates.and(SkyQueryEnvironment.IS_TTV, unfilteredUniverse)), rdep -> new DepAndRdep(reverseDepsEntry.getKey(), rdep)))); return new Visit( @@ -183,7 +190,7 @@ @Override protected Iterable<DepAndRdep> preprocessInitialVisit(Iterable<SkyKey> keys) { return Iterables.transform( - Iterables.filter(keys, k -> universe.apply(k)), key -> new DepAndRdep(null, key)); + Iterables.filter(keys, k -> unfilteredUniverse.apply(k)), key -> new DepAndRdep(null, key)); } @Override
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 2df8008..cba76ba 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
@@ -458,13 +458,11 @@ /** * Returns deps in the form of {@link SkyKey}s. * - * <p>The implementation of this method does not filter deps, therefore it is expected to be used - * only when {@link SkyQueryEnvironment#dependencyFilter} is set to {@link - * DependencyFilter#ALL_DEPS}. + * <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> getDirectDepsOfSkyKeys(Iterable<SkyKey> keys) + public Multimap<SkyKey, SkyKey> getUnfilteredDirectDepsOfSkyKeys(Iterable<SkyKey> keys) throws InterruptedException { - Preconditions.checkState(dependencyFilter == DependencyFilter.ALL_DEPS, dependencyFilter); ImmutableMultimap.Builder<SkyKey, SkyKey> builder = ImmutableMultimap.builder(); graph.getDirectDeps(keys).forEach(builder::putAll); return builder.build(); @@ -1192,7 +1190,7 @@ this, expression, depth, context, callback, packageSemaphore); } - protected QueryTaskFuture<Predicate<SkyKey>> getUniverseDTCSkyKeyPredicateFuture( + protected QueryTaskFuture<Predicate<SkyKey>> getUnfilteredUniverseDTCSkyKeyPredicateFuture( QueryExpression universe, QueryExpressionContext<Target> context) { return ParallelSkyQueryUtils.getDTCSkyKeyPredicateFuture( this, @@ -1210,9 +1208,9 @@ QueryExpressionContext<Target> context, Callback<Target> callback) { return transformAsync( - getUniverseDTCSkyKeyPredicateFuture(universe, context), - universePredicate -> ParallelSkyQueryUtils.getRdepsInUniverseUnboundedParallel( - this, expression, universePredicate, context, callback, packageSemaphore)); + getUnfilteredUniverseDTCSkyKeyPredicateFuture(universe, context), + unfilteredUniversePredicate -> ParallelSkyQueryUtils.getRdepsInUniverseUnboundedParallel( + this, expression, unfilteredUniversePredicate, context, callback, packageSemaphore)); } @Override @@ -1240,7 +1238,7 @@ QueryExpressionContext<Target> context, Callback<Target> callback) { return transformAsync( - getUniverseDTCSkyKeyPredicateFuture(universe, context), + getUnfilteredUniverseDTCSkyKeyPredicateFuture(universe, context), universePredicate -> ParallelSkyQueryUtils.getRdepsInUniverseBoundedParallel( this, expression, depth, universePredicate, context, callback, packageSemaphore)); }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/TransitiveTraversalValueDTCVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/UnfilteredTransitiveTraversalValueDTCVisitor.java similarity index 84% rename from src/main/java/com/google/devtools/build/lib/query2/TransitiveTraversalValueDTCVisitor.java rename to src/main/java/com/google/devtools/build/lib/query2/UnfilteredTransitiveTraversalValueDTCVisitor.java index 3d887f5..e1d10eb 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/TransitiveTraversalValueDTCVisitor.java +++ b/src/main/java/com/google/devtools/build/lib/query2/UnfilteredTransitiveTraversalValueDTCVisitor.java
@@ -26,20 +26,23 @@ /** * Helper class that computes the TTV-only DTC of some given TTV keys, via BFS following all - * TTV->TTV dep edges. + * TTV->TTV dep edges. Disallowed edge filtering is *not* performed. */ -class TransitiveTraversalValueDTCVisitor extends ParallelVisitor<SkyKey, SkyKey> { +// TODO(nharmata): Unify with UnfilteredUnboundedDepsSkyKeyVisitor. +class UnfilteredTransitiveTraversalValueDTCVisitor extends AbstractSkyKeyParallelVisitor<SkyKey> { private final SkyQueryEnvironment env; - private final Uniquifier<SkyKey> uniquifier; - private TransitiveTraversalValueDTCVisitor( + private UnfilteredTransitiveTraversalValueDTCVisitor( SkyQueryEnvironment env, Uniquifier<SkyKey> uniquifier, int processResultsBatchSize, AggregateAllCallback<SkyKey, ImmutableSet<SkyKey>> aggregateAllCallback) { - super(aggregateAllCallback, ParallelSkyQueryUtils.VISIT_BATCH_SIZE, processResultsBatchSize); + super( + uniquifier, + aggregateAllCallback, + ParallelSkyQueryUtils.VISIT_BATCH_SIZE, + processResultsBatchSize); this.env = env; - this.uniquifier = uniquifier; } static class Factory implements ParallelVisitor.Factory { @@ -61,7 +64,7 @@ @Override public ParallelVisitor<SkyKey, SkyKey> create() { - return new TransitiveTraversalValueDTCVisitor( + return new UnfilteredTransitiveTraversalValueDTCVisitor( env, uniquifier, processResultsBatchSize, aggregateAllCallback); } } @@ -75,7 +78,7 @@ @Override protected Visit getVisitResult(Iterable<SkyKey> ttvKeys) throws InterruptedException { - Multimap<SkyKey, SkyKey> deps = env.getDirectDepsOfSkyKeys(ttvKeys); + Multimap<SkyKey, SkyKey> deps = env.getUnfilteredDirectDepsOfSkyKeys(ttvKeys); return new Visit( /*keysToUseForResult=*/ deps.keySet(), /*keysToVisit=*/ deps.values() @@ -90,9 +93,4 @@ Preconditions.checkState(Iterables.all(keys, SkyQueryEnvironment.IS_TTV), keys); return keys; } - - @Override - protected ImmutableList<SkyKey> getUniqueValues(Iterable<SkyKey> values) throws QueryException { - return uniquifier.unique(values); - } }