diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionAnalysisMetadata.java b/src/main/java/com/google/devtools/build/lib/actions/ActionAnalysisMetadata.java
index 9a0edfd..4b45965 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionAnalysisMetadata.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionAnalysisMetadata.java
@@ -73,6 +73,11 @@
   /**
    * Returns the environment variables from the client environment that this action depends on. May
    * be empty.
+   *
+   * <p>Warning: For optimization reasons, the available environment variables are restricted to
+   * those white-listed on the command line. If actions want to specify additional client
+   * environment variables to depend on, that restriction must be lifted in
+   * {@link com.google.devtools.build.lib.runtime.CommandEnvironment}.
    */
   Iterable<String> getClientEnvironmentVariables();
 
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
index 5b913ad..b97d323 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
@@ -15,6 +15,7 @@
 
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
 import com.google.devtools.build.lib.actions.cache.ActionCache;
@@ -125,10 +126,41 @@
     }
   }
 
+  private void reportClientEnv(EventHandler handler, Action action, Map<String, String> used) {
+    if (handler != null) {
+      if (verboseExplanations) {
+        StringBuilder message = new StringBuilder();
+        message.append("Effective client environment has changed. Now using\n");
+        for (Map.Entry<String, String> entry : used.entrySet()) {
+          message.append("  ").append(entry.getKey()).append("=").append(entry.getValue())
+              .append("\n");
+        }
+        reportRebuild(handler, action, message.toString());
+      } else {
+        reportRebuild(
+            handler,
+            action,
+            "Effective client environment has changed (try --verbose_explanations for more info)");
+      }
+    }
+  }
+
   protected boolean unconditionalExecution(Action action) {
     return !isActionExecutionProhibited(action) && action.executeUnconditionally();
   }
 
+  private static Map<String, String> computeUsedClientEnv(
+      Action action, Map<String, String> clientEnv) {
+    Map<String, String> used = new HashMap<>();
+    for (String var : action.getClientEnvironmentVariables()) {
+      String value = clientEnv.get(var);
+      if (value != null) {
+        used.put(var, value);
+      }
+    }
+    return used;
+  }
+
   /**
    * Checks whether {@code action} needs to be executed and returns a non-null Token if so.
    *
@@ -141,8 +173,12 @@
    */
   // Note: the handler should only be used for DEPCHECKER events; there's no
   // guarantee it will be available for other events.
-  public Token getTokenIfNeedToExecute(Action action, Iterable<Artifact> resolvedCacheArtifacts,
-      EventHandler handler, MetadataHandler metadataHandler) {
+  public Token getTokenIfNeedToExecute(
+      Action action,
+      Iterable<Artifact> resolvedCacheArtifacts,
+      Map<String, String> clientEnv,
+      EventHandler handler,
+      MetadataHandler metadataHandler) {
     // TODO(bazel-team): (2010) For RunfilesAction/SymlinkAction and similar actions that
     // produce only symlinks we should not check whether inputs are valid at all - all that matters
     // that inputs and outputs are still exist (and new inputs have not appeared). All other checks
@@ -168,7 +204,7 @@
       actionInputs = resolvedCacheArtifacts;
     }
     ActionCache.Entry entry = getCacheEntry(action);
-    if (mustExecute(action, entry, handler, metadataHandler, actionInputs)) {
+    if (mustExecute(action, entry, handler, metadataHandler, actionInputs, clientEnv)) {
       if (entry != null) {
         removeCacheEntry(action);
       }
@@ -181,8 +217,13 @@
     return null;
   }
 
-  protected boolean mustExecute(Action action, @Nullable ActionCache.Entry entry,
-      EventHandler handler, MetadataHandler metadataHandler, Iterable<Artifact> actionInputs) {
+  protected boolean mustExecute(
+      Action action,
+      @Nullable ActionCache.Entry entry,
+      EventHandler handler,
+      MetadataHandler metadataHandler,
+      Iterable<Artifact> actionInputs,
+      Map<String, String> clientEnv) {
     // Unconditional execution can be applied only for actions that are allowed to be executed.
     if (unconditionalExecution(action)) {
       Preconditions.checkState(action.isVolatile());
@@ -204,12 +245,19 @@
       reportCommand(handler, action);
       return true; // must execute -- action key is different
     }
+    Map<String, String> usedClientEnv = computeUsedClientEnv(action, clientEnv);
+    if (!entry.getUsedClientEnvDigest().equals(DigestUtils.fromEnv(usedClientEnv))) {
+      reportClientEnv(handler, action, usedClientEnv);
+      return true; // different values taken from the environment -- must execute
+    }
+
 
     entry.getFileDigest();
     return false; // cache hit
   }
 
-  public void afterExecution(Action action, Token token, MetadataHandler metadataHandler)
+  public void afterExecution(
+      Action action, Token token, MetadataHandler metadataHandler, Map<String, String> clientEnv)
       throws IOException {
     Preconditions.checkArgument(token != null);
     String key = token.cacheKey;
@@ -217,7 +265,9 @@
       // This cache entry has already been updated by a shared action. We don't need to do it again.
       return;
     }
-    ActionCache.Entry entry = new ActionCache.Entry(action.getKey(), action.discoversInputs());
+    Map<String, String> usedClientEnv = computeUsedClientEnv(action, clientEnv);
+    ActionCache.Entry entry =
+        new ActionCache.Entry(action.getKey(), usedClientEnv, action.discoversInputs());
     for (Artifact output : action.getOutputs()) {
       // Remove old records from the cache if they used different key.
       String execPath = output.getExecPathString();
@@ -295,7 +345,7 @@
       // Compute the aggregated middleman digest.
       // Since we never validate action key for middlemen, we should not store
       // it in the cache entry and just use empty string instead.
-      entry = new ActionCache.Entry("", false);
+      entry = new ActionCache.Entry("", ImmutableMap.<String, String>of(), false);
       for (Artifact input : action.getInputs()) {
         entry.addFile(input.getExecPath(), metadataHandler.getMetadataMaybe(input));
       }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java b/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
index 5dc88cf..1e123e5 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/ActionCache.java
@@ -74,15 +74,22 @@
     // If null, md5Digest is non-null and the entry is immutable.
     private Map<String, Metadata> mdMap;
     private Md5Digest md5Digest;
+    private final Md5Digest usedClientEnvDigest;
 
-    public Entry(String key, boolean discoversInputs) {
+    public Entry(String key, Map<String, String> usedClientEnv, boolean discoversInputs) {
       actionKey = key;
+      this.usedClientEnvDigest = DigestUtils.fromEnv(usedClientEnv);
       files = discoversInputs ? new ArrayList<String>() : null;
       mdMap = new HashMap<>();
     }
 
-    public Entry(String key, @Nullable List<String> files, Md5Digest md5Digest) {
+    public Entry(
+        String key,
+        Md5Digest usedClientEnvDigest,
+        @Nullable List<String> files,
+        Md5Digest md5Digest) {
       actionKey = key;
+      this.usedClientEnvDigest = usedClientEnvDigest;
       this.files = files;
       this.md5Digest = md5Digest;
       mdMap = null;
@@ -111,6 +118,11 @@
       return actionKey;
     }
 
+    /** @return the effectively used client environment */
+    public Md5Digest getUsedClientEnvDigest() {
+      return usedClientEnvDigest;
+    }
+
     /**
      * Returns the combined md5Digest of the action's inputs and outputs.
      *
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
index f0b47f8..a644000 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
@@ -16,6 +16,7 @@
 import static java.nio.charset.StandardCharsets.ISO_8859_1;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ConditionallyThreadSafe;
 import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.util.Clock;
@@ -62,7 +63,7 @@
 
   private static final int NO_INPUT_DISCOVERY_COUNT = -1;
 
-  private static final int VERSION = 11;
+  private static final int VERSION = 12;
 
   private static final Logger LOG = Logger.getLogger(CompactPersistentActionCache.class.getName());
 
@@ -152,7 +153,8 @@
 
   private final PersistentMap<Integer, byte[]> map;
   private final PersistentStringIndexer indexer;
-  static final ActionCache.Entry CORRUPTED = new ActionCache.Entry(null, false);
+  static final ActionCache.Entry CORRUPTED =
+      new ActionCache.Entry(null, ImmutableMap.<String, String>of(), false);
 
   public CompactPersistentActionCache(Path cacheRoot, Clock clock) throws IOException {
     Path cacheFile = cacheFile(cacheRoot);
@@ -351,12 +353,14 @@
       // + 16 bytes for the digest
       // + 5 bytes max for the file list length
       // + 5 bytes max for each file id
+      // + 16 bytes for the environment digest
       int maxSize =
           VarInt.MAX_VARINT_SIZE
               + actionKeyBytes.length
               + Md5Digest.MD5_SIZE
               + VarInt.MAX_VARINT_SIZE
-              + files.size() * VarInt.MAX_VARINT_SIZE;
+              + files.size() * VarInt.MAX_VARINT_SIZE
+              + Md5Digest.MD5_SIZE;
       ByteArrayOutputStream sink = new ByteArrayOutputStream(maxSize);
 
       VarInt.putVarInt(actionKeyBytes.length, sink);
@@ -368,6 +372,9 @@
       for (String file : files) {
         VarInt.putVarInt(indexer.getOrCreateIndex(file), sink);
       }
+
+      DigestUtils.write(entry.getUsedClientEnvDigest(), sink);
+
       return sink.toByteArray();
     } catch (IOException e) {
       // This Exception can never be thrown by ByteArrayOutputStream.
@@ -400,11 +407,17 @@
         }
         builder.add(filename);
       }
+
+      Md5Digest usedClientEnvDigest = DigestUtils.read(source);
+
       if (source.remaining() > 0) {
         throw new IOException("serialized entry data has not been fully decoded");
       }
       return new Entry(
-          actionKey, count == NO_INPUT_DISCOVERY_COUNT ? null : builder.build(), md5Digest);
+          actionKey,
+          usedClientEnvDigest,
+          count == NO_INPUT_DISCOVERY_COUNT ? null : builder.build(),
+          md5Digest);
     } catch (BufferUnderflowException e) {
       throw new IOException("encoded entry data is incomplete", e);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java b/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
index ef4d9dc..a35eed6 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/DigestUtils.java
@@ -171,6 +171,21 @@
     return new Md5Digest(result);
   }
 
+  /**
+   * @param env A collection of (String, String) pairs.
+   * @return an order-independent digest of the given set of pairs.
+   */
+  public static Md5Digest fromEnv(Map<String, String> env) {
+    byte[] result = new byte[Md5Digest.MD5_SIZE];
+    Fingerprint fp = new Fingerprint();
+    for (Map.Entry<String, String> entry : env.entrySet()) {
+      fp.addStringLatin1(entry.getKey());
+      fp.addStringLatin1(entry.getValue());
+      xorWith(result, fp.digestAndReset());
+    }
+    return new Md5Digest(result);
+  }
+
   private static byte[] getDigest(Fingerprint fp, String execPath, Metadata md) {
     fp.addStringLatin1(execPath);
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
index 59e9988..f51a41e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
@@ -599,6 +599,9 @@
     )
     public List<Map.Entry<String, String>> testEnvironment;
 
+    // TODO(bazel-team): The set of available variables from the client environment for actions
+    // is computed independently in CommandEnvironment to inject a more restricted client
+    // environment to skyframe.
     @Option(
       name = "action_env",
       converter = Converters.OptionalAssignmentConverter.class,
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java b/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
index 1ace4ad..bb6fb83 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
@@ -57,10 +57,11 @@
 import java.io.IOException;
 import java.util.Collection;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.TreeMap;
+import java.util.TreeSet;
 import java.util.UUID;
 import java.util.concurrent.atomic.AtomicReference;
 
@@ -77,7 +78,8 @@
   private final Reporter reporter;
   private final EventBus eventBus;
   private final BlazeModule.ModuleEnvironment blazeModuleEnvironment;
-  private final Map<String, String> clientEnv = new HashMap<>();
+  private final Map<String, String> clientEnv = new TreeMap<>();
+  private final Set<String> visibleClientEnv = new TreeSet<>();
   private final TimestampGranularityMonitor timestampGranularityMonitor;
 
   private String[] crashData;
@@ -163,6 +165,21 @@
     return Collections.unmodifiableMap(clientEnv);
   }
 
+  /**
+   * Return an ordered version of the client environment restricted to those variables
+   * whitelisted by the command-line options to be inheritable by actions.
+   */
+  private Map<String, String> getCommandlineWhitelistedClientEnv() {
+    Map<String, String> visibleEnv = new TreeMap<>();
+    for (String var : visibleClientEnv) {
+      String value = clientEnv.get(var);
+      if (value != null) {
+        visibleEnv.put(var, value);
+      }
+    }
+    return Collections.unmodifiableMap(visibleEnv);
+  }
+
   @VisibleForTesting
   void updateClientEnv(List<Map.Entry<String, String>> clientEnvList, boolean ignoreClientEnv) {
     Preconditions.checkState(clientEnv.isEmpty());
@@ -407,8 +424,16 @@
     if (!skyframeExecutor.hasIncrementalState()) {
       skyframeExecutor.resetEvaluator();
     }
-    skyframeExecutor.sync(reporter, packageCacheOptions, getOutputBase(),
-        getWorkingDirectory(), defaultsPackageContents, getCommandId(),
+    skyframeExecutor.sync(
+        reporter,
+        packageCacheOptions,
+        getOutputBase(),
+        getWorkingDirectory(),
+        defaultsPackageContents,
+        getCommandId(),
+        // TODO(bazel-team): this optimization disallows rule-specified additional dependencies
+        // on the client environment!
+        getCommandlineWhitelistedClientEnv(),
         timestampGranularityMonitor);
   }
 
@@ -499,6 +524,17 @@
         testEnv.put(entry.getKey(), entry.getValue());
       }
 
+      // Compute the set of environment variables that are whitelisted on the commandline
+      // for inheritence.
+      for (Map.Entry<String, String> entry :
+             optionsParser.getOptions(BuildConfiguration.Options.class).actionEnvironment) {
+        if (entry.getValue() == null) {
+          visibleClientEnv.add(entry.getKey());
+        } else {
+          visibleClientEnv.remove(entry.getKey());
+        }
+      }
+
       try {
         for (Map.Entry<String, String> entry : testEnv.entrySet()) {
           if (entry.getValue() == null) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index f73d247..0808b7c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -102,6 +102,9 @@
       // Depending on the buildID ensure that these actions have a chance to execute.
       PrecomputedValue.BUILD_ID.get(env);
     }
+    // The client environment might influence the action.
+    Map<String, String> clientEnv = PrecomputedValue.CLIENT_ENV.get(env);
+
     // For restarts of this ActionExecutionFunction we use a ContinuationState variable, below, to
     // avoid redoing work. However, if two actions are shared and the first one executes, when the
     // second one goes to execute, we should detect that and short-circuit, even without taking
@@ -170,7 +173,7 @@
 
     ActionExecutionValue result;
     try {
-      result = checkCacheAndExecuteIfNeeded(action, state, env);
+      result = checkCacheAndExecuteIfNeeded(action, state, env, clientEnv);
     } catch (ActionExecutionException e) {
       // Remove action from state map in case it's there (won't be unless it discovers inputs).
       stateMap.remove(action);
@@ -326,9 +329,8 @@
   }
 
   private ActionExecutionValue checkCacheAndExecuteIfNeeded(
-      Action action,
-      ContinuationState state,
-      Environment env) throws ActionExecutionException, InterruptedException {
+      Action action, ContinuationState state, Environment env, Map<String, String> clientEnv)
+      throws ActionExecutionException, InterruptedException {
     // If this is a shared action and the other action is the one that executed, we must use that
     // other action's value, provided here, since it is populated with metadata for the outputs.
     if (!state.hasArtifactData()) {
@@ -340,8 +342,13 @@
     long actionStartTime = System.nanoTime();
     // We only need to check the action cache if we haven't done it on a previous run.
     if (!state.hasCheckedActionCache()) {
-      state.token = skyframeActionExecutor.checkActionCache(action, metadataHandler,
-          actionStartTime, state.allInputs.actionCacheInputs);
+      state.token =
+          skyframeActionExecutor.checkActionCache(
+              action,
+              metadataHandler,
+              actionStartTime,
+              state.allInputs.actionCacheInputs,
+              clientEnv);
     }
 
     if (state.token == null) {
@@ -451,7 +458,7 @@
       }
     }
     Preconditions.checkState(!env.valuesMissing(), action);
-    skyframeActionExecutor.afterExecution(action, metadataHandler, state.token);
+    skyframeActionExecutor.afterExecution(action, metadataHandler, state.token, clientEnv);
     return state.value;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
index bc9977e..d572058 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
@@ -83,6 +83,9 @@
   static final Precomputed<UUID> BUILD_ID =
       new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "build_id"));
 
+  static final Precomputed<Map<String, String>> CLIENT_ENV =
+      new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "client_env"));
+
   static final Precomputed<WorkspaceStatusAction> WORKSPACE_STATUS_KEY =
       new Precomputed<>(SkyKey.create(SkyFunctions.PRECOMPUTED, "workspace_status_action"));
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index 18903e8..bda49c2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -249,12 +249,18 @@
   }
 
   @Override
-  public void sync(EventHandler eventHandler, PackageCacheOptions packageCacheOptions,
-      Path outputBase, Path workingDirectory, String defaultsPackageContents, UUID commandId,
+  public void sync(
+      EventHandler eventHandler,
+      PackageCacheOptions packageCacheOptions,
+      Path outputBase,
+      Path workingDirectory,
+      String defaultsPackageContents,
+      UUID commandId,
+      Map<String, String> clientEnv,
       TimestampGranularityMonitor tsgm)
-          throws InterruptedException, AbruptExitException {
+      throws InterruptedException, AbruptExitException {
     super.sync(eventHandler, packageCacheOptions, outputBase, workingDirectory,
-        defaultsPackageContents, commandId, tsgm);
+        defaultsPackageContents, commandId, clientEnv, tsgm);
     handleDiffs(eventHandler, packageCacheOptions.checkOutputFiles);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index f6c6742..d69e647 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -459,11 +459,16 @@
    * if the action is up to date, and non-null if it needs to be executed, in which case that token
    * should be provided to the ActionCacheChecker after execution.
    */
-  Token checkActionCache(Action action, MetadataHandler metadataHandler,
-      long actionStartTime, Iterable<Artifact> resolvedCacheArtifacts) {
+  Token checkActionCache(
+      Action action,
+      MetadataHandler metadataHandler,
+      long actionStartTime,
+      Iterable<Artifact> resolvedCacheArtifacts,
+      Map<String, String> clientEnv) {
     profiler.startTask(ProfilerTask.ACTION_CHECK, action);
-    Token token = actionCacheChecker.getTokenIfNeedToExecute(
-        action, resolvedCacheArtifacts, explain ? reporter : null, metadataHandler);
+    Token token =
+        actionCacheChecker.getTokenIfNeedToExecute(
+            action, resolvedCacheArtifacts, clientEnv, explain ? reporter : null, metadataHandler);
     profiler.completeTask(ProfilerTask.ACTION_CHECK);
     if (token == null) {
       boolean eventPosted = false;
@@ -487,7 +492,8 @@
     return token;
   }
 
-  void afterExecution(Action action, MetadataHandler metadataHandler, Token token) {
+  void afterExecution(
+      Action action, MetadataHandler metadataHandler, Token token, Map<String, String> clientEnv) {
     if (!actionReallyExecuted(action)) {
       // If an action shared with this one executed, then we need not update the action cache, since
       // the other action will do it. Moreover, this action is not aware of metadata acquired
@@ -495,7 +501,7 @@
       return;
     }
     try {
-      actionCacheChecker.afterExecution(action, token, metadataHandler);
+      actionCacheChecker.afterExecution(action, token, metadataHandler, clientEnv);
     } catch (IOException e) {
       // Skyframe has already done all the filesystem access needed for outputs and swallows
       // IOExceptions for inputs. So an IOException is impossible here.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 3110f50..65011b7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -685,6 +685,10 @@
     buildId.set(commandId);
   }
 
+  protected void setPrecomputedClientEnv(Map<String, String> clientEnv) {
+    PrecomputedValue.CLIENT_ENV.set(injectable(), clientEnv);
+  }
+
   /** Returns the build-info.txt and build-changelist.txt artifacts. */
   public Collection<Artifact> getWorkspaceStatusArtifacts(EventHandler eventHandler)
       throws InterruptedException {
@@ -891,11 +895,16 @@
    *
    * <p>MUST be run before every incremental build.
    */
-  @VisibleForTesting  // productionVisibility = Visibility.PRIVATE
-  public void preparePackageLoading(PathPackageLocator pkgLocator, RuleVisibility defaultVisibility,
-                                    boolean showLoadingProgress, int globbingThreads,
-                                    String defaultsPackageContents, UUID commandId,
-                                    TimestampGranularityMonitor tsgm) {
+  @VisibleForTesting // productionVisibility = Visibility.PRIVATE
+  public void preparePackageLoading(
+      PathPackageLocator pkgLocator,
+      RuleVisibility defaultVisibility,
+      boolean showLoadingProgress,
+      int globbingThreads,
+      String defaultsPackageContents,
+      UUID commandId,
+      Map<String, String> clientEnv,
+      TimestampGranularityMonitor tsgm) {
     Preconditions.checkNotNull(pkgLocator);
     Preconditions.checkNotNull(tsgm);
     setActive(true);
@@ -903,6 +912,7 @@
     this.tsgm.set(tsgm);
     maybeInjectPrecomputedValuesForAnalysis();
     setCommandId(commandId);
+    setPrecomputedClientEnv(clientEnv);
     setBlacklistedPackagePrefixesFile(getBlacklistedPackagePrefixesFile());
     setShowLoadingProgress(showLoadingProgress);
     setDefaultVisibility(defaultVisibility);
@@ -1627,16 +1637,30 @@
     return memoizingEvaluator;
   }
 
-  public void sync(EventHandler eventHandler, PackageCacheOptions packageCacheOptions,
-      Path outputBase, Path workingDirectory, String defaultsPackageContents, UUID commandId,
+  public void sync(
+      EventHandler eventHandler,
+      PackageCacheOptions packageCacheOptions,
+      Path outputBase,
+      Path workingDirectory,
+      String defaultsPackageContents,
+      UUID commandId,
+      Map<String, String> clientEnv,
       TimestampGranularityMonitor tsgm)
-          throws InterruptedException, AbruptExitException{
+      throws InterruptedException, AbruptExitException {
     preparePackageLoading(
         createPackageLocator(
-            eventHandler, packageCacheOptions, outputBase, directories.getWorkspace(),
+            eventHandler,
+            packageCacheOptions,
+            outputBase,
+            directories.getWorkspace(),
             workingDirectory),
-        packageCacheOptions.defaultVisibility, packageCacheOptions.showLoadingProgress,
-        packageCacheOptions.globbingThreads, defaultsPackageContents, commandId, tsgm);
+        packageCacheOptions.defaultVisibility,
+        packageCacheOptions.showLoadingProgress,
+        packageCacheOptions.globbingThreads,
+        defaultsPackageContents,
+        commandId,
+        clientEnv,
+        tsgm);
     setDeletedPackages(packageCacheOptions.getDeletedPackages());
 
     incrementalBuildMonitor = new SkyframeIncrementalBuildMonitor();
diff --git a/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java b/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java
index 41dfd5d..479e152 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java
@@ -22,6 +22,7 @@
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.util.Clock;
 import com.google.devtools.build.lib.vfs.Path;
@@ -163,7 +164,8 @@
   // Mutations may result in IllegalStateException.
   @Test
   public void testEntryToStringIsIdempotent() throws Exception {
-    ActionCache.Entry entry = new ActionCache.Entry("actionKey", false);
+    ActionCache.Entry entry =
+        new ActionCache.Entry("actionKey", ImmutableMap.<String, String>of(), false);
     entry.toString();
     entry.addFile(new PathFragment("foo/bar"), Metadata.CONSTANT_METADATA);
     entry.toString();
@@ -217,7 +219,8 @@
   }
 
   private void putKey(String key, ActionCache ac, boolean discoversInputs) {
-    ActionCache.Entry entry = new ActionCache.Entry(key, discoversInputs);
+    ActionCache.Entry entry =
+        new ActionCache.Entry(key, ImmutableMap.<String, String>of(), discoversInputs);
     entry.getFileDigest();
     ac.put(key, entry);
   }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
index e7d0655..3cb4951 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
@@ -15,6 +15,7 @@
 
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
 import com.google.common.eventbus.EventBus;
@@ -182,6 +183,7 @@
         ruleClassProvider.getDefaultsPackageContent(
             analysisMock.getInvocationPolicyEnforcer().getInvocationPolicy()),
         UUID.randomUUID(),
+        ImmutableMap.of(),
         new TimestampGranularityMonitor(BlazeClock.instance()));
     packageManager = skyframeExecutor.getPackageManager();
     loadingPhaseRunner = skyframeExecutor.getLoadingPhaseRunner(
@@ -285,6 +287,7 @@
         ruleClassProvider.getDefaultsPackageContent(
             analysisMock.getInvocationPolicyEnforcer().getInvocationPolicy()),
         UUID.randomUUID(),
+        ImmutableMap.of(),
         new TimestampGranularityMonitor(BlazeClock.instance()));
     skyframeExecutor.invalidateFilesUnderPathForTesting(reporter,
         ModifiedFileSet.EVERYTHING_MODIFIED, rootDirectory);
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index aac6fe6..7da4ca5 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -227,8 +227,13 @@
             analysisMock.getProductName());
     skyframeExecutor.preparePackageLoading(
         new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
-        ConstantRuleVisibility.PUBLIC, true, 7, "",
-        UUID.randomUUID(), tsgm);
+        ConstantRuleVisibility.PUBLIC,
+        true,
+        7,
+        "",
+        UUID.randomUUID(),
+        ImmutableMap.of(),
+        tsgm);
     useConfiguration();
     setUpSkyframe();
     // Also initializes ResourceManager.
@@ -310,10 +315,15 @@
   private void setUpSkyframe() {
     PathPackageLocator pkgLocator = PathPackageLocator.create(
         outputBase, packageCacheOptions.packagePath, reporter, rootDirectory, rootDirectory);
-    skyframeExecutor.preparePackageLoading(pkgLocator,
-        packageCacheOptions.defaultVisibility, true,
-        7, ruleClassProvider.getDefaultsPackageContent(optionsParser),
-        UUID.randomUUID(), tsgm);
+    skyframeExecutor.preparePackageLoading(
+        pkgLocator,
+        packageCacheOptions.defaultVisibility,
+        true,
+        7,
+        ruleClassProvider.getDefaultsPackageContent(optionsParser),
+        UUID.randomUUID(),
+        ImmutableMap.<String, String>of(),
+        tsgm);
     skyframeExecutor.setDeletedPackages(ImmutableSet.copyOf(packageCacheOptions.getDeletedPackages()));
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
index af92ecf..b5ecba0 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
@@ -17,6 +17,7 @@
 
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Root;
@@ -122,6 +123,7 @@
         ruleClassProvider.getDefaultsPackageContent(
             analysisMock.getInvocationPolicyEnforcer().getInvocationPolicy()),
         UUID.randomUUID(),
+        ImmutableMap.of(),
         new TimestampGranularityMonitor(BlazeClock.instance()));
 
     mockToolsConfig = new MockToolsConfig(rootDirectory);
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java b/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
index 8b8d039..6b1eebb 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
@@ -49,15 +49,13 @@
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.common.options.OptionsParser;
-
-import org.junit.Before;
-
 import java.io.IOException;
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 import java.util.UUID;
+import org.junit.Before;
 
 /**
  * This is a specialization of {@link FoundationTestCase} that's useful for
@@ -131,7 +129,8 @@
     skyframeExecutor.preparePackageLoading(
         new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
         defaultVisibility, true, GLOBBING_THREADS, defaultsPackageContents,
-        UUID.randomUUID(), new TimestampGranularityMonitor(BlazeClock.instance()));
+        UUID.randomUUID(), ImmutableMap.of(),
+        new TimestampGranularityMonitor(BlazeClock.instance()));
   }
 
   private void setUpSkyframe(PackageCacheOptions packageCacheOptions) {
@@ -144,8 +143,10 @@
         GLOBBING_THREADS,
         loadingMock.getDefaultsPackageContent(),
         UUID.randomUUID(),
+        ImmutableMap.of(),
         new TimestampGranularityMonitor(BlazeClock.instance()));
-    skyframeExecutor.setDeletedPackages(ImmutableSet.copyOf(packageCacheOptions.getDeletedPackages()));
+    skyframeExecutor.setDeletedPackages(
+        ImmutableSet.copyOf(packageCacheOptions.getDeletedPackages()));
   }
 
   private PackageCacheOptions parsePackageCacheOptions(String... options) throws Exception {
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java
index 3a2798f..3069a1d 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/IncrementalLoadingTest.java
@@ -55,20 +55,17 @@
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
-
-import org.junit.Before;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
 import java.io.FileNotFoundException;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.List;
 import java.util.UUID;
-
 import javax.annotation.Nullable;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
 
 /**
  * Tests for incremental loading; these cover both normal operation and diff awareness, for which a
@@ -488,7 +485,8 @@
       skyframeExecutor.preparePackageLoading(
           new PathPackageLocator(outputBase, ImmutableList.of(workspace)),
           ConstantRuleVisibility.PUBLIC, true, 7, "",
-          UUID.randomUUID(), new TimestampGranularityMonitor(BlazeClock.instance()));
+          UUID.randomUUID(), ImmutableMap.of(),
+          new TimestampGranularityMonitor(BlazeClock.instance()));
     }
 
     Path addFile(String fileName, String... content) throws IOException {
@@ -567,7 +565,8 @@
       skyframeExecutor.preparePackageLoading(
           new PathPackageLocator(outputBase, ImmutableList.of(workspace)),
           ConstantRuleVisibility.PUBLIC, true, 7, "",
-          UUID.randomUUID(), new TimestampGranularityMonitor(BlazeClock.instance()));
+          UUID.randomUUID(), ImmutableMap.of(),
+          new TimestampGranularityMonitor(BlazeClock.instance()));
       skyframeExecutor.invalidateFilesUnderPathForTesting(
           new Reporter(), modifiedFileSet, workspace);
       ((SequencedSkyframeExecutor) skyframeExecutor).handleDiffs(new Reporter());
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java
index afa781a..ceb26a1 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunnerTest.java
@@ -26,6 +26,7 @@
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableListMultimap;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.eventbus.EventBus;
@@ -620,9 +621,10 @@
           7,
           analysisMock.getDefaultsPackageContent(),
           UUID.randomUUID(),
+          ImmutableMap.of(),
           new TimestampGranularityMonitor(clock));
-      loadingPhaseRunner = skyframeExecutor.getLoadingPhaseRunner(
-          pkgFactory.getRuleClassNames(), useNewImpl);
+      loadingPhaseRunner =
+          skyframeExecutor.getLoadingPhaseRunner(pkgFactory.getRuleClassNames(), useNewImpl);
       this.options = Options.getDefaults(LoadingOptions.class);
     }
 
diff --git a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
index 9afcce1..5735458 100644
--- a/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/pkgcache/PackageCacheTest.java
@@ -24,6 +24,7 @@
 
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
@@ -55,17 +56,15 @@
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.common.options.OptionsParser;
 import com.google.devtools.common.options.OptionsParsingException;
-
-import org.junit.Before;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
 import java.io.IOException;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 import java.util.UUID;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
 
 /**
  * Tests for package loading.
@@ -112,8 +111,10 @@
         7,
         analysisMock.getDefaultsPackageContent(),
         UUID.randomUUID(),
+        ImmutableMap.of(),
         new TimestampGranularityMonitor(BlazeClock.instance()));
-    skyframeExecutor.setDeletedPackages(ImmutableSet.copyOf(packageCacheOptions.getDeletedPackages()));
+    skyframeExecutor.setDeletedPackages(
+        ImmutableSet.copyOf(packageCacheOptions.getDeletedPackages()));
   }
 
   private PackageCacheOptions parsePackageCacheOptions(String... options) throws Exception {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
index 2aec594..f6ee2ee 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
@@ -71,10 +71,16 @@
   private CustomInMemoryFs fs = new CustomInMemoryFs(new ManualClock());
 
   private void preparePackageLoading(Path... roots) {
-    getSkyframeExecutor().preparePackageLoading(
-        new PathPackageLocator(outputBase, ImmutableList.copyOf(roots)),
-        ConstantRuleVisibility.PUBLIC, true,
-        7, "", UUID.randomUUID(), new TimestampGranularityMonitor(BlazeClock.instance()));
+    getSkyframeExecutor()
+        .preparePackageLoading(
+            new PathPackageLocator(outputBase, ImmutableList.copyOf(roots)),
+            ConstantRuleVisibility.PUBLIC,
+            true,
+            7,
+            "",
+            UUID.randomUUID(),
+            ImmutableMap.<String, String>of(),
+            new TimestampGranularityMonitor(BlazeClock.instance()));
   }
 
   @Override
@@ -435,10 +441,16 @@
             Label.parseAbsoluteUnchecked("//foo:b.txt"))
         .inOrder();
     getSkyframeExecutor().resetEvaluator();
-    getSkyframeExecutor().preparePackageLoading(
-        new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
-        ConstantRuleVisibility.PUBLIC, true, 7, "",
-        UUID.randomUUID(), tsgm);
+    getSkyframeExecutor()
+        .preparePackageLoading(
+            new PathPackageLocator(outputBase, ImmutableList.<Path>of(rootDirectory)),
+            ConstantRuleVisibility.PUBLIC,
+            true,
+            7,
+            "",
+            UUID.randomUUID(),
+            ImmutableMap.of(),
+            tsgm);
     value = validPackage(skyKey);
     assertThat(
             (Iterable<Label>)
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTest.java
index b5a9494..902c62f 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTest.java
@@ -18,6 +18,7 @@
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Event;
@@ -33,14 +34,12 @@
 import com.google.devtools.build.lib.vfs.ModifiedFileSet;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
 import java.io.IOException;
 import java.util.Collection;
 import java.util.UUID;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
 
 @RunWith(JUnit4.class)
 public class SkyframeLabelVisitorTest extends SkyframeLabelVisitorTestCase {
@@ -410,6 +409,7 @@
             7,
             loadingMock.getDefaultsPackageContent(),
             UUID.randomUUID(),
+            ImmutableMap.of(),
             new TimestampGranularityMonitor(BlazeClock.instance()));
     this.visitor = getSkyframeExecutor().pkgLoader();
     scratch.file("pkg/BUILD", "sh_library(name = 'x', deps = ['z'])", "sh_library(name = 'z')");
@@ -454,6 +454,7 @@
             7,
             loadingMock.getDefaultsPackageContent(),
             UUID.randomUUID(),
+            ImmutableMap.of(),
             new TimestampGranularityMonitor(BlazeClock.instance()));
     this.visitor = getSkyframeExecutor().pkgLoader();
     scratch.file("a/BUILD", "subinclude('//b:c/d/foo')");
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkFileContentHashTests.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkFileContentHashTests.java
index 089d6a4..23f7171 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkFileContentHashTests.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkFileContentHashTests.java
@@ -17,6 +17,7 @@
 import static org.junit.Assert.assertFalse;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.packages.ConstantRuleVisibility;
@@ -28,15 +29,13 @@
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyKey;
-
+import java.util.Collection;
+import java.util.UUID;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.util.Collection;
-import java.util.UUID;
-
 /**
  * Tests for the hash code calculated for Skylark RuleClasses based on the transitive closure
  * of the imports of their respective definition SkylarkEnvironments.
@@ -164,6 +163,7 @@
             7,
             "",
             UUID.randomUUID(),
+            ImmutableMap.of(),
             new TimestampGranularityMonitor(BlazeClock.instance()));
     SkyKey pkgLookupKey = PackageValue.key(PackageIdentifier.parse("@//" + pkg));
     EvaluationResult<PackageValue> result =
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunctionTest.java
index 838302f..78100f7 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunctionTest.java
@@ -19,6 +19,7 @@
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.ConstantRuleVisibility;
@@ -30,14 +31,12 @@
 import com.google.devtools.build.skyframe.ErrorInfo;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyKey;
-
+import java.util.UUID;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.util.UUID;
-
 /**
  * Tests for SkylarkImportLookupFunction.
  */
@@ -55,6 +54,7 @@
             7,
             "",
             UUID.randomUUID(),
+            ImmutableMap.of(),
             new TimestampGranularityMonitor(BlazeClock.instance()));
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index 0a2c7dd..a8ffdfe 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -195,6 +195,7 @@
             evaluationProgressReceiver);
     final SequentialBuildDriver driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.CLIENT_ENV.set(differencer, ImmutableMap.<String, String>of());
     PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
 
     return new Builder() {
diff --git a/src/test/shell/integration/action_env_test.sh b/src/test/shell/integration/action_env_test.sh
index 24e87ee..156473b 100755
--- a/src/test/shell/integration/action_env_test.sh
+++ b/src/test/shell/integration/action_env_test.sh
@@ -72,4 +72,52 @@
   expect_log "FOO=client_foo"
 }
 
+function test_redo_action() {
+  export FOO=initial_foo
+  export UNRELATED=some_value
+  bazel build --action_env=FOO pkg:showenv || fail "bazel build showenv failed"
+  cat `bazel info bazel-genfiles`/pkg/env.txt > $TEST_log
+  expect_log "FOO=initial_foo"
+
+  # If an unrelated value changes, we expect the action not to be executed again
+  export UNRELATED=some_other_value
+  bazel build --action_env=FOO pkg:showenv 2> $TEST_log \
+      || fail "bazel build showenv failed"
+  expect_log "Critical Path: 0.00s"
+
+  # However, if a used variable changes, we expect the change to be propagated
+  export FOO=changed_foo
+  bazel build --action_env=FOO pkg:showenv || fail "bazel build showenv failed"
+  cat `bazel info bazel-genfiles`/pkg/env.txt > $TEST_log
+  expect_log "FOO=changed_foo"
+
+  # But repeating the build with no further changes, no action should happen
+  bazel build --action_env=FOO pkg:showenv 2> $TEST_log \
+      || fail "bazel build showenv failed"
+  expect_log "Critical Path: 0.00s"
+
+}
+
+function test_latest_wins_arg() {
+  export FOO=bar
+  export BAR=baz
+  bazel build --action_env=BAR --action_env=FOO --action_env=FOO=foo \
+      pkg:showenv || fail "bazel build showenv failed"
+  cat `bazel info bazel-genfiles`/pkg/env.txt > $TEST_log
+  expect_log "FOO=foo"
+  expect_log "BAR=baz"
+  expect_not_log "FOO=bar"
+}
+
+function test_latest_wins_env() {
+  export FOO=bar
+  export BAR=baz
+  bazel build --action_env=BAR --action_env=FOO=foo --action_env=FOO \
+      pkg:showenv || fail "bazel build showenv failed"
+  cat `bazel info bazel-genfiles`/pkg/env.txt > $TEST_log
+  expect_log "FOO=bar"
+  expect_log "BAR=baz"
+  expect_not_log "FOO=foo"
+}
+
 run_suite "Tests for bazel's handling of environment variables in actions"