From 643063d582dcf346f276680288b11f958f5c551d Mon Sep 17 00:00:00 2001 From: Janak Ramakrishnan Date: Thu, 25 Jun 2015 16:21:49 +0000 Subject: 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 --- .../build/lib/query2/SkyQueryEnvironment.java | 7 ++ .../build/lib/query2/engine/AllRdepsFunction.java | 96 ++++++++++++++++++++++ .../build/lib/query2/engine/RdepsFunction.java | 45 ++-------- 3 files changed, 110 insertions(+), 38 deletions(-) create mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java (limited to 'src/main/java/com/google/devtools/build/lib/query2') 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 { public Target getOrCreate(Target target) { return target; } + + @Override + public Iterable getFunctions() { + return ImmutableList.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. + * + * 
expr ::= ALLRDEPS '(' expr ')'
+ * 
       | ALLRDEPS '(' expr ',' WORD ')'
+ */ +// 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 getArgumentTypes() { + return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.INTEGER); + } + + /** + * Breadth-first search from the argument while sticking to nodes satisfying the {@param universe} + * predicate. + */ + protected Set eval(QueryEnvironment env, List args, Predicate universe) + throws QueryException { + Set argumentValue = args.get(0).getExpression().eval(env); + int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; + Set visited = new LinkedHashSet<>(); + Collection current = argumentValue; + + // We need to iterate depthBound + 1 times. + for (int i = 0; i <= depthBound; i++) { + List next = new ArrayList<>(); + // Restrict to nodes satisfying the universe predicate. + Iterable 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 Set eval(QueryEnvironment env, QueryExpression expression, List args) + throws QueryException { + return eval(env, args, Predicates.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; * 
expr ::= RDEPS '(' expr ',' expr ')'
* 
       | RDEPS '(' expr ',' expr ',' WORD ')'
*/ -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 getArgumentTypes() { - return ImmutableList.of( - ArgumentType.EXPRESSION, ArgumentType.EXPRESSION, ArgumentType.INTEGER); + return ImmutableList.builder() + .add(ArgumentType.EXPRESSION).addAll(super.getArgumentTypes()).build(); } /** @@ -62,34 +56,9 @@ final class RdepsFunction implements QueryFunction { public Set eval(QueryEnvironment env, QueryExpression expression, List args) throws QueryException { Set universeValue = args.get(0).getExpression().eval(env); - Set 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 visited = new LinkedHashSet<>(); - Set reachableFromUniverse = env.getTransitiveClosure(universeValue); - Collection current = argumentValue; - - // We need to iterate depthBound + 1 times. - for (int i = 0; i <= depthBound; i++) { - List next = new ArrayList<>(); - // Restrict to nodes in our universe. - Iterable 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))); } } -- cgit v1.2.3