diff options
5 files changed, 61 insertions, 25 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java index 79ff3a9e15..e7992f43a9 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java +++ b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java @@ -200,11 +200,29 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> } @Override + public Collection<Target> getFwdDeps(Iterable<Target> targets) { + Set<Target> result = new HashSet<>(); + for (Target target : targets) { + result.addAll(getFwdDeps(target)); + } + return result; + } + + @Override public Collection<Target> getReverseDeps(Target target) { return getTargetsFromNodes(getNode(target).getPredecessors()); } @Override + public Collection<Target> getReverseDeps(Iterable<Target> targets) { + Set<Target> result = new HashSet<>(); + for (Target target : targets) { + result.addAll(getReverseDeps(target)); + } + return result; + } + + @Override public Set<Target> getTransitiveClosure(Set<Target> targetNodes) { for (Target node : targetNodes) { checkBuilt(node); 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 d76a45ea95..6129c64a90 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 @@ -167,6 +167,15 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> { } @Override + public Collection<Target> getFwdDeps(Iterable<Target> targets) { + Set<Target> result = new HashSet<>(); + for (Target target : targets) { + result.addAll(getFwdDeps(target)); + } + return result; + } + + @Override public Collection<Target> getReverseDeps(final Target target) { return Collections2.filter(getRawReverseDeps(target), new Predicate<Target>() { @Override @@ -178,6 +187,15 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> { } @Override + public Collection<Target> getReverseDeps(Iterable<Target> targets) { + Set<Target> result = new HashSet<>(); + for (Target target : targets) { + result.addAll(getReverseDeps(target)); + } + return result; + } + + @Override public Set<Target> getTransitiveClosure(Set<Target> targets) { Set<Target> visited = new HashSet<>(); List<Target> result = new ArrayList<>(targets); diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java index 2b693eb8a7..25b1da7944 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java @@ -13,7 +13,9 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; +import com.google.common.base.Predicates; import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction; @@ -66,16 +68,12 @@ final class DepsFunction implements QueryFunction { // We need to iterate depthBound + 1 times. for (int i = 0; i <= depthBound; i++) { List<T> next = new ArrayList<>(); - for (T node : current) { - if (!visited.add(node)) { - // Already visited; if we see a node in a later round, then we don't need to visit it - // again, because the depth at which we see it at must be greater than or equal to the - // last visit. - continue; - } - - next.addAll(env.getFwdDeps(node)); - } + // Filter already visited nodes: if we see a node in a later round, then we don't need to + // visit it again, because the depth at which we see it at must be greater than or equal to + // the last visit. + next.addAll(env.getFwdDeps(Iterables.filter(current, + Predicates.not(Predicates.in(visited))))); + visited.addAll(current); if (next.isEmpty()) { // Exit when there are no more nodes to visit. break; diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java index 1a7d8d844d..a6d6156050 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java @@ -155,9 +155,15 @@ public interface QueryEnvironment<T> { /** Returns the direct forward dependencies of the specified target. */ Collection<T> getFwdDeps(T target); + /** Returns the direct forward dependencies of the specified targets. */ + Collection<T> getFwdDeps(Iterable<T> targets); + /** Returns the direct reverse dependencies of the specified target. */ Collection<T> getReverseDeps(T target); + /** Returns the direct reverse dependencies of the specified targets. */ + Collection<T> getReverseDeps(Iterable<T> targets); + /** * Returns the forward transitive closure of all of the targets in * "targets". Callers must ensure that {@link #buildTransitiveClosure} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java index 6a8734bb3f..9c61139700 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java @@ -13,7 +13,9 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; +import com.google.common.base.Predicates; import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction; @@ -72,21 +74,15 @@ final class RdepsFunction implements QueryFunction { // We need to iterate depthBound + 1 times. for (int i = 0; i <= depthBound; i++) { List<T> next = new ArrayList<>(); - for (T node : current) { - if (!reachableFromUniverse.contains(node)) { - // Traversed outside the transitive closure of the universe. - continue; - } - - if (!visited.add(node)) { - // Already visited; if we see a node in a later round, then we don't need to visit it - // again, because the depth at which we see it at must be greater than or equal to the - // last visit. - continue; - } - - next.addAll(env.getReverseDeps(node)); - } + // Restrict to nodes in our universe. + Iterable<T> currentInUniverse = Iterables.filter(current, + Predicates.in(reachableFromUniverse)); + // Filter already visited nodes: if we see a node in a later round, then we don't need to + // visit it again, because the depth at which we see it at must be greater than or equal to + // the last visit. + next.addAll(env.getReverseDeps(Iterables.filter(currentInUniverse, + Predicates.not(Predicates.in(visited))))); + Iterables.addAll(visited, currentInUniverse); if (next.isEmpty()) { // Exit when there are no more nodes to visit. break; |