Re-implement variables in the blaze query language. Instead of using a mutable global context of variable bindings, pass around immutable local contexts.

The motivation is so we can safely evaluate all blaze query expressions concurrently under the hood. A global context is hostile to this goal.

--
MOS_MIGRATED_REVID=127324600

26 files changed, 221 insertions, 114 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 0292f08458..07df0c6ce0 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
@@ -31,13 +31,12 @@ import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
+import com.google.devtools.build.lib.query2.engine.VariableContext;
 import com.google.devtools.build.lib.util.Preconditions;
 
 import java.util.Collection;
-import java.util.HashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
-import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.logging.Logger;
@@ -49,7 +48,6 @@ import java.util.logging.Logger;
 public abstract class AbstractBlazeQueryEnvironment<T>
     implements QueryEnvironment<T>, AutoCloseable {
   protected final ErrorSensingEventHandler eventHandler;
-  private final Map<String, Set<T>> letBindings = new HashMap<>();
   protected final boolean keepGoing;
   protected final boolean strictScope;
 
@@ -117,7 +115,7 @@ public abstract class AbstractBlazeQueryEnvironment<T>
         throw new QueryException(expr, e.getMessage());
       }
       try {
-        this.eval(expr, new Callback<T>() {
+        this.eval(expr, VariableContext.<T>empty(), new Callback<T>() {
           @Override
           public void process(Iterable<T> partialResult)
               throws QueryException, InterruptedException {
@@ -169,16 +167,6 @@ public abstract class AbstractBlazeQueryEnvironment<T>
 
   public abstract Target getTarget(Label label) throws TargetNotFoundException, QueryException;
 
-  @Override
-  public Set<T> getVariable(String name) {
-    return letBindings.get(name);
-  }
-
-  @Override
-  public Set<T> setVariable(String name, Set<T> value) {
-    return letBindings.put(name, value);
-  }
-
   protected boolean validateScope(Label label, boolean strict) throws QueryException {
     if (!labelFilter.apply(label)) {
       String error = String.format("target '%s' is not within the scope of the query", label);
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 29a9ea96dd..a29c2c6093 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
@@ -45,6 +45,7 @@ import com.google.devtools.build.lib.query2.engine.QueryUtil.AbstractUniquifier;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
 import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException;
 import com.google.devtools.build.lib.query2.engine.Uniquifier;
+import com.google.devtools.build.lib.query2.engine.VariableContext;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
@@ -291,10 +292,10 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
   }
 
   @Override
-  public void eval(QueryExpression expr, Callback<Target> callback)
+  public void eval(QueryExpression expr, VariableContext<Target> context, Callback<Target> callback)
       throws QueryException, InterruptedException {
     AggregateAllCallback<Target> aggregator = new AggregateAllCallback<>();
-    expr.eval(this, aggregator);
+    expr.eval(this, context, aggregator);
     callback.process(aggregator.getResult());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java
index 5bc8612b16..9de4769654 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java
@@ -24,6 +24,7 @@ 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.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.query2.engine.VariableContext;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.List;
@@ -66,8 +67,12 @@ public class RBuildFilesFunction implements QueryFunction {
 
   @Override
   @SuppressWarnings("unchecked") // Cast from <Target> to <T>. This will only be used with <Target>.
-  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
-      List<Argument> args, Callback<T> callback) throws QueryException, InterruptedException {
+  public <T> void eval(
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
+      List<Argument> args,
+      Callback<T> callback) throws QueryException, InterruptedException {
     if (!(env instanceof SkyQueryEnvironment)) {
       throw new QueryException("rbuildfiles can only be used with SkyQueryEnvironment");
     }
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 1546b4e94e..586c493485 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
@@ -65,6 +65,7 @@ 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.Uniquifier;
+import com.google.devtools.build.lib.query2.engine.VariableContext;
 import com.google.devtools.build.lib.skyframe.BlacklistedPackagePrefixesValue;
 import com.google.devtools.build.lib.skyframe.ContainingPackageLookupFunction;
 import com.google.devtools.build.lib.skyframe.FileValue;
@@ -320,9 +321,10 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     try (final AutoProfiler p = AutoProfiler.logged("evaluating query", LOG)) {
       try {
         if (expr.canEvalConcurrently()) {
-          expr.evalConcurrently(this, callbackWithEmptyCheck, threadPool);
+          expr.evalConcurrently(
+              this, VariableContext.<Target>empty(), callbackWithEmptyCheck, threadPool);
         } else {
-          expr.eval(this, callbackWithEmptyCheck);
+          expr.eval(this, VariableContext.<Target>empty(), callbackWithEmptyCheck);
         }
       } catch (QueryException e) {
         throw new QueryException(e, expr);
@@ -487,9 +489,9 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
   }
 
   @Override
-  public void eval(QueryExpression expr, Callback<Target> callback)
+  public void eval(QueryExpression expr, VariableContext<Target> context, Callback<Target> callback)
       throws QueryException, InterruptedException {
-    expr.eval(this, callback);
+    expr.eval(this, context, callback);
   }
 
   @Override
@@ -979,10 +981,11 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
   public void getAllRdeps(
       QueryExpression expression,
       Predicate<Target> universe,
-      final Callback<Target> callback,
-      final int depth)
+      VariableContext<Target> context,
+      Callback<Target> callback,
+      int depth)
       throws QueryException, InterruptedException {
-    getAllRdeps(expression, universe, callback, depth, BATCH_CALLBACK_SIZE);
+    getAllRdeps(expression, universe, context, callback, depth, BATCH_CALLBACK_SIZE);
   }
 
   /**
@@ -994,13 +997,17 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
   @VisibleForTesting
   protected void getAllRdeps(
       QueryExpression expression,
-      final Predicate<Target> universe,
-      final Callback<Target> callback,
-      final int depth,
-      final int batchSize)
+      Predicate<Target> universe,
+      VariableContext<Target> context,
+      Callback<Target> callback,
+      int depth,
+      int batchSize)
       throws QueryException, InterruptedException {
     Uniquifier<Target> uniquifier = createUniquifier();
-    eval(expression, new BatchAllRdepsCallback(uniquifier, universe, callback, depth, batchSize));
+    eval(
+        expression,
+        context,
+        new BatchAllRdepsCallback(uniquifier, universe, callback, depth, batchSize));
   }
 
   private class BatchAllRdepsCallback implements Callback<Target> {
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 b528127661..68b92d31a9 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
@@ -50,11 +50,15 @@ public class AllPathsFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args,
+  public <T> void eval(
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
+      List<Argument> args,
       Callback<T> callback) throws QueryException, InterruptedException {
 
-    Set<T> fromValue = QueryUtil.evalAll(env, args.get(0).getExpression());
-    Set<T> toValue = QueryUtil.evalAll(env, args.get(1).getExpression());
+    Set<T> fromValue = QueryUtil.evalAll(env, context, args.get(0).getExpression());
+    Set<T> toValue = QueryUtil.evalAll(env, context, args.get(1).getExpression());
 
     // Algorithm: compute "reachableFromX", the forward transitive closure of
     // the "from" set, then find the intersection of "reachableFromX" with the
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 1fe882fae9..a39efd9a97 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
@@ -51,13 +51,18 @@ public class AllRdepsFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args,
+  public <T> void eval(
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
+      List<Argument> args,
       Callback<T> callback) throws QueryException, InterruptedException {
-    eval(env, args, callback, Predicates.<T>alwaysTrue());
+    eval(env, context, args, callback, Predicates.<T>alwaysTrue());
   }
 
   protected <T> void eval(
       final QueryEnvironment<T> env,
+      VariableContext<T> context,
       final List<Argument> args,
       final Callback<T> callback,
       final Predicate<T> universe)
@@ -66,11 +71,12 @@ public class AllRdepsFunction implements QueryFunction {
     final int depth = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
     if (env instanceof StreamableQueryEnvironment<?>) {
       ((StreamableQueryEnvironment<T>) env)
-          .getAllRdeps(args.get(0).getExpression(), universe, callback, depth);
+          .getAllRdeps(args.get(0).getExpression(), universe, context, callback, depth);
     } else {
       final Uniquifier<T> uniquifier = env.createUniquifier();
       env.eval(
           args.get(0).getExpression(),
+          context,
           new Callback<T>() {
             @Override
             public void process(Iterable<T> partialResult)
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 8da82b2f72..987e8fd9b4 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
@@ -53,19 +53,19 @@ public class BinaryOperatorExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
       throws QueryException, InterruptedException {
 
     if (operator == TokenKind.PLUS || operator == TokenKind.UNION) {
       for (QueryExpression operand : operands) {
-        env.eval(operand, callback);
+        env.eval(operand, context, callback);
       }
       return;
     }
     // We cannot do differences with partial results. So we fully evaluate the operands
-    Set<T> lhsValue = QueryUtil.evalAll(env, operands.get(0));
+    Set<T> lhsValue = QueryUtil.evalAll(env, context, operands.get(0));
     for (int i = 1; i < operands.size(); i++) {
-      Set<T> rhsValue = QueryUtil.evalAll(env, operands.get(i));
+      Set<T> rhsValue = QueryUtil.evalAll(env, context, operands.get(i));
       switch (operator) {
         case INTERSECT:
         case CARET:
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 ea391e9627..acc7917b7e 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
@@ -41,11 +41,16 @@ class BuildFilesFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression,
-      List<Argument> args, final Callback<T> callback)
+  public <T> void eval(
+      final QueryEnvironment<T> env,
+      VariableContext<T> context,
+      final QueryExpression expression,
+      List<Argument> args,
+      final Callback<T> callback)
       throws QueryException, InterruptedException {
     env.eval(
         args.get(0).getExpression(),
+        context,
         new Callback<T>() {
           @Override
           public void process(Iterable<T> partialResult)
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 b7bc59ae5b..ecc8d8edb6 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
@@ -53,12 +53,15 @@ final class DepsFunction implements QueryFunction {
    * Breadth-first search from the arguments.
    */
   @Override
-  public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression,
-      List<Argument> args, final Callback<T> callback)
-      throws QueryException, InterruptedException {
+  public <T> void eval(
+      final QueryEnvironment<T> env,
+      VariableContext<T> context,
+      final QueryExpression expression,
+      List<Argument> args,
+      final Callback<T> callback) throws QueryException, InterruptedException {
     final int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
     final Uniquifier<T> uniquifier = env.createUniquifier();
-    env.eval(args.get(0).getExpression(), new Callback<T>() {
+    env.eval(args.get(0).getExpression(), context, new Callback<T>() {
       @Override
       public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
         Collection<T> current = Sets.newHashSet(partialResult);
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 f6fcc27ef5..59fb70ced3 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,9 +45,9 @@ public class FunctionExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
       throws QueryException, InterruptedException {
-    function.eval(env, this, args, callback);
+    function.eval(env, context, this, args, callback);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java
index a13f42cfb8..140e732437 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
@@ -52,12 +52,16 @@ class LabelsFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression,
-      final List<Argument> args, final Callback<T> callback)
+  public <T> void eval(
+      final QueryEnvironment<T> env,
+      VariableContext<T> context,
+      final QueryExpression expression,
+      final List<Argument> args,
+      final Callback<T> callback)
       throws QueryException, InterruptedException {
     final String attrName = args.get(0).getWord();
     final Uniquifier<T> uniquifier = env.createUniquifier();
-    env.eval(args.get(1).getExpression(), new Callback<T>() {
+    env.eval(args.get(1).getExpression(), context, new Callback<T>() {
       @Override
       public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
         for (T input : partialResult) {
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 a1cc7a7cbf..3c3c27338d 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,22 +64,14 @@ class LetExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+  public <T> void eval(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");
     }
-    // We eval all because we would need a stack of variable contexts for implementing setVariable
-    // correctly.
-    Set<T> varValue = QueryUtil.evalAll(env, varExpr);
-    Set<T> prevValue = env.setVariable(varName, varValue);
-    try {
-      // Same as varExpr. We cannot pass partial results to the parent without having
-      // a stack of variable contexts.
-      callback.process(QueryUtil.evalAll(env, bodyExpr));
-    } finally {
-      env.setVariable(varName, prevValue); // restore
-    }
+    Set<T> varValue = QueryUtil.evalAll(env, context, varExpr);
+    VariableContext<T> 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 1566f2166c..6b6866ebd6 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
@@ -39,12 +39,14 @@ class LoadFilesFunction implements QueryEnvironment.QueryFunction {
   @Override
   public <T> void eval(
       final QueryEnvironment<T> env,
+      VariableContext<T> context,
       final QueryExpression expression,
       List<QueryEnvironment.Argument> args,
       final Callback<T> callback)
       throws QueryException, InterruptedException {
     env.eval(
         args.get(0).getExpression(),
+        context,
         new Callback<T>() {
           @Override
           public void process(Iterable<T> partialResult)
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 0ebf71139c..88a2ea99f1 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java
@@ -116,7 +116,11 @@ public interface QueryEnvironment<T> {
      * @param args the input arguments. These are type-checked against the specification returned
      *     by {@link #getArgumentTypes} and {@link #getMandatoryArguments}
      */
-    <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args,
+    <T> void eval(
+        QueryEnvironment<T> env,
+        VariableContext<T> context,
+        QueryExpression expression,
+        List<Argument> args,
         Callback<T> callback) throws QueryException, InterruptedException;
   }
 
@@ -178,24 +182,14 @@ public interface QueryEnvironment<T> {
   Set<T> getNodesOnPath(T from, T to);
 
   /**
-   * Returns the value of the specified variable, or null if it is undefined.
-   */
-  Set<T> getVariable(String name);
-
-  /**
-   * Sets the value of the specified variable.  If value is null the variable
-   * becomes undefined.  Returns the previous value, if any.
-   */
-  Set<T> setVariable(String name, Set<T> value);
-
-  /**
    * Eval an expression {@code expr} and pass the results to the {@code callback}.
    *
    * <p>Note that this method should guarantee that the callback does not see repeated elements.
    * @param expr The expression to evaluate
    * @param callback The caller callback to notify when results are available
    */
-  void eval(QueryExpression expr, Callback<T> callback) throws QueryException, InterruptedException;
+  void eval(QueryExpression expr, VariableContext<T> context, Callback<T> callback)
+      throws QueryException, InterruptedException;
 
   /**
    * Creates a Uniquifier for use in a {@code QueryExpression}. Note that the usage of this an
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 2c6d331b3d..d0de7c0d64 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
@@ -70,21 +70,26 @@ 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(QueryEnvironment<T> env, Callback<T> callback)
-      throws QueryException, InterruptedException;
+  public abstract <T> void eval(
+      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, Callback)}, employing {@code executorService}.
+   * {@link #eval(QueryEnvironment, VariableContext, Callback)}, employing {@code executorService}.
    *
-   * <p>The caller must ensure that both {@code env} and {@code callback} are effectively
-   * threadsafe. The query expression may call their methods from multiple threads.
+   * <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.
    */
   public <T> void evalConcurrently(
-      QueryEnvironment<T> env, Callback<T> callback, ListeningExecutorService executorService)
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      Callback<T> callback,
+      ListeningExecutorService executorService)
       throws QueryException, InterruptedException {
     Preconditions.checkState(canEvalConcurrently());
-    eval(env, callback);
+    eval(env, context, callback);
   }
 
   /**
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 f70dcd08c7..68f0a5a22e 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
@@ -51,10 +51,11 @@ public final class QueryUtil {
    *
    * <p>Should ony be used by QueryExpressions when it is the only way of achieving correctness.
    */
-  public static <T> Set<T> evalAll(QueryEnvironment<T> env, QueryExpression expr)
-      throws QueryException, InterruptedException {
+  public static <T> Set<T> evalAll(
+      QueryEnvironment<T> env, VariableContext<T> context, QueryExpression expr)
+          throws QueryException, InterruptedException {
     AggregateAllCallback<T> callback = new AggregateAllCallback<>();
-    env.eval(expr, callback);
+    env.eval(expr, context, callback);
     return callback.result;
   }
 
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 6cd72dd75a..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
@@ -54,13 +54,16 @@ public final class RdepsFunction extends AllRdepsFunction {
    * towards the universe while staying within the transitive closure.
    */
   @Override
-  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
+  public <T> void eval(QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
       List<Argument> args, Callback<T> callback)
-      throws QueryException, InterruptedException {
-    Set<T> universeValue = QueryUtil.evalAll(env, args.get(0).getExpression());
+      throws QueryException,
+      InterruptedException {
+    Set<T> universeValue = QueryUtil.evalAll(env, context, args.get(0).getExpression());
     env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE);
 
     Predicate<T> universe = Predicates.in(env.getTransitiveClosure(universeValue));
-    eval(env, args.subList(1, args.size()), callback, universe);
+    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 b9f6f579b9..26779082a9 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
@@ -15,6 +15,7 @@ package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
@@ -30,8 +31,12 @@ public abstract class RegexFilterExpression implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression,
-      final List<Argument> args, final Callback<T> callback)
+  public <T> void eval(
+      final QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
+      final List<Argument> args,
+      Callback<T> callback)
       throws QueryException, InterruptedException {
     final Pattern compiledPattern;
     try {
@@ -53,7 +58,9 @@ public abstract class RegexFilterExpression implements QueryFunction {
       }
     };
 
-    env.eval(args.get(args.size() - 1).getExpression(),
+    env.eval(
+        Iterables.getLast(args).getExpression(),
+        context,
         QueryUtil.filteredCallback(callback, matchFilter));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
index 1369d8ace6..5ccdec899e 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,10 +46,10 @@ class SetExpression extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
       throws QueryException, InterruptedException {
     for (TargetLiteral expr : words) {
-      env.eval(expr, callback);
+      env.eval(expr, context, callback);
     }
   }
 
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 d6885e44f6..8560992f93 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
@@ -49,11 +49,14 @@ class SomeFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
-      List<Argument> args, final Callback<T> callback)
-      throws QueryException, InterruptedException {
+  public <T> void eval(
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
+      List<Argument> args,
+      final Callback<T> callback) throws QueryException, InterruptedException {
     final AtomicBoolean someFound = new AtomicBoolean(false);
-    env.eval(args.get(0).getExpression(), new Callback<T>() {
+    env.eval(args.get(0).getExpression(), context, new Callback<T>() {
       @Override
       public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
         if (someFound.get() || Iterables.isEmpty(partialResult)) {
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 9e2b44392b..23988bf2fc 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
@@ -50,11 +50,14 @@ class SomePathFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
-      List<Argument> args, final Callback<T> callback)
-      throws QueryException, InterruptedException {
-    Set<T> fromValue = QueryUtil.evalAll(env, args.get(0).getExpression());
-    Set<T> toValue = QueryUtil.evalAll(env, args.get(1).getExpression());
+  public <T> void eval(
+      QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
+      List<Argument> args,
+      final Callback<T> callback) throws QueryException, InterruptedException {
+    Set<T> fromValue = QueryUtil.evalAll(env, context, args.get(0).getExpression());
+    Set<T> toValue = QueryUtil.evalAll(env, context, args.get(1).getExpression());
 
     // Implementation strategy: for each x in "from", compute its forward
     // transitive closure.  If it intersects "to", then do a path search from x
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 0f0a593267..db52c32902 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
@@ -26,7 +26,8 @@ public interface StreamableQueryEnvironment<T> extends QueryEnvironment<T> {
   void getAllRdeps(
       QueryExpression expression,
       Predicate<T> universe,
-      final Callback<T> callback,
-      final int depth)
+      VariableContext<T> context,
+      Callback<T> callback,
+      int depth)
       throws QueryException, InterruptedException;
 }
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 72847bf16d..bb24022ee1 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,11 +45,11 @@ public final class TargetLiteral extends QueryExpression {
   }
 
   @Override
-  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+  public <T> void eval(QueryEnvironment<T> env, VariableContext<T> context, Callback<T> callback)
       throws QueryException, InterruptedException {
     if (isVariableReference()) {
       String varName = LetExpression.getNameFromReference(pattern);
-      Set<T> value = env.getVariable(varName);
+      Set<T> value = context.get(varName);
       if (value == null) {
         throw new QueryException(this, "undefined variable '" + varName + "'");
       }
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 d5479ee6cf..02ce8cc405 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java
@@ -62,11 +62,15 @@ class TestsFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression,
-      List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException {
+  public <T> void eval(
+      final QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
+      List<Argument> args,
+      final Callback<T> callback) throws QueryException, InterruptedException {
     final Closure<T> closure = new Closure<>(expression, env);
 
-    env.eval(args.get(0).getExpression(), new Callback<T>() {
+    env.eval(args.get(0).getExpression(), context, new Callback<T>() {
       @Override
       public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
         for (T target : partialResult) {
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
new file mode 100644
index 0000000000..a75f890d1b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/VariableContext.java
@@ -0,0 +1,66 @@
+// 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.ImmutableMap;
+
+import java.util.Map;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+/** An immutable context of variable bindings for variables introduced by {@link LetExpression}s. */
+public class VariableContext<T> {
+  private final ImmutableMap<String, Set<T>> context;
+
+  private VariableContext(ImmutableMap<String, Set<T>> context) {
+    this.context = context;
+  }
+
+  /**
+   * Returns the value bound to the specified variable given by {@code name}, or {@code null} if
+   * there is no such binding.
+   */
+  @Nullable
+  Set<T> get(String name) {
+    return context.get(name);
+  }
+
+  /** Returns a {@link VariableContext} with no variables defined. */
+  public static <T> VariableContext<T> empty() {
+    return new VariableContext<>(ImmutableMap.<String, Set<T>>of());
+  }
+
+  /**
+   * Returns a {@link VariableContext} that has all the same bindings as the given
+   * {@code variableContext} and also the binding of {@code name} to {@code value}.
+   */
+  static <T> VariableContext<T> with(
+      VariableContext<T> variableContext,
+      String name,
+      Set<T> value) {
+    ImmutableMap.Builder<String, Set<T>> newContextBuilder = ImmutableMap.builder();
+    for (Map.Entry<String, Set<T>> entry : variableContext.context.entrySet()) {
+      if (entry.getKey().equals(name)) {
+        // The binding of 'name' to 'value' should override any existing binding of name in
+        // 'variableContext'. These are the semantics we want in order for nested let-expressions
+        // to have the semantics we want.
+        newContextBuilder.put(entry);
+      }
+    }
+    newContextBuilder.put(name, value);
+    return new VariableContext<>(newContextBuilder.build());
+  }
+}
+
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 e4d095eecb..03a2ccf2bb 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
@@ -52,11 +52,14 @@ public class VisibleFunction implements QueryFunction {
   }
 
   @Override
-  public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression,
+  public <T> void eval(
+      final QueryEnvironment<T> env,
+      VariableContext<T> context,
+      QueryExpression expression,
       List<Argument> args,
       final Callback<T> callback) throws QueryException, InterruptedException {
-    final Set<T> toSet = QueryUtil.evalAll(env, args.get(0).getExpression());
-    env.eval(args.get(1).getExpression(), new Callback<T>() {
+    final Set<T> toSet = QueryUtil.evalAll(env, context, args.get(0).getExpression());
+    env.eval(args.get(1).getExpression(), context, new Callback<T>() {
       @Override
       public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
         for (T t : partialResult) {