Create batch versions of query environment methods getFwdDeps and getReverseDeps, and migrate DepsFunction and RdepsFunction to use them.
This makes our (unordered) results potentially dependent on the iteration order of hash sets, but what do we care?
--
MOS_MIGRATED_REVID=96117626
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 79ff3a9..e7992f4 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 @@
}
@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 d76a45e..6129c64 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 @@
}
@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 @@
}
@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 2b693eb..25b1da7 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 @@
// 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 1a7d8d8..a6d6156 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 @@
/** 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 6a8734b..9c61139 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 @@
// 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;
