Optimizes performance of ActionFS staging and eliminates ActionFS updates.

Extracts a class, InputArtifactData to hold the input data instead of using a raw map. This provides the flexibility needed to support both ActionFS and existing code so ActionFS does not need to rekey the input data.

Uses the smaller, getDeclaredIncludeSrcs instead of getAllowedDerivedInputs
when possible for staging optional inputs in ActionFS.

PiperOrigin-RevId: 196736703

11 files changed, 318 insertions, 357 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index 5281e04f76..8259018bc3 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -567,6 +567,7 @@ java_library(
         "//src/main/java/com/google/devtools/build/lib/graph",
         "//src/main/java/com/google/devtools/build/lib/profiler",
         "//src/main/java/com/google/devtools/build/lib/profiler/memory:current_rule_tracker",
+        "//src/main/java/com/google/devtools/build/lib/rules/cpp:cpp_interface",
         "//src/main/java/com/google/devtools/build/lib/shell",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
         "//src/main/java/com/google/devtools/build/lib/skylarkbuildapi",
diff --git a/src/main/java/com/google/devtools/build/lib/profiler/ProfilerTask.java b/src/main/java/com/google/devtools/build/lib/profiler/ProfilerTask.java
index 804a154721..9c17ef9173 100644
--- a/src/main/java/com/google/devtools/build/lib/profiler/ProfilerTask.java
+++ b/src/main/java/com/google/devtools/build/lib/profiler/ProfilerTask.java
@@ -90,7 +90,6 @@ public enum ProfilerTask {
   SKYLARK_BUILTIN_FN("Skylark builtin function call", -1, 0x990033, 0),
   SKYLARK_USER_COMPILED_FN("Skylark compiled user function call", -1, 0xCC0033, 0),
   ACTION_FS_STAGING("Staging per-action file system", -1, 0x000000, 0),
-  ACTION_FS_UPDATE("Updating per-action file system", -1, 0x000000, 0),
   UNKNOWN("Unknown event", -1, 0x339966, 0);
 
   // Size of the ProfilerTask value space.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/BUILD b/src/main/java/com/google/devtools/build/lib/rules/cpp/BUILD
index 028a0d662f..034f816261 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/BUILD
@@ -6,15 +6,23 @@ filegroup(
     visibility = ["//src/main/java/com/google/devtools/build/lib:__pkg__"],
 )
 
+INTERFACE_SOURCES = [
+    "IncludeScannable.java",
+]
+
 # Description:
 #   C++ rule support
 java_library(
     name = "cpp",
-    srcs = glob([
-        "*.java",
-        "transitions/*.java",
-    ]),
+    srcs = glob(
+        [
+            "*.java",
+            "transitions/*.java",
+        ],
+        exclude = INTERFACE_SOURCES,
+    ),
     deps = [
+        ":cpp_interface",
         "//src/main/java/com/google/devtools/build/lib:build-base",
         "//src/main/java/com/google/devtools/build/lib:events",
         "//src/main/java/com/google/devtools/build/lib:io",
@@ -45,3 +53,14 @@ java_library(
         "//third_party/protobuf:protobuf_java",
     ],
 )
+
+java_library(
+    name = "cpp_interface",
+    srcs = INTERFACE_SOURCES,
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib/actions",
+        "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
+        "//src/main/java/com/google/devtools/build/lib/vfs",
+        "//third_party:jsr305",
+    ],
+)
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 283f0d9e03..937f630dd4 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
@@ -15,7 +15,6 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
-import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -42,6 +41,8 @@ import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.rules.cpp.IncludeScannable;
+import com.google.devtools.build.lib.skyframe.InputArtifactData.MutableInputArtifactData;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -149,8 +150,7 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
       env.getValues(state.allInputs.keysRequested);
       Preconditions.checkState(!env.valuesMissing(), "%s %s", action, state);
     }
-    Pair<Map<Artifact, FileArtifactValue>, Map<Artifact, Collection<Artifact>>> checkedInputs =
-        null;
+    Pair<MutableInputArtifactData, Map<Artifact, Collection<Artifact>>> checkedInputs = null;
     try {
       // Declare deps on known inputs to action. We do this unconditionally to maintain our
       // invariant of asking for the same deps each build.
@@ -190,14 +190,29 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
       state.inputArtifactData = checkedInputs.first;
       state.expandedArtifacts = checkedInputs.second;
       if (skyframeActionExecutor.usesActionFileSystem()) {
+        Iterable<Artifact> optionalInputs;
+        if (action.discoversInputs()) {
+          if (action instanceof IncludeScannable) {
+            // This is a performance optimization to minimize nested set traversals for cpp
+            // compilation. CppCompileAction.getAllowedDerivedInputs iterates over mandatory inputs,
+            // prunable inputs, declared include srcs, transitive compilation prerequisites and
+            // transitive modules.
+            //
+            // The only one of those sets known to be needed is the declared include srcs.
+            optionalInputs = ((IncludeScannable) action).getDeclaredIncludeSrcs();
+          } else {
+            // This might be reachable by LtoBackendAction and ExtraAction.
+            optionalInputs = action.getAllowedDerivedInputs();
+          }
+        } else {
+          optionalInputs = ImmutableList.of();
+        }
         state.actionFileSystem =
             new ActionFileSystem(
+                skyframeActionExecutor.getExecRoot(),
+                skyframeActionExecutor.getSourceRoots(),
                 checkedInputs.first,
-                // TODO(shahan): based on experimentation, it suffices to include only {@link
-                // com.google.devtools.build.lib.rules.cpp.IncludeScannable#getDeclaredIncludeSrcs}.
-                // That may be a smaller set and more efficient but makes this class have an
-                // awkward dependency on something in the cpp package.
-                action.discoversInputs() ? action.getAllowedDerivedInputs() : ImmutableList.of(),
+                optionalInputs,
                 action.getOutputs());
       }
     }
@@ -428,7 +443,6 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
       }
       perActionFileCache =
           new PerActionFileCache(state.inputArtifactData, /*missingArtifactsAllowed=*/ false);
-      state.updateFileSystemInputData();
 
       // Stage 1 finished, let's do stage 2. The stage 1 of input discovery will have added some
       // files with addDiscoveredInputs() and then have waited for those files to be available
@@ -446,7 +460,6 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
         }
         perActionFileCache =
             new PerActionFileCache(state.inputArtifactData, /*missingArtifactsAllowed=*/ false);
-        state.updateFileSystemInputData();
       }
       metadataHandler =
           new ActionMetadataHandler(state.inputArtifactData, action.getOutputs(), tsgm.get());
@@ -502,8 +515,7 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
     }
 
     if (action.discoversInputs()) {
-      Iterable<Artifact> newInputs =
-          filterKnownInputs(action.getInputs(), state.inputArtifactData.keySet());
+      Iterable<Artifact> newInputs = filterKnownInputs(action.getInputs(), state.inputArtifactData);
       Map<SkyKey, SkyValue> metadataFoundDuringActionExecution =
           env.getValues(toKeys(newInputs, action.getMandatoryInputs()));
       state.discoveredInputs = newInputs;
@@ -514,13 +526,10 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
         // We are in the interesting case of an action that discovered its inputs during
         // execution, and found some new ones, but the new ones were already present in the graph.
         // We must therefore cache the metadata for those new ones.
-        Map<Artifact, FileArtifactValue> inputArtifactData = new HashMap<>();
-        inputArtifactData.putAll(state.inputArtifactData);
         for (Map.Entry<SkyKey, SkyValue> entry : metadataFoundDuringActionExecution.entrySet()) {
-          inputArtifactData.put(
+          state.inputArtifactData.put(
               ArtifactSkyKey.artifact(entry.getKey()), (FileArtifactValue) entry.getValue());
         }
-        state.inputArtifactData = inputArtifactData;
         // TODO(ulfjack): This causes information loss about omitted and injected outputs. Also see
         // the documentation on MetadataHandler.artifactOmitted. This works by accident because
         // markOmitted is only called for remote execution, and this code only gets executed for
@@ -545,13 +554,13 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
       };
 
   private static Iterable<SkyKey> newlyDiscoveredInputsToSkyKeys(
-      Iterable<Artifact> discoveredInputs, Set<Artifact> knownInputs) {
+      Iterable<Artifact> discoveredInputs, MutableInputArtifactData inputArtifactData) {
     return Iterables.transform(
-        filterKnownInputs(discoveredInputs, knownInputs), TO_NONMANDATORY_SKYKEY);
+        filterKnownInputs(discoveredInputs, inputArtifactData), TO_NONMANDATORY_SKYKEY);
   }
 
   private static void addDiscoveredInputs(
-      Map<Artifact, FileArtifactValue> inputData,
+      MutableInputArtifactData inputData,
       Map<Artifact, Collection<Artifact>> expandedArtifacts,
       Iterable<Artifact> discoveredInputs,
       Environment env)
@@ -564,15 +573,17 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
     // discovery.
     // Therefore there is no need to catch and rethrow exceptions as there is with #checkInputs.
     Map<SkyKey, SkyValue> nonMandatoryDiscovered =
-        env.getValues(newlyDiscoveredInputsToSkyKeys(discoveredInputs, inputData.keySet()));
+        env.getValues(newlyDiscoveredInputsToSkyKeys(discoveredInputs, inputData));
     if (!env.valuesMissing()) {
       for (Map.Entry<SkyKey, SkyValue> entry : nonMandatoryDiscovered.entrySet()) {
         Artifact input = ArtifactSkyKey.artifact(entry.getKey());
         if (entry.getValue() instanceof TreeArtifactValue) {
           TreeArtifactValue treeValue = (TreeArtifactValue) entry.getValue();
           expandedArtifacts.put(input, ImmutableSet.<Artifact>copyOf(treeValue.getChildren()));
-          inputData.putAll(treeValue.getChildValues());
-
+          for (Map.Entry<Artifact.TreeFileArtifact, FileArtifactValue> child :
+              treeValue.getChildValues().entrySet()) {
+            inputData.put(child.getKey(), child.getValue());
+          }
           inputData.put(input, treeValue.getSelfData());
         } else {
           inputData.put(input, (FileArtifactValue) entry.getValue());
@@ -632,8 +643,9 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
    * Declare dependency on all known inputs of action. Throws exception if any are known to be
    * missing. Some inputs may not yet be in the graph, in which case the builder should abort.
    */
-  private Pair<Map<Artifact, FileArtifactValue>, Map<Artifact, Collection<Artifact>>>
-  checkInputs(Environment env, Action action,
+  private Pair<MutableInputArtifactData, Map<Artifact, Collection<Artifact>>> checkInputs(
+      Environment env,
+      Action action,
       Map<SkyKey, ValueOrException2<MissingInputFileException, ActionExecutionException>> inputDeps)
       throws ActionExecutionException {
     int missingCount = 0;
@@ -644,8 +656,8 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
     // some deps are still missing.
     boolean populateInputData = !env.valuesMissing();
     NestedSetBuilder<Cause> rootCauses = NestedSetBuilder.stableOrder();
-    Map<Artifact, FileArtifactValue> inputArtifactData =
-        new HashMap<>(populateInputData ? inputDeps.size() : 0);
+    MutableInputArtifactData inputArtifactData =
+        new MutableInputArtifactData(populateInputData ? inputDeps.size() : 0);
     Map<Artifact, Collection<Artifact>> expandedArtifacts =
         new HashMap<>(populateInputData ? 128 : 0);
 
@@ -672,7 +684,10 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
           } else if (value instanceof TreeArtifactValue) {
             TreeArtifactValue treeValue = (TreeArtifactValue) value;
             expandedArtifacts.put(input, ImmutableSet.<Artifact>copyOf(treeValue.getChildren()));
-            inputArtifactData.putAll(treeValue.getChildValues());
+            for (Map.Entry<Artifact.TreeFileArtifact, FileArtifactValue> child :
+                treeValue.getChildValues().entrySet()) {
+              inputArtifactData.put(child.getKey(), child.getValue());
+            }
 
             // Again, we cache the "digest" of the value for cache checking.
             inputArtifactData.put(input, treeValue.getSelfData());
@@ -729,8 +744,8 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
   }
 
   private static Iterable<Artifact> filterKnownInputs(
-      Iterable<Artifact> newInputs, Set<Artifact> knownInputs) {
-    return Iterables.filter(newInputs, Predicates.not(Predicates.in(knownInputs)));
+      Iterable<Artifact> newInputs, MutableInputArtifactData inputArtifactData) {
+    return Iterables.filter(newInputs, input -> !inputArtifactData.contains(input));
   }
 
   /**
@@ -785,7 +800,8 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
   private static class ContinuationState {
     AllInputs allInputs;
     /** Mutable map containing metadata for known artifacts. */
-    Map<Artifact, FileArtifactValue> inputArtifactData = null;
+    MutableInputArtifactData inputArtifactData = null;
+
     Map<Artifact, Collection<Artifact>> expandedArtifacts = null;
     Token token = null;
     Iterable<Artifact> discoveredInputs = null;
@@ -821,13 +837,6 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
       }
     }
 
-    /** Propagates {@link inputArtifactData} changes due to input discovery. */
-    void updateFileSystemInputData() {
-      if (actionFileSystem != null) {
-        actionFileSystem.updateInputData(inputArtifactData);
-      }
-    }
-
     @Override
     public String toString() {
       return token + ", " + value + ", " + allInputs + ", " + inputArtifactData + ", "
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionFileSystem.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionFileSystem.java
index 6ebc0cbcf2..804009a085 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionFileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionFileSystem.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.skyframe;
 import static java.nio.charset.StandardCharsets.US_ASCII;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Streams;
 import com.google.common.io.BaseEncoding;
@@ -28,6 +29,7 @@ import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.vfs.AbstractFileSystem;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.protobuf.ByteString;
 import java.io.FileNotFoundException;
@@ -37,11 +39,7 @@ import java.io.InterruptedIOException;
 import java.io.OutputStream;
 import java.util.Collection;
 import java.util.HashMap;
-import java.util.LinkedHashSet;
-import java.util.Map;
 import java.util.concurrent.ConcurrentHashMap;
-import java.util.function.Function;
-import java.util.function.Supplier;
 import java.util.logging.Logger;
 import javax.annotation.Nullable;
 
@@ -51,8 +49,7 @@ import javax.annotation.Nullable;
  * <p>This class is thread-safe except that
  *
  * <ul>
- *   <li>{@link updateContext} and {@link updateInputData} must be called exclusively of any other
- *       methods.
+ *   <li>{@link updateContext} must be called exclusively of any other methods.
  *   <li>This class relies on synchronized access to {@link env}. If there are other threads, that
  *       access {@link env}, they must also used synchronized access.
  * </ul>
@@ -60,21 +57,20 @@ import javax.annotation.Nullable;
 final class ActionFileSystem extends AbstractFileSystem implements ActionInputFileCache {
   private static final Logger LOGGER = Logger.getLogger(ActionFileSystem.class.getName());
 
-  /**
-   * Exec root and source roots.
-   *
-   * <p>First entry is exec root. Used to convert paths into exec paths.
-   */
-  private final LinkedHashSet<PathFragment> roots = new LinkedHashSet<>();
+  private final PathFragment execRootFragment;
+  private final Path execRootPath;
+  private final ImmutableList<PathFragment> sourceRoots;
 
-  /** exec path → artifact and metadata */
-  private final Map<PathFragment, ArtifactAndMetadata> inputs;
+  private final InputArtifactData inputArtifactData;
 
   /** exec path → artifact and metadata */
-  private final ImmutableMap<PathFragment, ArtifactAndMutableMetadata> outputs;
+  private final HashMap<PathFragment, OptionalInputMetadata> optionalInputs;
 
   /** digest → artifacts in {@link inputs} */
-  private final ConcurrentHashMap<ByteString, Artifact> reverseMap;
+  private final ConcurrentHashMap<ByteString, Artifact> optionalInputsByDigest;
+
+  /** exec path → artifact and metadata */
+  private final ImmutableMap<PathFragment, OutputMetadata> outputs;
 
   /** Used to lookup metadata for optional inputs. */
   private SkyFunction.Environment env = null;
@@ -88,38 +84,44 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
   private MetadataConsumer metadataConsumer = null;
 
   ActionFileSystem(
-      Map<Artifact, FileArtifactValue> inputData,
+      Path execRoot,
+      ImmutableList<Root> sourceRoots,
+      InputArtifactData inputArtifactData,
       Iterable<Artifact> allowedInputs,
       Iterable<Artifact> outputArtifacts) {
     try {
       Profiler.instance().startTask(ProfilerTask.ACTION_FS_STAGING, "staging");
-      roots.add(computeExecRoot(outputArtifacts));
-
-      // TODO(shahan): Underestimates because this doesn't account for discovered inputs. Improve
-      // this estimate using data.
-      this.reverseMap = new ConcurrentHashMap<>(inputData.size());
-
-      HashMap<PathFragment, ArtifactAndMetadata> inputs = new HashMap<>();
-      for (Map.Entry<Artifact, FileArtifactValue> entry : inputData.entrySet()) {
-        Artifact input = entry.getKey();
-        updateRootsIfSource(input);
-        inputs.put(input.getExecPath(), new SimpleArtifactAndMetadata(input, entry.getValue()));
-        updateReverseMapIfDigestExists(entry.getValue(), entry.getKey());
-      }
+      this.inputArtifactData = inputArtifactData;
+      this.execRootFragment = execRoot.asFragment();
+      this.execRootPath = getPath(execRootFragment);
+      this.sourceRoots =
+          sourceRoots
+              .stream()
+              .map(root -> root.asPath().asFragment())
+              .collect(ImmutableList.toImmutableList());
+
+      validateRoots();
+
+      this.optionalInputs = new HashMap<>();
       for (Artifact input : allowedInputs) {
-        PathFragment execPath = input.getExecPath();
-        inputs.computeIfAbsent(execPath, unused -> new OptionalInputArtifactAndMetadata(input));
-        updateRootsIfSource(input);
+        // Skips staging source artifacts as a performance optimization. We may want to stage them
+        // if we want stricter enforcement of source sandboxing.
+        //
+        // TODO(shahan): there are no currently known cases where metadata is requested for an
+        // optional source input. If there are any, we may want to stage those.
+        if (input.isSourceArtifact() || inputArtifactData.contains(input)) {
+          continue;
+        }
+        optionalInputs.computeIfAbsent(
+            input.getExecPath(), unused -> new OptionalInputMetadata(input));
       }
-      this.inputs = inputs;
 
-      validateRoots();
+      this.optionalInputsByDigest = new ConcurrentHashMap<>();
 
       this.outputs =
           Streams.stream(outputArtifacts)
               .collect(
-                  ImmutableMap.toImmutableMap(
-                      a -> a.getExecPath(), a -> new ArtifactAndMutableMetadata(a)));
+                  ImmutableMap.toImmutableMap(a -> a.getExecPath(), a -> new OutputMetadata(a)));
     } finally {
       Profiler.instance().completeTask(ProfilerTask.ACTION_FS_STAGING);
     }
@@ -137,73 +139,29 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
     this.metadataConsumer = metadataConsumer;
   }
 
-  /** Input discovery changes the values of the input data map so it must be updated accordingly. */
-  public void updateInputData(Map<Artifact, FileArtifactValue> inputData) {
-    try {
-      Profiler.instance().startTask(ProfilerTask.ACTION_FS_UPDATE, "update");
-      boolean foundNewRoots = false;
-      for (Map.Entry<Artifact, FileArtifactValue> entry : inputData.entrySet()) {
-        ArtifactAndMetadata current = inputs.get(entry.getKey().getExecPath());
-        if (current == null || isUnsetOptional(current)) {
-          Artifact input = entry.getKey();
-          inputs.put(input.getExecPath(), new SimpleArtifactAndMetadata(input, entry.getValue()));
-          foundNewRoots = updateRootsIfSource(entry.getKey()) || foundNewRoots;
-          updateReverseMapIfDigestExists(entry.getValue(), entry.getKey());
-        }
-      }
-      if (foundNewRoots) {
-        validateRoots();
-      }
-    } finally {
-      Profiler.instance().completeTask(ProfilerTask.ACTION_FS_UPDATE);
-    }
-  }
-
   // -------------------- ActionInputFileCache implementation --------------------
 
   @Override
   @Nullable
-  public FileArtifactValue getMetadata(ActionInput actionInput) {
-    return apply(
-        actionInput.getExecPath(),
-        input -> {
-          try {
-            return input.getMetadata();
-          } catch (IOException e) {
-            // TODO(shahan): improve the handling of this error by propagating it correctly
-            // through MetadataHandler.getMetadata().
-            throw new IllegalStateException(e);
-          }
-        },
-        output -> output.getMetadata(),
-        () -> null);
+  public FileArtifactValue getMetadata(ActionInput actionInput) throws IOException {
+    return getMetadataChecked(actionInput.getExecPath());
   }
 
   @Override
   public boolean contentsAvailableLocally(ByteString digest) {
-    // TODO(shahan): we assume this is never true, though the digests might be present. Should
-    // this be relaxed for locally available source files?
-    return false;
+    return optionalInputsByDigest.containsKey(digest) || inputArtifactData.contains(digest);
   }
 
   @Override
   @Nullable
-  public Artifact getInputFromDigest(ByteString digest) {
-    return reverseMap.get(digest);
+  public ActionInput getInputFromDigest(ByteString digest) {
+    Artifact artifact = optionalInputsByDigest.get(digest);
+    return artifact != null ? artifact : inputArtifactData.get(digest);
   }
 
   @Override
   public Path getInputPath(ActionInput actionInput) {
-    ArtifactAndMetadata input = inputs.get(actionInput.getExecPath());
-    if (input != null) {
-      return getPath(input.getArtifact().getPath().getPathString());
-    }
-    ArtifactAndMutableMetadata output = outputs.get(actionInput.getExecPath());
-    if (output != null) {
-      return getPath(output.getArtifact().getPath().getPathString());
-    }
-    // TODO(shahan): this might need to be relaxed
-    throw new IllegalStateException(actionInput + " not found");
+    return execRootPath.getRelative(actionInput.getExecPath());
   }
 
   // -------------------- FileSystem implementation --------------------
@@ -305,19 +263,26 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
 
   @Override
   protected void createSymbolicLink(Path linkPath, PathFragment targetFragment) throws IOException {
-    ArtifactAndMetadata input = inputs.get(asExecPath(targetFragment));
-    if (input == null) {
+    PathFragment targetExecPath = asExecPath(targetFragment);
+    FileArtifactValue inputMetadata = inputArtifactData.get(targetExecPath);
+    if (inputMetadata == null) {
+      OptionalInputMetadata metadataHolder = optionalInputs.get(targetExecPath);
+      if (metadataHolder != null) {
+        inputMetadata = metadataHolder.get();
+      }
+    }
+    if (inputMetadata == null) {
       throw new FileNotFoundException(
           createSymbolicLinkErrorMessage(
               linkPath, targetFragment, targetFragment + " is not an input."));
     }
-    ArtifactAndMutableMetadata output = outputs.get(asExecPath(linkPath));
-    if (output == null) {
+    OutputMetadata outputHolder = outputs.get(asExecPath(linkPath));
+    if (outputHolder == null) {
       throw new FileNotFoundException(
           createSymbolicLinkErrorMessage(
               linkPath, targetFragment, linkPath + " is not an output."));
     }
-    output.setMetadata(input.getMetadata());
+    outputHolder.set(inputMetadata);
   }
 
   @Override
@@ -329,7 +294,7 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
   protected boolean exists(Path path, boolean followSymlinks) {
     Preconditions.checkArgument(
         followSymlinks, "ActionFileSystem doesn't support no-follow: %s", path);
-    return apply(path, input -> true, output -> output.getMetadata() != null, () -> false);
+    return getMetadataUnchecked(path) != null;
   }
 
   @Override
@@ -395,86 +360,68 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
   }
 
   private PathFragment asExecPath(PathFragment fragment) {
-    for (PathFragment root : roots) {
+    if (fragment.startsWith(execRootFragment)) {
+      return fragment.relativeTo(execRootFragment);
+    }
+    for (PathFragment root : sourceRoots) {
       if (fragment.startsWith(root)) {
         return fragment.relativeTo(root);
       }
     }
-    throw new IllegalArgumentException(fragment + " was not found under any known root: " + roots);
+    throw new IllegalArgumentException(
+        fragment + " was not found under any known root: " + execRootFragment + ", " + sourceRoots);
   }
 
-  private boolean isOutput(Path path) {
-    return outputs.containsKey(asExecPath(path));
-  }
-
-  /**
-   * Lambda-based case implementation.
-   *
-   * <p>One of {@code inputOp} or {@code outputOp} will be called depending on whether {@code path}
-   * is an input or output.
-   */
-  private <T> T apply(Path path, InputFileOperator<T> inputOp, OutputFileOperator<T> outputOp)
-      throws IOException {
-    PathFragment execPath = asExecPath(path);
-    ArtifactAndMetadata input = inputs.get(execPath);
-    if (input != null) {
-      return inputOp.apply(input);
+  @Nullable
+  private FileArtifactValue getMetadataChecked(PathFragment execPath) throws IOException {
+    {
+      FileArtifactValue metadata = inputArtifactData.get(execPath);
+      if (metadata != null) {
+        return metadata;
+      }
     }
-    ArtifactAndMutableMetadata output = outputs.get(execPath);
-    if (output != null) {
-      return outputOp.apply(output);
+    {
+      OptionalInputMetadata metadataHolder = optionalInputs.get(execPath);
+      if (metadataHolder != null) {
+        return metadataHolder.get();
+      }
     }
-    throw new FileNotFoundException(path.getPathString());
+    {
+      OutputMetadata metadataHolder = outputs.get(execPath);
+      if (metadataHolder != null) {
+        FileArtifactValue metadata = metadataHolder.get();
+        if (metadata != null) {
+          return metadata;
+        }
+      }
+    }
+    return null;
   }
 
-  /**
-   * Apply variant that doesn't throw exceptions.
-   *
-   * <p>Useful for implementing existence-type methods.
-   */
-  private <T> T apply(
-      Path path,
-      Function<ArtifactAndMetadata, T> inputOp,
-      Function<ArtifactAndMutableMetadata, T> outputOp,
-      Supplier<T> notFoundOp) {
-    return apply(asExecPath(path), inputOp, outputOp, notFoundOp);
-  }
-
-  private <T> T apply(
-      PathFragment execPath,
-      Function<ArtifactAndMetadata, T> inputOp,
-      Function<ArtifactAndMutableMetadata, T> outputOp,
-      Supplier<T> notFoundOp) {
-    ArtifactAndMetadata input = inputs.get(execPath);
-    if (input != null) {
-      return inputOp.apply(input);
-    }
-    ArtifactAndMutableMetadata output = outputs.get(execPath);
-    if (output != null) {
-      return outputOp.apply(output);
+  private FileArtifactValue getMetadataOrThrowFileNotFound(Path path) throws IOException {
+    FileArtifactValue metadata = getMetadataChecked(asExecPath(path));
+    if (metadata == null) {
+      throw new FileNotFoundException(path.getPathString() + " was not found");
     }
-    return notFoundOp.get();
+    return metadata;
   }
 
-  private boolean updateRootsIfSource(Artifact input) {
-    if (input.isSourceArtifact()) {
-      return roots.add(input.getRoot().getRoot().asPath().asFragment());
+  @Nullable
+  private FileArtifactValue getMetadataUnchecked(Path path) {
+    try {
+      return getMetadataChecked(asExecPath(path));
+    } catch (IOException e) {
+      throw new IllegalStateException(
+          "Error getting metadata for " + path.getPathString() + ": " + e.getMessage(), e);
     }
-    return false;
   }
 
-  /**
-   * The execution root is globally unique for a build so can be derived from any output.
-   *
-   * <p>Outputs must be nonempty.
-   */
-  private static PathFragment computeExecRoot(Iterable<Artifact> outputs) {
-    Artifact derived = outputs.iterator().next();
-    Preconditions.checkArgument(!derived.isSourceArtifact(), derived);
-    PathFragment rootFragment = derived.getRoot().getRoot().asPath().asFragment();
-    int rootSegments = rootFragment.segmentCount();
-    int execSegments = derived.getRoot().getExecPath().segmentCount();
-    return rootFragment.subFragment(0, rootSegments - execSegments);
+  private boolean isOutput(Path path) {
+    PathFragment fragment = path.asFragment();
+    if (!fragment.startsWith(execRootFragment)) {
+      return false;
+    }
+    return outputs.containsKey(fragment.relativeTo(execRootFragment));
   }
 
   /**
@@ -484,8 +431,12 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
    * relation between roots.
    */
   private void validateRoots() {
-    for (PathFragment root1 : roots) {
-      for (PathFragment root2 : roots) {
+    for (PathFragment root1 : sourceRoots) {
+      Preconditions.checkState(
+          !root1.startsWith(execRootFragment), "%s starts with %s", root1, execRootFragment);
+      Preconditions.checkState(
+          !execRootFragment.startsWith(root1), "%s starts with %s", execRootFragment, root1);
+      for (PathFragment root2 : sourceRoots) {
         if (root1 == root2) {
           continue;
         }
@@ -498,115 +449,20 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
     return ByteString.copyFrom(BaseEncoding.base16().lowerCase().encode(digest).getBytes(US_ASCII));
   }
 
-  private static boolean isUnsetOptional(ArtifactAndMetadata input) {
-    if (input instanceof OptionalInputArtifactAndMetadata) {
-      OptionalInputArtifactAndMetadata optional = (OptionalInputArtifactAndMetadata) input;
-      return !optional.hasMetadata();
-    }
-    return false;
-  }
-
-  private void updateReverseMapIfDigestExists(FileArtifactValue metadata, Artifact artifact) {
-    if (metadata.getDigest() != null) {
-      reverseMap.put(toByteString(metadata.getDigest()), artifact);
-    }
-  }
-
-  private FileArtifactValue getMetadataOrThrowFileNotFound(Path path) throws IOException {
-    return apply(
-        path,
-        input -> input.getMetadata(),
-        output -> {
-          if (output.getMetadata() == null) {
-            throw new FileNotFoundException(path.getPathString());
-          }
-          return output.getMetadata();
-        });
-  }
-
-  @Nullable
-  private FileArtifactValue getMetadataUnchecked(Path path) {
-    return apply(
-        path,
-        input -> {
-          try {
-            return input.getMetadata();
-          } catch (IOException e) {
-            // TODO(shahan): propagate this error correctly through higher level APIs.
-            throw new IllegalStateException(e);
-          }
-        },
-        output -> output.getMetadata(),
-        () -> null);
-  }
-
-  @FunctionalInterface
-  private static interface InputFileOperator<T> {
-    T apply(ArtifactAndMetadata entry) throws IOException;
-  }
-
-  @FunctionalInterface
-  private static interface OutputFileOperator<T> {
-    T apply(ArtifactAndMutableMetadata entry) throws IOException;
-  }
-
   @FunctionalInterface
   public static interface MetadataConsumer {
     void accept(Artifact artifact, FileArtifactValue value) throws IOException;
   }
 
-  private abstract static class ArtifactAndMetadata {
-    public abstract Artifact getArtifact();
-
-    public abstract FileArtifactValue getMetadata() throws IOException;
-
-    @Override
-    public String toString() {
-      String metadataText = null;
-      try {
-        metadataText = "" + getMetadata();
-      } catch (IOException e) {
-        metadataText = "Error getting metadata(" + e.getMessage() + ")";
-      }
-      return getArtifact() + ": " + metadataText;
-    }
-  }
-
-  private static class SimpleArtifactAndMetadata extends ArtifactAndMetadata {
-    private final Artifact artifact;
-    private final FileArtifactValue metadata;
-
-    private SimpleArtifactAndMetadata(Artifact artifact, FileArtifactValue metadata) {
-      this.artifact = artifact;
-      this.metadata = metadata;
-    }
-
-    @Override
-    public Artifact getArtifact() {
-      return artifact;
-    }
-
-    @Override
-    public FileArtifactValue getMetadata() {
-      return metadata;
-    }
-  }
-
-  private class OptionalInputArtifactAndMetadata extends ArtifactAndMetadata {
+  private class OptionalInputMetadata {
     private final Artifact artifact;
     private volatile FileArtifactValue metadata = null;
 
-    private OptionalInputArtifactAndMetadata(Artifact artifact) {
+    private OptionalInputMetadata(Artifact artifact) {
       this.artifact = artifact;
     }
 
-    @Override
-    public Artifact getArtifact() {
-      return artifact;
-    }
-
-    @Override
-    public FileArtifactValue getMetadata() throws IOException {
+    public FileArtifactValue get() throws IOException {
       if (metadata == null) {
         synchronized (this) {
           if (metadata == null) {
@@ -631,40 +487,32 @@ final class ActionFileSystem extends AbstractFileSystem implements ActionInputFi
             if (metadata == null) {
               throw new ActionExecutionFunction.MissingDepException();
             }
-            updateReverseMapIfDigestExists(metadata, artifact);
+            if (metadata.getType().exists() && metadata.getDigest() != null) {
+              optionalInputsByDigest.put(toByteString(metadata.getDigest()), artifact);
+            }
           }
         }
       }
       return metadata;
     }
-
-    public boolean hasMetadata() {
-      return metadata != null;
-    }
   }
 
-  private class ArtifactAndMutableMetadata extends ArtifactAndMetadata {
+  private class OutputMetadata {
     private final Artifact artifact;
     @Nullable private volatile FileArtifactValue metadata = null;
 
-    @Override
-    public Artifact getArtifact() {
-      return artifact;
+    private OutputMetadata(Artifact artifact) {
+      this.artifact = artifact;
     }
 
-    @Override
     @Nullable
-    public FileArtifactValue getMetadata() {
+    public FileArtifactValue get() {
       return metadata;
     }
 
-    public void setMetadata(FileArtifactValue metadata) throws IOException {
+    public void set(FileArtifactValue metadata) throws IOException {
       metadataConsumer.accept(artifact, metadata);
       this.metadata = metadata;
     }
-
-    private ArtifactAndMutableMetadata(Artifact artifact) {
-      this.artifact = artifact;
-    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
index 2b001d981c..6e992960e4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
@@ -76,9 +76,9 @@ public class ActionMetadataHandler implements MetadataHandler {
   /**
    * Data for input artifacts. Immutable.
    *
-   * <p>This should never be read directly. Use {@link #getInputFileArtifactValue} instead.</p>
+   * <p>This should never be read directly. Use {@link #getInputFileArtifactValue} instead.
    */
-  private final Map<Artifact, FileArtifactValue> inputArtifactData;
+  private final InputArtifactData inputArtifactData;
 
   /** FileValues for each output Artifact. */
   private final ConcurrentMap<Artifact, FileValue> outputArtifactData =
@@ -128,7 +128,8 @@ public class ActionMetadataHandler implements MetadataHandler {
   private final AtomicBoolean executionMode = new AtomicBoolean(false);
 
   @VisibleForTesting
-  public ActionMetadataHandler(Map<Artifact, FileArtifactValue> inputArtifactData,
+  public ActionMetadataHandler(
+      InputArtifactData inputArtifactData,
       Iterable<Artifact> outputs,
       TimestampGranularityMonitor tsgm) {
     this.inputArtifactData = Preconditions.checkNotNull(inputArtifactData);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/InputArtifactData.java b/src/main/java/com/google/devtools/build/lib/skyframe/InputArtifactData.java
new file mode 100644
index 0000000000..bb0560438a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/InputArtifactData.java
@@ -0,0 +1,102 @@
+// Copyright 2018 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.skyframe;
+
+import static java.nio.charset.StandardCharsets.US_ASCII;
+
+import com.google.common.io.BaseEncoding;
+import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.protobuf.ByteString;
+import java.util.HashMap;
+import javax.annotation.Nullable;
+
+/** An bidirectional mapping between artifacts and metadata. */
+interface InputArtifactData {
+
+  boolean contains(ActionInput input);
+
+  @Nullable
+  FileArtifactValue get(ActionInput input);
+
+  boolean contains(ByteString digest);
+
+  @Nullable
+  Artifact get(ByteString digest);
+
+  @Nullable
+  FileArtifactValue get(PathFragment fragment);
+
+  /**
+   * This implementation has a privileged {@link put} method supporting mutations.
+   *
+   * <p>Action execution has distinct phases where this data can be read from multiple threads. It's
+   * important that the underlying data is not modified during those phases.
+   */
+  final class MutableInputArtifactData implements InputArtifactData {
+    private final HashMap<PathFragment, FileArtifactValue> inputs;
+    private final HashMap<ByteString, Artifact> reverseMap;
+
+    public MutableInputArtifactData(int sizeHint) {
+      this.inputs = new HashMap<>(sizeHint);
+      this.reverseMap = new HashMap<>(sizeHint);
+    }
+
+    @Override
+    public boolean contains(ActionInput input) {
+      return inputs.containsKey(input.getExecPath());
+    }
+
+    @Override
+    @Nullable
+    public FileArtifactValue get(ActionInput input) {
+      return inputs.get(input.getExecPath());
+    }
+
+    @Override
+    public boolean contains(ByteString digest) {
+      return reverseMap.containsKey(digest);
+    }
+
+    @Override
+    @Nullable
+    public Artifact get(ByteString digest) {
+      return reverseMap.get(digest);
+    }
+
+    @Override
+    @Nullable
+    public FileArtifactValue get(PathFragment fragment) {
+      return inputs.get(fragment);
+    }
+
+    public void put(Artifact artifact, FileArtifactValue value) {
+      inputs.put(artifact.getExecPath(), value);
+      if (value.getType().exists() && value.getDigest() != null) {
+        reverseMap.put(toByteString(value.getDigest()), artifact);
+      }
+    }
+
+    @Override
+    public String toString() {
+      return inputs.toString();
+    }
+
+    private static ByteString toByteString(byte[] digest) {
+      return ByteString.copyFrom(
+          BaseEncoding.base16().lowerCase().encode(digest).getBytes(US_ASCII));
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java b/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
index 8a222ece2f..50ef5c660a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
@@ -14,16 +14,12 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
-import com.google.common.io.BaseEncoding;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.cache.Metadata;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.protobuf.ByteString;
-import java.nio.charset.StandardCharsets;
-import java.util.HashMap;
-import java.util.Map;
 import javax.annotation.Nullable;
 
 /**
@@ -34,18 +30,15 @@ import javax.annotation.Nullable;
  * the source of truth.
  */
 class PerActionFileCache implements ActionInputFileCache {
-  private final Map<Artifact, FileArtifactValue> inputArtifactData;
+  private final InputArtifactData inputArtifactData;
   private final boolean missingArtifactsAllowed;
-  // null until first call to getInputFromDigest()
-  private volatile HashMap<ByteString, Artifact> reverseMap;
 
   /**
    * @param inputArtifactData Map from artifact to metadata, used to return metadata upon request.
    * @param missingArtifactsAllowed whether to tolerate missing artifacts: can happen during input
    *     discovery.
    */
-  PerActionFileCache(
-      Map<Artifact, FileArtifactValue> inputArtifactData, boolean missingArtifactsAllowed) {
+  PerActionFileCache(InputArtifactData inputArtifactData, boolean missingArtifactsAllowed) {
     this.inputArtifactData = Preconditions.checkNotNull(inputArtifactData);
     this.missingArtifactsAllowed = missingArtifactsAllowed;
   }
@@ -68,38 +61,12 @@ class PerActionFileCache implements ActionInputFileCache {
 
   @Override
   public boolean contentsAvailableLocally(ByteString digest) {
-    return getInputFromDigest(digest) != null;
+    return inputArtifactData.contains(digest);
   }
 
   @Nullable
   @Override
   public Artifact getInputFromDigest(ByteString digest) {
-    HashMap<ByteString, Artifact> r = reverseMap;  // volatile load
-    if (r == null) {
-      r = buildReverseMap();
-    }
-    return r.get(digest);
-  }
-
-  private synchronized HashMap<ByteString, Artifact> buildReverseMap() {
-    HashMap<ByteString, Artifact> r = reverseMap;  // volatile load
-    if (r != null) {
-      return r;
-    }
-    r = new HashMap<>(inputArtifactData.size());
-    // It would be nice to have a view of the entries which treats them as a map keyed on digest but
-    // does not require constructing another wrapper object for each entry.  Java doesn't come with
-    // any collections which can do this, but cloning RegularImmutableSet and adding the necessary
-    // features wouldn't be too bad.
-    for (Map.Entry<Artifact, FileArtifactValue> e : inputArtifactData.entrySet()) {
-      byte[] bytes = e.getValue().getDigest();
-      if (bytes != null) {
-        ByteString digest = ByteString.copyFrom(BaseEncoding.base16().lowerCase().encode(bytes)
-            .getBytes(StandardCharsets.US_ASCII));
-        r.put(digest, e.getKey());
-      }
-    }
-    reverseMap = r;  // volatile store
-    return r;
+    return inputArtifactData.get(digest);
   }
 }
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 37683f3d8b..db6452ff61 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
@@ -81,6 +81,7 @@ import com.google.devtools.build.lib.util.io.OutErr;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.Symlinks;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.protobuf.ByteString;
@@ -104,6 +105,7 @@ import java.util.concurrent.FutureTask;
 import java.util.concurrent.atomic.AtomicReference;
 import java.util.concurrent.locks.Lock;
 import java.util.function.BooleanSupplier;
+import java.util.function.Supplier;
 import java.util.logging.Logger;
 import javax.annotation.Nullable;
 
@@ -157,14 +159,17 @@ public final class SkyframeActionExecutor {
 
   private final AtomicReference<ActionExecutionStatusReporter> statusReporterRef;
   private OutputService outputService;
+  private final Supplier<ImmutableList<Root>> sourceRootSupplier;
   private final BooleanSupplier usesActionFileSystem;
 
   SkyframeActionExecutor(
       ActionKeyContext actionKeyContext,
       AtomicReference<ActionExecutionStatusReporter> statusReporterRef,
+      Supplier<ImmutableList<Root>> sourceRootSupplier,
       BooleanSupplier usesActionFileSystem) {
     this.actionKeyContext = actionKeyContext;
     this.statusReporterRef = statusReporterRef;
+    this.sourceRootSupplier = sourceRootSupplier;
     this.usesActionFileSystem = usesActionFileSystem;
   }
 
@@ -359,6 +364,14 @@ public final class SkyframeActionExecutor {
     this.clientEnv = clientEnv;
   }
 
+  public Path getExecRoot() {
+    return executorEngine.getExecRoot();
+  }
+
+  public ImmutableList<Root> getSourceRoots() {
+    return sourceRootSupplier.get();
+  }
+
   public boolean usesActionFileSystem() {
     return usesActionFileSystem.getAsBoolean();
   }
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 c7c38478bc..34286bde16 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
@@ -358,7 +358,8 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
         syscalls, cyclesReporter, pkgLocator, numPackagesLoaded, this);
     this.resourceManager = ResourceManager.instance();
     this.skyframeActionExecutor =
-        new SkyframeActionExecutor(actionKeyContext, statusReporterRef, usesActionFileSystem);
+        new SkyframeActionExecutor(
+            actionKeyContext, statusReporterRef, this::getPathEntries, usesActionFileSystem);
     this.fileSystem = fileSystem;
     this.directories = Preconditions.checkNotNull(directories);
     this.actionKeyContext = Preconditions.checkNotNull(actionKeyContext);
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 56ada85c9e..5bf742bb9f 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
@@ -189,6 +189,7 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
         new SkyframeActionExecutor(
             actionKeyContext,
             new AtomicReference<>(statusReporter),
+            /*sourceRootSupplier=*/ () -> ImmutableList.of(),
             /*usesActionFileSystem=*/ () -> false);
 
     Path actionOutputBase = scratch.dir("/usr/local/google/_blaze_jrluser/FAKEMD5/action_out/");