A bunch of small changes to prepare SkyQueryEnvironment for full-parallel evaluation:

-Rename QueryExpression#evalConcurrently to QueryExpression#parEval. (parallelism is not concurrency! See https://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/)
-Have SkyQueryEnvironment#eval (used recursively in #evaluateQuery) dynamically call QueryExpression#parEval when appropriate.
-Delete QueryExpression#canEvalConcurrently.
-Add ThreadSafety annotations in a bunch of relevant places in the query codebase.
-A bunch of testing infrastructure to test parallel query evaluation.
-TODOs for implementing parallel evaluation of all QueryExpression nodes.

--
MOS_MIGRATED_REVID=132436340

16 files changed, 185 insertions, 41 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
index 769bdb29bd..cd597a66cd 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
@@ -30,6 +30,7 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
 import com.google.devtools.build.lib.query2.engine.VariableContext;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -55,6 +56,7 @@ public abstract class AbstractBlazeQueryEnvironment<T>
 
   private final Set<Setting> settings;
   private final List<QueryFunction> extraFunctions;
+  private final QueryExpressionEvalListener<T> evalListener;
 
   private static final Logger LOG = Logger.getLogger(AbstractBlazeQueryEnvironment.class.getName());
 
@@ -63,7 +65,8 @@ public abstract class AbstractBlazeQueryEnvironment<T>
       Predicate<Label> labelFilter,
       EventHandler eventHandler,
       Set<Setting> settings,
-      Iterable<QueryFunction> extraFunctions) {
+      Iterable<QueryFunction> extraFunctions,
+      QueryExpressionEvalListener<T> evalListener) {
     this.eventHandler = new ErrorSensingEventHandler(eventHandler);
     this.keepGoing = keepGoing;
     this.strictScope = strictScope;
@@ -71,6 +74,7 @@ public abstract class AbstractBlazeQueryEnvironment<T>
     this.labelFilter = labelFilter;
     this.settings = Sets.immutableEnumSet(settings);
     this.extraFunctions = ImmutableList.copyOf(extraFunctions);
+    this.evalListener = evalListener;
   }
 
   private static DependencyFilter constructDependencyFilter(
@@ -213,4 +217,9 @@ public abstract class AbstractBlazeQueryEnvironment<T>
     builder.addAll(extraFunctions);
     return builder.build();
   }
+
+  @Override
+  public QueryExpressionEvalListener<T> getEvalListener() {
+    return evalListener;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
index 65b853b473..1b1749fe08 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
@@ -41,6 +41,7 @@ import com.google.devtools.build.lib.query2.engine.DigraphQueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AbstractUniquifier;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
 import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException;
@@ -96,8 +97,10 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
       Predicate<Label> labelFilter,
       EventHandler eventHandler,
       Set<Setting> settings,
-      Iterable<QueryFunction> extraFunctions) {
-    super(keepGoing, strictScope, labelFilter, eventHandler, settings, extraFunctions);
+      Iterable<QueryFunction> extraFunctions,
+      QueryExpressionEvalListener<Target> evalListener) {
+    super(
+        keepGoing, strictScope, labelFilter, eventHandler, settings, extraFunctions, evalListener);
     this.targetPatternEvaluator = targetPatternEvaluator;
     this.transitivePackageLoader = transitivePackageLoader;
     this.targetProvider = packageProvider;
diff --git a/src/main/java/com/google/devtools/build/lib/query2/QueryEnvironmentFactory.java b/src/main/java/com/google/devtools/build/lib/query2/QueryEnvironmentFactory.java
index c2f8f80592..42b9f203a4 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/QueryEnvironmentFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/QueryEnvironmentFactory.java
@@ -24,6 +24,7 @@ import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
 import com.google.devtools.build.lib.pkgcache.TransitivePackageLoader;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory;
 
@@ -42,6 +43,7 @@ public class QueryEnvironmentFactory {
       boolean orderedResults, List<String> universeScope, int loadingPhaseThreads,
       Predicate<Label> labelFilter,
       EventHandler eventHandler, Set<Setting> settings, Iterable<QueryFunction> functions,
+      QueryExpressionEvalListener<Target> evalListener,
       @Nullable PathPackageLocator packagePath) {
     Preconditions.checkNotNull(universeScope);
     if (canUseSkyQuery(orderedResults, universeScope, packagePath, strictScope, labelFilter)) {
@@ -51,6 +53,7 @@ public class QueryEnvironmentFactory {
           eventHandler,
           settings,
           functions,
+          evalListener,
           targetPatternEvaluator.getOffset(),
           graphFactory,
           universeScope,
@@ -58,7 +61,7 @@ public class QueryEnvironmentFactory {
     } else {
       return new BlazeQueryEnvironment(transitivePackageLoader, packageProvider,
           targetPatternEvaluator, keepGoing, strictScope, loadingPhaseThreads, labelFilter,
-          eventHandler, settings, functions);
+          eventHandler, settings, functions, evalListener);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index 407c4f24de..6623ca695a 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -58,10 +58,12 @@ import com.google.devtools.build.lib.query2.engine.FunctionExpression;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.query2.engine.QueryExpressionMapper;
 import com.google.devtools.build.lib.query2.engine.RdepsFunction;
 import com.google.devtools.build.lib.query2.engine.StreamableQueryEnvironment;
 import com.google.devtools.build.lib.query2.engine.TargetLiteral;
+import com.google.devtools.build.lib.query2.engine.ThreadSafeCallback;
 import com.google.devtools.build.lib.query2.engine.Uniquifier;
 import com.google.devtools.build.lib.query2.engine.VariableContext;
 import com.google.devtools.build.lib.skyframe.BlacklistedPackagePrefixesValue;
@@ -154,6 +156,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
       EventHandler eventHandler,
       Set<Setting> settings,
       Iterable<QueryFunction> extraFunctions,
+      QueryExpressionEvalListener<Target> evalListener,
       String parserPrefix,
       WalkableGraphFactory graphFactory,
       List<String> universeScope,
@@ -164,7 +167,8 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
         /*labelFilter=*/ Rule.ALL_LABELS,
         eventHandler,
         settings,
-        extraFunctions);
+        extraFunctions,
+        evalListener);
     this.loadingPhaseThreads = loadingPhaseThreads;
     this.graphFactory = graphFactory;
     this.pkgPath = pkgPath;
@@ -306,8 +310,8 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
         new BatchStreamedCallback(callback, BATCH_CALLBACK_SIZE);
 
     final AtomicBoolean empty = new AtomicBoolean(true);
-    Callback<Target> callbackWithEmptyCheck =
-        new Callback<Target>() {
+    ThreadSafeCallback<Target> callbackWithEmptyCheck =
+        new ThreadSafeCallback<Target>() {
           @Override
           public void process(Iterable<Target> partialResult)
               throws QueryException, InterruptedException {
@@ -317,12 +321,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
         };
     try (final AutoProfiler p = AutoProfiler.logged("evaluating query", LOG)) {
       try {
-        if (expr.canEvalConcurrently()) {
-          expr.evalConcurrently(
-              this, VariableContext.<Target>empty(), callbackWithEmptyCheck, threadPool);
-        } else {
-          expr.eval(this, VariableContext.<Target>empty(), callbackWithEmptyCheck);
-        }
+        eval(expr, VariableContext.<Target>empty(), callbackWithEmptyCheck);
       } catch (QueryException e) {
         throw new QueryException(e, expr);
       }
@@ -499,17 +498,26 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     return null;
   }
 
+  @ThreadSafe
   @Override
   public void eval(QueryExpression expr, VariableContext<Target> context, Callback<Target> callback)
       throws QueryException, InterruptedException {
-    expr.eval(this, context, callback);
+    // TODO(bazel-team): Refactor QueryEnvironment et al. such that this optimization is enabled for
+    // all QueryEnvironment implementations.
+    if (callback instanceof ThreadSafeCallback) {
+      expr.parEval(this, context, (ThreadSafeCallback<Target>) callback, threadPool);
+    } else {
+      expr.eval(this, context, callback);
+    }
   }
 
+  @ThreadSafe
   @Override
   public Uniquifier<Target> createUniquifier() {
     return new ConcurrentUniquifier();
   }
 
+  @ThreadSafe
   @Override
   public void getTargetsMatchingPattern(
       QueryExpression owner, String pattern, Callback<Target> callback)
@@ -530,6 +538,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     }
   }
 
+  @ThreadSafe
   @Override
   public Set<Target> getBuildFiles(
       QueryExpression caller,
@@ -592,11 +601,13 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     return new FakeSubincludeTarget(label, pkg);
   }
 
+  @ThreadSafe
   @Override
   public TargetAccessor<Target> getAccessor() {
     return accessor;
   }
 
+  @ThreadSafe
   @Override
   public Target getTarget(Label label)
       throws TargetNotFoundException, QueryException, InterruptedException {
@@ -621,6 +632,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     }
   }
 
+  @ThreadSafe
   public Map<PackageIdentifier, Package> bulkGetPackages(Iterable<PackageIdentifier> pkgIds)
       throws InterruptedException {
     Set<SkyKey> pkgKeys = ImmutableSet.copyOf(PackageValue.keys(pkgIds));
@@ -864,6 +876,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
    * Calculates the set of {@link Package} objects, represented as source file targets, that depend
    * on the given list of BUILD files and subincludes (other files are filtered out).
    */
+  @ThreadSafe
   void getRBuildFiles(Collection<PathFragment> fileIdentifiers, Callback<Target> callback)
       throws QueryException, InterruptedException {
     Collection<SkyKey> files = getSkyKeysForFileFragments(fileIdentifiers);
@@ -955,7 +968,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
    * call the wrapped {@code callback} concurrently.
    */
   @ThreadSafe
-  private static class BatchStreamedCallback implements Callback<Target> {
+  private static class BatchStreamedCallback implements ThreadSafeCallback<Target> {
 
     private final Callback<Target> callback;
     private final Uniquifier<Target> uniquifier = new ConcurrentUniquifier();
@@ -992,6 +1005,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     }
   }
 
+  @ThreadSafe
   @Override
   public void getAllRdeps(
       QueryExpression expression,
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 364485354a..ac5e000cbb 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
@@ -52,8 +52,9 @@ public class BinaryOperatorExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
-      throws QueryException, InterruptedException {
+  protected <T> void evalImpl(
+      QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
+          throws QueryException, InterruptedException {
 
     if (operator == TokenKind.PLUS || operator == TokenKind.UNION) {
       for (QueryExpression operand : operands) {
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 59fb70ced3..5f2b1aba1b 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
@@ -45,8 +45,9 @@ public class FunctionExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
-      throws QueryException, InterruptedException {
+  protected <T> void evalImpl(
+      QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
+          throws QueryException, InterruptedException {
     function.eval(env, context, this, 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 3c3c27338d..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
@@ -64,8 +64,9 @@ class LetExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
-      throws QueryException, InterruptedException {
+  protected <T> void evalImpl(
+      QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
+          throws QueryException, InterruptedException {
     if (!NAME_PATTERN.matcher(varName).matches()) {
       throw new QueryException(this, "invalid variable name '" + varName + "' in let expression");
     }
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 9653841b1b..3abe19be2b 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
@@ -346,6 +346,9 @@ public interface QueryEnvironment<T> {
     Set<QueryVisibility<T>> getVisibility(T from) throws QueryException, InterruptedException;
   }
 
+  /** Returns the {@link QueryExpressionEvalListener} that this {@link QueryEnvironment} uses. */
+  QueryExpressionEvalListener<T> getEvalListener();
+
   /** List of the default query functions. */
   List<QueryFunction> 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 d0de7c0d64..667fcecf27 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java
@@ -14,7 +14,7 @@
 package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.util.concurrent.ListeningExecutorService;
-import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 
 import java.util.Collection;
 
@@ -45,6 +45,7 @@ import java.util.Collection;
  * different ways of printing out the result of a query.  Each accepts a {@code
  * Digraph} of {@code Target}s, and an output stream.
  */
+@ThreadSafe
 public abstract class QueryExpression {
 
   /**
@@ -70,34 +71,44 @@ public abstract class QueryExpression {
    * thrown.  If disabled, evaluation will stumble on to produce a (possibly
    * inaccurate) result, but a result nonetheless.
    */
-  public abstract <T> void eval(
+  public final <T> void eval(
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      Callback<T> callback) throws QueryException, InterruptedException {
+    env.getEvalListener().onEval(this, env, context, callback);
+    evalImpl(env, context, callback);
+  }
+
+  protected abstract <T> void evalImpl(
       QueryEnvironment<T> env,
       VariableContext<T> context,
       Callback<T> callback) throws QueryException, InterruptedException;
 
   /**
-   * If {@code canEvalConcurrently()}, evaluates this query in the specified environment, as in
-   * {@link #eval(QueryEnvironment, VariableContext, Callback)}, employing {@code executorService}.
+   * Evaluates this query in the specified environment, as in
+   * {@link #eval(QueryEnvironment, VariableContext, Callback)}, using {@code executorService} to
+   * achieve parallelism.
    *
-   * <p>The caller must ensure that both {@code env}, {@code context}, and {@code callback} are
-   * effectively threadsafe. The query expression may call their methods from multiple threads.
+   * <p>The caller must ensure that {@code env} is thread safe.
    */
-  public <T> void evalConcurrently(
+  @ThreadSafe
+  public final <T> void parEval(
       QueryEnvironment<T> env,
       VariableContext<T> context,
-      Callback<T> callback,
+      ThreadSafeCallback<T> callback,
       ListeningExecutorService executorService)
       throws QueryException, InterruptedException {
-    Preconditions.checkState(canEvalConcurrently());
-    eval(env, context, callback);
+    env.getEvalListener().onParEval(this, env, context, callback, executorService);
+    parEvalImpl(env, context, callback, executorService);
   }
 
-  /**
-   * Whether the query expression can be evaluated concurrently. If so, {@link #evalConcurrently}
-   * should be preferred over {@link #eval}.
-   */
-  public boolean canEvalConcurrently() {
-    return false;
+  protected <T> void parEvalImpl(
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      ThreadSafeCallback<T> callback,
+      ListeningExecutorService executorService)
+      throws QueryException, InterruptedException {
+    evalImpl(env, context, callback);
   }
 
   /**
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..7255a47dd7
--- /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.common.util.concurrent.ListeningExecutorService;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
+/** Listener for calls to the internal methods of {@link QueryExpression} used for evaluation. */
+@ThreadSafe
+public interface QueryExpressionEvalListener<T> {
+  /** Called right before {@link QueryExpression#evalImpl} is called. */
+  void onEval(
+      QueryExpression expr,
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      Callback<T> callback);
+
+  /** Called right before {@link QueryExpression#parEvalImpl} is called. */
+  void onParEval(
+      QueryExpression expr,
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      ThreadSafeCallback<T> callback,
+      ListeningExecutorService executorService);
+
+  /** A {@link QueryExpressionEvalListener} that does nothing. */
+  class NullListener<T> implements QueryExpressionEvalListener<T> {
+    private static final NullListener<?> INSTANCE = new NullListener<>();
+
+    private NullListener() {
+    }
+
+    @SuppressWarnings("unchecked")
+    public static <T> NullListener<T> instance() {
+      return (NullListener<T>) INSTANCE;
+    }
+
+    @Override
+    public void onEval(
+        QueryExpression expr,
+        QueryEnvironment<T> env,
+        VariableContext<T> context,
+        Callback<T> callback) {
+    }
+
+    @Override
+    public void onParEval(
+        QueryExpression expr,
+        QueryEnvironment<T> env,
+        VariableContext<T> context,
+        ThreadSafeCallback<T> callback,
+        ListeningExecutorService executorService) {
+    }
+  }
+}
+
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 5ccdec899e..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
@@ -46,8 +46,9 @@ class SetExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
-      throws QueryException, InterruptedException {
+  protected <T> void evalImpl(
+      QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
+          throws QueryException, InterruptedException {
     for (TargetLiteral expr : words) {
       env.eval(expr, context, callback);
     }
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 bb24022ee1..8b718ab01a 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
@@ -45,8 +45,9 @@ public final class TargetLiteral extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
-      throws QueryException, InterruptedException {
+  protected <T> void evalImpl(
+      QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
+          throws QueryException, InterruptedException {
     if (isVariableReference()) {
       String varName = LetExpression.getNameFromReference(pattern);
       Set<T> value = context.get(varName);
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..d39172819f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeCallback.java
@@ -0,0 +1,21 @@
+// 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;
+
+/** Marker interface for a {@link Callback} that is {@link ThreadSafe}. */
+@ThreadSafe
+public interface ThreadSafeCallback<T> extends Callback<T> {
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/VariableContext.java b/src/main/java/com/google/devtools/build/lib/query2/engine/VariableContext.java
index 1c23334f45..9feb85242f 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/VariableContext.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/VariableContext.java
@@ -14,6 +14,8 @@
 package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 
 import java.util.Map;
 import java.util.Set;
@@ -21,6 +23,8 @@ import java.util.Set;
 import javax.annotation.Nullable;
 
 /** An immutable context of variable bindings for variables introduced by {@link LetExpression}s. */
+@Immutable
+@ThreadSafe
 public class VariableContext<T> {
   private final ImmutableMap<String, Set<T>> context;
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index 2a336da0bf..849238a44a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -55,6 +55,7 @@ import com.google.devtools.build.lib.query2.engine.DigraphQueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting;
 import com.google.devtools.build.lib.query2.engine.QueryException;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
 import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException;
 import com.google.devtools.build.lib.query2.output.OutputFormatter;
@@ -295,6 +296,7 @@ public class GenQuery implements RuleConfiguredTargetFactory {
               getEventHandler(ruleContext),
               settings,
               ImmutableList.<QueryFunction>of(),
+              QueryExpressionEvalListener.NullListener.<Target>instance(),
               /*packagePath=*/null);
       queryResult = (DigraphQueryEvalResult<Target>) queryEnvironment.evaluateQuery(query, targets);
     } catch (SkyframeRestartQueryException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java b/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java
index 9be185eea0..565f7a82cf 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java
@@ -30,6 +30,7 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.query2.output.OutputFormatter;
 import com.google.devtools.build.lib.query2.output.OutputFormatter.StreamedFormatter;
 import com.google.devtools.build.lib.query2.output.QueryOptions;
@@ -286,6 +287,7 @@ public final class QueryCommand implements BlazeCommand {
             env.getReporter(),
             settings,
             env.getRuntime().getQueryFunctions(),
+            QueryExpressionEvalListener.NullListener.<Target>instance(),
             env.getPackageManager().getPackagePath());
   }