From b869e584641521dc063f0589d7ce6a850ffc0b61 Mon Sep 17 00:00:00 2001 From: Nathan Harmata Date: Wed, 1 Mar 2017 02:55:48 +0000 Subject: Rollback of commit 822c37816ac669e51bec3853b41849a19ec5e230. -- PiperOrigin-RevId: 148844518 MOS_MIGRATED_REVID=148844518 --- .../query2/engine/AbstractQueryEnvironment.java | 194 ------------------- .../build/lib/query2/engine/AllPathsFunction.java | 73 ++++---- .../build/lib/query2/engine/AllRdepsFunction.java | 45 +++-- .../query2/engine/BinaryOperatorExpression.java | 202 ++++++++++---------- .../lib/query2/engine/BuildFilesFunction.java | 24 ++- .../devtools/build/lib/query2/engine/Callback.java | 5 +- .../build/lib/query2/engine/DepsFunction.java | 19 +- .../lib/query2/engine/FunctionExpression.java | 19 +- .../build/lib/query2/engine/LabelsFunction.java | 20 +- .../build/lib/query2/engine/LetExpression.java | 25 +-- .../build/lib/query2/engine/LoadFilesFunction.java | 21 ++- .../lib/query2/engine/OutputFormatterCallback.java | 2 +- .../lib/query2/engine/ParallelQueryUtils.java | 188 +++++++++++++++++++ .../build/lib/query2/engine/QueryEnvironment.java | 207 +++++---------------- .../build/lib/query2/engine/QueryExpression.java | 48 ++++- .../query2/engine/QueryExpressionEvalListener.java | 67 +++++++ .../build/lib/query2/engine/QueryUtil.java | 108 +++++------ .../build/lib/query2/engine/RdepsFunction.java | 41 ++-- .../lib/query2/engine/RegexFilterExpression.java | 50 ++++- .../build/lib/query2/engine/SetExpression.java | 12 +- .../build/lib/query2/engine/SomeFunction.java | 58 +++--- .../build/lib/query2/engine/SomePathFunction.java | 82 ++++---- .../query2/engine/StreamableQueryEnvironment.java | 12 +- ...chronizedDelegatingOutputFormatterCallback.java | 58 ------ .../build/lib/query2/engine/TargetLiteral.java | 40 ++-- .../build/lib/query2/engine/TestsFunction.java | 29 ++- .../lib/query2/engine/ThreadSafeCallback.java | 23 +++ .../engine/ThreadSafeOutputFormatterCallback.java | 21 --- .../lib/query2/engine/ThreadSafeUniquifier.java | 22 +++ .../build/lib/query2/engine/Uniquifier.java | 2 - .../build/lib/query2/engine/VisibleFunction.java | 51 ++--- 31 files changed, 900 insertions(+), 868 deletions(-) delete mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/AbstractQueryEnvironment.java create mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/ParallelQueryUtils.java create mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpressionEvalListener.java delete mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/SynchronizedDelegatingOutputFormatterCallback.java create mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeCallback.java delete mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeOutputFormatterCallback.java create mode 100644 src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeUniquifier.java (limited to 'src/main/java/com/google/devtools/build/lib/query2/engine') diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AbstractQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AbstractQueryEnvironment.java deleted file mode 100644 index 62fd91b56f..0000000000 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/AbstractQueryEnvironment.java +++ /dev/null @@ -1,194 +0,0 @@ -// Copyright 2017 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.Function; -import com.google.common.base.Throwables; -import com.google.common.collect.ImmutableList; -import com.google.common.collect.Iterables; -import com.google.common.util.concurrent.AsyncFunction; -import com.google.common.util.concurrent.Futures; -import com.google.common.util.concurrent.ListenableFuture; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskCallable; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; -import com.google.devtools.build.lib.util.Preconditions; -import java.util.concurrent.CancellationException; -import java.util.concurrent.ExecutionException; -import java.util.concurrent.Executor; -import java.util.concurrent.TimeUnit; -import java.util.concurrent.TimeoutException; - -/** - * A partial implementation of {@link QueryEnvironment} that has trivial in-thread implementations - * of all the {@link QueryTaskFuture}/{@link QueryTaskCallable} helper methods. - */ -public abstract class AbstractQueryEnvironment implements QueryEnvironment { - /** Concrete implementation of {@link QueryTaskFuture}. */ - protected static final class QueryTaskFutureImpl - extends QueryTaskFutureImplBase implements ListenableFuture { - private final ListenableFuture delegate; - - private QueryTaskFutureImpl(ListenableFuture delegate) { - this.delegate = delegate; - } - - public static QueryTaskFutureImpl ofDelegate(ListenableFuture delegate) { - return (delegate instanceof QueryTaskFutureImpl) - ? (QueryTaskFutureImpl) delegate - : new QueryTaskFutureImpl<>(delegate); - } - - @Override - public boolean cancel(boolean mayInterruptIfRunning) { - return delegate.cancel(mayInterruptIfRunning); - } - - @Override - public boolean isCancelled() { - return delegate.isCancelled(); - } - - @Override - public boolean isDone() { - return delegate.isDone(); - } - - @Override - public T get() throws InterruptedException, ExecutionException { - return delegate.get(); - } - - @Override - public T get(long timeout, TimeUnit unit) - throws InterruptedException, ExecutionException, TimeoutException { - return delegate.get(timeout, unit); - } - - @Override - public void addListener(Runnable listener, Executor executor) { - delegate.addListener(listener, executor); - } - - @Override - public T getIfSuccessful() { - Preconditions.checkState(delegate.isDone()); - try { - return delegate.get(); - } catch (CancellationException | InterruptedException | ExecutionException e) { - throw new IllegalStateException(e); - } - } - - public T getChecked() throws InterruptedException, QueryException { - try { - return get(); - } catch (CancellationException e) { - throw new InterruptedException(); - } catch (ExecutionException e) { - Throwable cause = e.getCause(); - Throwables.propagateIfPossible(cause, QueryException.class); - Throwables.propagateIfPossible(cause, InterruptedException.class); - throw new IllegalStateException(e.getCause()); - } - } - } - - @Override - public QueryTaskFuture immediateSuccessfulFuture(R value) { - return new QueryTaskFutureImpl<>(Futures.immediateFuture(value)); - } - - @Override - public QueryTaskFuture immediateFailedFuture(QueryException e) { - return new QueryTaskFutureImpl<>(Futures.immediateFailedFuture(e)); - } - - @Override - public QueryTaskFuture immediateCancelledFuture() { - return new QueryTaskFutureImpl<>(Futures.immediateCancelledFuture()); - } - - @Override - public QueryTaskFuture eval( - QueryExpression expr, VariableContext context, Callback callback) { - return expr.eval(this, context, callback); - } - - @Override - public QueryTaskFuture executeAsync(QueryTaskCallable callable) { - try { - return immediateSuccessfulFuture(callable.call()); - } catch (QueryException e) { - return immediateFailedFuture(e); - } catch (InterruptedException e) { - return immediateCancelledFuture(); - } - } - - @Override - public QueryTaskFuture whenSucceedsCall( - QueryTaskFuture future, QueryTaskCallable callable) { - return whenAllSucceedCall(ImmutableList.of(future), callable); - } - - private static class Dummy implements QueryTaskCallable { - public static final Dummy INSTANCE = new Dummy(); - - private Dummy() {} - - @Override - public Void call() { - return null; - } - } - - @Override - public QueryTaskFuture whenAllSucceed(Iterable> futures) { - return whenAllSucceedCall(futures, Dummy.INSTANCE); - } - - @Override - public QueryTaskFuture whenAllSucceedCall( - Iterable> futures, QueryTaskCallable callable) { - return QueryTaskFutureImpl.ofDelegate( - Futures.whenAllSucceed(cast(futures)).call(callable)); - } - - @Override - public QueryTaskFuture transformAsync( - QueryTaskFuture future, - final Function> function) { - return QueryTaskFutureImpl.ofDelegate( - Futures.transformAsync( - (QueryTaskFutureImpl) future, - new AsyncFunction() { - @Override - public ListenableFuture apply(T1 input) throws Exception { - return (QueryTaskFutureImpl) function.apply(input); - } - })); - } - - protected static Iterable> cast( - Iterable> futures) { - return Iterables.transform( - futures, - new Function, QueryTaskFutureImpl>() { - @Override - public QueryTaskFutureImpl apply(QueryTaskFuture future) { - return (QueryTaskFutureImpl) future; - } - }); - } -} 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 81be4c8ca2..adc12d278f 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 @@ -21,12 +21,12 @@ 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 com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskCallable; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.Collection; import java.util.HashSet; import java.util.List; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * Implementation of the allpaths() function. @@ -51,47 +51,46 @@ public class AllPathsFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( - final QueryEnvironment env, + public void eval( + QueryEnvironment env, VariableContext context, - final QueryExpression expression, + QueryExpression expression, List args, - final Callback callback) { - final QueryTaskFuture> fromValueFuture = - QueryUtil.evalAll(env, context, args.get(0).getExpression()); - final QueryTaskFuture> toValueFuture = - QueryUtil.evalAll(env, context, args.get(1).getExpression()); + Callback callback) throws QueryException, InterruptedException { + + Set fromValue = QueryUtil.evalAll(env, context, args.get(0).getExpression()); + Set toValue = QueryUtil.evalAll(env, context, args.get(1).getExpression()); - return env.whenAllSucceedCall( - ImmutableList.of(fromValueFuture, toValueFuture), - new QueryTaskCallable() { - @Override - public Void call() throws QueryException, InterruptedException { - // Algorithm: compute "reachableFromX", the forward transitive closure of - // the "from" set, then find the intersection of "reachableFromX" with the - // reverse transitive closure of the "to" set. The reverse transitive - // closure and intersection operations are interleaved for efficiency. - // "result" holds the intersection. + // Algorithm: compute "reachableFromX", the forward transitive closure of + // the "from" set, then find the intersection of "reachableFromX" with the + // reverse transitive closure of the "to" set. The reverse transitive + // closure and intersection operations are interleaved for efficiency. + // "result" holds the intersection. - Set fromValue = fromValueFuture.getIfSuccessful(); - Set toValue = toValueFuture.getIfSuccessful(); + env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); - env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); + Set reachableFromX = env.getTransitiveClosure(fromValue); + Predicate reachable = Predicates.in(reachableFromX); + Uniquifier uniquifier = env.createUniquifier(); + Collection result = uniquifier.unique(intersection(reachableFromX, toValue)); + callback.process(result); + Collection worklist = result; + while (!worklist.isEmpty()) { + Collection reverseDeps = env.getReverseDeps(worklist); + worklist = uniquifier.unique(Iterables.filter(reverseDeps, reachable)); + callback.process(worklist); + } + } - Set reachableFromX = env.getTransitiveClosure(fromValue); - Predicate reachable = Predicates.in(reachableFromX); - Uniquifier uniquifier = env.createUniquifier(); - Collection result = uniquifier.unique(intersection(reachableFromX, toValue)); - callback.process(result); - Collection worklist = result; - while (!worklist.isEmpty()) { - Collection reverseDeps = env.getReverseDeps(worklist); - worklist = uniquifier.unique(Iterables.filter(reverseDeps, reachable)); - callback.process(worklist); - } - return null; - } - }); + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); } /** 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 f800d804dc..518b67497b 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 @@ -13,7 +13,6 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; -import com.google.common.base.Optional; import com.google.common.base.Predicate; import com.google.common.base.Predicates; import com.google.common.collect.ImmutableList; @@ -21,9 +20,10 @@ 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 com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.ArrayList; import java.util.List; +import java.util.concurrent.ForkJoinPool; /** * An "allrdeps" query expression, which computes the reverse dependencies of the argument within @@ -52,34 +52,30 @@ public class AllRdepsFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( QueryEnvironment env, VariableContext context, QueryExpression expression, List args, - Callback callback) { - return eval(env, context, args, callback, Optional.>absent()); + Callback callback) throws QueryException, InterruptedException { + eval(env, context, args, callback, Predicates.alwaysTrue()); } - protected QueryTaskFuture eval( + protected void eval( final QueryEnvironment env, VariableContext context, final List args, final Callback callback, - Optional> universeMaybe) { + final Predicate universe) + throws QueryException, InterruptedException { + final int depth = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; - final Predicate universe = universeMaybe.isPresent() - ? universeMaybe.get() - : Predicates.alwaysTrue(); if (env instanceof StreamableQueryEnvironment) { - StreamableQueryEnvironment streamableEnv = ((StreamableQueryEnvironment) env); - return depth == Integer.MAX_VALUE && !universeMaybe.isPresent() - ? streamableEnv.getAllRdepsUnboundedParallel(args.get(0).getExpression(), context, callback) - : streamableEnv.getAllRdeps( - args.get(0).getExpression(), universe, context, callback, depth); + ((StreamableQueryEnvironment) env) + .getAllRdeps(args.get(0).getExpression(), universe, context, callback, depth); } else { final Uniquifier uniquifier = env.createUniquifier(); - return env.eval( + env.eval( args.get(0).getExpression(), context, new Callback() { @@ -107,4 +103,21 @@ public class AllRdepsFunction implements QueryFunction { }); } } + + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + boolean unbounded = args.size() == 1; + if (unbounded && env instanceof StreamableQueryEnvironment) { + ((StreamableQueryEnvironment) env).getAllRdepsUnboundedParallel( + args.get(0).getExpression(), context, callback, forkJoinPool); + } else { + eval(env, context, expression, args, callback); + } + } } 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 f9d20dbb19..89374d0a94 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 @@ -13,16 +13,16 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; -import com.google.common.base.Function; import com.google.common.collect.ImmutableList; import com.google.common.collect.Sets; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskCallable; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; +import com.google.devtools.build.lib.query2.engine.Lexer.TokenKind; +import com.google.devtools.build.lib.query2.engine.ParallelQueryUtils.QueryTask; import com.google.devtools.build.lib.util.Preconditions; import java.util.ArrayList; import java.util.Collection; import java.util.List; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A binary algebraic set operation. @@ -56,84 +56,40 @@ public class BinaryOperatorExpression extends QueryExpression { } @Override - public QueryTaskFuture eval( - QueryEnvironment env, VariableContext context, Callback callback) { - switch (operator) { - case PLUS: - case UNION: - return evalPlus(operands, env, context, callback); - case MINUS: - case EXCEPT: - return evalMinus(operands, env, context, callback); - case INTERSECT: - case CARET: - return evalIntersect(env, context, callback); - default: - throw new IllegalStateException(operator.toString()); - } - } + protected void evalImpl( + QueryEnvironment env, VariableContext context, Callback callback) + throws QueryException, InterruptedException { - /** - * Evaluates an expression of the form "e1 + e2 + ... + eK" by evaluating all the subexpressions - * separately. - * - *

N.B. {@code operands.size()} may be {@code 1}. - */ - private static QueryTaskFuture evalPlus( - ImmutableList operands, - QueryEnvironment env, - VariableContext context, - Callback callback) { - ArrayList> queryTasks = new ArrayList<>(operands.size()); - for (QueryExpression operand : operands) { - queryTasks.add(env.eval(operand, context, callback)); + if (operator == TokenKind.PLUS || operator == TokenKind.UNION) { + for (QueryExpression operand : operands) { + env.eval(operand, context, callback); + } + return; } - return env.whenAllSucceed(queryTasks); - } - /** - * Evaluates an expression of the form "e1 - e2 - ... - eK" by noting its equivalence to - * "e1 - (e2 + ... + eK)" and evaluating the subexpressions on the right-hand-side separately. - */ - private static QueryTaskFuture evalMinus( - final ImmutableList operands, - final QueryEnvironment env, - final VariableContext context, - final Callback callback) { - QueryTaskFuture> lhsValueFuture = QueryUtil.evalAll(env, context, operands.get(0)); - Function, QueryTaskFuture> substractAsyncFunction = - new Function, QueryTaskFuture>() { - @Override - public QueryTaskFuture apply(Set lhsValue) { - final Set threadSafeLhsValue = Sets.newConcurrentHashSet(lhsValue); - Callback subtractionCallback = new Callback() { - @Override - public void process(Iterable partialResult) { - for (T target : partialResult) { - threadSafeLhsValue.remove(target); - } - } - }; - QueryTaskFuture rhsEvaluatedFuture = evalPlus( - operands.subList(1, operands.size()), env, context, subtractionCallback); - return env.whenSucceedsCall( - rhsEvaluatedFuture, - new QueryTaskCallable() { + // Once we have fully evaluated the left-hand side, we can stream-process the right-hand side + // for minus operations. Note that this is suboptimal if the left-hand side results are very + // large compared to the right-hand side. Which is the case is hard to know before evaluating. + // We could consider determining this dynamically, however, by evaluating both the left and + // right hand side partially until one side finishes sooner. + final Set lhsValue = QueryUtil.evalAll(env, context, operands.get(0)); + if (operator == TokenKind.EXCEPT || operator == TokenKind.MINUS) { + for (int i = 1; i < operands.size(); i++) { + env.eval(operands.get(i), context, + new Callback() { @Override - public Void call() throws QueryException, InterruptedException { - callback.process(threadSafeLhsValue); - return null; + public void process(Iterable partialResult) + throws QueryException, InterruptedException { + for (T target : partialResult) { + lhsValue.remove(target); + } } }); } - }; - return env.transformAsync(lhsValueFuture, substractAsyncFunction); - } + callback.process(lhsValue); + return; + } - private QueryTaskFuture evalIntersect( - final QueryEnvironment env, - final VariableContext context, - final Callback callback) { // For each right-hand side operand, intersection cannot be performed in a streaming manner; the // entire result of that operand is needed. So, in order to avoid pinning too much in memory at // once, we process each right-hand side operand one at a time and throw away that operand's @@ -141,39 +97,77 @@ public class BinaryOperatorExpression extends QueryExpression { // TODO(bazel-team): Consider keeping just the name / label of the right-hand side results // instead of the potentially heavy-weight instances of type T. This would let us process all // right-hand side operands in parallel without worrying about memory usage. - QueryTaskFuture> rollingResultFuture = QueryUtil.evalAll(env, context, operands.get(0)); + Preconditions.checkState(operator == TokenKind.INTERSECT || operator == TokenKind.CARET, + operator); for (int i = 1; i < operands.size(); i++) { - final int index = i; - Function, QueryTaskFuture>> evalOperandAndIntersectAsyncFunction = - new Function, QueryTaskFuture>>() { - @Override - public QueryTaskFuture> apply(final Set rollingResult) { - final QueryTaskFuture> rhsOperandValueFuture = - QueryUtil.evalAll(env, context, operands.get(index)); - return env.whenSucceedsCall( - rhsOperandValueFuture, - new QueryTaskCallable>() { - @Override - public Set call() throws QueryException, InterruptedException { - rollingResult.retainAll(rhsOperandValueFuture.getIfSuccessful()); - return rollingResult; - } - }); - } - }; - rollingResultFuture = - env.transformAsync(rollingResultFuture, evalOperandAndIntersectAsyncFunction); + lhsValue.retainAll(QueryUtil.evalAll(env, context, operands.get(i))); } - final QueryTaskFuture> resultFuture = rollingResultFuture; - return env.whenSucceedsCall( - resultFuture, - new QueryTaskCallable() { - @Override - public Void call() throws QueryException, InterruptedException { - callback.process(resultFuture.getIfSuccessful()); - return null; - } - }); + callback.process(lhsValue); + } + + @Override + protected void parEvalImpl( + QueryEnvironment env, + VariableContext context, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) + throws QueryException, InterruptedException { + if (operator == TokenKind.PLUS || operator == TokenKind.UNION) { + parEvalPlus(operands, env, context, callback, forkJoinPool); + } else if (operator == TokenKind.EXCEPT || operator == TokenKind.MINUS) { + parEvalMinus(operands, env, context, callback, forkJoinPool); + } else { + evalImpl(env, context, callback); + } + } + + /** + * Evaluates an expression of the form "e1 + e2 + ... + eK" by evaluating all the subexpressions + * in parallel. + */ + private static void parEvalPlus( + ImmutableList operands, + final QueryEnvironment env, + final VariableContext context, + final ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) + throws QueryException, InterruptedException { + ArrayList queryTasks = new ArrayList<>(operands.size()); + for (final QueryExpression operand : operands) { + queryTasks.add(new QueryTask() { + @Override + public void execute() throws QueryException, InterruptedException { + env.eval(operand, context, callback); + } + }); + } + ParallelQueryUtils.executeQueryTasksAndWaitInterruptiblyFailFast(queryTasks, forkJoinPool); + } + + /** + * Evaluates an expression of the form "e1 - e2 - ... - eK" by noting its equivalence to + * "e1 - (e2 + ... + eK)" and evaluating the subexpressions on the right-hand-side in parallel. + */ + private static void parEvalMinus( + ImmutableList operands, + QueryEnvironment env, + VariableContext context, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) + throws QueryException, InterruptedException { + final Set lhsValue = + Sets.newConcurrentHashSet(QueryUtil.evalAll(env, context, operands.get(0))); + ThreadSafeCallback subtractionCallback = new ThreadSafeCallback() { + @Override + public void process(Iterable partialResult) throws QueryException, InterruptedException { + for (T target : partialResult) { + lhsValue.remove(target); + } + } + }; + parEvalPlus( + operands.subList(1, operands.size()), env, context, subtractionCallback, forkJoinPool); + 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 cbc0ae8d38..d2a2eb0fa8 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 @@ -19,9 +19,10 @@ 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; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.List; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A buildfiles(x) query expression, which computes the set of BUILD files and @@ -41,17 +42,18 @@ class BuildFilesFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( final QueryEnvironment env, VariableContext context, final QueryExpression expression, List args, - final Callback callback) { + final Callback callback) + throws QueryException, InterruptedException { final Uniquifier uniquifier = env.createUniquifier(); - return env.eval( + env.eval( args.get(0).getExpression(), context, - new Callback() { + new ThreadSafeCallback() { @Override public void process(Iterable partialResult) throws QueryException, InterruptedException { @@ -64,6 +66,18 @@ class BuildFilesFunction implements QueryFunction { }); } + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + // 'eval' is written in such a way that it enables parallel evaluation of 'expression'. + eval(env, context, expression, args, callback); + } + @Override public int getMandatoryArguments() { return 1; 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 index 51c51fa99b..0f4321145d 100644 --- 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 @@ -13,17 +13,14 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; -import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; import com.google.devtools.build.lib.util.BatchCallback; -import com.google.devtools.build.lib.util.ThreadSafeBatchCallback; /** * 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. */ -@ThreadSafe -public interface Callback extends ThreadSafeBatchCallback { +public interface Callback extends BatchCallback { /** * According to the {@link BatchCallback} interface, repeated elements may be passed in here. 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 7317a35028..5eca701702 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 @@ -18,10 +18,10 @@ 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 com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import java.util.Collection; import java.util.List; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A "deps" query expression, which computes the dependencies of the argument. An optional @@ -53,15 +53,15 @@ final class DepsFunction implements QueryFunction { * Breadth-first search from the arguments. */ @Override - public QueryTaskFuture eval( + public void eval( final QueryEnvironment env, VariableContext context, final QueryExpression expression, List args, - final Callback callback) { + final Callback callback) throws QueryException, InterruptedException { final int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; final Uniquifier uniquifier = env.createUniquifier(); - return env.eval(args.get(0).getExpression(), context, new Callback() { + env.eval(args.get(0).getExpression(), context, new Callback() { @Override public void process(Iterable partialResult) throws QueryException, InterruptedException { Collection current = Sets.newHashSet(partialResult); @@ -83,4 +83,15 @@ final class DepsFunction implements QueryFunction { } }); } + + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); + } } 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 85cfe9fddb..a31196aba5 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 @@ -20,9 +20,10 @@ 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 com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.Collection; import java.util.List; +import java.util.concurrent.ForkJoinPool; /** * A query expression for user-defined query functions. @@ -45,9 +46,19 @@ public class FunctionExpression extends QueryExpression { } @Override - public QueryTaskFuture eval( - QueryEnvironment env, VariableContext context, Callback callback) { - return function.eval(env, context, this, args, callback); + protected void evalImpl( + QueryEnvironment env, VariableContext context, Callback callback) + throws QueryException, InterruptedException { + function.eval(env, context, this, args, callback); + } + + @Override + protected void parEvalImpl( + QueryEnvironment env, + VariableContext context, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + function.parEval(env, context, this, args, callback, forkJoinPool); } @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 1d68573578..4fa428adb5 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 @@ -17,9 +17,9 @@ 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.ArgumentType; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import java.util.ArrayList; import java.util.List; +import java.util.concurrent.ForkJoinPool; /** * A label(attr_name, argument) expression, which computes the set of targets @@ -52,15 +52,16 @@ class LabelsFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( final QueryEnvironment env, VariableContext context, final QueryExpression expression, final List args, - final Callback callback) { + final Callback callback) + throws QueryException, InterruptedException { final String attrName = args.get(0).getWord(); final Uniquifier uniquifier = env.createUniquifier(); - return env.eval(args.get(1).getExpression(), context, new Callback() { + env.eval(args.get(1).getExpression(), context, new Callback() { @Override public void process(Iterable partialResult) throws QueryException, InterruptedException { for (T input : partialResult) { @@ -79,4 +80,15 @@ class LabelsFunction implements QueryFunction { } }); } + + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); + } } 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 a7c3abeb62..64d94da19a 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 @@ -13,8 +13,6 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; -import com.google.common.base.Function; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import java.util.Collection; import java.util.Set; import java.util.regex.Pattern; @@ -66,24 +64,15 @@ class LetExpression extends QueryExpression { } @Override - public QueryTaskFuture eval( - final QueryEnvironment env, - final VariableContext context, - final Callback callback) { + protected void evalImpl( + QueryEnvironment env, VariableContext context, Callback callback) + throws QueryException, InterruptedException { if (!NAME_PATTERN.matcher(varName).matches()) { - return env.immediateFailedFuture( - new QueryException(this, "invalid variable name '" + varName + "' in let expression")); + throw new QueryException(this, "invalid variable name '" + varName + "' in let expression"); } - QueryTaskFuture> varValueFuture = QueryUtil.evalAll(env, context, varExpr); - Function, QueryTaskFuture> evalBodyAsyncFunction = - new Function, QueryTaskFuture>() { - @Override - public QueryTaskFuture apply(Set varValue) { - VariableContext bodyContext = VariableContext.with(context, varName, varValue); - return env.eval(bodyExpr, bodyContext, callback); - } - }; - return env.transformAsync(varValueFuture, evalBodyAsyncFunction); + Set varValue = QueryUtil.evalAll(env, context, varExpr); + VariableContext bodyContext = VariableContext.with(context, varName, varValue); + env.eval(bodyExpr, bodyContext, callback); } @Override diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LoadFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LoadFilesFunction.java index 80b912f6d7..311a6afff5 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/LoadFilesFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LoadFilesFunction.java @@ -16,9 +16,10 @@ 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.QueryTaskFuture; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; import java.util.List; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A loadfiles(x) query expression, which computes the set of .bzl files @@ -37,14 +38,15 @@ class LoadFilesFunction implements QueryEnvironment.QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( final QueryEnvironment env, VariableContext context, final QueryExpression expression, List args, - final Callback callback) { + final Callback callback) + throws QueryException, InterruptedException { final Uniquifier uniquifier = env.createUniquifier(); - return env.eval( + env.eval( args.get(0).getExpression(), context, new Callback() { @@ -64,6 +66,17 @@ class LoadFilesFunction implements QueryEnvironment.QueryFunction { }); } + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); + } + @Override public int getMandatoryArguments() { return 1; diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/OutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/engine/OutputFormatterCallback.java index 50708d6816..5d21c874be 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/OutputFormatterCallback.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/OutputFormatterCallback.java @@ -46,7 +46,7 @@ public abstract class OutputFormatterCallback implements Callback { * disambiguate between real interruptions or IO Exceptions. */ @Override - public void process(Iterable partialResult) throws QueryException, InterruptedException { + public final void process(Iterable partialResult) throws QueryException, InterruptedException { try { processOutput(partialResult); } catch (IOException e) { diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/ParallelQueryUtils.java b/src/main/java/com/google/devtools/build/lib/query2/engine/ParallelQueryUtils.java new file mode 100644 index 0000000000..6e22709deb --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/ParallelQueryUtils.java @@ -0,0 +1,188 @@ +// Copyright 2016 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.Iterables; +import com.google.devtools.build.lib.concurrent.MoreFutures; +import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; +import java.util.ArrayList; +import java.util.List; +import java.util.concurrent.CountDownLatch; +import java.util.concurrent.ExecutionException; +import java.util.concurrent.ForkJoinPool; +import java.util.concurrent.ForkJoinTask; +import java.util.concurrent.Future; + +/** Several utilities to aid in writing {@link QueryExpression#parEvalImpl} implementations. */ +public class ParallelQueryUtils { + /** + * Encapsulation of a subtask of parallel evaluation of a {@link QueryExpression}. See + * {@link #executeQueryTasksAndWaitInterruptiblyFailFast}. + */ + @ThreadSafe + public interface QueryTask { + void execute() throws QueryException, InterruptedException; + } + + /** + * Executes the given {@link QueryTask}s using the given {@link ForkJoinPool} and interruptibly + * waits for their completion. Throws the first {@link QueryException} encountered during parallel + * execution or an {@link InterruptedException} if the calling thread is interrupted. + * + *

These "fail-fast" semantics are desirable to avoid doing unneeded work when evaluating + * multiple {@link QueryTask}s in parallel: if serial execution of the tasks would result in a + * {@link QueryException} then we want parallel execution to do so as well, but there's no need to + * continue waiting for completion of the tasks after at least one of them results in a + * {@link QueryException}. + */ + public static void executeQueryTasksAndWaitInterruptiblyFailFast( + List queryTasks, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + int numTasks = queryTasks.size(); + if (numTasks == 1) { + Iterables.getOnlyElement(queryTasks).execute(); + return; + } + FailFastCountDownLatch failFastLatch = new FailFastCountDownLatch(numTasks); + ArrayList forkJoinTasks = new ArrayList<>(numTasks); + for (QueryTask queryTask : queryTasks) { + QueryTaskForkJoinTask forkJoinTask = adaptAsForkJoinTask(queryTask, failFastLatch); + forkJoinTasks.add(forkJoinTask); + @SuppressWarnings("unused") + Future possiblyIgnoredError = forkJoinPool.submit(forkJoinTask); + } + failFastLatch.await(); + try { + MoreFutures.waitForAllInterruptiblyFailFast(forkJoinTasks); + } catch (ExecutionException e) { + throw rethrowCause(e); + } + } + + private static QueryTaskForkJoinTask adaptAsForkJoinTask( + QueryTask queryTask, + FailFastCountDownLatch failFastLatch) { + return new QueryTaskForkJoinTask(queryTask, failFastLatch); + } + + private static RuntimeException rethrowCause(ExecutionException e) + throws QueryException, InterruptedException { + Throwable cause = e.getCause(); + if (cause instanceof ParallelRuntimeException) { + ((ParallelRuntimeException) cause).rethrow(); + } + throw new IllegalStateException(e); + } + + /** + * Wrapper around a {@link CountDownLatch} with initial count {@code n} that counts down once on + * "success" and {@code n} times on "failure". + * + *

This can be used in a concurrent context to wait until either {@code n} tasks are successful + * or at least one of them fails. + */ + @ThreadSafe + private static class FailFastCountDownLatch { + private final int n; + private final CountDownLatch completionLatch; + + private FailFastCountDownLatch(int n) { + this.n = n; + this.completionLatch = new CountDownLatch(n); + } + + private void await() throws InterruptedException { + completionLatch.await(); + } + + private void countDown(boolean success) { + if (success) { + completionLatch.countDown(); + } else { + for (int i = 0; i < n; i++) { + completionLatch.countDown(); + } + } + } + } + + // ForkJoinTask#adapt(Callable) wraps thrown checked exceptions as RuntimeExceptions. We avoid + // having to think about that messiness (which is inconsistent with other Future implementations) + // by having our own ForkJoinTask subclass and managing checked exceptions ourselves. + @ThreadSafe + private static class QueryTaskForkJoinTask extends ForkJoinTask { + private final QueryTask queryTask; + private final FailFastCountDownLatch completionLatch; + + private QueryTaskForkJoinTask(QueryTask queryTask, FailFastCountDownLatch completionLatch) { + this.queryTask = queryTask; + this.completionLatch = completionLatch; + } + + @Override + public Void getRawResult() { + return null; + } + + @Override + protected void setRawResult(Void value) { + } + + @Override + protected boolean exec() { + boolean successful = false; + try { + queryTask.execute(); + successful = true; + return true; + } catch (QueryException queryException) { + throw new ParallelRuntimeQueryException(queryException); + } catch (InterruptedException interruptedException) { + throw new ParallelInterruptedQueryException(interruptedException); + } finally { + completionLatch.countDown(successful); + } + } + } + + private abstract static class ParallelRuntimeException extends RuntimeException { + abstract void rethrow() throws QueryException, InterruptedException; + } + + private static class ParallelRuntimeQueryException extends ParallelRuntimeException { + private final QueryException queryException; + + private ParallelRuntimeQueryException(QueryException queryException) { + this.queryException = queryException; + } + + @Override + void rethrow() throws QueryException, InterruptedException { + throw queryException; + } + } + + private static class ParallelInterruptedQueryException extends ParallelRuntimeException { + private final InterruptedException interruptedException; + + private ParallelInterruptedQueryException(InterruptedException interruptedException) { + this.interruptedException = interruptedException; + } + + @Override + void rethrow() throws QueryException, InterruptedException { + throw interruptedException; + } + } +} 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 0c11eec8f2..879c9c1ddb 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 @@ -13,13 +13,11 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; -import com.google.common.base.Function; import com.google.common.collect.ImmutableList; -import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; import java.util.Collection; import java.util.List; import java.util.Set; -import java.util.concurrent.Callable; +import java.util.concurrent.ForkJoinPool; import javax.annotation.Nonnull; /** @@ -93,14 +91,16 @@ public interface QueryEnvironment { /** A user-defined query function. */ interface QueryFunction { - /** Name of the function as it appears in the query language. */ + /** + * Name of the function as it appears in the query language. + */ String getName(); /** * The number of arguments that are required. The rest is optional. * - *

This should be greater than or equal to zero and at smaller than or equal to the length of - * the list returned by {@link #getArgumentTypes}. + *

This should be greater than or equal to zero and at smaller than or equal to the length + * of the list returned by {@link #getArgumentTypes}. */ int getMandatoryArguments(); @@ -108,21 +108,34 @@ public interface QueryEnvironment { Iterable getArgumentTypes(); /** - * Returns a {@link QueryTaskFuture} representing the asynchronous application of this - * {@link QueryFunction} to the given {@code args}, feeding the results to the given - * {@code callback}. + * Called when a user-defined function is to be evaluated. * * @param env the query environment this function is evaluated in. * @param expression the expression being evaluated. - * @param args the input arguments. These are type-checked against the specification returned by - * {@link #getArgumentTypes} and {@link #getMandatoryArguments} + * @param args the input arguments. These are type-checked against the specification returned + * by {@link #getArgumentTypes} and {@link #getMandatoryArguments} + */ + void eval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + Callback callback) throws QueryException, InterruptedException; + + /** + * Same as {@link #eval(QueryEnvironment, VariableContext, QueryExpression, List, Callback)}, + * except that this {@link QueryFunction} may use {@code forkJoinPool} to achieve + * parallelism. + * + *

The caller must ensure that {@code env} is thread safe. */ - QueryTaskFuture eval( + void parEval( QueryEnvironment env, VariableContext context, QueryExpression expression, List args, - Callback callback); + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException; } /** @@ -143,8 +156,18 @@ public interface QueryEnvironment { * Invokes {@code callback} with the set of target nodes in the graph for the specified target * pattern, in 'blaze build' syntax. */ - QueryTaskFuture getTargetsMatchingPattern( - QueryExpression owner, String pattern, Callback callback); + void getTargetsMatchingPattern(QueryExpression owner, String pattern, Callback callback) + throws QueryException, InterruptedException; + + /** + * Same as {@link #getTargetsMatchingPattern}, but optionally making use of the given + * {@link ForkJoinPool} to achieve parallelism. + */ + void getTargetsMatchingPatternPar( + QueryExpression owner, + String pattern, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException; /** Ensures the specified target exists. */ // NOTE(bazel-team): this method is left here as scaffolding from a previous refactoring. It may @@ -180,159 +203,14 @@ public interface QueryEnvironment { Set getNodesOnPath(T from, T to) throws InterruptedException; /** - * Returns a {@link QueryTaskFuture} representing the asynchronous evaluation of the given - * {@code expr} and passing of the results to the given {@code callback}. + * Eval an expression {@code expr} and pass the results to the {@code callback}. * *

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 */ - QueryTaskFuture eval( - QueryExpression expr, VariableContext context, Callback callback); - - /** - * An asynchronous computation of part of a query evaluation. - * - *

A {@link QueryTaskFuture} can only be produced from scratch via {@link #eval}, - * {@link #executeAsync}, {@link #immediateSuccessfulFuture}, {@link #immediateFailedFuture}, and - * {@link #immediateCancelledFuture}. - * - *

Combined with the helper methods like {@link #whenSucceedsCall} below, this is very similar - * to Guava's {@link ListenableFuture}. - * - *

This class is deliberately opaque; the only ways to compose/use {@link #QueryTaskFuture} - * instances are the helper methods like {@link #whenSucceedsCall} below. A crucial consequence of - * this is there is no way for a {@link QueryExpression} or {@link QueryFunction} implementation - * to block on the result of a {@link #QueryTaskFuture}. This eliminates a large class of - * deadlocks by design! - */ - @ThreadSafe - public abstract class QueryTaskFuture { - // We use a public abstract class with a private constructor so that this type is visible to all - // the query codebase, but yet the only possible implementation is under our control in this - // file. - private QueryTaskFuture() {} - - /** - * If this {@link QueryTasksFuture}'s encapsulated computation is currently complete and - * successful, returns the result. This method is intended to be used in combination with - * {@link #whenSucceedsCall}. - * - *

See the javadoc for the various helper methods that produce {@link QueryTasksFuture} for - * the precise definition of "successful". - */ - public abstract T getIfSuccessful(); - } - - /** - * Returns a {@link QueryTaskFuture} representing the successful computation of {@code value}. - * - *

The returned {@link QueryTaskFuture} is considered "successful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful}. - */ - abstract QueryTaskFuture immediateSuccessfulFuture(R value); - - /** - * Returns a {@link QueryTaskFuture} representing a computation that was unsuccessful because of - * {@code e}. - * - *

The returned {@link QueryTaskFuture} is considered "unsuccessful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful}. - */ - abstract QueryTaskFuture immediateFailedFuture(QueryException e); - - /** - * Returns a {@link QueryTaskFuture} representing a cancelled computation. - * - *

The returned {@link QueryTaskFuture} is considered "unsuccessful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful}. - */ - abstract QueryTaskFuture immediateCancelledFuture(); - - /** A {@link ThreadSafe} {@link Callable} for computations during query evaluation. */ - @ThreadSafe - public interface QueryTaskCallable extends Callable { - /** - * Returns the computed value or throws a {@link QueryException} on failure or a - * {@link InterruptedException} on interruption. - */ - @Override - T call() throws QueryException, InterruptedException; - } - - /** - * Returns a {@link QueryTaskFuture} representing the given computation {@code callable} being - * performed asynchronously. - * - *

The returned {@link QueryTaskFuture} is considered "successful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful} iff {@code callable#call} does not throw an exception. - */ - QueryTaskFuture executeAsync(QueryTaskCallable callable); - - /** - * Returns a {@link QueryTaskFuture} representing the given computation {@code callable} being - * performed after the successful completion of the computation encapsulated by the given - * {@code future} has completed successfully. - * - *

The returned {@link QueryTaskFuture} is considered "successful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful} iff {@code future} is successful and - * {@code callable#call} does not throw an exception. - */ - QueryTaskFuture whenSucceedsCall(QueryTaskFuture future, QueryTaskCallable callable); - - /** - * Returns a {@link QueryTaskFuture} representing the successful completion of all the - * computations encapsulated by the given {@code futures}. - * - *

The returned {@link QueryTaskFuture} is considered "successful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful} iff all of the given computations are "successful". - */ - QueryTaskFuture whenAllSucceed(Iterable> futures); - - /** - * Returns a {@link QueryTaskFuture} representing the given computation {@code callable} being - * performed after the successful completion of all the computations encapsulated by the given - * {@code futures}. - * - *

The returned {@link QueryTaskFuture} is considered "successful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful} iff all of the given computations are "successful" and - * {@code callable#call} does not throw an exception. - */ - QueryTaskFuture whenAllSucceedCall( - Iterable> futures, QueryTaskCallable callable); - - /** - * Returns a {@link QueryTaskFuture} representing the asynchronous application of the given - * {@code function} to the value produced by the computation encapsulated by the given - * {@code future}. - * - *

The returned {@link QueryTaskFuture} is considered "successful" for purposes of - * {@link #whenSucceedsCall}, {@link #whenAllSucceed}, and - * {@link QueryTaskFuture#getIfSuccessful} iff {@code} future is "successful". - */ - QueryTaskFuture transformAsync( - QueryTaskFuture future, Function> function); - - /** - * The sole package-protected subclass of {@link QueryTaskFuture}. - * - *

Do not subclass this class; it's an implementation detail. {@link QueryExpression} and - * {@link QueryFunction} implementations should use {@link #eval} and {@link #executeAsync} to get - * access to {@link QueryTaskFuture} instances and the then use the helper methods like - * {@link #whenSucceedsCall} to transform them. - */ - abstract class QueryTaskFutureImplBase extends QueryTaskFuture { - protected QueryTaskFutureImplBase() { - } - } + void eval(QueryExpression expr, VariableContext context, Callback callback) + throws QueryException, InterruptedException; /** * Creates a Uniquifier for use in a {@code QueryExpression}. Note that the usage of this an @@ -494,6 +372,9 @@ public interface QueryEnvironment { Set> getVisibility(T from) throws QueryException, InterruptedException; } + /** Returns the {@link QueryExpressionEvalListener} that this {@link QueryEnvironment} uses. */ + QueryExpressionEvalListener getEvalListener(); + /** List of the default query functions. */ List DEFAULT_QUERY_FUNCTIONS = ImmutableList.of( 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 920722db4b..e35e9e4807 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,8 +14,9 @@ package com.google.devtools.build.lib.query2.engine; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.Collection; +import java.util.concurrent.ForkJoinPool; /** * Base class for expressions in the Blaze query language, revision 2. @@ -58,9 +59,9 @@ public abstract class QueryExpression { protected QueryExpression() {} /** - * Returns a {@link QueryTaskFuture} representing the asynchronous evaluation of this query in the - * specified environment, notifying the callback with a result. Note that it is allowed to notify - * the callback with partial results instead of just one final result. + * Evaluates this query in the specified environment, and notifies the callback with a 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 * QueryException to be thrown. @@ -70,10 +71,45 @@ public abstract class QueryExpression { * thrown. If disabled, evaluation will stumble on to produce a (possibly * inaccurate) result, but a result nonetheless. */ - public abstract QueryTaskFuture eval( + public final void eval( + QueryEnvironment env, + VariableContext context, + Callback callback) throws QueryException, InterruptedException { + env.getEvalListener().onEval(this, env, context, callback); + evalImpl(env, context, callback); + } + + protected abstract void evalImpl( + QueryEnvironment env, + VariableContext context, + Callback callback) throws QueryException, InterruptedException; + + /** + * Evaluates this query in the specified environment, as in + * {@link #eval(QueryEnvironment, VariableContext, Callback)}, using {@code forkJoinPool} to + * achieve parallelism. + * + *

The caller must ensure that {@code env} is thread safe. + */ + @ThreadSafe + public final void parEval( + QueryEnvironment env, + VariableContext context, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) + throws QueryException, InterruptedException { + env.getEvalListener().onParEval(this, env, context, callback, forkJoinPool); + parEvalImpl(env, context, callback, forkJoinPool); + } + + protected void parEvalImpl( QueryEnvironment env, VariableContext context, - Callback callback); + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) + throws QueryException, InterruptedException { + evalImpl(env, context, callback); + } /** * Collects all target patterns that are referenced anywhere within this query expression and adds diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpressionEvalListener.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpressionEvalListener.java new file mode 100644 index 0000000000..e6bdaef7a9 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpressionEvalListener.java @@ -0,0 +1,67 @@ +// Copyright 2016 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.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; +import java.util.concurrent.ForkJoinPool; + +/** Listener for calls to the internal methods of {@link QueryExpression} used for evaluation. */ +@ThreadSafe +public interface QueryExpressionEvalListener { + /** Called right before {@link QueryExpression#evalImpl} is called. */ + void onEval( + QueryExpression expr, + QueryEnvironment env, + VariableContext context, + Callback callback); + + /** Called right before {@link QueryExpression#parEvalImpl} is called. */ + void onParEval( + QueryExpression expr, + QueryEnvironment env, + VariableContext context, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool); + + /** A {@link QueryExpressionEvalListener} that does nothing. */ + class NullListener implements QueryExpressionEvalListener { + private static final NullListener INSTANCE = new NullListener<>(); + + private NullListener() { + } + + @SuppressWarnings("unchecked") + public static NullListener instance() { + return (NullListener) INSTANCE; + } + + @Override + public void onEval( + QueryExpression expr, + QueryEnvironment env, + VariableContext context, + Callback callback) { + } + + @Override + public void onParEval( + QueryExpression expr, + QueryEnvironment env, + VariableContext context, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) { + } + } +} + 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 index afb4192128..2d7be2ed74 100644 --- 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 @@ -13,13 +13,11 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; + import com.google.common.collect.ImmutableList; import com.google.common.collect.Iterables; import com.google.common.collect.MapMaker; -import com.google.common.collect.Sets; import com.google.devtools.build.lib.collect.CompactHashSet; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskCallable; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import java.util.Collections; import java.util.Set; @@ -30,18 +28,17 @@ public final class QueryUtil { /** A {@link Callback} that can aggregate all the partial results into one set. */ public interface AggregateAllCallback extends Callback { - /** Returns a (mutable) set of all the results. */ Set getResult(); } - /** A {@link OutputFormatterCallback} that is also a {@link AggregateAllCallback}. */ + /** A {@link OutputFormatterCallback} that can aggregate all the partial results into one set. */ public abstract static class AggregateAllOutputFormatterCallback - extends ThreadSafeOutputFormatterCallback implements AggregateAllCallback { + extends OutputFormatterCallback implements AggregateAllCallback { } private static class AggregateAllOutputFormatterCallbackImpl extends AggregateAllOutputFormatterCallback { - private final Set result = Sets.newConcurrentHashSet(); + private final Set result = CompactHashSet.create(); @Override public final void processOutput(Iterable partialResult) { @@ -54,64 +51,65 @@ public final class QueryUtil { } } - private static class OrderedAggregateAllOutputFormatterCallbackImpl - extends AggregateAllOutputFormatterCallback { - private final Set result = CompactHashSet.create(); - - @Override - public final synchronized void processOutput(Iterable partialResult) { - Iterables.addAll(result, partialResult); - } - - @Override - public synchronized Set getResult() { - return result; - } - } - /** - * Returns a fresh {@link AggregateAllOutputFormatterCallback} instance whose - * {@link AggregateAllCallback#getResult} returns all the elements of the result in the order they - * were processed. + * Returns a fresh {@link AggregateAllOutputFormatterCallback} that can aggregate all the partial + * results into one set. + * + *

Intended to be used by top-level evaluation of {@link QueryExpression}s; contrast with + * {@link #newAggregateAllCallback}. */ public static AggregateAllOutputFormatterCallback - newOrderedAggregateAllOutputFormatterCallback() { - return new OrderedAggregateAllOutputFormatterCallbackImpl<>(); + newAggregateAllOutputFormatterCallback() { + return new AggregateAllOutputFormatterCallbackImpl<>(); } - /** Returns a fresh {@link AggregateAllCallback} instance. */ + /** + * Returns a fresh {@link AggregateAllCallback}. + * + *

Intended to be used by {@link QueryExpression} implementations; contrast with + * {@link #newAggregateAllOutputFormatterCallback}. + */ public static AggregateAllCallback newAggregateAllCallback() { return new AggregateAllOutputFormatterCallbackImpl<>(); } /** - * Returns a {@link QueryTaskFuture} representing the evaluation of {@code expr} as a (mutable) - * {@link Set} comprised of all the results. + * Fully evaluate a {@code QueryExpression} and return a set with all the results. * *

Should only be used by QueryExpressions when it is the only way of achieving correctness. */ - public static QueryTaskFuture> evalAll( - QueryEnvironment env, VariableContext context, QueryExpression expr) { - final AggregateAllCallback callback = newAggregateAllCallback(); - return env.whenSucceedsCall( - env.eval(expr, context, callback), - new QueryTaskCallable>() { - @Override - public Set call() { - return callback.getResult(); - } - }); + public static Set evalAll( + QueryEnvironment env, VariableContext context, QueryExpression expr) + throws QueryException, InterruptedException { + AggregateAllCallback callback = newAggregateAllCallback(); + env.eval(expr, context, callback); + return callback.getResult(); } /** A trivial {@link Uniquifier} base class. */ - public abstract static class AbstractUniquifier implements Uniquifier { - private final Set alreadySeen; + public abstract static class AbstractUniquifier + extends AbstractUniquifierBase { + private final CompactHashSet alreadySeen = CompactHashSet.create(); - protected AbstractUniquifier() { - this(/*concurrencyLevel=*/ 1); + @Override + public final boolean unique(T element) { + return alreadySeen.add(extractKey(element)); } - protected AbstractUniquifier(int concurrencyLevel) { + /** + * Extracts an unique key that can be used to dedupe the given {@code element}. + * + *

Depending on the choice of {@code K}, this enables potential memory optimizations. + */ + protected abstract K extractKey(T element); + } + + /** A trivial {@link ThreadSafeUniquifier} base class. */ + public abstract static class AbstractThreadSafeUniquifier + extends AbstractUniquifierBase implements ThreadSafeUniquifier { + private final Set alreadySeen; + + protected AbstractThreadSafeUniquifier(int concurrencyLevel) { this.alreadySeen = Collections.newSetFromMap( new MapMaker().concurrencyLevel(concurrencyLevel).makeMap()); } @@ -121,6 +119,15 @@ public final class QueryUtil { return alreadySeen.add(extractKey(element)); } + /** + * Extracts an unique key that can be used to dedupe the given {@code element}. + * + *

Depending on the choice of {@code K}, this enables potential memory optimizations. + */ + protected abstract K extractKey(T element); + } + + private abstract static class AbstractUniquifierBase implements Uniquifier { @Override public final ImmutableList unique(Iterable newElements) { ImmutableList.Builder result = ImmutableList.builder(); @@ -131,12 +138,5 @@ public final class QueryUtil { } return result.build(); } - - /** - * Extracts an unique key that can be used to dedupe the given {@code element}. - * - *

Depending on the choice of {@code K}, this enables potential memory optimizations. - */ - protected abstract K extractKey(T element); } -} \ No newline at end of file +} 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 82faf72538..7d691c0b04 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,14 +13,12 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; -import com.google.common.base.Function; -import com.google.common.base.Optional; 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; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.List; import java.util.Set; @@ -56,31 +54,16 @@ public final class RdepsFunction extends AllRdepsFunction { * towards the universe while staying within the transitive closure. */ @Override - public QueryTaskFuture eval( - final QueryEnvironment env, - final VariableContext context, - final QueryExpression expression, - final List args, - final Callback callback) { - QueryTaskFuture> universeValueFuture = - QueryUtil.evalAll(env, context, args.get(0).getExpression()); - Function, QueryTaskFuture> evalInUniverseAsyncFunction = - new Function, QueryTaskFuture>() { - @Override - public QueryTaskFuture apply(Set universeValue) { - Predicate universe; - try { - env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE); - universe = Predicates.in(env.getTransitiveClosure(universeValue)); - } catch (InterruptedException e) { - return env.immediateCancelledFuture(); - } catch (QueryException e) { - return env.immediateFailedFuture(e); - } - return RdepsFunction.this.eval( - env, context, args.subList(1, args.size()), callback, Optional.of(universe)); - } - }; - return env.transformAsync(universeValueFuture, evalInUniverseAsyncFunction); + public void eval(QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, Callback callback) + throws QueryException, + InterruptedException { + Set universeValue = QueryUtil.evalAll(env, context, args.get(0).getExpression()); + env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE); + + Predicate universe = Predicates.in(env.getTransitiveClosure(universeValue)); + eval(env, context, 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 6b182ee7b1..9dc75a43e1 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 @@ -18,8 +18,9 @@ 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.QueryFunction; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.List; +import java.util.concurrent.ForkJoinPool; import java.util.regex.Pattern; import java.util.regex.PatternSyntaxException; @@ -32,24 +33,25 @@ public abstract class RegexFilterExpression implements QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( final QueryEnvironment env, VariableContext context, QueryExpression expression, final List args, - Callback callback) { + Callback callback) + throws QueryException, InterruptedException { String rawPattern = getPattern(args); final Pattern compiledPattern; try { compiledPattern = Pattern.compile(rawPattern); } catch (PatternSyntaxException e) { - return env.immediateFailedFuture(new QueryException( + throw new QueryException( expression, String.format( "illegal '%s' pattern regexp '%s': %s", getName(), rawPattern, - e.getMessage()))); + e.getMessage())); } // Note that Patttern#matcher is thread-safe and so this Predicate can safely be used @@ -66,10 +68,21 @@ public abstract class RegexFilterExpression implements QueryFunction { } }; - return env.eval( + env.eval( Iterables.getLast(args).getExpression(), context, - new FilteredCallback<>(callback, matchFilter)); + filteredCallback(callback, matchFilter)); + } + + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); } /** @@ -98,6 +111,21 @@ public abstract class RegexFilterExpression implements QueryFunction { protected abstract String getPattern(List args); + /** + * Returns a new {@link Callback} that forwards values that satisfies the given {@link Predicate} + * to the given {@code parentCallback}. + * + *

The returned {@link Callback} will be a {@link ThreadSafeCallback} iff + * {@code parentCallback} is as well. + */ + private static Callback filteredCallback( + final Callback parentCallback, + final Predicate retainIfTrue) { + return (parentCallback instanceof ThreadSafeCallback) + ? new ThreadSafeFilteredCallback<>((ThreadSafeCallback) parentCallback, retainIfTrue) + : new FilteredCallback<>(parentCallback, retainIfTrue); + } + private static class FilteredCallback implements Callback { private final Callback parentCallback; private final Predicate retainIfTrue; @@ -120,4 +148,12 @@ public abstract class RegexFilterExpression implements QueryFunction { return "filtered parentCallback of : " + retainIfTrue; } } + + private static class ThreadSafeFilteredCallback + extends FilteredCallback implements ThreadSafeCallback { + private ThreadSafeFilteredCallback( + ThreadSafeCallback parentCallback, Predicate retainIfTrue) { + super(parentCallback, retainIfTrue); + } + } } 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 e1eadf3aa5..ac4b460f40 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 @@ -14,8 +14,7 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.base.Joiner; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; -import java.util.ArrayList; + import java.util.Collection; import java.util.List; @@ -47,13 +46,12 @@ class SetExpression extends QueryExpression { } @Override - public QueryTaskFuture eval( - QueryEnvironment env, VariableContext context, Callback callback) { - ArrayList> queryTasks = new ArrayList<>(words.size()); + protected void evalImpl( + QueryEnvironment env, VariableContext context, Callback callback) + throws QueryException, InterruptedException { for (TargetLiteral expr : words) { - queryTasks.add(env.eval(expr, context, callback)); + env.eval(expr, context, callback); } - return env.whenAllSucceed(queryTasks); } @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 4b07a99f07..8dc0442468 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 @@ -19,9 +19,8 @@ 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 com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskCallable; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import java.util.List; +import java.util.concurrent.ForkJoinPool; import java.util.concurrent.atomic.AtomicBoolean; /** @@ -50,37 +49,36 @@ class SomeFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( QueryEnvironment env, VariableContext context, - final QueryExpression expression, + QueryExpression expression, List args, - final Callback callback) { + final Callback callback) throws QueryException, InterruptedException { final AtomicBoolean someFound = new AtomicBoolean(false); - QueryTaskFuture operandEvalFuture = env.eval( - args.get(0).getExpression(), - context, - new Callback() { - @Override - public void process(Iterable partialResult) - throws QueryException, InterruptedException { - if (someFound.get() || Iterables.isEmpty(partialResult)) { - return; - } - callback.process(ImmutableSet.of(partialResult.iterator().next())); - someFound.set(true); - } - }); - return env.whenSucceedsCall( - operandEvalFuture, - new QueryTaskCallable() { - @Override - public Void call() throws QueryException { - if (!someFound.get()) { - throw new QueryException(expression, "argument set is empty"); - } - return null; - } - }); + env.eval(args.get(0).getExpression(), context, new Callback() { + @Override + public void process(Iterable 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"); + } + } + + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); } } 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 229863c79a..2d0df0ef59 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 @@ -20,10 +20,10 @@ import com.google.common.collect.Sets.SetView; 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 com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskCallable; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; + import java.util.List; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A somepath(x, y) query expression, which computes the set of nodes @@ -51,52 +51,50 @@ class SomePathFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( - final QueryEnvironment env, + public void eval( + QueryEnvironment env, VariableContext context, - final QueryExpression expression, + QueryExpression expression, List args, - final Callback callback) { - final QueryTaskFuture> fromValueFuture = - QueryUtil.evalAll(env, context, args.get(0).getExpression()); - final QueryTaskFuture> toValueFuture = - QueryUtil.evalAll(env, context, args.get(1).getExpression()); + final Callback callback) throws QueryException, InterruptedException { + Set fromValue = QueryUtil.evalAll(env, context, args.get(0).getExpression()); + Set toValue = QueryUtil.evalAll(env, context, args.get(1).getExpression()); - return env.whenAllSucceedCall( - ImmutableList.of(fromValueFuture, toValueFuture), - new QueryTaskCallable() { - @Override - public Void call() throws QueryException, InterruptedException { - // Implementation strategy: for each x in "from", compute its forward - // transitive closure. If it intersects "to", then do a path search from x - // to an arbitrary node in the intersection, and return the path. This - // avoids computing the full transitive closure of "from" in some cases. + // Implementation strategy: for each x in "from", compute its forward + // transitive closure. If it intersects "to", then do a path search from x + // to an arbitrary node in the intersection, and return the path. This + // avoids computing the full transitive closure of "from" in some cases. - Set fromValue = fromValueFuture.getIfSuccessful(); - Set toValue = toValueFuture.getIfSuccessful(); + env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); - env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); + // This set contains all nodes whose TC does not intersect "toValue". + Uniquifier uniquifier = env.createUniquifier(); - // This set contains all nodes whose TC does not intersect "toValue". - Uniquifier uniquifier = env.createUniquifier(); + for (T x : uniquifier.unique(fromValue)) { + Set xtc = env.getTransitiveClosure(ImmutableSet.of(x)); + SetView result; + if (xtc.size() > toValue.size()) { + result = Sets.intersection(toValue, xtc); + } else { + result = Sets.intersection(xtc, toValue); + } + if (!result.isEmpty()) { + callback.process(env.getNodesOnPath(x, result.iterator().next())); + return; + } + uniquifier.unique(xtc); + } + callback.process(ImmutableSet.of()); + } - for (T x : uniquifier.unique(fromValue)) { - Set xtc = env.getTransitiveClosure(ImmutableSet.of(x)); - SetView result; - if (xtc.size() > toValue.size()) { - result = Sets.intersection(toValue, xtc); - } else { - result = Sets.intersection(xtc, toValue); - } - if (!result.isEmpty()) { - callback.process(env.getNodesOnPath(x, result.iterator().next())); - return null; - } - uniquifier.unique(xtc); - } - callback.process(ImmutableSet.of()); - return null; - } - }); + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/StreamableQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/engine/StreamableQueryEnvironment.java index bb67e93ad5..eda505a7ce 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/StreamableQueryEnvironment.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/StreamableQueryEnvironment.java @@ -14,6 +14,7 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.base.Predicate; +import java.util.concurrent.ForkJoinPool; /** * The environment of a Blaze query which supports predefined streaming operations. @@ -23,19 +24,22 @@ import com.google.common.base.Predicate; public interface StreamableQueryEnvironment extends QueryEnvironment { /** Retrieve and process all reverse dependencies of given expression in a streaming manner. */ - QueryTaskFuture getAllRdeps( + void getAllRdeps( QueryExpression expression, Predicate universe, VariableContext context, Callback callback, - int depth); + int depth) + throws QueryException, InterruptedException; /** * Similar to {@link #getAllRdeps} but finds all rdeps without a depth bound, making use of the * provided {@code forkJoinPool}. */ - QueryTaskFuture getAllRdepsUnboundedParallel( + void getAllRdepsUnboundedParallel( QueryExpression expression, VariableContext context, - Callback callback); + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) + throws QueryException, InterruptedException; } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SynchronizedDelegatingOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SynchronizedDelegatingOutputFormatterCallback.java deleted file mode 100644 index 68a79338b7..0000000000 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/SynchronizedDelegatingOutputFormatterCallback.java +++ /dev/null @@ -1,58 +0,0 @@ -// Copyright 2017 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 java.io.IOException; -import javax.annotation.Nullable; - -/** - * A {@link ThreadSafeOutputFormatterCallback} wrapper around a {@link OutputFormatterCallback} - * delegate. - */ -public final class SynchronizedDelegatingOutputFormatterCallback - extends ThreadSafeOutputFormatterCallback { - private final OutputFormatterCallback delegate; - - public SynchronizedDelegatingOutputFormatterCallback(OutputFormatterCallback delegate) { - this.delegate = delegate; - } - - @Override - public synchronized void start() throws IOException { - delegate.start(); - } - - @Override - public synchronized void close(boolean failFast) throws InterruptedException, IOException { - delegate.close(failFast); - } - - @Override - public synchronized void process(Iterable partialResult) - throws QueryException, InterruptedException { - delegate.process(partialResult); - } - - @Override - public synchronized void processOutput(Iterable partialResult) - throws IOException, InterruptedException { - delegate.processOutput(partialResult); - } - - @Override - @Nullable - public IOException getIoException() { - return delegate.getIoException(); - } -} 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 733bffb065..aeace9aa70 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 @@ -13,10 +13,11 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import com.google.devtools.build.lib.util.Preconditions; + import java.util.Collection; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A literal set of targets, using 'blaze build' syntax. Or, a reference to a @@ -44,31 +45,38 @@ public final class TargetLiteral extends QueryExpression { return LetExpression.isValidVarReference(pattern); } - private QueryTaskFuture evalVarReference( - QueryEnvironment env, VariableContext context, Callback callback) { + private void evalVarReference(VariableContext context, Callback callback) + throws QueryException, InterruptedException { String varName = LetExpression.getNameFromReference(pattern); Set value = context.get(varName); if (value == null) { - return env.immediateFailedFuture( - new QueryException(this, "undefined variable '" + varName + "'")); + throw new QueryException(this, "undefined variable '" + varName + "'"); } - try { - callback.process(value); - return env.immediateSuccessfulFuture(null); - } catch (QueryException e) { - return env.immediateFailedFuture(e); - } catch (InterruptedException e) { - return env.immediateCancelledFuture(); + callback.process(value); + } + + @Override + protected void evalImpl( + QueryEnvironment env, VariableContext context, Callback callback) + throws QueryException, InterruptedException { + if (isVariableReference()) { + evalVarReference(context, callback); + } else { + env.getTargetsMatchingPattern(this, pattern, callback); } } @Override - public QueryTaskFuture eval( - QueryEnvironment env, VariableContext context, Callback callback) { + protected void parEvalImpl( + QueryEnvironment env, + VariableContext context, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) + throws QueryException, InterruptedException { if (isVariableReference()) { - return evalVarReference(env, context, callback); + evalVarReference(context, callback); } else { - return env.getTargetsMatchingPattern(this, pattern, callback); + env.getTargetsMatchingPatternPar(this, pattern, callback, forkJoinPool); } } 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 d9ed576a5d..956e604a44 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 @@ -15,11 +15,9 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.collect.ImmutableList; import com.google.common.collect.Sets; -import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; 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 com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting; import java.util.ArrayList; import java.util.Collection; @@ -29,6 +27,7 @@ import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A tests(x) filter expression, which returns all the tests in set x, @@ -63,15 +62,15 @@ class TestsFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( final QueryEnvironment env, VariableContext context, QueryExpression expression, List args, - final Callback callback) { + final Callback callback) throws QueryException, InterruptedException { final Closure closure = new Closure<>(expression, env); - return env.eval(args.get(0).getExpression(), context, new Callback() { + env.eval(args.get(0).getExpression(), context, new Callback() { @Override public void process(Iterable partialResult) throws QueryException, InterruptedException { for (T target : partialResult) { @@ -87,6 +86,17 @@ class TestsFunction implements QueryFunction { }); } + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); + } + /** * Decides whether to include a test in a test_suite or not. * @param testTags Collection of all tags exhibited by a given test. @@ -141,8 +151,10 @@ class TestsFunction implements QueryFunction { } } - /** A closure over the temporary state needed to compute the expression. */ - @ThreadSafe + /** + * A closure over the temporary state needed to compute the expression. This makes the evaluation + * thread-safe, as long as instances of this class are used only within a single thread. + */ private static final class Closure { private final QueryExpression expression; /** A dynamically-populated mapping from test_suite rules to their tests. */ @@ -165,8 +177,7 @@ class TestsFunction implements QueryFunction { * * @precondition env.getAccessor().isTestSuite(testSuite) */ - private synchronized Set getTestsInSuite(T testSuite) - throws QueryException, InterruptedException { + private Set getTestsInSuite(T testSuite) throws QueryException, InterruptedException { Set tests = testsInSuite.get(testSuite); if (tests == null) { tests = Sets.newHashSet(); diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeCallback.java b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeCallback.java new file mode 100644 index 0000000000..950335e38a --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeCallback.java @@ -0,0 +1,23 @@ +// Copyright 2014 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.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; +import com.google.devtools.build.lib.util.ThreadSafeBatchCallback; + +/** Marker interface for a {@link Callback} that is {@link ThreadSafe}. */ +@ThreadSafe +public interface ThreadSafeCallback + extends Callback, ThreadSafeBatchCallback { +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeOutputFormatterCallback.java deleted file mode 100644 index bc3eb59f84..0000000000 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeOutputFormatterCallback.java +++ /dev/null @@ -1,21 +0,0 @@ -// Copyright 2017 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.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; - -/** A marker parent class for a {@link ThreadSafe} {@link OutputFormatterCallback}. */ -@ThreadSafe -public abstract class ThreadSafeOutputFormatterCallback extends OutputFormatterCallback { -} \ No newline at end of file diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeUniquifier.java b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeUniquifier.java new file mode 100644 index 0000000000..747185582f --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeUniquifier.java @@ -0,0 +1,22 @@ +// Copyright 2016 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.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; + +/** Marker interface for a {@link ThreadSafe} {@link Uniquifier}. */ +@ThreadSafe +public interface ThreadSafeUniquifier extends Uniquifier { +} + 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 index 5f8faf56b1..ed2b2376fa 100644 --- 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 @@ -14,10 +14,8 @@ package com.google.devtools.build.lib.query2.engine; import com.google.common.collect.ImmutableList; -import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; /** A helper for deduping values. */ -@ThreadSafe public interface Uniquifier { /** Returns whether {@code newElement} has been seen before. */ boolean unique(T newElement); 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 b09910c715..532f331378 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 @@ -14,14 +14,13 @@ package com.google.devtools.build.lib.query2.engine; -import com.google.common.base.Function; 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.ArgumentType; import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction; -import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture; import java.util.List; import java.util.Set; +import java.util.concurrent.ForkJoinPool; /** * A visible(x, y) query expression, which computes the subset of nodes in y @@ -53,32 +52,34 @@ public class VisibleFunction implements QueryFunction { } @Override - public QueryTaskFuture eval( + public void eval( final QueryEnvironment env, - final VariableContext context, + VariableContext context, QueryExpression expression, - final List args, - final Callback callback) { - final QueryTaskFuture> toSetFuture = - QueryUtil.evalAll(env, context, args.get(0).getExpression()); - Function, QueryTaskFuture> computeVisibleNodesAsyncFunction = - new Function, QueryTaskFuture>() { - @Override - public QueryTaskFuture apply(final Set toSet) { - return env.eval(args.get(1).getExpression(), context, new Callback() { - @Override - public void process(Iterable partialResult) - throws QueryException, InterruptedException { - for (T t : partialResult) { - if (visibleToAll(env, toSet, t)) { - callback.process(ImmutableList.of(t)); - } - } - } - }); + List args, + final Callback callback) throws QueryException, InterruptedException { + final Set toSet = QueryUtil.evalAll(env, context, args.get(0).getExpression()); + env.eval(args.get(1).getExpression(), context, new Callback() { + @Override + public void process(Iterable partialResult) throws QueryException, InterruptedException { + for (T t : partialResult) { + if (visibleToAll(env, toSet, t)) { + callback.process(ImmutableList.of(t)); } - }; - return env.transformAsync(toSetFuture, computeVisibleNodesAsyncFunction); + } + } + }); + } + + @Override + public void parEval( + QueryEnvironment env, + VariableContext context, + QueryExpression expression, + List args, + ThreadSafeCallback callback, + ForkJoinPool forkJoinPool) throws QueryException, InterruptedException { + eval(env, context, expression, args, callback); } /** Returns true if {@code target} is visible to all targets in {@code toSet}. */ -- cgit v1.2.3