Add "allrdeps" function that computes rdeps in whatever universe happens to be loaded.
This avoids having to materialize the full universe scope in memory when doing an rdeps query over "//...".
Another option considered was special-casing the string "//..." if it was the first argument to rdeps, but this seemed cleaner.
--
MOS_MIGRATED_REVID=96878999
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 44db228..8a6e5dc 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
@@ -39,6 +39,7 @@
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
+import com.google.devtools.build.lib.query2.engine.AllRdepsFunction;
import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
import com.google.devtools.build.lib.query2.engine.QueryException;
import com.google.devtools.build.lib.query2.engine.QueryExpression;
@@ -460,4 +461,10 @@
public Target getOrCreate(Target target) {
return target;
}
+
+ @Override
+ public Iterable<QueryFunction> getFunctions() {
+ return ImmutableList.<QueryFunction>builder()
+ .addAll(super.getFunctions()).add(new AllRdepsFunction()).build();
+ }
}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java
new file mode 100644
index 0000000..5f1493e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java
@@ -0,0 +1,96 @@
+// Copyright 2015 Google Inc. 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.engine;
+
+import com.google.common.base.Predicate;
+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;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * An "allrdeps" query expression, which computes the reverse dependencies of the argument within
+ * the currently known universe. An optional integer-literal second argument may be specified; its
+ * value bounds the search from the arguments.
+ *
+ * <pre>expr ::= ALLRDEPS '(' expr ')'</pre>
+ * <pre> | ALLRDEPS '(' expr ',' WORD ')'</pre>
+ */
+// Public because SkyQueryEnvironment needs to refer to it directly.
+public class AllRdepsFunction implements QueryFunction {
+ public AllRdepsFunction() {}
+
+ @Override
+ public String getName() {
+ return "allrdeps";
+ }
+
+ @Override
+ public int getMandatoryArguments() {
+ return 1; // last argument is optional
+ }
+
+ @Override
+ public List<ArgumentType> getArgumentTypes() {
+ return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.INTEGER);
+ }
+
+ /**
+ * Breadth-first search from the argument while sticking to nodes satisfying the {@param universe}
+ * predicate.
+ */
+ protected <T> Set<T> eval(QueryEnvironment<T> env, List<Argument> args, Predicate<T> universe)
+ throws QueryException {
+ Set<T> argumentValue = args.get(0).getExpression().eval(env);
+ int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
+ Set<T> visited = new LinkedHashSet<>();
+ Collection<T> current = argumentValue;
+
+ // We need to iterate depthBound + 1 times.
+ for (int i = 0; i <= depthBound; i++) {
+ List<T> next = new ArrayList<>();
+ // Restrict to nodes satisfying the universe predicate.
+ Iterable<T> currentInUniverse = Iterables.filter(current, universe);
+ // 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 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;
+ }
+ current = next;
+ }
+
+ return visited;
+
+ }
+
+ /** Breadth-first search from the argument. */
+ @Override
+ public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+ throws QueryException {
+ return eval(env, args, Predicates.<T>alwaysTrue());
+ }
+}
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 9c61139..68d0d8b 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
@@ -15,14 +15,9 @@
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;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
@@ -34,9 +29,8 @@
* <pre>expr ::= RDEPS '(' expr ',' expr ')'</pre>
* <pre> | RDEPS '(' expr ',' expr ',' WORD ')'</pre>
*/
-final class RdepsFunction implements QueryFunction {
- RdepsFunction() {
- }
+final class RdepsFunction extends AllRdepsFunction {
+ RdepsFunction() {}
@Override
public String getName() {
@@ -45,13 +39,13 @@
@Override
public int getMandatoryArguments() {
- return 2; // last argument is optional
+ return super.getMandatoryArguments() + 1; // +1 for the universe.
}
@Override
public List<ArgumentType> getArgumentTypes() {
- return ImmutableList.of(
- ArgumentType.EXPRESSION, ArgumentType.EXPRESSION, ArgumentType.INTEGER);
+ return ImmutableList.<ArgumentType>builder()
+ .add(ArgumentType.EXPRESSION).addAll(super.getArgumentTypes()).build();
}
/**
@@ -62,34 +56,9 @@
public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
throws QueryException {
Set<T> universeValue = args.get(0).getExpression().eval(env);
- Set<T> argumentValue = args.get(1).getExpression().eval(env);
- int depthBound = args.size() > 2 ? args.get(2).getInteger() : Integer.MAX_VALUE;
-
env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE);
- Set<T> visited = new LinkedHashSet<>();
- Set<T> reachableFromUniverse = env.getTransitiveClosure(universeValue);
- Collection<T> current = argumentValue;
-
- // We need to iterate depthBound + 1 times.
- for (int i = 0; i <= depthBound; i++) {
- List<T> next = new ArrayList<>();
- // 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;
- }
- current = next;
- }
-
- return visited;
+ return eval(env, args.subList(1, args.size()),
+ Predicates.in(env.getTransitiveClosure(universeValue)));
}
}
