diff options
Diffstat (limited to 'src/main/java/com/google/devtools/build/lib/query2')
25 files changed, 468 insertions, 186 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java index 73849928bb..11eef89f1d 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java +++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java @@ -35,6 +35,7 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment; 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; +import com.google.devtools.build.lib.query2.engine.QueryUtil; import com.google.devtools.build.lib.util.BinaryPredicate; import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory; @@ -153,7 +154,7 @@ public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironme } try { - resultNodes = expr.eval(this); + resultNodes = QueryUtil.evalAll(this, expr); } catch (QueryException e) { throw new QueryException(e, expr); } 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 7422340f69..55b1bc7be5 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 @@ -38,10 +38,14 @@ import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator; import com.google.devtools.build.lib.pkgcache.TargetProvider; import com.google.devtools.build.lib.pkgcache.TransitivePackageLoader; import com.google.devtools.build.lib.query2.engine.BlazeQueryEvalResult; +import com.google.devtools.build.lib.query2.engine.Callback; 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; +import com.google.devtools.build.lib.query2.engine.QueryUtil.AbstractUniquifier; +import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback; import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException; +import com.google.devtools.build.lib.query2.engine.Uniquifier; import com.google.devtools.build.lib.vfs.PathFragment; import java.util.Collection; @@ -262,6 +266,24 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> return getTargetsFromNodes(graph.getShortestPath(getNode(from), getNode(to))); } + @Override + public void eval(QueryExpression expr, Callback<Target> callback) + throws QueryException, InterruptedException { + AggregateAllCallback<Target> aggregator = new AggregateAllCallback<>(); + expr.eval(this, aggregator); + callback.process(aggregator.getResult()); + } + + @Override + public Uniquifier<Target> createUniquifier() { + return new AbstractUniquifier<Target, Label>() { + @Override + protected Label extractKey(Target target) { + return target.getLabel(); + } + }; + } + private void preloadTransitiveClosure(Set<Target> targets, int maxDepth) throws QueryException { if (maxDepth >= MAX_DEPTH_FULL_SCAN_LIMIT && transitivePackageLoader != null) { // Only do the full visitation if "maxDepth" is large enough. Otherwise, the benefits of diff --git a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java index 632cfa2e9c..624573c132 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java @@ -17,6 +17,7 @@ import com.google.common.base.Function; import com.google.common.collect.Collections2; import com.google.common.collect.ImmutableList; import com.google.common.collect.Iterables; +import com.google.devtools.build.lib.query2.engine.Callback; import com.google.devtools.build.lib.query2.engine.QueryEnvironment; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType; @@ -66,8 +67,8 @@ public class RBuildFilesFunction implements QueryFunction { @Override @SuppressWarnings("unchecked") // Cast from <Target> to <T>. This will only be used with <Target>. - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) - throws QueryException { + public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, + List<Argument> args, Callback<T> callback) throws QueryException, InterruptedException { if (!(env instanceof SkyQueryEnvironment)) { throw new QueryException("rbuildfiles can only be used with SkyQueryEnvironment"); } @@ -75,8 +76,8 @@ public class RBuildFilesFunction implements QueryFunction { for (Argument arg : args) { fileNames.add(arg.getWord()); } - return (Set<T>) + callback.process((Set<T>) ((SkyQueryEnvironment) env) - .getRBuildFiles(Collections2.transform(args, ARGUMENT_TO_PATH_FRAGMENT)); + .getRBuildFiles(Collections2.transform(args, ARGUMENT_TO_PATH_FRAGMENT))); } } 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 8c409fd943..54219cc3b1 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 @@ -47,9 +47,13 @@ import com.google.devtools.build.lib.pkgcache.PathPackageLocator; import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator; import com.google.devtools.build.lib.profiler.Profiler; import com.google.devtools.build.lib.query2.engine.AllRdepsFunction; +import com.google.devtools.build.lib.query2.engine.Callback; 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; +import com.google.devtools.build.lib.query2.engine.QueryUtil.AbstractUniquifier; +import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback; +import com.google.devtools.build.lib.query2.engine.Uniquifier; import com.google.devtools.build.lib.skyframe.FileValue; import com.google.devtools.build.lib.skyframe.GraphBackedRecursivePackageProvider; import com.google.devtools.build.lib.skyframe.PackageLookupValue; @@ -299,6 +303,24 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> { } @Override + public void eval(QueryExpression expr, Callback<Target> callback) + throws QueryException, InterruptedException { + AggregateAllCallback<Target> aggregator = new AggregateAllCallback<>(); + expr.eval(this, aggregator); + callback.process(aggregator.getResult()); + } + + @Override + public Uniquifier<Target> createUniquifier() { + return new AbstractUniquifier<Target, Label>() { + @Override + protected Label extractKey(Target target) { + return target.getLabel(); + } + }; + } + + @Override public Set<Target> getTargetsMatchingPattern(QueryExpression owner, String pattern) throws QueryException { Set<Target> targets = new LinkedHashSet<>(resolvedTargetPatterns.get(pattern)); diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java index 967493ca1b..b528127661 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java @@ -13,13 +13,15 @@ // 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.common.collect.Sets; 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.HashSet; import java.util.List; @@ -48,13 +50,11 @@ public class AllPathsFunction implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) - throws QueryException, InterruptedException { - QueryExpression from = args.get(0).getExpression(); - QueryExpression to = args.get(1).getExpression(); + public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args, + Callback<T> callback) throws QueryException, InterruptedException { - Set<T> fromValue = from.eval(env); - Set<T> toValue = to.eval(env); + Set<T> fromValue = QueryUtil.evalAll(env, args.get(0).getExpression()); + Set<T> toValue = QueryUtil.evalAll(env, args.get(1).getExpression()); // Algorithm: compute "reachableFromX", the forward transitive closure of // the "from" set, then find the intersection of "reachableFromX" with the @@ -65,18 +65,16 @@ public class AllPathsFunction implements QueryFunction { env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); Set<T> reachableFromX = env.getTransitiveClosure(fromValue); - Set<T> result = intersection(reachableFromX, toValue); + Predicate<T> reachable = Predicates.in(reachableFromX); + Uniquifier<T> uniquifier = env.createUniquifier(); + Collection<T> result = uniquifier.unique(intersection(reachableFromX, toValue)); + callback.process(result); Collection<T> worklist = result; while (!worklist.isEmpty()) { Collection<T> reverseDeps = env.getReverseDeps(worklist); - worklist = new ArrayList<>(); - for (T np : reverseDeps) { - if (reachableFromX.contains(np) && result.add(np)) { - worklist.add(np); - } - } + worklist = uniquifier.unique(Iterables.filter(reverseDeps, reachable)); + callback.process(worklist); } - return result; } /** 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 index f844af97d8..ed49ef4f93 100644 --- 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 @@ -22,10 +22,7 @@ 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 @@ -58,39 +55,41 @@ public class AllRdepsFunction implements QueryFunction { * Breadth-first search from the argument while sticking to nodes satisfying the {@code universe} * predicate. */ - protected <T> Set<T> eval(QueryEnvironment<T> env, List<Argument> args, Predicate<T> universe) + protected static <T> void eval(final QueryEnvironment<T> env, final List<Argument> args, + final Callback<T> callback, final Predicate<T> universe) throws QueryException, InterruptedException { - 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; + final Uniquifier<T> uniquifier = env.createUniquifier(); + final int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; + env.eval(args.get(0).getExpression(), new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + Iterable<T> current = partialResult; + // 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(uniquifier.unique(currentInUniverse))); + callback.process(currentInUniverse); + if (next.isEmpty()) { + // Exit when there are no more nodes to visit. + break; + } + current = next; + } - // 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, InterruptedException { - return eval(env, args, Predicates.<T>alwaysTrue()); + public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args, + Callback<T> callback) throws QueryException, InterruptedException { + eval(env, args, callback, Predicates.<T>alwaysTrue()); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java index 28bb6e7eca..b62565e3f7 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java @@ -15,9 +15,9 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; +import com.google.devtools.build.lib.query2.engine.Lexer.TokenKind; import java.util.Collection; -import java.util.LinkedHashSet; import java.util.List; import java.util.Set; @@ -46,29 +46,35 @@ class BinaryOperatorExpression extends QueryExpression { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException, InterruptedException { - Set<T> lhsValue = new LinkedHashSet<>(operands.get(0).eval(env)); + public <T> void eval(QueryEnvironment<T> env, Callback<T> callback) + throws QueryException, InterruptedException { + if (operator == TokenKind.PLUS || operator == TokenKind.UNION) { + for (QueryExpression operand : operands) { + env.eval(operand, callback); + } + return; + } + // We cannot do differences with partial results. So we fully evaluate the operands + Set<T> lhsValue = QueryUtil.evalAll(env, operands.get(0)); for (int i = 1; i < operands.size(); i++) { - Set<T> rhsValue = operands.get(i).eval(env); + Set<T> rhsValue = QueryUtil.evalAll(env, operands.get(i)); switch (operator) { case INTERSECT: case CARET: lhsValue.retainAll(rhsValue); break; - case UNION: - case PLUS: - lhsValue.addAll(rhsValue); - break; case EXCEPT: case MINUS: lhsValue.removeAll(rhsValue); break; + case UNION: + case PLUS: default: throw new IllegalStateException("operator=" + operator); } } - return lhsValue; + callback.process(lhsValue); } @Override diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java index ca8f102a8a..c36f98a29f 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java @@ -14,6 +14,8 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.devtools.build.lib.collect.CompactHashSet; 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; @@ -39,9 +41,17 @@ class BuildFilesFunction implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression, + List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { - return env.getBuildFiles(expression, args.get(0).getExpression().eval(env)); + env.eval(args.get(0).getExpression(), new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + Set<T> result = CompactHashSet.create(); + Iterables.addAll(result, partialResult); + callback.process(env.getBuildFiles(expression, result)); + } + }); } @Override diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java b/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java new file mode 100644 index 0000000000..ef9c3cde18 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java @@ -0,0 +1,35 @@ +// Copyright 2015 The Bazel Authors. 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; + +/** + * Query callback to be called by a {@link QueryExpression} when it has part of the computation + * result. Assuming the {@code QueryEnvironment} supports it, it would allow the caller + * to stream the results. + */ +public interface Callback<T> { + + /** + * Called by {@code QueryExpression} when it has been able to compute part of the result. + * + * <p>Note that this method can be called several times for a QueryExpression. Callers + * implementing this method should assume that multiple calls can happen. + * + * @param partialResult Part of the result. Note that from the caller's perspective, it is + * guaranteed that no repeated elements will be returned. However {@code QueryExpression}s calling + * the callback do not need to maintain this property, as the {@code QueryEnvironment} should + * handle the uniqueness. + */ + void process(Iterable<T> partialResult) throws QueryException, InterruptedException; +} 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 265de4c60d..b7bc59ae5b 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,16 +13,13 @@ // 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.common.collect.Sets; 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; @@ -56,31 +53,31 @@ final class DepsFunction implements QueryFunction { * Breadth-first search from the arguments. */ @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression, + List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { - Set<T> argumentValue = args.get(0).getExpression().eval(env); - int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; - env.buildTransitiveClosure(expression, argumentValue, depthBound); + final int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; + final Uniquifier<T> uniquifier = env.createUniquifier(); + env.eval(args.get(0).getExpression(), new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + Collection<T> current = Sets.newHashSet(partialResult); + env.buildTransitiveClosure(expression, (Set<T>) current, depthBound); - 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<>(); - // 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; + // We need to iterate depthBound + 1 times. + for (int i = 0; i <= depthBound; i++) { + // 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. + ImmutableList<T> toProcess = uniquifier.unique(current); + callback.process(toProcess); + current = ImmutableList.copyOf(env.getFwdDeps(toProcess)); + if (current.isEmpty()) { + // Exit when there are no more nodes to visit. + break; + } + } } - current = next; - } - - return visited; + }); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java index 57667a25eb..d74056516f 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java @@ -23,7 +23,6 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunctio import java.util.Collection; import java.util.List; -import java.util.Set; /** * A query expression for user-defined query functions. @@ -38,8 +37,9 @@ public class FunctionExpression extends QueryExpression { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException, InterruptedException { - return function.<T>eval(env, this, args); + public <T> void eval(QueryEnvironment<T> env, Callback<T> callback) + throws QueryException, InterruptedException { + function.eval(env, this, args, callback); } @Override diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java index 33dc85c36e..a13f42cfb8 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java @@ -18,9 +18,8 @@ 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.LinkedHashSet; +import java.util.ArrayList; import java.util.List; -import java.util.Set; /** * A label(attr_name, argument) expression, which computes the set of targets @@ -53,20 +52,28 @@ class LabelsFunction implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression, + final List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { - Set<T> inputs = args.get(1).getExpression().eval(env); - Set<T> result = new LinkedHashSet<>(); - String attrName = args.get(0).getWord(); - for (T input : inputs) { - if (env.getAccessor().isRule(input)) { - List<T> targets = env.getAccessor().getLabelListAttr(expression, input, attrName, - "in '" + attrName + "' of rule " + env.getAccessor().getLabel(input) + ": "); - for (T target : targets) { - result.add(env.getOrCreate(target)); + final String attrName = args.get(0).getWord(); + final Uniquifier<T> uniquifier = env.createUniquifier(); + env.eval(args.get(1).getExpression(), new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + for (T input : partialResult) { + if (env.getAccessor().isRule(input)) { + List<T> targets = uniquifier.unique( + env.getAccessor().getLabelListAttr(expression, input, attrName, + "in '" + attrName + "' of rule " + env.getAccessor().getLabel(input) + ": ")); + List<T> result = new ArrayList<>(targets.size()); + for (T target : targets) { + result.add(env.getOrCreate(target)); + } + callback.process(result); + } } + } - } - return result; + }); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java index 0fe8fdfde9..2e198077bb 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java @@ -52,14 +52,19 @@ class LetExpression extends QueryExpression { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException, InterruptedException { + public <T> void eval(QueryEnvironment<T> env, Callback<T> callback) + throws QueryException, InterruptedException { if (!NAME_PATTERN.matcher(varName).matches()) { throw new QueryException(this, "invalid variable name '" + varName + "' in let expression"); } - Set<T> varValue = varExpr.eval(env); + // We eval all because we would need a stack of variable contexts for implementing setVariable + // correctly. + Set<T> varValue = QueryUtil.evalAll(env, varExpr); Set<T> prevValue = env.setVariable(varName, varValue); try { - return bodyExpr.eval(env); + // Same as varExpr. We cannot pass partial results to the parent without having + // a stack of variable contexts. + callback.process(QueryUtil.evalAll(env, bodyExpr)); } finally { env.setVariable(varName, prevValue); // restore } 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 9d5d21268c..b8c065f936 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 @@ -116,8 +116,8 @@ public interface QueryEnvironment<T> { * @param args the input arguments. These are type-checked against the specification returned * by {@link #getArgumentTypes} and {@link #getMandatoryArguments} */ - <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) - throws QueryException, InterruptedException; + <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args, + Callback<T> callback) throws QueryException, InterruptedException; } /** @@ -188,6 +188,22 @@ public interface QueryEnvironment<T> { */ Set<T> setVariable(String name, Set<T> value); + /** + * Eval an expression {@code expr} and pass the results to the {@code callback}. + * + * <p>Note that this method should guarantee that the callback does not see repeated elements. + * @param expr The expression to evaluate + * @param callback The caller callback to notify when results are available + */ + void eval(QueryExpression expr, Callback<T> callback) throws QueryException, InterruptedException; + + /** + * Creates a Uniquifier for use in a {@code QueryExpression}. Note that the usage of this an + * uniquifier should not be used for returning unique results to the parent callback. It should + * only be used to avoid processing the same elements multiple times within this QueryExpression. + */ + Uniquifier<T> createUniquifier(); + void reportBuildFileError(QueryExpression expression, String msg) throws QueryException; /** diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java index 26860ef30b..b0ea774219 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java @@ -14,7 +14,6 @@ package com.google.devtools.build.lib.query2.engine; import java.util.Collection; -import java.util.Set; /** * Base class for expressions in the Blaze query language, revision 2. @@ -56,18 +55,19 @@ public abstract class QueryExpression { protected QueryExpression() {} /** - * Evaluates this query in the specified environment, and returns a subgraph, - * concretely represented a new (possibly-immutable) set of target nodes. + * Evaluates this query in the specified environment, and notifies the callback with a the result. + * Note that it is allowed to notify the callback with partial results instead of just one final + * result. * - * Failures resulting from evaluation of an ill-formed query cause + * <p>Failures resulting from evaluation of an ill-formed query cause * QueryException to be thrown. * - * The reporting of failures arising from errors in BUILD files depends on + * <p>The reporting of failures arising from errors in BUILD files depends on * the --keep_going flag. If enabled (the default), then QueryException is * thrown. If disabled, evaluation will stumble on to produce a (possibly * inaccurate) result, but a result nonetheless. */ - public abstract <T> Set<T> eval(QueryEnvironment<T> env) + public abstract <T> void eval(QueryEnvironment<T> env, Callback<T> callback) throws QueryException, InterruptedException; /** diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java new file mode 100644 index 0000000000..f70dcd08c7 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java @@ -0,0 +1,114 @@ +// Copyright 2015 The Bazel Authors. 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.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.devtools.build.lib.collect.CompactHashSet; + +import java.util.Set; + +/** Several query utilities to make easier to work with query callbacks and uniquifiers. */ +public final class QueryUtil { + + private QueryUtil() { } + + /** A callback that can aggregate all the partial results in one set */ + public static class AggregateAllCallback<T> implements Callback<T> { + + private final CompactHashSet<T> result = CompactHashSet.create(); + + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + Iterables.addAll(result, partialResult); + } + + public Set<T> getResult() { + return result; + } + + @Override + public String toString() { + return "Aggregate all: " + result; + } + } + + /** + * Fully evaluate a {@code QueryExpression} and return a set with all the results. + * + * <p>Should ony be used by QueryExpressions when it is the only way of achieving correctness. + */ + public static <T> Set<T> evalAll(QueryEnvironment<T> env, QueryExpression expr) + throws QueryException, InterruptedException { + AggregateAllCallback<T> callback = new AggregateAllCallback<>(); + env.eval(expr, callback); + return callback.result; + } + + /** + * Notify {@code parentCallback} only about the events that match {@code retainIfTrue} predicate. + * + * @param parentCallback The parent callback to notify with the matching elements + * @param retainIfTrue A predicate that defines what elements to notify to the parent callback. + */ + public static <T> Callback<T> filteredCallback(final Callback<T> parentCallback, + final Predicate<T> retainIfTrue) { + return new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + Iterable<T> filter = Iterables.filter(partialResult, retainIfTrue); + if (!Iterables.isEmpty(filter)) { + parentCallback.process(filter); + } + } + + @Override + public String toString() { + return "filtered parentCallback of : " + retainIfTrue; + } + }; + } + + /** + * An uniquifier that uses a CompactHashSet and a key extractor for making the elements unique. + * + * <p>Using a key extractor allows to improve memory since we don't have to keep the whole element + * in the set but just the key. + */ + public abstract static class AbstractUniquifier<T, K> implements Uniquifier<T> { + + private final CompactHashSet<K> alreadySeen = CompactHashSet.create(); + + @Override + public final ImmutableList<T> unique(Iterable<T> newElements) { + ImmutableList.Builder<T> result = ImmutableList.builder(); + for (T element : newElements) { + if (alreadySeen.add(extractKey(element))) { + result.add(element); + } + } + return result.build(); + } + + /** Extracts an unique key that represents the target. For example the label. */ + protected abstract K extractKey(T t); + + @Override + public String toString() { + return this.getClass().getName() + " uniquifier :" + alreadySeen; + } + } +} 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 2a0d41c7cc..24d0334df2 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,6 +13,7 @@ // 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.devtools.build.lib.query2.engine.QueryEnvironment.Argument; @@ -53,12 +54,13 @@ final class RdepsFunction extends AllRdepsFunction { * towards the universe while staying within the transitive closure. */ @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, + List<Argument> args, Callback<T> callback) throws QueryException, InterruptedException { - Set<T> universeValue = args.get(0).getExpression().eval(env); + Set<T> universeValue = QueryUtil.evalAll(env, args.get(0).getExpression()); env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE); - return eval(env, args.subList(1, args.size()), - Predicates.in(env.getTransitiveClosure(universeValue))); + Predicate<T> universe = Predicates.in(env.getTransitiveClosure(universeValue)); + eval(env, args.subList(1, args.size()), callback, universe); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java index 254e658610..7647f4d211 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java @@ -13,13 +13,12 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; +import com.google.common.base.Predicate; import com.google.common.collect.ImmutableList; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction; -import java.util.LinkedHashSet; import java.util.List; -import java.util.Set; import java.util.regex.Pattern; /** @@ -31,9 +30,10 @@ abstract class RegexFilterExpression implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression, + final List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { - Pattern compiledPattern; + final Pattern compiledPattern; try { compiledPattern = Pattern.compile(getPattern(args)); } catch (IllegalArgumentException e) { @@ -41,18 +41,20 @@ abstract class RegexFilterExpression implements QueryFunction { + e.getMessage()); } - QueryExpression argument = args.get(args.size() - 1).getExpression(); - - Set<T> result = new LinkedHashSet<>(); - for (T target : argument.eval(env)) { - for (String str : getFilterStrings(env, args, target)) { - if ((str != null) && compiledPattern.matcher(str).find()) { - result.add(target); - break; + final Predicate<T> matchFilter = new Predicate<T>() { + @Override + public boolean apply(T target) { + for (String str : getFilterStrings(env, args, target)) { + if ((str != null) && compiledPattern.matcher(str).find()) { + return true; + } } + return false; } - } - return result; + }; + + env.eval(args.get(args.size() - 1).getExpression(), + QueryUtil.filteredCallback(callback, matchFilter)); } /** diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java index 229e3c7078..41aa9281dc 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java @@ -16,9 +16,7 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.base.Joiner; import java.util.Collection; -import java.util.LinkedHashSet; import java.util.List; -import java.util.Set; /** * A set(word, ..., word) expression, which computes the union of zero or more @@ -48,12 +46,11 @@ class SetExpression extends QueryExpression { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException { - Set<T> result = new LinkedHashSet<>(); + public <T> void eval(QueryEnvironment<T> env, Callback<T> callback) + throws QueryException, InterruptedException { for (TargetLiteral expr : words) { - result.addAll(expr.eval(env)); + env.eval(expr, callback); } - return result; } @Override diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java index f6abf368e5..d6885e44f6 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java @@ -15,12 +15,13 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; +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.List; -import java.util.Set; +import java.util.concurrent.atomic.AtomicBoolean; /** * A some(x) filter expression, which returns an arbitrary node in set x, or @@ -48,12 +49,22 @@ class SomeFunction implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, + List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { - Set<T> argumentValue = args.get(0).getExpression().eval(env); - if (argumentValue.isEmpty()) { + final AtomicBoolean someFound = new AtomicBoolean(false); + env.eval(args.get(0).getExpression(), new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + if (someFound.get() || Iterables.isEmpty(partialResult)) { + return; + } + callback.process(ImmutableSet.of(partialResult.iterator().next())); + someFound.set(true); + } + }); + if (!someFound.get()) { throw new QueryException(expression, "argument set is empty"); } - return ImmutableSet.of(argumentValue.iterator().next()); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java index 0471d67944..9e2b44392b 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java @@ -21,7 +21,6 @@ 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.HashSet; import java.util.List; import java.util.Set; @@ -51,10 +50,11 @@ class SomePathFunction implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, + List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { - Set<T> fromValue = args.get(0).getExpression().eval(env); - Set<T> toValue = args.get(1).getExpression().eval(env); + Set<T> fromValue = QueryUtil.evalAll(env, args.get(0).getExpression()); + Set<T> toValue = QueryUtil.evalAll(env, args.get(1).getExpression()); // Implementation strategy: for each x in "from", compute its forward // transitive closure. If it intersects "to", then do a path search from x @@ -64,12 +64,9 @@ class SomePathFunction implements QueryFunction { env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); // This set contains all nodes whose TC does not intersect "toValue". - Set<T> done = new HashSet<>(); + Uniquifier<T> uniquifier = env.createUniquifier(); - for (T x : fromValue) { - if (done.contains(x)) { - continue; - } + for (T x : uniquifier.unique(fromValue)) { Set<T> xtc = env.getTransitiveClosure(ImmutableSet.of(x)); SetView<T> result; if (xtc.size() > toValue.size()) { @@ -78,10 +75,11 @@ class SomePathFunction implements QueryFunction { result = Sets.intersection(xtc, toValue); } if (!result.isEmpty()) { - return env.getNodesOnPath(x, result.iterator().next()); + callback.process(env.getNodesOnPath(x, result.iterator().next())); + return; } - done.addAll(xtc); + uniquifier.unique(xtc); } - return ImmutableSet.of(); + callback.process(ImmutableSet.<T>of()); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java index 7faad47f1a..886d9ce801 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java @@ -41,17 +41,18 @@ final class TargetLiteral extends QueryExpression { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException { + public <T> void eval(QueryEnvironment<T> env, Callback<T> callback) + throws QueryException, InterruptedException { if (isVariableReference()) { String varName = LetExpression.getNameFromReference(pattern); Set<T> value = env.getVariable(varName); if (value == null) { throw new QueryException(this, "undefined variable '" + varName + "'"); } - return env.getVariable(varName); + callback.process(value); + } else { + callback.process(env.getTargetsMatchingPattern(this, pattern)); } - - return env.getTargetsMatchingPattern(this, pattern); } @Override diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java index e1d7727f2e..d5479ee6cf 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java @@ -62,20 +62,24 @@ class TestsFunction implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) - throws QueryException, InterruptedException { - Closure<T> closure = new Closure<>(expression, env); - Set<T> result = new HashSet<>(); - for (T target : args.get(0).getExpression().eval(env)) { - if (env.getAccessor().isTestRule(target)) { - result.add(target); - } else if (env.getAccessor().isTestSuite(target)) { - for (T test : closure.getTestsInSuite(target)) { - result.add(env.getOrCreate(test)); + public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression, + List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { + final Closure<T> closure = new Closure<>(expression, env); + + env.eval(args.get(0).getExpression(), new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + for (T target : partialResult) { + if (env.getAccessor().isTestRule(target)) { + callback.process(ImmutableList.of(target)); + } else if (env.getAccessor().isTestSuite(target)) { + for (T test : closure.getTestsInSuite(target)) { + callback.process(ImmutableList.of(env.getOrCreate(test))); + } + } } } - } - return result; + }); } /** diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/Uniquifier.java b/src/main/java/com/google/devtools/build/lib/query2/engine/Uniquifier.java new file mode 100644 index 0000000000..d401921176 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/Uniquifier.java @@ -0,0 +1,33 @@ +// Copyright 2015 The Bazel Authors. 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.collect.ImmutableList; + +/** + * A class used for deduplication of {@code Iterable}s. If called with repeated elements or multiple + * times with repeated elements between calls, it guarantees to output only those elements exactly once. + */ +public interface Uniquifier<T> { + + /** + * Receives an iterable and returns the list of elements that were not already seen. The + * uniqueness need to be guaranteed for elements of the same iterable and multiple calls to the + * {@code unique} method. + * + * @param newElements The new elements to process. + * @return The subset of elements not already seen by this Uniquifier. + */ + ImmutableList<T> unique(Iterable<T> newElements); +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java index 1f097f2d27..e4d095eecb 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java @@ -15,7 +15,6 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableSet; 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; @@ -53,24 +52,26 @@ public class VisibleFunction implements QueryFunction { } @Override - public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) - throws QueryException, InterruptedException { - Set<T> toSet = args.get(0).getExpression().eval(env); - Set<T> targets = args.get(1).getExpression().eval(env); - - ImmutableSet.Builder<T> visible = ImmutableSet.builder(); - for (T target : targets) { - if (visibleToAll(env, toSet, target)) { - visible.add(target); + public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression, + List<Argument> args, + final Callback<T> callback) throws QueryException, InterruptedException { + final Set<T> toSet = QueryUtil.evalAll(env, args.get(0).getExpression()); + env.eval(args.get(1).getExpression(), new Callback<T>() { + @Override + public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { + for (T t : partialResult) { + if (visibleToAll(env, toSet, t)) { + callback.process(ImmutableList.of(t)); + } + } } - } - return visible.build(); + }); } /** * Returns true if {@code target} is visible to all targets in {@code toSet}. */ - private <T> boolean visibleToAll( + private static <T> boolean visibleToAll( QueryEnvironment<T> env, Set<T> toSet, T target) throws QueryException { for (T to : toSet) { if (!visible(env, to, target)) { @@ -83,7 +84,7 @@ public class VisibleFunction implements QueryFunction { /** * Returns true if the target {@code from} is visible to the target {@code to}. */ - public <T> boolean visible(QueryEnvironment<T> env, T to, T from) throws QueryException { + public static <T> boolean visible(QueryEnvironment<T> env, T to, T from) throws QueryException { Set<QueryVisibility<T>> visiblePackages = env.getAccessor().getVisibility(from); for (QueryVisibility<T> spec : visiblePackages) { if (spec.contains(to)) { |