diff options
3 files changed, 110 insertions, 38 deletions
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 44db228fdd..8a6e5dc38a 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.Rule; 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 class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> { 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 0000000000..5f1493e54b --- /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 9c61139700..68d0d8b7b2 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 @@ 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; -import java.util.ArrayList; -import java.util.Collection; -import java.util.LinkedHashSet; import java.util.List; import java.util.Set; @@ -34,9 +29,8 @@ import java.util.Set; * <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 @@ final class RdepsFunction implements QueryFunction { @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 @@ final class RdepsFunction implements QueryFunction { 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))); } } |