diff options
7 files changed, 755 insertions, 580 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractEdgeVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractEdgeVisitor.java new file mode 100644 index 0000000000..dd689f0f06 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractEdgeVisitor.java @@ -0,0 +1,100 @@ +// Copyright 2016 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 static com.google.common.collect.ImmutableSet.toImmutableSet; + +import com.google.common.collect.ArrayListMultimap; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.common.collect.ListMultimap; +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.packages.Target; +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.Set; + +/** Helper class to traverse edges, processing targets. */ +abstract class AbstractEdgeVisitor<T> extends ParallelVisitor<T, Target> { + private static final int PROCESS_RESULTS_BATCH_SIZE = SkyQueryEnvironment.BATCH_CALLBACK_SIZE; + + protected final SkyQueryEnvironment env; + protected final MultisetSemaphore<PackageIdentifier> packageSemaphore; + + protected AbstractEdgeVisitor( + SkyQueryEnvironment env, + Callback<Target> callback, + MultisetSemaphore<PackageIdentifier> packageSemaphore) { + super(callback, ParallelSkyQueryUtils.VISIT_BATCH_SIZE, PROCESS_RESULTS_BATCH_SIZE); + this.env = env; + this.packageSemaphore = packageSemaphore; + } + + @Override + protected void processPartialResults( + Iterable<SkyKey> keysToUseForResult, Callback<Target> callback) + throws QueryException, InterruptedException { + Multimap<SkyKey, SkyKey> packageKeyToTargetKeyMap = + env.makePackageKeyToTargetKeyMap(keysToUseForResult); + Set<PackageIdentifier> pkgIdsNeededForResult = + packageKeyToTargetKeyMap + .keySet() + .stream() + .map(SkyQueryEnvironment.PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER) + .collect(toImmutableSet()); + packageSemaphore.acquireAll(pkgIdsNeededForResult); + try { + callback.process( + env.makeTargetsFromPackageKeyToTargetKeyMap(packageKeyToTargetKeyMap).values()); + } finally { + packageSemaphore.releaseAll(pkgIdsNeededForResult); + } + } + + protected abstract SkyKey getNewNodeFromEdge(T visit); + + @Override + protected Iterable<Task> getVisitTasks(Collection<T> pendingVisits) { + // Group pending visitation by the package of the new node, since we'll be targetfying the + // node during the visitation. + ListMultimap<PackageIdentifier, T> visitsByPackage = ArrayListMultimap.create(); + for (T visit : pendingVisits) { + Label label = SkyQueryEnvironment.SKYKEY_TO_LABEL.apply(getNewNodeFromEdge(visit)); + if (label != null) { + visitsByPackage.put(label.getPackageIdentifier(), visit); + } + } + + ImmutableList.Builder<Task> builder = ImmutableList.builder(); + + // A couple notes here: + // (i) ArrayListMultimap#values returns the values grouped by key, which is exactly what we + // want. + // (ii) ArrayListMultimap#values returns a Collection view, so we make a copy to avoid + // accidentally retaining the entire ArrayListMultimap object. + for (Iterable<T> visitBatch : + Iterables.partition( + ImmutableList.copyOf(visitsByPackage.values()), + ParallelSkyQueryUtils.VISIT_BATCH_SIZE)) { + builder.add(new VisitTask(visitBatch)); + } + + return builder.build(); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractSkyKeyParallelVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractSkyKeyParallelVisitor.java new file mode 100644 index 0000000000..972e6703c6 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractSkyKeyParallelVisitor.java @@ -0,0 +1,38 @@ +// Copyright 2016 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.collect.ImmutableList; +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; + +/** A {@link ParallelVisitor} whose visitations occur on {@link SkyKey}s. */ +public abstract class AbstractSkyKeyParallelVisitor<T> extends ParallelVisitor<SkyKey, T> { + private final Uniquifier<SkyKey> uniquifier; + + protected AbstractSkyKeyParallelVisitor( + Uniquifier<SkyKey> uniquifier, + Callback<T> callback, + int visitBatchSize, + int processResultsBatchSize) { + super(callback, visitBatchSize, processResultsBatchSize); + this.uniquifier = uniquifier; + } + + @Override + protected ImmutableList<SkyKey> getUniqueValues(Iterable<SkyKey> values) { + return uniquifier.unique(values); + } +} 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 b14f69bb11..516d2e6f84 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 @@ -13,46 +13,29 @@ // limitations under the License. package com.google.devtools.build.lib.query2; -import static com.google.common.collect.ImmutableSet.toImmutableSet; - import com.google.common.annotations.VisibleForTesting; import com.google.common.base.Function; -import com.google.common.base.Preconditions; import com.google.common.base.Predicate; import com.google.common.base.Predicates; -import com.google.common.collect.ArrayListMultimap; -import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; -import com.google.common.collect.ListMultimap; -import com.google.common.collect.Multimap; -import com.google.common.collect.Streams; -import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.cmdline.PackageIdentifier; -import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet; import com.google.devtools.build.lib.concurrent.MultisetSemaphore; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; import com.google.devtools.build.lib.packages.Target; import com.google.devtools.build.lib.query2.engine.Callback; -import com.google.devtools.build.lib.query2.engine.MinDepthUniquifier; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ThreadSafeMutableSet; 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.QueryUtil; import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback; -import com.google.devtools.build.lib.query2.engine.QueryUtil.UniquifierImpl; 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.PackageValue; -import com.google.devtools.build.lib.skyframe.SkyFunctions; import com.google.devtools.build.lib.vfs.PathFragment; import com.google.devtools.build.skyframe.SkyKey; -import java.util.ArrayList; import java.util.Collection; import java.util.Collections; -import java.util.HashMap; -import java.util.Map; import java.util.Objects; import java.util.Set; import java.util.concurrent.ConcurrentHashMap; @@ -187,87 +170,11 @@ public class ParallelSkyQueryUtils { visitor.visitAndWaitForCompletion(env.getFileStateKeysForFileFragments(fileIdentifiers)); } - /** A {@link ParallelVisitor} whose visitations occur on {@link SkyKey}s. */ - public abstract static class AbstractSkyKeyParallelVisitor<T> extends ParallelVisitor<SkyKey, T> { - private final Uniquifier<SkyKey> uniquifier; - - protected AbstractSkyKeyParallelVisitor( - Uniquifier<SkyKey> uniquifier, - Callback<T> callback, - int visitBatchSize, - int processResultsBatchSize) { - super(callback, visitBatchSize, processResultsBatchSize); - this.uniquifier = uniquifier; - } - - @Override - protected ImmutableList<SkyKey> getUniqueValues(Iterable<SkyKey> values) { - return uniquifier.unique(values); - } - } - - /** A helper class that computes 'rbuildfiles(<blah>)' via BFS. */ - private static class RBuildFilesVisitor extends AbstractSkyKeyParallelVisitor<Target> { - - // Each target in the full output of 'rbuildfiles' corresponds to BUILD file InputFile of a - // unique package. So the processResultsBatchSize we choose to pass to the ParallelVisitor ctor - // influences how many packages each leaf task doing processPartialResults will have to - // deal with at once. A value of 100 was chosen experimentally. - private static final int PROCESS_RESULTS_BATCH_SIZE = 100; - private static final SkyKey EXTERNAL_PACKAGE_KEY = - PackageValue.key(Label.EXTERNAL_PACKAGE_IDENTIFIER); - private final SkyQueryEnvironment env; + static class DepAndRdep { + @Nullable final SkyKey dep; + final SkyKey rdep; - private RBuildFilesVisitor( - SkyQueryEnvironment env, - Uniquifier<SkyKey> uniquifier, - Callback<Target> callback) { - super(uniquifier, callback, VISIT_BATCH_SIZE, PROCESS_RESULTS_BATCH_SIZE); - this.env = env; - } - - @Override - protected Visit getVisitResult(Iterable<SkyKey> values) throws InterruptedException { - Collection<Iterable<SkyKey>> reverseDeps = env.graph.getReverseDeps(values).values(); - Set<SkyKey> keysToUseForResult = CompactHashSet.create(); - Set<SkyKey> keysToVisitNext = CompactHashSet.create(); - for (SkyKey rdep : Iterables.concat(reverseDeps)) { - if (rdep.functionName().equals(SkyFunctions.PACKAGE)) { - keysToUseForResult.add(rdep); - // Every package has a dep on the external package, so we need to include those edges too. - if (rdep.equals(EXTERNAL_PACKAGE_KEY)) { - keysToVisitNext.add(rdep); - } - } else if (!rdep.functionName().equals(SkyFunctions.PACKAGE_LOOKUP) - && !rdep.functionName().equals(SkyFunctions.GLOB)) { - // Packages may depend on the existence of subpackages, but these edges aren't relevant to - // rbuildfiles. They may also depend on files transitively through globs, but these cannot - // be included in load statements and so we don't traverse through these either. - keysToVisitNext.add(rdep); - } - } - return new Visit(keysToUseForResult, keysToVisitNext); - } - - @Override - protected void processPartialResults( - Iterable<SkyKey> keysToUseForResult, Callback<Target> callback) - throws QueryException, InterruptedException { - env.getBuildFileTargetsForPackageKeysAndProcessViaCallback(keysToUseForResult, callback); - } - - @Override - protected Iterable<SkyKey> preprocessInitialVisit(Iterable<SkyKey> keys) { - return keys; - } - } - - private static class DepAndRdep { - @Nullable - private final SkyKey dep; - private final SkyKey rdep; - - private DepAndRdep(@Nullable SkyKey dep, SkyKey rdep) { + DepAndRdep(@Nullable SkyKey dep, SkyKey rdep) { this.dep = dep; this.rdep = rdep; } @@ -290,495 +197,16 @@ public class ParallelSkyQueryUtils { } } - private abstract static class AbstractRdepsVisitor<T> extends ParallelVisitor<T, Target> { - private static final int PROCESS_RESULTS_BATCH_SIZE = SkyQueryEnvironment.BATCH_CALLBACK_SIZE; - - protected final SkyQueryEnvironment env; - protected final MultisetSemaphore<PackageIdentifier> packageSemaphore; - - protected AbstractRdepsVisitor( - SkyQueryEnvironment env, - Callback<Target> callback, - MultisetSemaphore<PackageIdentifier> packageSemaphore) { - super(callback, VISIT_BATCH_SIZE, PROCESS_RESULTS_BATCH_SIZE); - this.env = env; - this.packageSemaphore = packageSemaphore; - } - - @Override - protected void processPartialResults( - Iterable<SkyKey> keysToUseForResult, Callback<Target> callback) - throws QueryException, InterruptedException { - Multimap<SkyKey, SkyKey> packageKeyToTargetKeyMap = - env.makePackageKeyToTargetKeyMap(keysToUseForResult); - Set<PackageIdentifier> pkgIdsNeededForResult = - packageKeyToTargetKeyMap - .keySet() - .stream() - .map(SkyQueryEnvironment.PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER) - .collect(toImmutableSet()); - packageSemaphore.acquireAll(pkgIdsNeededForResult); - try { - callback.process( - env.makeTargetsFromPackageKeyToTargetKeyMap(packageKeyToTargetKeyMap).values()); - } finally { - packageSemaphore.releaseAll(pkgIdsNeededForResult); - } - } - - protected abstract SkyKey getRdepOfVisit(T visit); - - @Override - protected Iterable<Task> getVisitTasks(Collection<T> pendingVisits) { - // Group pending visitation by the package of the rdep, since we'll be targetfying the - // rdep during the visitation. - ListMultimap<PackageIdentifier, T> visitsByPackage = ArrayListMultimap.create(); - for (T visit : pendingVisits) { - Label label = SkyQueryEnvironment.SKYKEY_TO_LABEL.apply(getRdepOfVisit(visit)); - if (label != null) { - visitsByPackage.put(label.getPackageIdentifier(), visit); - } - } - - ImmutableList.Builder<Task> builder = ImmutableList.builder(); - - // A couple notes here: - // (i) ArrayListMultimap#values returns the values grouped by key, which is exactly what we - // want. - // (ii) ArrayListMultimap#values returns a Collection view, so we make a copy to avoid - // accidentally retaining the entire ArrayListMultimap object. - for (Iterable<T> visitBatch : - Iterables.partition(ImmutableList.copyOf(visitsByPackage.values()), VISIT_BATCH_SIZE)) { - builder.add(new VisitTask(visitBatch)); - } - - return builder.build(); - } - } - - /** - * A helper class that computes unbounded 'allrdeps(<expr>)' or - * 'rdeps(<precomputed-universe>, <expr>)' via BFS. - * - * <p>The visitor uses {@link DepAndRdep} to keep track the nodes to visit and avoid dealing with - * targetification of reverse deps until they are needed. The rdep node itself is needed to filter - * out disallowed deps later. Compared against the approach using a single SkyKey, it consumes 16 - * more bytes in a 64-bit environment for each edge. However it defers the need to load all the - * packages which have at least a target as a rdep of the current batch, thus greatly reduces the - * risk of OOMs. The additional memory usage should not be a large concern here, as even with 10M - * edges, the memory overhead is around 160M, and the memory can be reclaimed by regular GC. - */ - private static class RdepsUnboundedVisitor extends AbstractRdepsVisitor<DepAndRdep> { - /** - * A {@link Uniquifier} for visitations. Solely used for {@link #getUniqueValues}, which - * actually isn't that useful. See the method javadoc. - */ - private final Uniquifier<DepAndRdep> depAndRdepUniquifier; - /** - * A {@link Uniquifier} for *valid* visitations of rdeps. {@code env}'s dependency filter might - * mean that some rdep edges are invalid, meaning that any individual {@link DepAndRdep} - * visitation may actually be invalid. Because the same rdep can be reached through more than - * one reverse edge, it'd be incorrect to naively dedupe visitations solely based on the rdep. - */ - private final Uniquifier<SkyKey> validRdepUniquifier; - private final Predicate<SkyKey> universe; - - private RdepsUnboundedVisitor( - SkyQueryEnvironment env, - Uniquifier<DepAndRdep> depAndRdepUniquifier, - Uniquifier<SkyKey> validRdepUniquifier, - Predicate<SkyKey> universe, - Callback<Target> callback, - MultisetSemaphore<PackageIdentifier> packageSemaphore) { - super(env, callback, packageSemaphore); - this.depAndRdepUniquifier = depAndRdepUniquifier; - this.validRdepUniquifier = validRdepUniquifier; - this.universe = universe; - } - - /** - * A {@link Factory} for {@link RdepsUnboundedVisitor} instances, each of which will be used - * to perform visitation of the reverse transitive closure of the {@link Target}s passed in a - * single {@link Callback#process} call. Note that all the created instances share the same - * {@link Uniquifier} so that we don't visit the same Skyframe node more than once. - */ - private static class Factory implements ParallelVisitor.Factory { - private final SkyQueryEnvironment env; - private final Uniquifier<DepAndRdep> depAndRdepUniquifier; - private final Uniquifier<SkyKey> validRdepUniquifier; - private final Predicate<SkyKey> universe; - private final Callback<Target> callback; - private final MultisetSemaphore<PackageIdentifier> packageSemaphore; - - private Factory( - SkyQueryEnvironment env, - Predicate<SkyKey> universe, - Callback<Target> callback, - MultisetSemaphore<PackageIdentifier> packageSemaphore) { - this.env = env; - this.universe = universe; - this.depAndRdepUniquifier = new UniquifierImpl<>(depAndRdep -> depAndRdep); - this.validRdepUniquifier = env.createSkyKeyUniquifier(); - this.callback = callback; - this.packageSemaphore = packageSemaphore; - } - - @Override - public ParallelVisitor<DepAndRdep, Target> create() { - return new RdepsUnboundedVisitor( - env, depAndRdepUniquifier, validRdepUniquifier, universe, callback, packageSemaphore); - } - } - - @Override - protected Visit getVisitResult(Iterable<DepAndRdep> depAndRdeps) throws InterruptedException { - Collection<SkyKey> validRdeps = new ArrayList<>(); - - // Multimap of dep to all the reverse deps in this visitation. Used to filter out the - // disallowed deps. - Multimap<SkyKey, SkyKey> reverseDepMultimap = ArrayListMultimap.create(); - for (DepAndRdep depAndRdep : depAndRdeps) { - // The "roots" of our visitation (see #preprocessInitialVisit) have a null 'dep' field. - if (depAndRdep.dep == null) { - validRdeps.add(depAndRdep.rdep); - } else { - reverseDepMultimap.put(depAndRdep.dep, depAndRdep.rdep); - } - } - - Multimap<SkyKey, SkyKey> packageKeyToTargetKeyMap = - env.makePackageKeyToTargetKeyMap(Iterables.concat(reverseDepMultimap.values())); - Set<PackageIdentifier> pkgIdsNeededForTargetification = - packageKeyToTargetKeyMap - .keySet() - .stream() - .map(SkyQueryEnvironment.PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER) - .collect(toImmutableSet()); - packageSemaphore.acquireAll(pkgIdsNeededForTargetification); - - try { - // Filter out disallowed deps. We cannot defer the targetification any further as we do not - // want to retrieve the rdeps of unwanted nodes (targets). - if (!reverseDepMultimap.isEmpty()) { - Collection<Target> filteredTargets = - env.filterRawReverseDepsOfTransitiveTraversalKeys( - reverseDepMultimap.asMap(), packageKeyToTargetKeyMap); - filteredTargets - .stream() - .map(SkyQueryEnvironment.TARGET_TO_SKY_KEY) - .forEachOrdered(validRdeps::add); - } - } finally { - packageSemaphore.releaseAll(pkgIdsNeededForTargetification); - } - - ImmutableList<SkyKey> uniqueValidRdeps = validRdeps.stream() - .filter(validRdepUniquifier::unique) - .collect(ImmutableList.toImmutableList()); - - // Retrieve the reverse deps as SkyKeys and defer the targetification and filtering to next - // recursive visitation. - ImmutableList.Builder<DepAndRdep> depAndRdepsToVisitBuilder = ImmutableList.builder(); - env.graph.getReverseDeps(uniqueValidRdeps).entrySet() - .forEach(reverseDepsEntry -> depAndRdepsToVisitBuilder.addAll( - Iterables.transform( - Iterables.filter( - reverseDepsEntry.getValue(), - Predicates.and(SkyQueryEnvironment.IS_TTV, universe)), - rdep -> new DepAndRdep(reverseDepsEntry.getKey(), rdep)))); - - return new Visit( - /*keysToUseForResult=*/ uniqueValidRdeps, - /*keysToVisit=*/ depAndRdepsToVisitBuilder.build()); - } - - @Override - protected Iterable<DepAndRdep> preprocessInitialVisit(Iterable<SkyKey> keys) { - return Iterables.transform( - Iterables.filter(keys, k -> universe.apply(k)), - key -> new DepAndRdep(null, key)); - } + static class DepAndRdepAtDepth { + final DepAndRdep depAndRdep; + final int rdepDepth; - @Override - protected SkyKey getRdepOfVisit(DepAndRdep visit) { - return visit.rdep; - } - - @Override - protected ImmutableList<DepAndRdep> getUniqueValues(Iterable<DepAndRdep> depAndRdeps) { - // See the javadoc for 'validRdepUniquifier'. - // - // N.B. - Except for the visitation roots, 'depAndRdepUniquifier' is actually completely - // unneeded in practice for ensuring literal unique {@link DepAndRdep} visitations. Valid rdep - // visitations are deduped in 'getVisitResult' using 'validRdepUniquifier', so there's - // actually no way the same DepAndRdep visitation can ever be returned from 'getVisitResult'. - // Still, we include an implementation of 'getUniqueValues' that is correct in isolation so as - // to not be depending on implementation details of 'ParallelVisitor'. - // - // Even so, there's value in not visiting a rdep if it's already been visited *validly* - // before. We use the intentionally racy {@link Uniquifier#uniquePure} to attempt to do this. - return depAndRdepUniquifier.unique( - Iterables.filter( - depAndRdeps, - depAndRdep -> validRdepUniquifier.uniquePure(depAndRdep.rdep))); - } - } - - private static class DepAndRdepAtDepth { - private final DepAndRdep depAndRdep; - private final int rdepDepth; - - private DepAndRdepAtDepth(DepAndRdep depAndRdep, int rdepDepth) { + DepAndRdepAtDepth(DepAndRdep depAndRdep, int rdepDepth) { this.depAndRdep = depAndRdep; this.rdepDepth = rdepDepth; } } - /** - * A helper class that computes bounded 'allrdeps(<expr>, <depth>)' or - * 'rdeps(<precomputed-universe>, <expr>, <depth>)' via BFS. - * - * <p>This is very similar to {@link RdepsUnboundedVisitor}. A lot of the same concerns apply here - * but there are additional subtle concerns about the correctness of the bounded traversal: just - * like for the sequential implementation of bounded allrdeps, we use {@link MinDepthUniquifier}. - */ - private static class RdepsBoundedVisitor extends AbstractRdepsVisitor<DepAndRdepAtDepth> { - private final int depth; - private final Uniquifier<DepAndRdepAtDepth> depAndRdepAtDepthUniquifier; - private final MinDepthUniquifier<SkyKey> validRdepMinDepthUniquifier; - private final Predicate<SkyKey> universe; - - private RdepsBoundedVisitor( - SkyQueryEnvironment env, - int depth, - Uniquifier<DepAndRdepAtDepth> depAndRdepAtDepthUniquifier, - MinDepthUniquifier<SkyKey> validRdepMinDepthUniquifier, - Predicate<SkyKey> universe, - Callback<Target> callback, - MultisetSemaphore<PackageIdentifier> packageSemaphore) { - super(env, callback, packageSemaphore); - this.depth = depth; - this.depAndRdepAtDepthUniquifier = depAndRdepAtDepthUniquifier; - this.validRdepMinDepthUniquifier = validRdepMinDepthUniquifier; - this.universe = universe; - } - - private static class Factory implements ParallelVisitor.Factory { - private final SkyQueryEnvironment env; - private final int depth; - private final Uniquifier<DepAndRdepAtDepth> depAndRdepAtDepthUniquifier; - private final MinDepthUniquifier<SkyKey> validRdepMinDepthUniquifier; - private final Predicate<SkyKey> universe; - private final Callback<Target> callback; - private final MultisetSemaphore<PackageIdentifier> packageSemaphore; - - private Factory( - SkyQueryEnvironment env, - int depth, - Predicate<SkyKey> universe, - Callback<Target> callback, - MultisetSemaphore<PackageIdentifier> packageSemaphore) { - this.env = env; - this.depth = depth; - this.universe = universe; - this.depAndRdepAtDepthUniquifier = - new UniquifierImpl<>(depAndRdepAtDepth -> depAndRdepAtDepth); - this.validRdepMinDepthUniquifier = env.createMinDepthSkyKeyUniquifier(); - this.callback = callback; - this.packageSemaphore = packageSemaphore; - } - - @Override - public ParallelVisitor<DepAndRdepAtDepth, Target> create() { - return new RdepsBoundedVisitor( - env, - depth, - depAndRdepAtDepthUniquifier, - validRdepMinDepthUniquifier, - universe, - callback, - packageSemaphore); - } - } - - @Override - protected Visit getVisitResult(Iterable<DepAndRdepAtDepth> depAndRdepAtDepths) - throws InterruptedException { - Map<SkyKey, Integer> shallowestRdepDepthMap = new HashMap<>(); - depAndRdepAtDepths.forEach( - depAndRdepAtDepth -> shallowestRdepDepthMap.merge( - depAndRdepAtDepth.depAndRdep.rdep, depAndRdepAtDepth.rdepDepth, Integer::min)); - - Collection<SkyKey> validRdeps = new ArrayList<>(); - - // Multimap of dep to all the reverse deps in this visitation. Used to filter out the - // disallowed deps. - Multimap<SkyKey, SkyKey> reverseDepMultimap = ArrayListMultimap.create(); - for (DepAndRdepAtDepth depAndRdepAtDepth : depAndRdepAtDepths) { - // The "roots" of our visitation (see #preprocessInitialVisit) have a null 'dep' field. - if (depAndRdepAtDepth.depAndRdep.dep == null) { - validRdeps.add(depAndRdepAtDepth.depAndRdep.rdep); - } else { - reverseDepMultimap.put( - depAndRdepAtDepth.depAndRdep.dep, depAndRdepAtDepth.depAndRdep.rdep); - } - } - - Multimap<SkyKey, SkyKey> packageKeyToTargetKeyMap = - env.makePackageKeyToTargetKeyMap(Iterables.concat(reverseDepMultimap.values())); - Set<PackageIdentifier> pkgIdsNeededForTargetification = - packageKeyToTargetKeyMap - .keySet() - .stream() - .map(SkyQueryEnvironment.PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER) - .collect(toImmutableSet()); - packageSemaphore.acquireAll(pkgIdsNeededForTargetification); - - try { - // Filter out disallowed deps. We cannot defer the targetification any further as we do not - // want to retrieve the rdeps of unwanted nodes (targets). - if (!reverseDepMultimap.isEmpty()) { - Collection<Target> filteredTargets = - env.filterRawReverseDepsOfTransitiveTraversalKeys( - reverseDepMultimap.asMap(), packageKeyToTargetKeyMap); - filteredTargets - .stream() - .map(SkyQueryEnvironment.TARGET_TO_SKY_KEY) - .forEachOrdered(validRdeps::add); - } - } finally { - packageSemaphore.releaseAll(pkgIdsNeededForTargetification); - } - - ImmutableList<SkyKey> uniqueValidRdeps = validRdeps.stream() - .filter(validRdep -> validRdepMinDepthUniquifier.uniqueAtDepthLessThanOrEqualTo( - validRdep, shallowestRdepDepthMap.get(validRdep))) - .collect(ImmutableList.toImmutableList()); - - // Don't bother getting the rdeps of the rdeps that are already at the depth bound. - Iterable<SkyKey> uniqueValidRdepsBelowDepthBound = Iterables.filter( - uniqueValidRdeps, - uniqueValidRdep -> shallowestRdepDepthMap.get(uniqueValidRdep) < depth); - - // Retrieve the reverse deps as SkyKeys and defer the targetification and filtering to next - // recursive visitation. - Map<SkyKey, Iterable<SkyKey>> unfilteredRdepsOfRdeps = - env.graph.getReverseDeps(uniqueValidRdepsBelowDepthBound); - - ImmutableList.Builder<DepAndRdepAtDepth> depAndRdepAtDepthsToVisitBuilder = - ImmutableList.builder(); - unfilteredRdepsOfRdeps.entrySet().forEach(entry -> { - SkyKey rdep = entry.getKey(); - int depthOfRdepOfRdep = shallowestRdepDepthMap.get(rdep) + 1; - Streams.stream(entry.getValue()) - .filter(Predicates.and(SkyQueryEnvironment.IS_TTV, universe)) - .forEachOrdered(rdepOfRdep -> { - depAndRdepAtDepthsToVisitBuilder.add( - new DepAndRdepAtDepth(new DepAndRdep(rdep, rdepOfRdep), depthOfRdepOfRdep)); - }); - }); - - return new Visit( - /*keysToUseForResult=*/ uniqueValidRdeps, - /*keysToVisit=*/ depAndRdepAtDepthsToVisitBuilder.build()); - } - - @Override - protected Iterable<DepAndRdepAtDepth> preprocessInitialVisit(Iterable<SkyKey> keys) { - return Iterables.transform( - Iterables.filter(keys, k -> universe.apply(k)), - key -> new DepAndRdepAtDepth(new DepAndRdep(null, key), 0)); - } - - @Override - protected SkyKey getRdepOfVisit(DepAndRdepAtDepth visit) { - return visit.depAndRdep.rdep; - } - - @Override - protected ImmutableList<DepAndRdepAtDepth> getUniqueValues( - Iterable<DepAndRdepAtDepth> depAndRdepAtDepths) { - // See the comment in RdepsUnboundedVisitor#getUniqueValues. - return depAndRdepAtDepthUniquifier.unique( - Iterables.filter( - depAndRdepAtDepths, - depAndRdepAtDepth -> validRdepMinDepthUniquifier.uniqueAtDepthLessThanOrEqualToPure( - depAndRdepAtDepth.depAndRdep.rdep, depAndRdepAtDepth.rdepDepth))); - } - } - - /** - * Helper class that computes the TTV-only DTC of some given TTV keys, via BFS following all - * TTV->TTV dep edges. - */ - private static class TransitiveTraversalValueDTCVisitor extends ParallelVisitor<SkyKey, SkyKey> { - private final SkyQueryEnvironment env; - private final Uniquifier<SkyKey> uniquifier; - - private TransitiveTraversalValueDTCVisitor( - SkyQueryEnvironment env, - Uniquifier<SkyKey> uniquifier, - int processResultsBatchSize, - AggregateAllCallback<SkyKey, ImmutableSet<SkyKey>> aggregateAllCallback) { - super(aggregateAllCallback, VISIT_BATCH_SIZE, processResultsBatchSize); - this.env = env; - this.uniquifier = uniquifier; - } - - private static class Factory implements ParallelVisitor.Factory { - private final SkyQueryEnvironment env; - private final Uniquifier<SkyKey> uniquifier; - private final AggregateAllCallback<SkyKey, ImmutableSet<SkyKey>> aggregateAllCallback; - private final int processResultsBatchSize; - - private Factory( - SkyQueryEnvironment env, - Uniquifier<SkyKey> uniquifier, - int processResultsBatchSize, - AggregateAllCallback<SkyKey, ImmutableSet<SkyKey>> aggregateAllCallback) { - this.env = env; - this.uniquifier = uniquifier; - this.processResultsBatchSize = processResultsBatchSize; - this.aggregateAllCallback = aggregateAllCallback; - } - - @Override - public ParallelVisitor<SkyKey, SkyKey> create() { - return new TransitiveTraversalValueDTCVisitor( - env, uniquifier, processResultsBatchSize, aggregateAllCallback); - } - } - - @Override - protected void processPartialResults( - Iterable<SkyKey> keysToUseForResult, Callback<SkyKey> callback) - throws QueryException, InterruptedException { - callback.process(keysToUseForResult); - } - - @Override - protected Visit getVisitResult(Iterable<SkyKey> ttvKeys) throws InterruptedException { - Multimap<SkyKey, SkyKey> deps = env.getDirectDepsOfSkyKeys(ttvKeys); - return new Visit( - /*keysToUseForResult=*/ deps.keySet(), - /*keysToVisit=*/ deps.values().stream() - .filter(SkyQueryEnvironment.IS_TTV) - .collect(ImmutableList.toImmutableList())); - } - - @Override - protected Iterable<SkyKey> preprocessInitialVisit(Iterable<SkyKey> keys) { - // ParallelVisitorCallback passes in TTV keys. - Preconditions.checkState(Iterables.all(keys, SkyQueryEnvironment.IS_TTV), keys); - return keys; - } - - @Override - protected ImmutableList<SkyKey> getUniqueValues(Iterable<SkyKey> values) { - return uniquifier.unique(values); - } - } - /** Thread-safe {@link AggregateAllCallback} backed by a concurrent {@link Set}. */ @ThreadSafe private static class ThreadSafeAggregateAllSkyKeysCallback diff --git a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java new file mode 100644 index 0000000000..cd76b1b542 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesVisitor.java @@ -0,0 +1,81 @@ +// Copyright 2016 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.collect.Iterables; +import com.google.devtools.build.lib.cmdline.Label; +import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet; +import com.google.devtools.build.lib.packages.Target; +import com.google.devtools.build.lib.query2.engine.Callback; +import com.google.devtools.build.lib.query2.engine.QueryException; +import com.google.devtools.build.lib.query2.engine.Uniquifier; +import com.google.devtools.build.lib.skyframe.PackageValue; +import com.google.devtools.build.lib.skyframe.SkyFunctions; +import com.google.devtools.build.skyframe.SkyKey; +import java.util.Collection; +import java.util.Set; + +/** A helper class that computes 'rbuildfiles(<blah>)' via BFS. */ +class RBuildFilesVisitor extends AbstractSkyKeyParallelVisitor<Target> { + + // Each target in the full output of 'rbuildfiles' corresponds to BUILD file InputFile of a + // unique package. So the processResultsBatchSize we choose to pass to the ParallelVisitor ctor + // influences how many packages each leaf task doing processPartialResults will have to + // deal with at once. A value of 100 was chosen experimentally. + private static final int PROCESS_RESULTS_BATCH_SIZE = 100; + private static final SkyKey EXTERNAL_PACKAGE_KEY = + PackageValue.key(Label.EXTERNAL_PACKAGE_IDENTIFIER); + private final SkyQueryEnvironment env; + + RBuildFilesVisitor( + SkyQueryEnvironment env, Uniquifier<SkyKey> uniquifier, Callback<Target> callback) { + super(uniquifier, callback, ParallelSkyQueryUtils.VISIT_BATCH_SIZE, PROCESS_RESULTS_BATCH_SIZE); + this.env = env; + } + + @Override + protected Visit getVisitResult(Iterable<SkyKey> values) throws InterruptedException { + Collection<Iterable<SkyKey>> reverseDeps = env.graph.getReverseDeps(values).values(); + Set<SkyKey> keysToUseForResult = CompactHashSet.create(); + Set<SkyKey> keysToVisitNext = CompactHashSet.create(); + for (SkyKey rdep : Iterables.concat(reverseDeps)) { + if (rdep.functionName().equals(SkyFunctions.PACKAGE)) { + keysToUseForResult.add(rdep); + // Every package has a dep on the external package, so we need to include those edges too. + if (rdep.equals(EXTERNAL_PACKAGE_KEY)) { + keysToVisitNext.add(rdep); + } + } else if (!rdep.functionName().equals(SkyFunctions.PACKAGE_LOOKUP) + && !rdep.functionName().equals(SkyFunctions.GLOB)) { + // Packages may depend on the existence of subpackages, but these edges aren't relevant to + // rbuildfiles. They may also depend on files transitively through globs, but these cannot + // be included in load statements and so we don't traverse through these either. + keysToVisitNext.add(rdep); + } + } + return new Visit(keysToUseForResult, keysToVisitNext); + } + + @Override + protected void processPartialResults( + Iterable<SkyKey> keysToUseForResult, Callback<Target> callback) + throws QueryException, InterruptedException { + env.getBuildFileTargetsForPackageKeysAndProcessViaCallback(keysToUseForResult, callback); + } + + @Override + protected Iterable<SkyKey> preprocessInitialVisit(Iterable<SkyKey> keys) { + return keys; + } +} 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 new file mode 100644 index 0000000000..d6c59c642c --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java @@ -0,0 +1,223 @@ +// Copyright 2016 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 static com.google.common.collect.ImmutableSet.toImmutableSet; + +import com.google.common.base.Predicate; +import com.google.common.base.Predicates; +import com.google.common.collect.ArrayListMultimap; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.common.collect.Multimap; +import com.google.common.collect.Streams; +import com.google.devtools.build.lib.cmdline.PackageIdentifier; +import com.google.devtools.build.lib.concurrent.MultisetSemaphore; +import com.google.devtools.build.lib.packages.Target; +import com.google.devtools.build.lib.query2.ParallelSkyQueryUtils.DepAndRdep; +import com.google.devtools.build.lib.query2.ParallelSkyQueryUtils.DepAndRdepAtDepth; +import com.google.devtools.build.lib.query2.engine.Callback; +import com.google.devtools.build.lib.query2.engine.MinDepthUniquifier; +import com.google.devtools.build.lib.query2.engine.QueryUtil.UniquifierImpl; +import com.google.devtools.build.lib.query2.engine.Uniquifier; +import com.google.devtools.build.skyframe.SkyKey; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.Map; +import java.util.Set; + +/** + * A helper class that computes bounded 'allrdeps(<expr>, <depth>)' or + * 'rdeps(<precomputed-universe>, <expr>, <depth>)' via BFS. + * + * <p>This is very similar to {@link RdepsUnboundedVisitor}. A lot of the same concerns apply here + * but there are additional subtle concerns about the correctness of the bounded traversal: just + * like for the sequential implementation of bounded allrdeps, we use {@link MinDepthUniquifier}. + */ +class RdepsBoundedVisitor extends AbstractEdgeVisitor<DepAndRdepAtDepth> { + private final int depth; + private final Uniquifier<DepAndRdepAtDepth> depAndRdepAtDepthUniquifier; + private final MinDepthUniquifier<SkyKey> validRdepMinDepthUniquifier; + private final Predicate<SkyKey> universe; + + private RdepsBoundedVisitor( + SkyQueryEnvironment env, + int depth, + Uniquifier<DepAndRdepAtDepth> depAndRdepAtDepthUniquifier, + MinDepthUniquifier<SkyKey> validRdepMinDepthUniquifier, + Predicate<SkyKey> universe, + Callback<Target> callback, + MultisetSemaphore<PackageIdentifier> packageSemaphore) { + super(env, callback, packageSemaphore); + this.depth = depth; + this.depAndRdepAtDepthUniquifier = depAndRdepAtDepthUniquifier; + this.validRdepMinDepthUniquifier = validRdepMinDepthUniquifier; + this.universe = universe; + } + + static class Factory implements ParallelVisitor.Factory { + private final SkyQueryEnvironment env; + private final int depth; + private final Uniquifier<DepAndRdepAtDepth> depAndRdepAtDepthUniquifier; + private final MinDepthUniquifier<SkyKey> validRdepMinDepthUniquifier; + private final Predicate<SkyKey> universe; + private final Callback<Target> callback; + private final MultisetSemaphore<PackageIdentifier> packageSemaphore; + + Factory( + SkyQueryEnvironment env, + int depth, + Predicate<SkyKey> universe, + Callback<Target> callback, + MultisetSemaphore<PackageIdentifier> packageSemaphore) { + this.env = env; + this.depth = depth; + this.universe = universe; + this.depAndRdepAtDepthUniquifier = + new UniquifierImpl<>(depAndRdepAtDepth -> depAndRdepAtDepth); + this.validRdepMinDepthUniquifier = env.createMinDepthSkyKeyUniquifier(); + this.callback = callback; + this.packageSemaphore = packageSemaphore; + } + + @Override + public ParallelVisitor<DepAndRdepAtDepth, Target> create() { + return new RdepsBoundedVisitor( + env, + depth, + depAndRdepAtDepthUniquifier, + validRdepMinDepthUniquifier, + universe, + callback, + packageSemaphore); + } + } + + @Override + protected Visit getVisitResult(Iterable<DepAndRdepAtDepth> depAndRdepAtDepths) + throws InterruptedException { + Map<SkyKey, Integer> shallowestRdepDepthMap = new HashMap<>(); + depAndRdepAtDepths.forEach( + depAndRdepAtDepth -> + shallowestRdepDepthMap.merge( + depAndRdepAtDepth.depAndRdep.rdep, depAndRdepAtDepth.rdepDepth, Integer::min)); + + Collection<SkyKey> validRdeps = new ArrayList<>(); + + // Multimap of dep to all the reverse deps in this visitation. Used to filter out the + // disallowed deps. + Multimap<SkyKey, SkyKey> reverseDepMultimap = ArrayListMultimap.create(); + for (DepAndRdepAtDepth depAndRdepAtDepth : depAndRdepAtDepths) { + // The "roots" of our visitation (see #preprocessInitialVisit) have a null 'dep' field. + if (depAndRdepAtDepth.depAndRdep.dep == null) { + validRdeps.add(depAndRdepAtDepth.depAndRdep.rdep); + } else { + reverseDepMultimap.put(depAndRdepAtDepth.depAndRdep.dep, depAndRdepAtDepth.depAndRdep.rdep); + } + } + + Multimap<SkyKey, SkyKey> packageKeyToTargetKeyMap = + env.makePackageKeyToTargetKeyMap(Iterables.concat(reverseDepMultimap.values())); + Set<PackageIdentifier> pkgIdsNeededForTargetification = + packageKeyToTargetKeyMap + .keySet() + .stream() + .map(SkyQueryEnvironment.PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER) + .collect(toImmutableSet()); + packageSemaphore.acquireAll(pkgIdsNeededForTargetification); + + try { + // Filter out disallowed deps. We cannot defer the targetification any further as we do not + // want to retrieve the rdeps of unwanted nodes (targets). + if (!reverseDepMultimap.isEmpty()) { + Collection<Target> filteredTargets = + env.filterRawReverseDepsOfTransitiveTraversalKeys( + reverseDepMultimap.asMap(), packageKeyToTargetKeyMap); + filteredTargets + .stream() + .map(SkyQueryEnvironment.TARGET_TO_SKY_KEY) + .forEachOrdered(validRdeps::add); + } + } finally { + packageSemaphore.releaseAll(pkgIdsNeededForTargetification); + } + + ImmutableList<SkyKey> uniqueValidRdeps = + validRdeps + .stream() + .filter( + validRdep -> + validRdepMinDepthUniquifier.uniqueAtDepthLessThanOrEqualTo( + validRdep, shallowestRdepDepthMap.get(validRdep))) + .collect(ImmutableList.toImmutableList()); + + // Don't bother getting the rdeps of the rdeps that are already at the depth bound. + Iterable<SkyKey> uniqueValidRdepsBelowDepthBound = + Iterables.filter( + uniqueValidRdeps, + uniqueValidRdep -> shallowestRdepDepthMap.get(uniqueValidRdep) < depth); + + // Retrieve the reverse deps as SkyKeys and defer the targetification and filtering to next + // recursive visitation. + Map<SkyKey, Iterable<SkyKey>> unfilteredRdepsOfRdeps = + env.graph.getReverseDeps(uniqueValidRdepsBelowDepthBound); + + ImmutableList.Builder<DepAndRdepAtDepth> depAndRdepAtDepthsToVisitBuilder = + ImmutableList.builder(); + unfilteredRdepsOfRdeps + .entrySet() + .forEach( + entry -> { + SkyKey rdep = entry.getKey(); + int depthOfRdepOfRdep = shallowestRdepDepthMap.get(rdep) + 1; + Streams.stream(entry.getValue()) + .filter(Predicates.and(SkyQueryEnvironment.IS_TTV, universe)) + .forEachOrdered( + rdepOfRdep -> { + depAndRdepAtDepthsToVisitBuilder.add( + new DepAndRdepAtDepth( + new DepAndRdep(rdep, rdepOfRdep), depthOfRdepOfRdep)); + }); + }); + + return new Visit( + /*keysToUseForResult=*/ uniqueValidRdeps, + /*keysToVisit=*/ depAndRdepAtDepthsToVisitBuilder.build()); + } + + @Override + protected Iterable<DepAndRdepAtDepth> preprocessInitialVisit(Iterable<SkyKey> keys) { + return Iterables.transform( + Iterables.filter(keys, k -> universe.apply(k)), + key -> new DepAndRdepAtDepth(new DepAndRdep(null, key), 0)); + } + + @Override + protected SkyKey getNewNodeFromEdge(DepAndRdepAtDepth visit) { + return visit.depAndRdep.rdep; + } + + @Override + protected ImmutableList<DepAndRdepAtDepth> getUniqueValues( + Iterable<DepAndRdepAtDepth> depAndRdepAtDepths) { + // See the comment in RdepsUnboundedVisitor#getUniqueValues. + return depAndRdepAtDepthUniquifier.unique( + Iterables.filter( + depAndRdepAtDepths, + depAndRdepAtDepth -> + validRdepMinDepthUniquifier.uniqueAtDepthLessThanOrEqualToPure( + depAndRdepAtDepth.depAndRdep.rdep, depAndRdepAtDepth.rdepDepth))); + } +} 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 new file mode 100644 index 0000000000..e2720490ef --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java @@ -0,0 +1,207 @@ +// Copyright 2016 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 static com.google.common.collect.ImmutableSet.toImmutableSet; + +import com.google.common.base.Predicate; +import com.google.common.base.Predicates; +import com.google.common.collect.ArrayListMultimap; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.common.collect.Multimap; +import com.google.devtools.build.lib.cmdline.PackageIdentifier; +import com.google.devtools.build.lib.concurrent.MultisetSemaphore; +import com.google.devtools.build.lib.packages.Target; +import com.google.devtools.build.lib.query2.ParallelSkyQueryUtils.DepAndRdep; +import com.google.devtools.build.lib.query2.engine.Callback; +import com.google.devtools.build.lib.query2.engine.QueryUtil.UniquifierImpl; +import com.google.devtools.build.lib.query2.engine.Uniquifier; +import com.google.devtools.build.skyframe.SkyKey; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Set; + +/** + * A helper class that computes unbounded 'allrdeps(<expr>)' or 'rdeps(<precomputed-universe>, + * <expr>)' via BFS. + * + * <p>The visitor uses {@link DepAndRdep} to keep track the nodes to visit and avoid dealing with + * targetification of reverse deps until they are needed. The rdep node itself is needed to filter + * out disallowed deps later. Compared against the approach using a single SkyKey, it consumes 16 + * more bytes in a 64-bit environment for each edge. However it defers the need to load all the + * packages which have at least a target as a rdep of the current batch, thus greatly reduces the + * risk of OOMs. The additional memory usage should not be a large concern here, as even with 10M + * edges, the memory overhead is around 160M, and the memory can be reclaimed by regular GC. + */ +class RdepsUnboundedVisitor extends AbstractEdgeVisitor<DepAndRdep> { + /** + * A {@link Uniquifier} for visitations. Solely used for {@link #getUniqueValues}, which actually + * isn't that useful. See the method javadoc. + */ + private final Uniquifier<DepAndRdep> depAndRdepUniquifier; + /** + * A {@link Uniquifier} for *valid* visitations of rdeps. {@code env}'s dependency filter might + * mean that some rdep edges are invalid, meaning that any individual {@link DepAndRdep} + * visitation may actually be invalid. Because the same rdep can be reached through more than one + * reverse edge, it'd be incorrect to naively dedupe visitations solely based on the rdep. + */ + private final Uniquifier<SkyKey> validRdepUniquifier; + + private final Predicate<SkyKey> universe; + + RdepsUnboundedVisitor( + SkyQueryEnvironment env, + Uniquifier<DepAndRdep> depAndRdepUniquifier, + Uniquifier<SkyKey> validRdepUniquifier, + Predicate<SkyKey> universe, + Callback<Target> callback, + MultisetSemaphore<PackageIdentifier> packageSemaphore) { + super(env, callback, packageSemaphore); + this.depAndRdepUniquifier = depAndRdepUniquifier; + this.validRdepUniquifier = validRdepUniquifier; + this.universe = universe; + } + + /** + * A {@link Factory} for {@link RdepsUnboundedVisitor} instances, each of which will be used to + * perform visitation of the reverse transitive closure of the {@link Target}s passed in a single + * {@link Callback#process} call. Note that all the created instances share the same {@link + * Uniquifier} so that we don't visit the same Skyframe node more than once. + */ + static class Factory implements ParallelVisitor.Factory { + private final SkyQueryEnvironment env; + private final Uniquifier<DepAndRdep> depAndRdepUniquifier; + private final Uniquifier<SkyKey> validRdepUniquifier; + private final Predicate<SkyKey> universe; + private final Callback<Target> callback; + private final MultisetSemaphore<PackageIdentifier> packageSemaphore; + + Factory( + SkyQueryEnvironment env, + Predicate<SkyKey> universe, + Callback<Target> callback, + MultisetSemaphore<PackageIdentifier> packageSemaphore) { + this.env = env; + this.universe = universe; + this.depAndRdepUniquifier = new UniquifierImpl<>(depAndRdep -> depAndRdep); + this.validRdepUniquifier = env.createSkyKeyUniquifier(); + this.callback = callback; + this.packageSemaphore = packageSemaphore; + } + + @Override + public ParallelVisitor<DepAndRdep, Target> create() { + return new RdepsUnboundedVisitor( + env, depAndRdepUniquifier, validRdepUniquifier, universe, callback, packageSemaphore); + } + } + + @Override + protected Visit getVisitResult(Iterable<DepAndRdep> depAndRdeps) throws InterruptedException { + Collection<SkyKey> validRdeps = new ArrayList<>(); + + // Multimap of dep to all the reverse deps in this visitation. Used to filter out the + // disallowed deps. + Multimap<SkyKey, SkyKey> reverseDepMultimap = ArrayListMultimap.create(); + for (DepAndRdep depAndRdep : depAndRdeps) { + // The "roots" of our visitation (see #preprocessInitialVisit) have a null 'dep' field. + if (depAndRdep.dep == null) { + validRdeps.add(depAndRdep.rdep); + } else { + reverseDepMultimap.put(depAndRdep.dep, depAndRdep.rdep); + } + } + + Multimap<SkyKey, SkyKey> packageKeyToTargetKeyMap = + env.makePackageKeyToTargetKeyMap(Iterables.concat(reverseDepMultimap.values())); + Set<PackageIdentifier> pkgIdsNeededForTargetification = + packageKeyToTargetKeyMap + .keySet() + .stream() + .map(SkyQueryEnvironment.PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER) + .collect(toImmutableSet()); + packageSemaphore.acquireAll(pkgIdsNeededForTargetification); + + try { + // Filter out disallowed deps. We cannot defer the targetification any further as we do not + // want to retrieve the rdeps of unwanted nodes (targets). + if (!reverseDepMultimap.isEmpty()) { + Collection<Target> filteredTargets = + env.filterRawReverseDepsOfTransitiveTraversalKeys( + reverseDepMultimap.asMap(), packageKeyToTargetKeyMap); + filteredTargets + .stream() + .map(SkyQueryEnvironment.TARGET_TO_SKY_KEY) + .forEachOrdered(validRdeps::add); + } + } finally { + packageSemaphore.releaseAll(pkgIdsNeededForTargetification); + } + + ImmutableList<SkyKey> uniqueValidRdeps = + validRdeps + .stream() + .filter(validRdepUniquifier::unique) + .collect(ImmutableList.toImmutableList()); + + // Retrieve the reverse deps as SkyKeys and defer the targetification and filtering to next + // recursive visitation. + ImmutableList.Builder<DepAndRdep> depAndRdepsToVisitBuilder = ImmutableList.builder(); + env.graph + .getReverseDeps(uniqueValidRdeps) + .entrySet() + .forEach( + reverseDepsEntry -> + depAndRdepsToVisitBuilder.addAll( + Iterables.transform( + Iterables.filter( + reverseDepsEntry.getValue(), + Predicates.and(SkyQueryEnvironment.IS_TTV, universe)), + rdep -> new DepAndRdep(reverseDepsEntry.getKey(), rdep)))); + + return new Visit( + /*keysToUseForResult=*/ uniqueValidRdeps, + /*keysToVisit=*/ depAndRdepsToVisitBuilder.build()); + } + + @Override + protected Iterable<DepAndRdep> preprocessInitialVisit(Iterable<SkyKey> keys) { + return Iterables.transform( + Iterables.filter(keys, k -> universe.apply(k)), key -> new DepAndRdep(null, key)); + } + + @Override + protected SkyKey getNewNodeFromEdge(DepAndRdep visit) { + return visit.rdep; + } + + @Override + protected ImmutableList<DepAndRdep> getUniqueValues(Iterable<DepAndRdep> depAndRdeps) { + // See the javadoc for 'validRdepUniquifier'. + // + // N.B. - Except for the visitation roots, 'depAndRdepUniquifier' is actually completely + // unneeded in practice for ensuring literal unique {@link DepAndRdep} visitations. Valid rdep + // visitations are deduped in 'getVisitResult' using 'validRdepUniquifier', so there's + // actually no way the same DepAndRdep visitation can ever be returned from 'getVisitResult'. + // Still, we include an implementation of 'getUniqueValues' that is correct in isolation so as + // to not be depending on implementation details of 'ParallelVisitor'. + // + // Even so, there's value in not visiting a rdep if it's already been visited *validly* + // before. We use the intentionally racy {@link Uniquifier#uniquePure} to attempt to do this. + return depAndRdepUniquifier.unique( + Iterables.filter( + depAndRdeps, depAndRdep -> validRdepUniquifier.uniquePure(depAndRdep.rdep))); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/TransitiveTraversalValueDTCVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/TransitiveTraversalValueDTCVisitor.java new file mode 100644 index 0000000000..1a5962c7c4 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/TransitiveTraversalValueDTCVisitor.java @@ -0,0 +1,98 @@ +// Copyright 2016 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.base.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +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.QueryException; +import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback; +import com.google.devtools.build.lib.query2.engine.Uniquifier; +import com.google.devtools.build.skyframe.SkyKey; + +/** + * Helper class that computes the TTV-only DTC of some given TTV keys, via BFS following all + * TTV->TTV dep edges. + */ +class TransitiveTraversalValueDTCVisitor extends ParallelVisitor<SkyKey, SkyKey> { + private final SkyQueryEnvironment env; + private final Uniquifier<SkyKey> uniquifier; + + private TransitiveTraversalValueDTCVisitor( + SkyQueryEnvironment env, + Uniquifier<SkyKey> uniquifier, + int processResultsBatchSize, + AggregateAllCallback<SkyKey, ImmutableSet<SkyKey>> aggregateAllCallback) { + super(aggregateAllCallback, ParallelSkyQueryUtils.VISIT_BATCH_SIZE, processResultsBatchSize); + this.env = env; + this.uniquifier = uniquifier; + } + + static class Factory implements ParallelVisitor.Factory { + private final SkyQueryEnvironment env; + private final Uniquifier<SkyKey> uniquifier; + private final AggregateAllCallback<SkyKey, ImmutableSet<SkyKey>> aggregateAllCallback; + private final int processResultsBatchSize; + + Factory( + SkyQueryEnvironment env, + Uniquifier<SkyKey> uniquifier, + int processResultsBatchSize, + AggregateAllCallback<SkyKey, ImmutableSet<SkyKey>> aggregateAllCallback) { + this.env = env; + this.uniquifier = uniquifier; + this.processResultsBatchSize = processResultsBatchSize; + this.aggregateAllCallback = aggregateAllCallback; + } + + @Override + public ParallelVisitor<SkyKey, SkyKey> create() { + return new TransitiveTraversalValueDTCVisitor( + env, uniquifier, processResultsBatchSize, aggregateAllCallback); + } + } + + @Override + protected void processPartialResults( + Iterable<SkyKey> keysToUseForResult, Callback<SkyKey> callback) + throws QueryException, InterruptedException { + callback.process(keysToUseForResult); + } + + @Override + protected Visit getVisitResult(Iterable<SkyKey> ttvKeys) throws InterruptedException { + Multimap<SkyKey, SkyKey> deps = env.getDirectDepsOfSkyKeys(ttvKeys); + return new Visit( + /*keysToUseForResult=*/ deps.keySet(), + /*keysToVisit=*/ deps.values() + .stream() + .filter(SkyQueryEnvironment.IS_TTV) + .collect(ImmutableList.toImmutableList())); + } + + @Override + protected Iterable<SkyKey> preprocessInitialVisit(Iterable<SkyKey> keys) { + // ParallelVisitorCallback passes in TTV keys. + Preconditions.checkState(Iterables.all(keys, SkyQueryEnvironment.IS_TTV), keys); + return keys; + } + + @Override + protected ImmutableList<SkyKey> getUniqueValues(Iterable<SkyKey> values) { + return uniquifier.unique(values); + } +} |