diff --git a/src/java_tools/junitrunner/java/com/google/testing/junit/runner/JUnit4Bazel.java b/src/java_tools/junitrunner/java/com/google/testing/junit/runner/JUnit4Bazel.java
index 5ea00cd..2443583 100644
--- a/src/java_tools/junitrunner/java/com/google/testing/junit/runner/JUnit4Bazel.java
+++ b/src/java_tools/junitrunner/java/com/google/testing/junit/runner/JUnit4Bazel.java
@@ -59,8 +59,8 @@
 import org.junit.runner.notification.RunListener;
 
 /**
- * Utility class to create a JUnit4Runner instance from a {@link Builder}. All required 
- * dependencies are being injected automatically.
+ * Utility class to create a JUnit4Runner instance from a {@link Builder}. All required dependencies
+ * are being injected automatically.
  */
 public final class JUnit4Bazel {
   private Supplier<Class<?>> topLevelSuiteSupplier;
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java b/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java
index 2d2ffd7..e7ef58c 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java
@@ -21,7 +21,9 @@
 import com.google.common.collect.Collections2;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
+import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -144,19 +146,10 @@
    */
   public static TreeFileArtifact treeFileArtifact(
       Artifact.SpecialArtifact parent, PathFragment relativePath) {
-    Preconditions.checkState(parent.isTreeArtifact(),
-        "Given parent %s must be a TreeArtifact", parent);
-    return new TreeFileArtifact(parent, relativePath);
-  }
-
-  public static TreeFileArtifact treeFileArtifact(
-      Artifact.SpecialArtifact parent, PathFragment relativePath, ArtifactOwner artifactOwner) {
-    Preconditions.checkState(parent.isTreeArtifact(),
-        "Given parent %s must be a TreeArtifact", parent);
-    return new TreeFileArtifact(
-        parent,
-        relativePath,
-        artifactOwner);
+    TreeFileArtifact result =
+        treeFileArtifactWithNoGeneratingActionSet(parent, relativePath, parent.getArtifactOwner());
+    result.setGeneratingActionKey(parent.getGeneratingActionKey());
+    return result;
   }
 
   /**
@@ -168,6 +161,13 @@
     return treeFileArtifact(parent, PathFragment.create(relativePath));
   }
 
+  public static TreeFileArtifact treeFileArtifactWithNoGeneratingActionSet(
+      SpecialArtifact parent, PathFragment relativePath, ActionLookupKey artifactOwner) {
+    Preconditions.checkState(
+        parent.isTreeArtifact(), "Given parent %s must be a TreeArtifact", parent);
+    return new TreeFileArtifact(parent, relativePath, artifactOwner);
+  }
+
   /** Returns an Iterable of TreeFileArtifacts with the given parent and parent relative paths. */
   public static Iterable<TreeFileArtifact> asTreeFileArtifacts(
       final Artifact.SpecialArtifact parent, Iterable<? extends PathFragment> parentRelativePaths) {
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
index b71f22d..fc33a23 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
@@ -13,12 +13,11 @@
 // limitations under the License.
 package com.google.devtools.build.lib.actions;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
-import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.skyframe.ShareabilityOfValue;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -27,7 +26,6 @@
 /** Data that uniquely identifies an action. */
 @AutoCodec
 public class ActionLookupData implements SkyKey {
-  private static final Interner<ActionLookupData> INTERNER = BlazeInterners.newWeakInterner();
   // Test actions are not shareable.
   // Action execution can be nondeterministic, so is semi-hermetic.
   public static final SkyFunctionName NAME = SkyFunctionName.createSemiHermetic("ACTION_EXECUTION");
@@ -40,9 +38,14 @@
     this.actionIndex = actionIndex;
   }
 
+  /**
+   * Creates a key for the result of action execution. Does <i>not</i> intern its results, so should
+   * only be called once per {@code (actionLookupKey, actionIndex)} pair.
+   */
+  @VisibleForTesting
   @AutoCodec.Instantiator
   public static ActionLookupData create(ActionLookupKey actionLookupKey, int actionIndex) {
-    return INTERNER.intern(new ActionLookupData(actionLookupKey, actionIndex));
+    return new ActionLookupData(actionLookupKey, actionIndex);
   }
 
   public ActionLookupKey getActionLookupKey() {
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
index 6611deb..278d9e8 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
@@ -15,15 +15,11 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.math.BigInteger;
-import java.util.List;
-import java.util.Map;
 import javax.annotation.Nullable;
 
 /**
@@ -39,38 +35,6 @@
   public abstract ImmutableList<ActionAnalysisMetadata> getActions();
 
   /**
-   * Returns a map where keys are artifacts generated by this {@link SkyValue}, and values are
-   * the index of the action which generates this artifact.
-   */
-  protected abstract ImmutableMap<Artifact, Integer> getGeneratingActionIndex();
-
-  /**
-   * Returns the index of the action that generates {@code artifact} in this value, or null if this
-   * value does not have a generating action for this artifact. The index together with the key for
-   * this {@link ActionLookupValue} uniquely identifies the action.
-   *
-   * <p>Unlike {@link #getAction}, this may be called after action execution.
-   */
-  @Nullable
-  public Integer getGeneratingActionIndex(Artifact artifact) {
-    return getGeneratingActionIndex().get(artifact);
-  }
-
-  /**
-   * Returns the action that generates {@code artifact}, if known to this value, or null. This
-   * method should be avoided. Call it only when the action is really needed, and it is known to be
-   * present.
-   */
-  @Nullable
-  public ActionAnalysisMetadata getGeneratingActionDangerousReadJavadoc(Artifact artifact) {
-    Integer actionIndex = getGeneratingActionIndex(artifact);
-    if (actionIndex == null) {
-      return null;
-    }
-    return getActions().get(actionIndex);
-  }
-
-  /**
    * Returns the {@link Action} with index {@code index} in this value. Never null. Should only be
    * called during action execution by {@code ArtifactFunction} and {@code ActionExecutionFunction}
    * -- after an action has executed, calling this with its index may crash.
@@ -98,17 +62,6 @@
     return getActions().get(index) instanceof ActionTemplate;
   }
 
-  /** To be used only when checking consistency of the action graph -- not by other values. */
-  public Map<Artifact, ActionAnalysisMetadata> getMapForConsistencyCheck() {
-    return getMapForConsistencyCheck(getGeneratingActionIndex(), getActions());
-  }
-
-  public static Map<Artifact, ActionAnalysisMetadata> getMapForConsistencyCheck(
-      Map<Artifact, Integer> generatingActionIndex,
-      final List<? extends ActionAnalysisMetadata> actions) {
-    return Maps.transformValues(generatingActionIndex, actions::get);
-  }
-
   /**
    * Returns the number of {@link Action} objects present in this value.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionTemplate.java b/src/main/java/com/google/devtools/build/lib/actions/ActionTemplate.java
index 335b5d4..df4e219 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionTemplate.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionTemplate.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.actions;
 
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.analysis.platform.PlatformInfo;
 import javax.annotation.Nullable;
@@ -78,7 +79,7 @@
    *     TreeFileArtifact}
    */
   Iterable<T> generateActionForInputArtifacts(
-      Iterable<TreeFileArtifact> inputTreeFileArtifacts, ArtifactOwner artifactOwner)
+      Iterable<TreeFileArtifact> inputTreeFileArtifacts, ActionLookupKey artifactOwner)
       throws ActionTemplateExpansionException;
 
   /** Returns the input TreeArtifact. */
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Actions.java b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
index 4e9fb5e..1726fc9 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Actions.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
@@ -19,9 +19,11 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.escape.Escaper;
 import com.google.common.escape.Escapers;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.vfs.OsPathPolicy;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.Collection;
@@ -31,8 +33,6 @@
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.SortedMap;
-import java.util.TreeMap;
-import java.util.function.Function;
 import javax.annotation.Nullable;
 
 /**
@@ -112,80 +112,154 @@
   }
 
   /**
-   * Finds action conflicts. An action conflict happens if two actions generate the same output
-   * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
+   * Assigns generating action keys to artifacts, and finds action conflicts. An action conflict
+   * happens if two actions generate the same output artifact. Shared actions are not allowed. See
+   * {@link #canBeShared} for details. Should only be called for special action lookup values: does
+   * not handle normal configured targets. In particular, {@link
+   * GeneratingActions#getArtifactsByOutputLabel} will be empty.
    *
-   * @param actions a list of actions to check for action conflicts
-   * @return a structure giving the mapping between artifacts and generating actions, with a level
-   *     of indirection.
+   * @param actions a list of actions to check for action conflict.
+   * @return a structure giving the actions, with a level of indirection.
    * @throws ActionConflictException iff there are two actions generate the same output
    */
-  public static GeneratingActions findAndThrowActionConflict(
-      ActionKeyContext actionKeyContext, ImmutableList<ActionAnalysisMetadata> actions)
+  public static GeneratingActions assignOwnersAndFindAndThrowActionConflict(
+      ActionKeyContext actionKeyContext,
+      ImmutableList<ActionAnalysisMetadata> actions,
+      ActionLookupValue.ActionLookupKey actionLookupKey)
       throws ActionConflictException {
-    return Actions.maybeFilterSharedActionsAndThrowIfConflict(
-        actionKeyContext, actions, /*allowSharedAction=*/ false);
+    return Actions.assignOwnersAndMaybeFilterSharedActionsAndThrowIfConflict(
+        actionKeyContext,
+        actions,
+        actionLookupKey,
+        /*allowSharedAction=*/ false,
+        /*outputFiles=*/ null);
   }
 
   /**
-   * Finds action conflicts. An action conflict happens if two actions generate the same output
-   * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
+   * Assigns generating action keys to artifacts and finds action conflicts. An action conflict
+   * happens if two actions generate the same output artifact. Shared actions are tolerated. See
+   * {@link #canBeShared} for details. Should be called by a configured target/aspect on the actions
+   * it owns. Should not be used for "global" checks of multiple configured targets: use {@link
+   * #findArtifactPrefixConflicts} for that.
    *
-   * @param actions a list of actions to check for action conflicts
-   * @return a structure giving the mapping between artifacts and generating actions, with a level
-   *     of indirection.
+   * @param actions a list of actions to check for action conflicts, all generated by the same
+   *     configured target/aspect.
+   * @return a structure giving the actions, with a level of indirection.
    * @throws ActionConflictException iff there are two unshareable actions generating the same
    *     output
    */
-  public static GeneratingActions filterSharedActionsAndThrowActionConflict(
-      ActionKeyContext actionKeyContext, ImmutableList<ActionAnalysisMetadata> actions)
-      throws ActionConflictException {
-    return Actions.maybeFilterSharedActionsAndThrowIfConflict(
-        actionKeyContext, actions, /*allowSharedAction=*/ true);
-  }
-
-  private static GeneratingActions maybeFilterSharedActionsAndThrowIfConflict(
+  public static GeneratingActions assignOwnersAndFilterSharedActionsAndThrowActionConflict(
       ActionKeyContext actionKeyContext,
       ImmutableList<ActionAnalysisMetadata> actions,
-      boolean allowSharedAction)
+      ActionLookupKey actionLookupKey,
+      @Nullable Collection<OutputFile> outputFiles)
       throws ActionConflictException {
-    Map<Artifact, Integer> generatingActions = new HashMap<>();
+    return Actions.assignOwnersAndMaybeFilterSharedActionsAndThrowIfConflict(
+        actionKeyContext, actions, actionLookupKey, /*allowSharedAction=*/ true, outputFiles);
+  }
+
+  private static void verifyGeneratingActionKeys(
+      Artifact.DerivedArtifact output,
+      ActionLookupData otherKey,
+      boolean allowSharedAction,
+      ActionKeyContext actionKeyContext,
+      ImmutableList<ActionAnalysisMetadata> actions)
+      throws ActionConflictException {
+    ActionLookupData firstKey = output.getGeneratingActionKey();
+    Preconditions.checkState(
+        firstKey.getActionLookupKey().equals(otherKey.getActionLookupKey()),
+        "Mismatched lookup keys? %s %s %s",
+        output,
+        firstKey,
+        otherKey);
+    int actionIndex = firstKey.getActionIndex();
+    int otherIndex = otherKey.getActionIndex();
+    if (actionIndex != otherIndex
+        && (!allowSharedAction
+            || !Actions.canBeShared(
+                actionKeyContext, actions.get(actionIndex), actions.get(otherIndex)))) {
+      throw new ActionConflictException(
+          actionKeyContext, output, actions.get(actionIndex), actions.get(otherIndex));
+    }
+  }
+
+  /**
+   * Checks {@code actions} for conflicts and sets each artifact's generating action key.
+   *
+   * <p>Conflicts can happen in one of two ways: the same artifact can be the output of multiple
+   * unshareable actions (or shareable actions if {@code allowSharedAction} is false), or two
+   * artifacts with the same execPath can be the outputs of different unshareable actions.
+   *
+   * <p>If {@code outputFiles} is non-null, also builds a map of output-file labels to artifacts,
+   * for use by output file configured targets when they are retrieving their artifacts from this
+   * associated rule configured target.
+   */
+  private static GeneratingActions assignOwnersAndMaybeFilterSharedActionsAndThrowIfConflict(
+      ActionKeyContext actionKeyContext,
+      ImmutableList<ActionAnalysisMetadata> actions,
+      ActionLookupKey actionLookupKey,
+      boolean allowSharedAction,
+      @Nullable Collection<OutputFile> outputFiles)
+      throws ActionConflictException {
+    Map<PathFragment, Artifact.DerivedArtifact> seenArtifacts = new HashMap<>();
+    @Nullable ImmutableMap<String, Label> outputFileNames = null;
+    if (outputFiles != null && !outputFiles.isEmpty()) {
+      ImmutableMap.Builder<String, Label> outputFileNamesBuilder =
+          ImmutableMap.builderWithExpectedSize(outputFiles.size());
+      outputFiles.forEach(o -> outputFileNamesBuilder.put(o.getLabel().getName(), o.getLabel()));
+      outputFileNames = outputFileNamesBuilder.build();
+    }
+    @Nullable
+    ImmutableMap.Builder<Label, Artifact> artifactsByOutputLabel =
+        outputFileNames != null ? ImmutableMap.builderWithExpectedSize(outputFiles.size()) : null;
+    @Nullable Label label = actionLookupKey.getLabel();
+    @Nullable
+    PathFragment packageDirectory =
+        outputFileNames != null
+            ? Preconditions.checkNotNull(label, actionLookupKey)
+                .getPackageIdentifier()
+                .getSourceRoot()
+            : null;
+    // Loop over the actions, looking at all outputs for conflicts.
     int actionIndex = 0;
     for (ActionAnalysisMetadata action : actions) {
+      ActionLookupData generatingActionKey = ActionLookupData.create(actionLookupKey, actionIndex);
       for (Artifact artifact : action.getOutputs()) {
-        Integer previousIndex = generatingActions.put(artifact, actionIndex);
-        if (previousIndex != null && previousIndex != actionIndex) {
-          if (!allowSharedAction
-              || !Actions.canBeShared(actionKeyContext, actions.get(previousIndex), action)) {
-            throw new ActionConflictException(
-                actionKeyContext, artifact, actions.get(previousIndex), action);
+        Artifact.DerivedArtifact output = (Artifact.DerivedArtifact) artifact;
+        // Has an artifact with this execPath been seen before?
+        Artifact.DerivedArtifact equalOutput =
+            seenArtifacts.putIfAbsent(output.getExecPath(), output);
+        if (equalOutput != null) {
+          // Yes: assert that its generating action and this artifact's are compatible.
+          verifyGeneratingActionKeys(
+              equalOutput, generatingActionKey, allowSharedAction, actionKeyContext, actions);
+        } else {
+          // No: populate the output label map with this artifact if applicable: if this
+          // artifact corresponds to a target that is an OutputFile with associated rule this label.
+          PathFragment rootRelativePath = output.getRootRelativePath();
+          if (packageDirectory != null && rootRelativePath.startsWith(packageDirectory)) {
+            PathFragment packageRelativePath = rootRelativePath.relativeTo(packageDirectory);
+            Label outputLabel = outputFileNames.get(packageRelativePath.getPathString());
+            if (outputLabel != null) {
+              artifactsByOutputLabel.put(outputLabel, artifact);
+            }
           }
         }
+        // Was this output already seen, so it has a generating action key set?
+        if (!output.hasGeneratingActionKey()) {
+          // Common case: artifact hasn't been seen before.
+          output.setGeneratingActionKey(generatingActionKey);
+        } else {
+          // Key is already set: verify that the generating action and this action are compatible.
+          verifyGeneratingActionKeys(
+              output, generatingActionKey, allowSharedAction, actionKeyContext, actions);
+        }
       }
       actionIndex++;
     }
-    return new GeneratingActions(actions, ImmutableMap.copyOf(generatingActions));
-  }
-
-  /**
-   * Finds Artifact prefix conflicts between generated artifacts. An artifact prefix conflict
-   * happens if one action generates an artifact whose path is a prefix of another artifact's path.
-   * Those two artifacts cannot exist simultaneously in the output tree.
-   *
-   * @param generatingActions a map between generated artifacts and their associated generating
-   *     actions.
-   * @return a map between actions that generated the conflicting artifacts and their associated
-   *     {@link ArtifactPrefixConflictException}.
-   */
-  public static Map<ActionAnalysisMetadata, ArtifactPrefixConflictException>
-      findArtifactPrefixConflicts(Map<Artifact, ActionAnalysisMetadata> generatingActions) {
-    TreeMap<PathFragment, Artifact> artifactPathMap = new TreeMap<>(comparatorForPrefixConflicts());
-    for (Artifact artifact : generatingActions.keySet()) {
-      artifactPathMap.put(artifact.getExecPath(), artifact);
-    }
-
-    return findArtifactPrefixConflicts(
-        new MapBasedImmutableActionGraph(generatingActions), artifactPathMap);
+    return new GeneratingActions(
+        actions,
+        artifactsByOutputLabel != null ? artifactsByOutputLabel.build() : ImmutableMap.of());
   }
 
   /**
@@ -321,52 +395,41 @@
     return PATH_ESCAPER.escape(label.getPackageName() + ":" + label.getName());
   }
 
-  private static class MapBasedImmutableActionGraph implements ActionGraph {
-    private final Map<Artifact, ActionAnalysisMetadata> generatingActions;
-
-    MapBasedImmutableActionGraph(
-        Map<Artifact, ActionAnalysisMetadata> generatingActions) {
-      this.generatingActions = ImmutableMap.copyOf(generatingActions);
-    }
-
-    @Nullable
-    @Override
-    public ActionAnalysisMetadata getGeneratingAction(Artifact artifact) {
-      return generatingActions.get(artifact);
-    }
-  }
-
-  /** Container class for actions and the artifacts they generate. */
+  /**
+   * Container class for actions, ensuring they have already been checked for conflicts and their
+   * generated artifacts have had owners assigned.
+   */
   public static class GeneratingActions {
     public static final GeneratingActions EMPTY =
         new GeneratingActions(ImmutableList.of(), ImmutableMap.of());
 
     private final ImmutableList<ActionAnalysisMetadata> actions;
-    private final ImmutableMap<Artifact, Integer> generatingActionIndex;
+    private final ImmutableMap<Label, Artifact> artifactsByOutputLabel;
 
     private GeneratingActions(
         ImmutableList<ActionAnalysisMetadata> actions,
-        ImmutableMap<Artifact, Integer> generatingActionIndex) {
+        ImmutableMap<Label, Artifact> artifactsByOutputLabel) {
       this.actions = actions;
-      this.generatingActionIndex = generatingActionIndex;
+      this.artifactsByOutputLabel = artifactsByOutputLabel;
     }
 
-    public static GeneratingActions fromSingleAction(ActionAnalysisMetadata action) {
-      return new GeneratingActions(
-          ImmutableList.of(action),
-          ImmutableMap.copyOf(
-              action
-                  .getOutputs()
-                  .stream()
-                  .collect(ImmutableMap.toImmutableMap(Function.identity(), (a) -> 0))));
-    }
-
-    public ImmutableMap<Artifact, Integer> getGeneratingActionIndex() {
-      return generatingActionIndex;
+    /** Used only for the workspace status action. Does not handle duplicate artifacts. */
+    public static GeneratingActions fromSingleAction(
+        ActionAnalysisMetadata action, ActionLookupValue.ActionLookupKey actionLookupKey) {
+      Preconditions.checkState(actionLookupKey.getLabel() == null, actionLookupKey);
+      ActionLookupData generatingActionKey = ActionLookupData.create(actionLookupKey, 0);
+      for (Artifact output : action.getOutputs()) {
+        ((Artifact.DerivedArtifact) output).setGeneratingActionKey(generatingActionKey);
+      }
+      return new GeneratingActions(ImmutableList.of(action), ImmutableMap.of());
     }
 
     public ImmutableList<ActionAnalysisMetadata> getActions() {
       return actions;
     }
+
+    public ImmutableMap<Label, Artifact> getArtifactsByOutputLabel() {
+      return artifactsByOutputLabel;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index 673143b..66abc0b 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -27,6 +27,7 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Streams;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.ArtifactResolver.ArtifactResolverSupplier;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
@@ -38,7 +39,6 @@
 import com.google.devtools.build.lib.skyframe.serialization.SerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.util.FileType;
@@ -103,7 +103,6 @@
  * </ul>
  */
 @Immutable
-@AutoCodec
 public abstract class Artifact
     implements FileType.HasFileType,
         ActionInput,
@@ -223,45 +222,11 @@
   /** A Predicate that evaluates to true if the Artifact is not a middleman artifact. */
   public static final Predicate<Artifact> MIDDLEMAN_FILTER = input -> !input.isMiddlemanArtifact();
 
-  private static final Interner<DerivedArtifact> ARTIFACT_INTERNER =
-      BlazeInterners.newWeakInterner();
-
   private final int hashCode;
   private final ArtifactRoot root;
   private final PathFragment execPath;
-  private final ArtifactOwner owner;
 
-  /**
-   * The {@code rootRelativePath is a few characters shorter than the {@code execPath} for derived
-   * artifacts, so we save a few bytes by serializing it rather than the {@code execPath},
-   * especially when the {@code root} is common to many artifacts and therefore memoized.
-   */
-  @AutoCodec.VisibleForSerialization
-  @AutoCodec.Instantiator
-  static Artifact createForSerialization(
-      ArtifactRoot root, ArtifactOwner owner, PathFragment rootRelativePath) {
-    if (rootRelativePath == null || rootRelativePath.isAbsolute() != root.getRoot().isAbsolute()) {
-      throw new IllegalArgumentException(
-          rootRelativePath
-              + ": illegal rootRelativePath for "
-              + rootRelativePath
-              + " (root: "
-              + root
-              + ")");
-    }
-    PathFragment rootExecPath = root.getExecPath();
-    if (rootExecPath.isEmpty()) {
-      return new Artifact.SourceArtifact(root, rootRelativePath, owner);
-    } else {
-      return ARTIFACT_INTERNER.intern(
-          new Artifact.DerivedArtifact(root, rootExecPath.getRelative(rootRelativePath), owner));
-    }
-  }
-
-  private Artifact(
-      ArtifactRoot root,
-      PathFragment execPath,
-      ArtifactOwner owner) {
+  private Artifact(ArtifactRoot root, PathFragment execPath) {
     Preconditions.checkNotNull(root);
     if (execPath.isEmpty()) {
       throw new IllegalArgumentException(
@@ -273,25 +238,129 @@
     this.hashCode = execPath.hashCode();
     this.root = root;
     this.execPath = execPath;
-    this.owner = Preconditions.checkNotNull(owner);
   }
 
   /** An artifact corresponding to a file in the output tree, generated by an {@link Action}. */
+  @AutoCodec
   public static class DerivedArtifact extends Artifact {
+    /** Only used for deserializing artifacts. */
+    private static final Interner<DerivedArtifact> INTERNER = BlazeInterners.newWeakInterner();
+
     private final PathFragment rootRelativePath;
+    /**
+     * An {@link ActionLookupKey} until {@link #setGeneratingActionKey} is set, at which point it is
+     * an {@link ActionLookupData}, whose {@link ActionLookupData#getActionLookupKey} will be the
+     * same as the original value of owner.
+     *
+     * <p>We overload this field in order to save memory.
+     */
+    private Object owner;
 
     @VisibleForTesting
-    public DerivedArtifact(ArtifactRoot root, PathFragment execPath, ArtifactOwner owner) {
-      super(root, execPath, owner);
+    public DerivedArtifact(ArtifactRoot root, PathFragment execPath, ActionLookupKey owner) {
+      super(root, execPath);
       Preconditions.checkState(
           !root.getExecPath().isEmpty(), "Derived root has no exec path: %s, %s", root, execPath);
       this.rootRelativePath = execPath.relativeTo(root.getExecPath());
+      this.owner = owner;
+    }
+
+    /**
+     * Called when a configured target's actions are being collected. {@code generatingActionKey}
+     * must have the same owner as this artifact's current {@link #getArtifactOwner}.
+     */
+    @VisibleForTesting
+    public void setGeneratingActionKey(ActionLookupData generatingActionKey) {
+      Preconditions.checkState(
+          this.owner instanceof ArtifactOwner,
+          "Already set generating action key: %s (%s %s)",
+          this,
+          this.owner,
+          generatingActionKey);
+      Preconditions.checkState(
+          Preconditions.checkNotNull(generatingActionKey, this).getActionLookupKey().equals(owner),
+          "Owner of generating action key not same as artifact's owner: %s (%s %s)",
+          this,
+          this.owner,
+          generatingActionKey);
+      this.owner = Preconditions.checkNotNull(generatingActionKey, this);
+    }
+
+    @VisibleForTesting
+    public boolean hasGeneratingActionKey() {
+      return this.owner instanceof ActionLookupData;
+    }
+
+    /** Can only be called once {@link #setGeneratingActionKey} is called. */
+    public ActionLookupData getGeneratingActionKey() {
+      Preconditions.checkState(owner instanceof ActionLookupData, "Bad owner: %s %s", this, owner);
+      return (ActionLookupData) owner;
+    }
+
+    @Override
+    public ActionLookupValue.ActionLookupKey getArtifactOwner() {
+      return owner instanceof ActionLookupData
+          ? getGeneratingActionKey().getActionLookupKey()
+          : (ActionLookupKey) owner;
+    }
+
+    @Override
+    public Label getOwnerLabel() {
+      return getArtifactOwner().getLabel();
     }
 
     @Override
     public PathFragment getRootRelativePath() {
       return rootRelativePath;
     }
+
+    @Override
+    boolean ownersEqual(Artifact other) {
+      DerivedArtifact that = (DerivedArtifact) other;
+      if (!(this.owner instanceof ActionLookupData) || !(that.owner instanceof ActionLookupData)) {
+        // Happens only intra-analysis of a configured target. Tolerate.
+        Preconditions.checkState(
+            this.getArtifactOwner().equals(that.getArtifactOwner()),
+            "Mismatched owners: %s %s %s %s",
+            this,
+            that,
+            this.getArtifactOwner(),
+            that.getArtifactOwner());
+        return true;
+      }
+      return this.owner.equals(that.owner);
+    }
+
+    /**
+     * The {@code rootRelativePath is a few characters shorter than the {@code execPath}, so we save
+     * a few bytes by serializing it rather than the {@code execPath}, especially when the {@code
+     * root} is common to many artifacts and therefore memoized.
+     */
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static DerivedArtifact createForSerialization(
+        ArtifactRoot root, PathFragment rootRelativePath, ActionLookupData generatingActionKey) {
+      if (rootRelativePath == null
+          || rootRelativePath.isAbsolute() != root.getRoot().isAbsolute()) {
+        throw new IllegalArgumentException(
+            rootRelativePath
+                + ": illegal rootRelativePath for "
+                + root
+                + " (generatingActionKey: "
+                + generatingActionKey
+                + ")");
+      }
+      Preconditions.checkState(
+          !root.isSourceRoot(), "Root not derived: %s %s", root, rootRelativePath);
+      PathFragment rootExecPath = root.getExecPath();
+      DerivedArtifact artifact =
+          new DerivedArtifact(
+              root,
+              rootExecPath.getRelative(rootRelativePath),
+              generatingActionKey.getActionLookupKey());
+      artifact.setGeneratingActionKey(generatingActionKey);
+      return INTERNER.intern(artifact);
+    }
   }
 
   public final Path getPath() {
@@ -356,10 +425,9 @@
     return getExecPathString();
   }
 
-  /**
-   * Returns the artifact owner. May be null.
-   */
-  @Nullable public final Label getOwner() {
+  /** Returns the artifact's owning label. May be null. */
+  @Nullable
+  public final Label getOwner() {
     return getOwnerLabel();
   }
 
@@ -371,14 +439,7 @@
    * derived artifacts, such as target completion middleman artifacts, build info artifacts, and the
    * like.
    */
-  public final ArtifactOwner getArtifactOwner() {
-    return owner;
-  }
-
-  @Override
-  public Label getOwnerLabel() {
-    return owner.getLabel();
-  }
+  public abstract ArtifactOwner getArtifactOwner();
 
   /**
    * Returns the root beneath which this Artifact resides, if any. This may be one of the
@@ -471,18 +532,21 @@
    * TODO(shahan): move {@link Artifact#getPath} to this subclass.
    * */
   public static final class SourceArtifact extends Artifact {
+    private final ArtifactOwner owner;
+
     @VisibleForTesting
     public SourceArtifact(ArtifactRoot root, PathFragment execPath, ArtifactOwner owner) {
-      super(root, execPath, owner);
+      super(root, execPath);
+      this.owner = owner;
     }
 
     /**
-     * SourceArtifacts are compared without their owners, since owners do not affect behavior,
-     * unlike with derived artifacts, whose owners determine their generating actions.
+     * Source artifacts do not consider their owners in equality checks, since their owners are
+     * purely cosmetic.
      */
     @Override
-    public boolean equals(Object other) {
-      return other instanceof SourceArtifact && equalsWithoutOwner((SourceArtifact) other);
+    boolean ownersEqual(Artifact other) {
+      return true;
     }
 
     @Override
@@ -490,8 +554,18 @@
       return getExecPath();
     }
 
+    @Override
+    public ArtifactOwner getArtifactOwner() {
+      return owner;
+    }
+
+    @Override
+    public Label getOwnerLabel() {
+      return owner.getLabel();
+    }
+
     boolean differentOwnerOrRoot(ArtifactOwner owner, ArtifactRoot root) {
-      return !this.getArtifactOwner().equals(owner) || !this.getRoot().equals(root);
+      return !this.owner.equals(owner) || !this.getRoot().equals(root);
     }
   }
 
@@ -519,13 +593,26 @@
   public static final class SpecialArtifact extends DerivedArtifact {
     private final SpecialArtifactType type;
 
-    @VisibleForSerialization
+    @VisibleForTesting
     public SpecialArtifact(
-        ArtifactRoot root, PathFragment execPath, ArtifactOwner owner, SpecialArtifactType type) {
+        ArtifactRoot root, PathFragment execPath, ActionLookupKey owner, SpecialArtifactType type) {
       super(root, execPath, owner);
       this.type = type;
     }
 
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static SpecialArtifact create(
+        ArtifactRoot root,
+        PathFragment execPath,
+        SpecialArtifactType type,
+        ActionLookupData generatingActionKey) {
+      SpecialArtifact result =
+          new SpecialArtifact(root, execPath, generatingActionKey.getActionLookupKey(), type);
+      result.setGeneratingActionKey(generatingActionKey);
+      return result;
+    }
+
     @Override
     public final boolean isFileset() {
       return type == SpecialArtifactType.FILESET;
@@ -596,9 +683,10 @@
      * Constructs a TreeFileArtifact with the given parent-relative path under the given parent
      * TreeArtifact, owned by the given {@code artifactOwner}.
      */
-    @AutoCodec.Instantiator
     TreeFileArtifact(
-        SpecialArtifact parentTreeArtifact, PathFragment parentRelativePath, ArtifactOwner owner) {
+        SpecialArtifact parentTreeArtifact,
+        PathFragment parentRelativePath,
+        ActionLookupKey owner) {
       super(
           parentTreeArtifact.getRoot(),
           parentTreeArtifact.getExecPath().getRelative(parentRelativePath),
@@ -620,6 +708,19 @@
       this.parentRelativePath = parentRelativePath;
     }
 
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static TreeFileArtifact createForSerialization(
+        SpecialArtifact parentTreeArtifact,
+        PathFragment parentRelativePath,
+        ActionLookupData generatingActionKey) {
+      TreeFileArtifact result =
+          new TreeFileArtifact(
+              parentTreeArtifact, parentRelativePath, generatingActionKey.getActionLookupKey());
+      result.setGeneratingActionKey(generatingActionKey);
+      return result;
+    }
+
     @Override
     public SpecialArtifact getParent() {
       return parentTreeArtifact;
@@ -683,7 +784,7 @@
 
   @SuppressWarnings("EqualsGetClass") // Distinct classes of Artifact are never equal.
   @Override
-  public boolean equals(Object other) {
+  public final boolean equals(Object other) {
     if (this == other) {
       return true;
     }
@@ -694,13 +795,15 @@
       return false;
     }
     Artifact that = (Artifact) other;
-    return equalsWithoutOwner(that) && owner.equals(that.owner);
+    return equalsWithoutOwner(that) && ownersEqual(that);
   }
 
-  public boolean equalsWithoutOwner(Artifact other) {
+  final boolean equalsWithoutOwner(Artifact other) {
     return hashCode == other.hashCode && execPath.equals(other.execPath) && root.equals(other.root);
   }
 
+  abstract boolean ownersEqual(Artifact other);
+
   @Override
   public final int hashCode() {
     // This is just execPath.hashCode() (along with the class). We cache a copy in the Artifact
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
index 3cc5e3b..c565492 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
@@ -17,6 +17,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.util.concurrent.Striped;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
@@ -325,9 +326,9 @@
     if (type == null) {
       return root.isSourceRoot()
           ? new Artifact.SourceArtifact(root, execPath, owner)
-          : new Artifact.DerivedArtifact(root, execPath, owner);
+          : new Artifact.DerivedArtifact(root, execPath, (ActionLookupKey) owner);
     } else {
-      return new Artifact.SpecialArtifact(root, execPath, owner, type);
+      return new Artifact.SpecialArtifact(root, execPath, (ActionLookupKey) owner, type);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/actions/BasicActionLookupValue.java b/src/main/java/com/google/devtools/build/lib/actions/BasicActionLookupValue.java
index 3b4a153..2e3eef9 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/BasicActionLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/BasicActionLookupValue.java
@@ -17,8 +17,6 @@
 import com.google.common.base.MoreObjects;
 import com.google.common.base.MoreObjects.ToStringHelper;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
 import java.math.BigInteger;
 import javax.annotation.Nullable;
 
@@ -28,22 +26,18 @@
  */
 public class BasicActionLookupValue extends ActionLookupValue {
   protected final ImmutableList<ActionAnalysisMetadata> actions;
-  @VisibleForSerialization protected final ImmutableMap<Artifact, Integer> generatingActionIndex;
 
   protected BasicActionLookupValue(
       ImmutableList<ActionAnalysisMetadata> actions,
-      ImmutableMap<Artifact, Integer> generatingActionIndex,
       @Nullable BigInteger nonceVersion) {
     super(nonceVersion);
     this.actions = actions;
-    this.generatingActionIndex = generatingActionIndex;
   }
 
   @VisibleForTesting
   public BasicActionLookupValue(
       Actions.GeneratingActions generatingActions, @Nullable BigInteger nonceVersion) {
-    this(
-        generatingActions.getActions(), generatingActions.getGeneratingActionIndex(), nonceVersion);
+    this(generatingActions.getActions(), nonceVersion);
   }
 
   @Override
@@ -51,14 +45,7 @@
     return actions;
   }
 
-  @Override
-  protected ImmutableMap<Artifact, Integer> getGeneratingActionIndex() {
-    return generatingActionIndex;
-  }
-
   protected ToStringHelper getStringHelper() {
-    return MoreObjects.toStringHelper(this)
-        .add("actions", actions)
-        .add("generatingActionIndex", generatingActionIndex);
+    return MoreObjects.toStringHelper(this).add("actions", actions);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 9e82277..96a7745 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -29,10 +29,11 @@
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionGraph;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.PackageRoots;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection;
@@ -77,7 +78,6 @@
 import com.google.devtools.build.lib.syntax.SkylarkImport.SkylarkImportSyntaxException;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.RegexFilter;
-import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.WalkableGraph;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -489,10 +489,11 @@
               allTargetsToTest,
               baselineCoverageArtifacts,
               getArtifactFactory(),
+              skyframeExecutor.getActionKeyContext(),
               CoverageReportValue.COVERAGE_REPORT_KEY,
               loadingResult.getWorkspaceName());
       if (actionsWrapper != null) {
-        ImmutableList<ActionAnalysisMetadata> actions = actionsWrapper.getActions();
+        Actions.GeneratingActions actions = actionsWrapper.getActions();
         skyframeExecutor.injectCoverageReportData(actions);
         actionsWrapper.getCoverageOutputs().forEach(artifactsToOwnerLabelsBuilder::addArtifact);
       }
@@ -516,19 +517,25 @@
           @Nullable
           @Override
           public ActionAnalysisMetadata getGeneratingAction(Artifact artifact) {
-            ArtifactOwner artifactOwner = artifact.getArtifactOwner();
-            if (artifactOwner instanceof ActionLookupValue.ActionLookupKey) {
-              SkyKey key = (ActionLookupValue.ActionLookupKey) artifactOwner;
-              ActionLookupValue val;
-              try {
-                val = (ActionLookupValue) graph.getValue(key);
-              } catch (InterruptedException e) {
-                throw new IllegalStateException(
-                    "Interruption not expected from this graph: " + key, e);
-              }
-              return val == null ? null : val.getGeneratingActionDangerousReadJavadoc(artifact);
+            if (artifact.isSourceArtifact()) {
+              return null;
             }
-            return null;
+            ActionLookupData generatingActionKey =
+                ((Artifact.DerivedArtifact) artifact).getGeneratingActionKey();
+            ActionLookupValue val;
+            try {
+              val = (ActionLookupValue) graph.getValue(generatingActionKey.getActionLookupKey());
+            } catch (InterruptedException e) {
+              throw new IllegalStateException(
+                  "Interruption not expected from this graph: " + generatingActionKey, e);
+            }
+            if (val == null) {
+              return null;
+            }
+            int actionIndex = generatingActionKey.getActionIndex();
+            return val.isActionTemplate(actionIndex)
+                ? val.getActionTemplate(actionIndex)
+                : val.getAction(actionIndex);
           }
         };
     return new AnalysisResult(
@@ -666,8 +673,8 @@
     ImmutableList.Builder<Artifact> artifacts = ImmutableList.builder();
     // Add to 'artifacts' all extra-actions which were registered by aspects which 'topLevel'
     // might have injected.
-    for (Artifact artifact : provider.getTransitiveExtraActionArtifacts()) {
-      ArtifactOwner owner = artifact.getArtifactOwner();
+    for (Artifact.DerivedArtifact artifact : provider.getTransitiveExtraActionArtifacts()) {
+      ActionLookupValue.ActionLookupKey owner = artifact.getArtifactOwner();
       if (owner instanceof AspectKey) {
         if (aspectClasses.contains(((AspectKey) owner).getAspectClass())) {
           artifacts.add(artifact);
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java b/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
index d66dee7..b31208d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
@@ -37,6 +37,7 @@
 import com.google.devtools.build.lib.skyframe.PrecomputedValue;
 import com.google.devtools.build.lib.skyframe.WorkspaceStatusValue;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics;
+import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
 import java.io.PrintWriter;
@@ -76,7 +77,15 @@
   private MiddlemanFactory middlemanFactory;
   private ExtendedEventHandler errorEventListener;
   private SkyFunction.Environment skyframeEnv;
-  private Map<Artifact, String> artifacts;
+  /**
+   * Map of artifacts to either themselves or to {@code Pair<Artifact, String>} if
+   * --experimental_extended_sanity_checks is enabled. In the latter case, the string will contain
+   * the stack trace of where the artifact was created. In the former case, we'll construct a
+   * generic message in case of error.
+   *
+   * <p>The artifact is stored so that we can deduplicate artifacts created multiple times.
+   */
+  private Map<Artifact, Object> artifacts;
 
   /**
    * The list of actions registered by the configured target this analysis environment is
@@ -198,12 +207,21 @@
     // The order of the artifacts.entrySet iteration is unspecified - we use a TreeMap here to
     // guarantee that the return value of this method is deterministic.
     Map<Artifact, String> orphanArtifacts = new TreeMap<>(Artifact.EXEC_PATH_COMPARATOR);
-    for (Map.Entry<Artifact, String> entry : artifacts.entrySet()) {
+    for (Map.Entry<Artifact, Object> entry : artifacts.entrySet()) {
       Artifact a = entry.getKey();
       if (!a.isSourceArtifact() && !artifactsWithActions.contains(a)) {
-        orphanArtifacts.put(a, String.format("%s\n%s",
-            a.getExecPathString(),  // uncovered artifact
-            entry.getValue()));  // origin of creation
+        Object value = entry.getValue();
+        if (value instanceof Artifact) {
+          value = "No origin, run with --experimental_extended_sanity_checks";
+        } else {
+          value = ((Pair<?, ?>) value).second;
+        }
+        orphanArtifacts.put(
+            a,
+            String.format(
+                "%s\n%s",
+                a.getExecPathString(), // uncovered artifact
+                value)); // origin of creation
       }
     }
     return orphanArtifacts;
@@ -240,14 +258,23 @@
    * sealed (disable()). For performance reasons we only track the originating stacktrace when
    * running with --experimental_extended_sanity_checks.
    */
-  private Artifact.DerivedArtifact trackArtifactAndOrigin(
+  @SuppressWarnings("unchecked") // Cast of artifacts map's value to Pair.
+  private Artifact.DerivedArtifact dedupAndTrackArtifactAndOrigin(
       Artifact.DerivedArtifact a, @Nullable Throwable e) {
-    if ((e != null) && !artifacts.containsKey(a)) {
+    if (artifacts.containsKey(a)) {
+      Object value = artifacts.get(a);
+      if (e == null) {
+        return (Artifact.DerivedArtifact) value;
+      } else {
+        return ((Pair<Artifact.DerivedArtifact, String>) value).first;
+      }
+    }
+    if ((e != null)) {
       StringWriter sw = new StringWriter();
       e.printStackTrace(new PrintWriter(sw));
-      artifacts.put(a, sw.toString());
+      artifacts.put(a, Pair.of(a, sw.toString()));
     } else {
-      artifacts.put(a, "No origin, run with --experimental_extended_sanity_checks");
+      artifacts.put(a, a);
     }
     return a;
   }
@@ -256,7 +283,7 @@
   public Artifact.DerivedArtifact getDerivedArtifact(
       PathFragment rootRelativePath, ArtifactRoot root) {
     Preconditions.checkState(enabled);
-    return trackArtifactAndOrigin(
+    return dedupAndTrackArtifactAndOrigin(
         artifactFactory.getDerivedArtifact(rootRelativePath, root, getOwner()),
         extendedSanityChecks ? new Throwable() : null);
   }
@@ -265,7 +292,7 @@
   public SpecialArtifact getTreeArtifact(PathFragment rootRelativePath, ArtifactRoot root) {
     Preconditions.checkState(enabled);
     return (SpecialArtifact)
-        trackArtifactAndOrigin(
+        dedupAndTrackArtifactAndOrigin(
             artifactFactory.getTreeArtifact(rootRelativePath, root, getOwner()),
             extendedSanityChecks ? new Throwable() : null);
   }
@@ -274,7 +301,7 @@
   public Artifact.DerivedArtifact getFilesetArtifact(
       PathFragment rootRelativePath, ArtifactRoot root) {
     Preconditions.checkState(enabled);
-    return trackArtifactAndOrigin(
+    return dedupAndTrackArtifactAndOrigin(
         artifactFactory.getFilesetArtifact(rootRelativePath, root, getOwner()),
         extendedSanityChecks ? new Throwable() : null);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
index 5c01533..86dd39e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
@@ -64,18 +64,15 @@
 public final class ConfiguredAspect {
   private final AspectDescriptor descriptor;
   private final ImmutableList<ActionAnalysisMetadata> actions;
-  private final ImmutableMap<Artifact, Integer> generatingActionIndex;
   private final TransitiveInfoProviderMap providers;
 
   @AutoCodec.VisibleForSerialization
   ConfiguredAspect(
       AspectDescriptor descriptor,
       ImmutableList<ActionAnalysisMetadata> actions,
-      ImmutableMap<Artifact, Integer> generatingActionIndex,
       TransitiveInfoProviderMap providers) {
     this.descriptor = descriptor;
     this.actions = actions;
-    this.generatingActionIndex = generatingActionIndex;
     this.providers = providers;
 
     // Initialize every SkylarkApiProvider
@@ -105,14 +102,6 @@
     return actions;
   }
 
-  /**
-   * Returns a map where keys are artifacts that are action outputs of this rule, and values are the
-   * index of the action that generates that artifact.
-   */
-  public ImmutableMap<Artifact, Integer> getGeneratingActionIndex() {
-    return generatingActionIndex;
-  }
-
   /** Returns the providers created by the aspect. */
   public TransitiveInfoProviderMap getProviders() {
     return providers;
@@ -145,15 +134,13 @@
   }
 
   public static ConfiguredAspect forAlias(ConfiguredAspect real) {
-    return new ConfiguredAspect(
-        real.descriptor, real.getActions(), real.getGeneratingActionIndex(), real.getProviders());
+    return new ConfiguredAspect(real.descriptor, real.getActions(), real.getProviders());
   }
 
   public static ConfiguredAspect forNonapplicableTarget(AspectDescriptor descriptor) {
     return new ConfiguredAspect(
         descriptor,
         ImmutableList.of(),
-        ImmutableMap.of(),
         new TransitiveInfoProviderMapBuilder().add().build());
   }
 
@@ -289,14 +276,15 @@
 
       AnalysisEnvironment analysisEnvironment = ruleContext.getAnalysisEnvironment();
       GeneratingActions generatingActions =
-          Actions.filterSharedActionsAndThrowActionConflict(
+          Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
               analysisEnvironment.getActionKeyContext(),
-              analysisEnvironment.getRegisteredActions());
+              analysisEnvironment.getRegisteredActions(),
+              ruleContext.getOwner(),
+              /*outputFiles=*/ null);
 
       return new ConfiguredAspect(
           descriptor,
           generatingActions.getActions(),
-          generatingActions.getGeneratingActionIndex(),
           providers.build());
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index d8096c6..ad4f8da 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -24,8 +24,6 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
-import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.FailAction;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
 import com.google.devtools.build.lib.analysis.DependencyResolver.DependencyKind;
@@ -36,6 +34,7 @@
 import com.google.devtools.build.lib.analysis.configuredtargets.InputFileConfiguredTarget;
 import com.google.devtools.build.lib.analysis.configuredtargets.OutputFileConfiguredTarget;
 import com.google.devtools.build.lib.analysis.configuredtargets.PackageGroupConfiguredTarget;
+import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
 import com.google.devtools.build.lib.analysis.skylark.SkylarkRuleConfiguredTargetUtil;
 import com.google.devtools.build.lib.analysis.test.AnalysisFailure;
 import com.google.devtools.build.lib.analysis.test.AnalysisFailureInfo;
@@ -70,7 +69,6 @@
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
-import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
@@ -160,29 +158,6 @@
     return null;
   }
 
-  /** Returns the output artifact for the given file, or null if Skyframe deps are missing. */
-  private Artifact getOutputArtifact(
-      OutputFile outputFile,
-      BuildConfiguration configuration,
-      boolean isFileset,
-      ArtifactFactory artifactFactory) {
-    Rule rule = outputFile.getAssociatedRule();
-    ArtifactRoot root =
-        rule.hasBinaryOutput()
-            ? configuration.getBinDirectory(rule.getRepository())
-            : configuration.getGenfilesDirectory(rule.getRepository());
-    ArtifactOwner owner = ConfiguredTargetKey.of(rule.getLabel(), configuration);
-    PathFragment rootRelativePath =
-        outputFile.getLabel().getPackageIdentifier().getSourceRoot().getRelative(
-            outputFile.getLabel().getName());
-    Artifact result = isFileset
-        ? artifactFactory.getFilesetArtifact(rootRelativePath, root, owner)
-        : artifactFactory.getDerivedArtifact(rootRelativePath, root, owner);
-    // The associated rule should have created the artifact.
-    Preconditions.checkNotNull(result, "no artifact for %s", rootRelativePath);
-    return result;
-  }
-
   /**
    * Invokes the appropriate constructor to create a {@link ConfiguredTarget} instance.
    *
@@ -231,14 +206,15 @@
               config,
               prerequisiteMap.get(DependencyResolver.OUTPUT_FILE_RULE_DEPENDENCY),
               visibility);
-      boolean isFileset = outputFile.getGeneratingRule().getRuleClass().equals("Fileset");
-      Artifact artifact = getOutputArtifact(outputFile, config, isFileset, artifactFactory);
       if (analysisEnvironment.getSkyframeEnv().valuesMissing()) {
         return null;
       }
-      TransitiveInfoCollection rule = targetContext.findDirectPrerequisite(
-          outputFile.getGeneratingRule().getLabel(), config);
-        return new OutputFileConfiguredTarget(targetContext, outputFile, rule, artifact);
+      RuleConfiguredTarget rule =
+          (RuleConfiguredTarget)
+              targetContext.findDirectPrerequisite(
+                  outputFile.getGeneratingRule().getLabel(), config);
+      Artifact artifact = rule.getArtifactByOutputLabel(outputFile.getLabel());
+      return new OutputFileConfiguredTarget(targetContext, outputFile, rule, artifact);
     } else if (target instanceof InputFile) {
       InputFile inputFile = (InputFile) target;
       TargetContext targetContext =
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
index 15f7937..910c5a9 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
@@ -49,6 +49,7 @@
 import com.google.devtools.build.lib.packages.InfoInterface;
 import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.Provider;
+import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Type;
@@ -222,13 +223,17 @@
     }
 
     AnalysisEnvironment analysisEnvironment = ruleContext.getAnalysisEnvironment();
-    GeneratingActions generatingActions = Actions.filterSharedActionsAndThrowActionConflict(
-          analysisEnvironment.getActionKeyContext(), analysisEnvironment.getRegisteredActions());
+    GeneratingActions generatingActions =
+        Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
+            analysisEnvironment.getActionKeyContext(),
+            analysisEnvironment.getRegisteredActions(),
+            ruleContext.getOwner(),
+            ((Rule) ruleContext.getTarget()).getOutputFiles());
     return new RuleConfiguredTarget(
         ruleContext,
         providers,
         generatingActions.getActions(),
-        generatingActions.getGeneratingActionIndex());
+        generatingActions.getArtifactsByOutputLabel());
   }
 
   private NestedSet<Label> transitiveLabels() {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplate.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplate.java
index 4ae6ca2..28a7993 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplate.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplate.java
@@ -21,12 +21,12 @@
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionKeyCacher;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionTemplate;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.CommandLine;
 import com.google.devtools.build.lib.actions.CommandLineExpansionException;
 import com.google.devtools.build.lib.analysis.FilesToRunProvider;
@@ -98,16 +98,15 @@
 
   @Override
   public Iterable<SpawnAction> generateActionForInputArtifacts(
-      Iterable<TreeFileArtifact> inputTreeFileArtifacts, ArtifactOwner artifactOwner) {
+      Iterable<TreeFileArtifact> inputTreeFileArtifacts, ActionLookupKey artifactOwner) {
     ImmutableList.Builder<SpawnAction> expandedActions = new ImmutableList.Builder<>();
     for (TreeFileArtifact inputTreeFileArtifact : inputTreeFileArtifacts) {
       PathFragment parentRelativeOutputPath =
           outputPathMapper.parentRelativeOutputPath(inputTreeFileArtifact);
 
-      TreeFileArtifact outputTreeFileArtifact = ActionInputHelper.treeFileArtifact(
-          outputTreeArtifact,
-          parentRelativeOutputPath,
-          artifactOwner);
+      TreeFileArtifact outputTreeFileArtifact =
+          ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+              outputTreeArtifact, parentRelativeOutputPath, artifactOwner);
 
       expandedActions.add(createAction(inputTreeFileArtifact, outputTreeFileArtifact));
     }
@@ -121,8 +120,10 @@
     TreeFileArtifact inputTreeFileArtifact =
         ActionInputHelper.treeFileArtifact(inputTreeArtifact, "dummy_for_key");
     TreeFileArtifact outputTreeFileArtifact =
-        ActionInputHelper.treeFileArtifact(
-            outputTreeArtifact, outputPathMapper.parentRelativeOutputPath(inputTreeFileArtifact));
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            outputTreeArtifact,
+            outputPathMapper.parentRelativeOutputPath(inputTreeFileArtifact),
+            outputTreeArtifact.getArtifactOwner());
     SpawnAction dummyAction = createAction(inputTreeFileArtifact, outputTreeFileArtifact);
     dummyAction.computeKey(actionKeyContext, fp);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
index 18038f2..93c9f9f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.analysis.configuredtargets;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
@@ -225,4 +226,9 @@
   public void repr(SkylarkPrinter printer) {
     printer.append("<merged target " + getLabel() + ">");
   }
+
+  @VisibleForTesting
+  public ConfiguredTarget getBaseConfiguredTargetForTesting() {
+    return base;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
index d5c5a17..9eba156 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
@@ -94,7 +94,8 @@
   private final ImmutableMap<Label, ConfigMatchingProvider> configConditions;
   private final String ruleClassString;
   private final ImmutableList<ActionAnalysisMetadata> actions;
-  private final ImmutableMap<Artifact, Integer> generatingActionIndex;
+  // TODO(b/133160730): can we only populate this map for outputs that have labels?
+  private final ImmutableMap<Label, Artifact> artifactsByOutputLabel;
 
   @Instantiator
   @VisibleForSerialization
@@ -107,8 +108,9 @@
       ImmutableSet<ConfiguredTargetKey> implicitDeps,
       String ruleClassString,
       ImmutableList<ActionAnalysisMetadata> actions,
-      ImmutableMap<Artifact, Integer> generatingActionIndex) {
+      ImmutableMap<Label, Artifact> artifactsByOutputLabel) {
     super(label, configurationKey, visibility);
+    this.artifactsByOutputLabel = artifactsByOutputLabel;
 
     // We don't use ImmutableMap.Builder here to allow augmenting the initial list of 'default'
     // providers by passing them in.
@@ -131,14 +133,13 @@
     this.implicitDeps = IMPLICIT_DEPS_INTERNER.intern(implicitDeps);
     this.ruleClassString = ruleClassString;
     this.actions = actions;
-    this.generatingActionIndex = generatingActionIndex;
   }
 
   public RuleConfiguredTarget(
       RuleContext ruleContext,
       TransitiveInfoProviderMap providers,
       ImmutableList<ActionAnalysisMetadata> actions,
-      ImmutableMap<Artifact, Integer> generatingActionIndex) {
+      ImmutableMap<Label, Artifact> artifactsByOutputLabel) {
     this(
         ruleContext.getLabel(),
         ruleContext.getConfigurationKey(),
@@ -148,7 +149,7 @@
         Util.findImplicitDeps(ruleContext),
         ruleContext.getRule().getRuleClass(),
         actions,
-        generatingActionIndex);
+        artifactsByOutputLabel);
 
     // If this rule is the run_under target, then check that we have an executable; note that
     // run_under is only set in the target configuration, and the target must also be analyzed for
@@ -251,10 +252,15 @@
   }
 
   /**
-   * Returns a map where keys are artifacts that are action outputs of this rule, and values are the
-   * index of the action that generates that artifact.
+   * Provide an artifact by its corresponding output label, for use by output file configured
+   * targets.
    */
-  public ImmutableMap<Artifact, Integer> getGeneratingActionIndex() {
-    return generatingActionIndex;
+  public Artifact getArtifactByOutputLabel(Label outputLabel) {
+    return Preconditions.checkNotNull(
+        artifactsByOutputLabel.get(outputLabel),
+        "%s %s %s",
+        outputLabel,
+        this,
+        this.artifactsByOutputLabel);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/CoverageReportActionFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/test/CoverageReportActionFactory.java
index 32b36e7..f8099db 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/CoverageReportActionFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/CoverageReportActionFactory.java
@@ -18,12 +18,16 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
+import com.google.devtools.build.lib.actions.MutableActionGraph;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.skyframe.CoverageReportValue;
 import java.util.Collection;
 import javax.annotation.Nullable;
 
@@ -32,27 +36,37 @@
  */
 public interface CoverageReportActionFactory {
   /**
-   * Wraps the necessary actions to get a coverage report as well as the final output artifacts.
-   * The lcovWriteAction creates a file containing a set of lcov files. This file is used as an
-   * input artifact for coverageReportAction. We are only interested about the output artifacts from
+   * Wraps the necessary actions to get a coverage report as well as the final output artifacts. The
+   * lcovWriteAction creates a file containing a set of lcov files. This file is used as an input
+   * artifact for coverageReportAction. We are only interested about the output artifacts from
    * coverageReportAction.
    */
-  public static final class CoverageReportActionsWrapper {
-    private final ActionAnalysisMetadata lcovWriteAction;
+  final class CoverageReportActionsWrapper {
     private final ActionAnalysisMetadata coverageReportAction;
+    private final Actions.GeneratingActions processedActions;
 
-    public CoverageReportActionsWrapper (
-        ActionAnalysisMetadata lcovWriteAction, ActionAnalysisMetadata coverageReportAction) {
-      this.lcovWriteAction = lcovWriteAction;
+    public CoverageReportActionsWrapper(
+        ActionAnalysisMetadata lcovWriteAction,
+        ActionAnalysisMetadata coverageReportAction,
+        ActionKeyContext actionKeyContext) {
       this.coverageReportAction = coverageReportAction;
+      try {
+        this.processedActions =
+            Actions.assignOwnersAndFindAndThrowActionConflict(
+                actionKeyContext,
+                ImmutableList.of(lcovWriteAction, coverageReportAction),
+                CoverageReportValue.COVERAGE_REPORT_KEY);
+      } catch (MutableActionGraph.ActionConflictException e) {
+        throw new IllegalStateException(e);
+      }
     }
 
     public ActionAnalysisMetadata getCoverageReportAction() {
       return coverageReportAction;
     }
 
-    public ImmutableList<ActionAnalysisMetadata> getActions() {
-      return ImmutableList.of(lcovWriteAction, coverageReportAction);
+    public Actions.GeneratingActions getActions() {
+      return processedActions;
     }
 
     public ImmutableSet<Artifact> getCoverageOutputs() {
@@ -73,6 +87,7 @@
       Collection<ConfiguredTarget> targetsToTest,
       Iterable<Artifact> baselineCoverageArtifacts,
       ArtifactFactory artifactFactory,
-      ArtifactOwner artifactOwner,
+      ActionKeyContext actionKeyContext,
+      ActionLookupValue.ActionLookupKey actionLookupKey,
       String workspaceName);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/coverage/BazelCoverageReportModule.java b/src/main/java/com/google/devtools/build/lib/bazel/coverage/BazelCoverageReportModule.java
index ba74cb0..81c0042 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/coverage/BazelCoverageReportModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/coverage/BazelCoverageReportModule.java
@@ -17,9 +17,10 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.eventbus.EventBus;
+import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.test.CoverageReportActionFactory;
@@ -85,7 +86,8 @@
           Collection<ConfiguredTarget> targetsToTest,
           Iterable<Artifact> baselineCoverageArtifacts,
           ArtifactFactory artifactFactory,
-          ArtifactOwner artifactOwner,
+          ActionKeyContext actionKeyContext,
+          ActionLookupValue.ActionLookupKey actionLookupKey,
           String workspaceName) {
         if (options == null || options.combinedReport == ReportType.NONE) {
           return null;
@@ -98,7 +100,8 @@
             targetsToTest,
             baselineCoverageArtifacts,
             artifactFactory,
-            artifactOwner,
+            actionKeyContext,
+            actionLookupKey,
             workspaceName,
             this::getArgs,
             this::getLocationMessage,
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/coverage/CoverageReportActionBuilder.java b/src/main/java/com/google/devtools/build/lib/bazel/coverage/CoverageReportActionBuilder.java
index ba1ef1d..aefa76f 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/coverage/CoverageReportActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/coverage/CoverageReportActionBuilder.java
@@ -161,6 +161,7 @@
       Collection<ConfiguredTarget> targetsToTest,
       Iterable<Artifact> baselineCoverageArtifacts,
       ArtifactFactory factory,
+      ActionKeyContext actionKeyContext,
       ArtifactOwner artifactOwner,
       String workspaceName,
       ArgsFunc argsFunction,
@@ -193,7 +194,8 @@
           CoverageArgs.create(directories, coverageArtifacts, lcovArtifact, factory, artifactOwner,
               reportGenerator, workspaceName, htmlReport),
           argsFunction, locationFunc);
-      return new CoverageReportActionsWrapper(lcovFileAction, coverageReportAction);
+      return new CoverageReportActionsWrapper(
+          lcovFileAction, coverageReportAction, actionKeyContext);
     } else {
       reporter.handle(
           Event.error("Cannot generate coverage report - no coverage information was collected"));
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 43679ed..a27a2c0 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -33,9 +33,6 @@
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
-import com.google.devtools.build.lib.actions.ActionLookupData;
-import com.google.devtools.build.lib.actions.ActionLookupValue;
-import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -56,7 +53,6 @@
 import com.google.devtools.build.lib.actions.extra.CppCompileInfo;
 import com.google.devtools.build.lib.actions.extra.EnvironmentVariable;
 import com.google.devtools.build.lib.actions.extra.ExtraActionInfo;
-import com.google.devtools.build.lib.bugreport.BugReport;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -1570,62 +1566,26 @@
   private static Map<Artifact, NestedSet<? extends Artifact>> computeTransitivelyUsedModules(
       SkyFunction.Environment env, Collection<Artifact.DerivedArtifact> usedModules)
       throws InterruptedException {
-    // ActionLookupKey → ActionLookupValue
-    Map<SkyKey, SkyValue> actionLookupValues =
+    Map<SkyKey, SkyValue> actionExecutionValues =
         env.getValues(
-            Iterables.transform(
-                usedModules, module -> (ActionLookupKey) module.getArtifactOwner()));
-    if (env.valuesMissing()) {
-      ImmutableList<SkyKey> missingKeys =
-          actionLookupValues.entrySet().stream()
-              .filter(e -> e.getValue() == null)
-              .map(Map.Entry::getKey)
-              .collect(ImmutableList.toImmutableList());
-      BugReport.sendBugReport(
-          new IllegalStateException("Missing keys: " + missingKeys + ". Modules " + usedModules));
-      return null;
-    }
-    ArrayList<ActionLookupData> executionValueLookups = new ArrayList<>(usedModules.size());
-    for (Artifact module : usedModules) {
-      ActionLookupData lookupData = lookupDataFromModule(actionLookupValues, module);
-      executionValueLookups.add(Preconditions.checkNotNull(lookupData, module));
-    }
-
-    // ActionLookupData → ActionExecutionValue
-    Map<SkyKey, SkyValue> actionExecutionValues = env.getValues(executionValueLookups);
+            Iterables.transform(usedModules, Artifact.DerivedArtifact::getGeneratingActionKey));
     if (env.valuesMissing()) {
       return null;
     }
     ImmutableMap.Builder<Artifact, NestedSet<? extends Artifact>> transitivelyUsedModules =
         ImmutableMap.builderWithExpectedSize(usedModules.size());
-    int pos = 0;
-    for (Artifact module : usedModules) {
-      ActionLookupData lookup = executionValueLookups.get(pos++);
-      ActionExecutionValue value = (ActionExecutionValue) actionExecutionValues.get(lookup);
+    for (Artifact.DerivedArtifact module : usedModules) {
+      Preconditions.checkState(
+          module.isFileType(CppFileTypes.CPP_MODULE), "Non-module? %s", module);
+      ActionExecutionValue value =
+          Preconditions.checkNotNull(
+              (ActionExecutionValue) actionExecutionValues.get(module.getGeneratingActionKey()),
+              module);
       transitivelyUsedModules.put(module, value.getDiscoveredModules());
     }
     return transitivelyUsedModules.build();
   }
 
-  @Nullable
-  private static ActionLookupData lookupDataFromModule(
-      Map<SkyKey, SkyValue> actionLookupValues, Artifact module) {
-    ActionLookupKey lookupKey = (ActionLookupKey) module.getArtifactOwner();
-    ActionLookupValue lookupValue = (ActionLookupValue) actionLookupValues.get(lookupKey);
-    if (lookupValue == null) {
-      return null;
-    }
-    Preconditions.checkState(
-        module.isFileType(CppFileTypes.CPP_MODULE), "Non-module? %s (%s)", module, lookupValue);
-    return ActionLookupData.create(
-        lookupKey,
-        Preconditions.checkNotNull(
-            lookupValue.getGeneratingActionIndex(module),
-            "%s missing action index for module %s",
-            lookupValue,
-            module));
-  }
-
   private static NestedSetBuilder<Artifact> createInputsBuilder(
       NestedSet<Artifact> mandatoryInputs, Iterable<Artifact> inputsForInvalidation) {
     return NestedSetBuilder.<Artifact>stableOrder()
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java
index de30e93..efcbed6 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java
@@ -22,11 +22,11 @@
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionKeyCacher;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionTemplate;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.CommandLineExpansionException;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
@@ -89,7 +89,7 @@
 
   @Override
   public Iterable<CppCompileAction> generateActionForInputArtifacts(
-      Iterable<TreeFileArtifact> inputTreeFileArtifacts, ArtifactOwner artifactOwner)
+      Iterable<TreeFileArtifact> inputTreeFileArtifacts, ActionLookupKey artifactOwner)
       throws ActionTemplateExpansionException {
     ImmutableList.Builder<CppCompileAction> expandedActions = new ImmutableList.Builder<>();
 
@@ -125,10 +125,10 @@
       try {
         String outputName = outputTreeFileArtifactName(inputTreeFileArtifact);
         TreeFileArtifact outputTreeFileArtifact =
-            ActionInputHelper.treeFileArtifact(
+            ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
                 outputTreeArtifact, PathFragment.create(outputName), artifactOwner);
         TreeFileArtifact dotdFileArtifact =
-            ActionInputHelper.treeFileArtifact(
+            ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
                 dotdTreeArtifact, PathFragment.create(outputName + ".d"), artifactOwner);
         expandedActions.add(
             createAction(
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java b/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java
index fedcaa9..35a7f5e 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java
@@ -37,7 +37,6 @@
 import java.time.Duration;
 import java.util.Comparator;
 import java.util.List;
-import java.util.Objects;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
@@ -361,7 +360,9 @@
     // shared action that is in the midst of being an action cache hit.
     for (Artifact actionOutput : action.getOutputs()) {
       if (input.equals(actionOutput)
-          && Objects.equals(input.getArtifactOwner(), actionOutput.getArtifactOwner())) {
+          && input
+              .getGeneratingActionKey()
+              .equals(((Artifact.DerivedArtifact) actionOutput).getGeneratingActionKey())) {
         // As far as we can tell, this (currently running) action is the same action that
         // produced input, not another shared action. This should be impossible.
         throw new IllegalStateException(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
index 3be7aad..f589d15 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
@@ -22,8 +21,6 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
-import com.google.devtools.build.lib.actions.ActionLookupData;
-import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.OwnerlessArtifactWrapper;
 import com.google.devtools.build.lib.actions.ArtifactFileMetadata;
@@ -37,7 +34,6 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.BigIntegerFingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.math.BigInteger;
 import java.util.Comparator;
@@ -236,18 +232,6 @@
         .sorted(Comparator.comparing(Entry::getKey, Artifact.EXEC_PATH_COMPARATOR));
   }
 
-  /**
-   * @param lookupKey A {@link SkyKey} whose argument is an {@code ActionLookupKey}, whose
-   *     corresponding {@code ActionLookupValue} contains the action to be executed.
-   * @param index the index of the action to be executed in the {@code ActionLookupValue}, to be
-   *     passed to {@code ActionLookupValue#getAction}.
-   */
-  @ThreadSafe
-  @VisibleForTesting
-  public static ActionLookupData key(ActionLookupValue.ActionLookupKey lookupKey, int index) {
-    return ActionLookupData.create(lookupKey, index);
-  }
-
   @Override
   public String toString() {
     return MoreObjects.toStringHelper(this)
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java
index 26ca7e2..d5771fc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionInputMapHelper.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionInputMapSink;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -27,7 +28,6 @@
 import com.google.devtools.build.lib.analysis.actions.SymlinkAction;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
-import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Collection;
 import java.util.Map;
@@ -93,27 +93,44 @@
   static ImmutableList<FilesetOutputSymlink> getFilesets(
       Environment env, Artifact.SpecialArtifact actionInput) throws InterruptedException {
     Preconditions.checkState(actionInput.isFileset(), actionInput);
-    ActionLookupKey filesetActionLookupKey = (ActionLookupKey) actionInput.getArtifactOwner();
+    ActionLookupData generatingActionKey = actionInput.getGeneratingActionKey();
+    ActionLookupKey filesetActionLookupKey = generatingActionKey.getActionLookupKey();
 
     ActionLookupValue filesetActionLookupValue =
         (ActionLookupValue) env.getValue(filesetActionLookupKey);
 
     ActionAnalysisMetadata generatingAction =
-        filesetActionLookupValue.getGeneratingActionDangerousReadJavadoc(actionInput);
-    int filesetManifestActionIndex;
+        filesetActionLookupValue.getAction(generatingActionKey.getActionIndex());
+    ActionLookupData filesetActionKey;
 
     if (generatingAction instanceof SymlinkAction) {
-      Artifact outputManifest = Iterables.getOnlyElement(generatingAction.getInputs());
+      Artifact.DerivedArtifact outputManifest =
+          (Artifact.DerivedArtifact) Iterables.getOnlyElement(generatingAction.getInputs());
+      ActionLookupData manifestGeneratingKey = outputManifest.getGeneratingActionKey();
+      Preconditions.checkState(
+          manifestGeneratingKey.getActionLookupKey().equals(filesetActionLookupKey),
+          "Mismatched actions and artifacts: %s %s %s %s",
+          actionInput,
+          outputManifest,
+          filesetActionLookupKey,
+          manifestGeneratingKey);
       ActionAnalysisMetadata symlinkTreeAction =
-          filesetActionLookupValue.getGeneratingActionDangerousReadJavadoc(outputManifest);
-      Artifact inputManifest = Iterables.getOnlyElement(symlinkTreeAction.getInputs());
-      filesetManifestActionIndex = filesetActionLookupValue.getGeneratingActionIndex(inputManifest);
+          filesetActionLookupValue.getAction(manifestGeneratingKey.getActionIndex());
+      Artifact.DerivedArtifact inputManifest =
+          (Artifact.DerivedArtifact) Iterables.getOnlyElement(symlinkTreeAction.getInputs());
+      ActionLookupData inputManifestGeneratingKey = inputManifest.getGeneratingActionKey();
+      Preconditions.checkState(
+          inputManifestGeneratingKey.getActionLookupKey().equals(filesetActionLookupKey),
+          "Mismatched actions and artifacts: %s %s %s %s",
+          actionInput,
+          inputManifest,
+          filesetActionLookupKey,
+          inputManifestGeneratingKey);
+      filesetActionKey = inputManifestGeneratingKey;
     } else {
-      filesetManifestActionIndex = filesetActionLookupValue.getGeneratingActionIndex(actionInput);
+      filesetActionKey = generatingActionKey;
     }
 
-    SkyKey filesetActionKey =
-        ActionExecutionValue.key(filesetActionLookupKey, filesetManifestActionIndex);
     ActionExecutionValue filesetValue = (ActionExecutionValue) env.getValue(filesetActionKey);
     if (filesetValue == null) {
       // At this point skyframe does not guarantee that the filesetValue will be ready, since
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
index d8b5b5f..41bed76 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
@@ -14,14 +14,18 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionGraph;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionTemplate;
 import com.google.devtools.build.lib.actions.ActionTemplate.ActionTemplateExpansionException;
 import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
+import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactPrefixConflictException;
 import com.google.devtools.build.lib.actions.ArtifactSkyKey;
@@ -29,11 +33,15 @@
 import com.google.devtools.build.lib.bugreport.BugReport;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.skyframe.ActionTemplateExpansionValue.ActionTemplateExpansionKey;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
+import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
+import java.util.TreeMap;
 import javax.annotation.Nullable;
 
 /**
@@ -80,7 +88,7 @@
       // of the ActionTemplate.
       generatingActions =
           checkActionAndArtifactConflicts(
-              actionTemplate.generateActionForInputArtifacts(inputTreeFileArtifacts, key));
+              actionTemplate.generateActionForInputArtifacts(inputTreeFileArtifacts, key), key);
     } catch (ActionConflictException e) {
       e.reportTo(env.getListener());
       throw new ActionTemplateExpansionFunctionException(e);
@@ -110,14 +118,14 @@
     }
   }
 
-  private GeneratingActions checkActionAndArtifactConflicts(Iterable<? extends Action> actions)
+  private GeneratingActions checkActionAndArtifactConflicts(
+      Iterable<? extends Action> actions, ActionLookupValue.ActionLookupKey actionLookupKey)
       throws ActionConflictException, ArtifactPrefixConflictException {
     GeneratingActions generatingActions =
-        Actions.findAndThrowActionConflict(actionKeyContext, ImmutableList.copyOf(actions));
+        Actions.assignOwnersAndFindAndThrowActionConflict(
+            actionKeyContext, ImmutableList.copyOf(actions), actionLookupKey);
     Map<ActionAnalysisMetadata, ArtifactPrefixConflictException> artifactPrefixConflictMap =
-        Actions.findArtifactPrefixConflicts(
-            ActionLookupValue.getMapForConsistencyCheck(
-                generatingActions.getGeneratingActionIndex(), generatingActions.getActions()));
+        findArtifactPrefixConflicts(getMapForConsistencyCheck(generatingActions.getActions()));
 
     if (!artifactPrefixConflictMap.isEmpty()) {
       throw artifactPrefixConflictMap.values().iterator().next();
@@ -125,6 +133,57 @@
     return generatingActions;
   }
 
+  private static Map<Artifact, ActionAnalysisMetadata> getMapForConsistencyCheck(
+      List<? extends ActionAnalysisMetadata> actions) {
+    if (actions.isEmpty()) {
+      return ImmutableMap.of();
+    }
+    HashMap<Artifact, ActionAnalysisMetadata> result =
+        Maps.newHashMapWithExpectedSize(actions.size() * actions.get(0).getOutputs().size());
+    for (ActionAnalysisMetadata action : actions) {
+      for (Artifact output : action.getOutputs()) {
+        result.put(output, action);
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Finds Artifact prefix conflicts between generated artifacts. An artifact prefix conflict
+   * happens if one action generates an artifact whose path is a prefix of another artifact's path.
+   * Those two artifacts cannot exist simultaneously in the output tree.
+   *
+   * @param generatingActions a map between generated artifacts and their associated generating
+   *     actions.
+   * @return a map between actions that generated the conflicting artifacts and their associated
+   *     {@link ArtifactPrefixConflictException}.
+   */
+  private static Map<ActionAnalysisMetadata, ArtifactPrefixConflictException>
+      findArtifactPrefixConflicts(Map<Artifact, ActionAnalysisMetadata> generatingActions) {
+    TreeMap<PathFragment, Artifact> artifactPathMap =
+        new TreeMap<>(Actions.comparatorForPrefixConflicts());
+    for (Artifact artifact : generatingActions.keySet()) {
+      artifactPathMap.put(artifact.getExecPath(), artifact);
+    }
+
+    return Actions.findArtifactPrefixConflicts(
+        new MapBasedImmutableActionGraph(generatingActions), artifactPathMap);
+  }
+
+  private static class MapBasedImmutableActionGraph implements ActionGraph {
+    private final Map<Artifact, ActionAnalysisMetadata> generatingActions;
+
+    MapBasedImmutableActionGraph(Map<Artifact, ActionAnalysisMetadata> generatingActions) {
+      this.generatingActions = ImmutableMap.copyOf(generatingActions);
+    }
+
+    @Nullable
+    @Override
+    public ActionAnalysisMetadata getGeneratingAction(Artifact artifact) {
+      return generatingActions.get(artifact);
+    }
+  }
+
   @Nullable
   @Override
   public String extractTag(SkyKey skyKey) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
index bfec907..b2b4d96 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Artifact.DerivedArtifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactFileMetadata;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -428,21 +429,12 @@
   // TODO(b/19539699): extend this to comprehensively support all special artifact types (e.g.
   // middleman, etc).
   static class ArtifactDependencies {
-
-    private final Artifact artifact;
-    private final ActionLookupKey actionLookupKey;
+    private final DerivedArtifact artifact;
     private final ActionLookupValue actionLookupValue;
-    private final int actionIndex;
 
-    private ArtifactDependencies(
-        Artifact artifact,
-        ActionLookupKey actionLookupKey,
-        ActionLookupValue actionLookupValue,
-        int actionIndex) {
+    private ArtifactDependencies(DerivedArtifact artifact, ActionLookupValue actionLookupValue) {
       this.artifact = artifact;
-      this.actionLookupKey = actionLookupKey;
       this.actionLookupValue = actionLookupValue;
-      this.actionIndex = actionIndex;
     }
 
     /**
@@ -454,25 +446,15 @@
         Artifact.DerivedArtifact derivedArtifact, SkyFunction.Environment env)
         throws InterruptedException {
 
-      ActionLookupKey actionLookupKey = ArtifactFunction.getActionLookupKey(derivedArtifact);
+      ActionLookupData generatingActionKey = derivedArtifact.getGeneratingActionKey();
       ActionLookupValue actionLookupValue =
-          ArtifactFunction.getActionLookupValue(actionLookupKey, env, derivedArtifact);
+          ArtifactFunction.getActionLookupValue(
+              generatingActionKey.getActionLookupKey(), env, derivedArtifact);
       if (actionLookupValue == null) {
         return null;
       }
-      Integer actionIndex = actionLookupValue.getGeneratingActionIndex(derivedArtifact);
-      if (derivedArtifact.hasParent() && actionIndex == null) {
-        // If a TreeFileArtifact is created by a templated action, then it should have the proper
-        // reference to its owner. However, if it was created as part of a directory, by the first
-        // TreeArtifact-generating action in a chain, then its parent's generating action also
-        // generated it. This catches that case.
-        actionIndex = actionLookupValue.getGeneratingActionIndex(derivedArtifact.getParent());
-      }
-      Preconditions.checkNotNull(
-          actionIndex, "%s %s %s", derivedArtifact, actionLookupKey, actionLookupValue);
 
-      return new ArtifactDependencies(
-          derivedArtifact, actionLookupKey, actionLookupValue, actionIndex);
+      return new ArtifactDependencies(derivedArtifact, actionLookupValue);
     }
 
     Artifact getArtifact() {
@@ -480,21 +462,21 @@
     }
 
     ActionLookupKey getActionLookupKey() {
-      return actionLookupKey;
+      return artifact.getArtifactOwner();
     }
 
     int getActionIndex() {
-      return actionIndex;
+      return artifact.getGeneratingActionKey().getActionIndex();
     }
 
     boolean isTemplateActionForTreeArtifact() {
-      return artifact.isTreeArtifact() && actionLookupValue.isActionTemplate(actionIndex);
+      return artifact.isTreeArtifact() && actionLookupValue.isActionTemplate(getActionIndex());
     }
 
     ActionLookupData getNontemplateActionExecutionKey() {
       Preconditions.checkState(
           !isTemplateActionForTreeArtifact(), "Action is unexpectedly template: %s", this);
-      return ActionExecutionValue.key(actionLookupKey, actionIndex);
+      return artifact.getGeneratingActionKey();
     }
 
     /**
@@ -509,7 +491,7 @@
       Preconditions.checkState(
           isTemplateActionForTreeArtifact(), "Action is unexpectedly non-template: %s", this);
       ActionTemplateExpansionValue.ActionTemplateExpansionKey key =
-          ActionTemplateExpansionValue.key(actionLookupKey, actionIndex);
+          ActionTemplateExpansionValue.key(getActionLookupKey(), getActionIndex());
       ActionTemplateExpansionValue value = (ActionTemplateExpansionValue) env.getValue(key);
       if (value == null) {
         return null;
@@ -518,16 +500,15 @@
     }
 
     Action getAction() {
-      return actionLookupValue.getAction(actionIndex);
+      return actionLookupValue.getAction(getActionIndex());
     }
 
     @Override
     public String toString() {
       return MoreObjects.toStringHelper(this)
           .add("artifact", artifact)
-          .add("actionLookupKey", actionLookupKey)
+          .add("generatingActionKey", artifact.getGeneratingActionKey())
           .add("actionLookupValue", actionLookupValue)
-          .add("actionIndex", actionIndex)
           .toString();
     }
   }
@@ -555,8 +536,9 @@
       int numActions = value.getNumActions();
       ImmutableList.Builder<ActionLookupData> expandedActionExecutionKeys =
           ImmutableList.builderWithExpectedSize(numActions);
-      for (int i = 0; i < numActions; i++) {
-        expandedActionExecutionKeys.add(ActionExecutionValue.key(key, i));
+      for (ActionAnalysisMetadata action : value.getActions()) {
+        expandedActionExecutionKeys.add(
+            ((DerivedArtifact) action.getPrimaryOutput()).getGeneratingActionKey());
       }
       return expandedActionExecutionKeys.build();
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
index b46fd13..50843d2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
@@ -444,7 +444,7 @@
       ConfiguredAspect configuredAspect,
       NestedSet<Package> transitivePackagesForPackageRootResolution,
       BigInteger nonceVersion) {
-    super(configuredAspect.getActions(), configuredAspect.getGeneratingActionIndex(), nonceVersion);
+    super(configuredAspect.getActions(), nonceVersion);
     this.label = Preconditions.checkNotNull(label, actions);
     this.aspect = Preconditions.checkNotNull(aspect, label);
     this.location = Preconditions.checkNotNull(location, label);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
index 641e01b..3425c32 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
@@ -98,8 +98,8 @@
     GeneratingActions generatingActions;
     try {
       generatingActions =
-          Actions.filterSharedActionsAndThrowActionConflict(
-              actionKeyContext, collection.getActions());
+          Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
+              actionKeyContext, collection.getActions(), keyAndConfig, /*outputFiles=*/ null);
     } catch (ActionConflictException e) {
       throw new IllegalStateException("Action conflicts not expected in build info: " + skyKey, e);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index a26a891..94231f6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -942,9 +942,11 @@
       // rule implementation).
       try {
         generatingActions =
-            Actions.filterSharedActionsAndThrowActionConflict(
+            Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
                 analysisEnvironment.getActionKeyContext(),
-                analysisEnvironment.getRegisteredActions());
+                analysisEnvironment.getRegisteredActions(),
+                configuredTargetKey,
+                /*outputFiles=*/ null);
       } catch (ActionConflictException e) {
         throw new ConfiguredTargetFunctionException(e);
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
index c83069e..9a5ca17 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
@@ -16,12 +16,10 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
-import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -50,16 +48,14 @@
       return null;
     }
 
-    ImmutableSet.Builder<Artifact> outputs = new ImmutableSet.Builder<>();
-
-    for (ActionAnalysisMetadata action : actions) {
-      outputs.addAll(action.getOutputs());
-    }
-
     GeneratingActions generatingActions;
     try {
       generatingActions =
-          Actions.filterSharedActionsAndThrowActionConflict(actionKeyContext, actions);
+          Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
+              actionKeyContext,
+              actions,
+              CoverageReportValue.COVERAGE_REPORT_KEY,
+              /*outputFiles=*/ null);
     } catch (ActionConflictException e) {
       throw new IllegalStateException("Action conflicts not expected in coverage: " + skyKey, e);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/NonRuleConfiguredTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/NonRuleConfiguredTargetValue.java
index 9b70e17..46151e5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/NonRuleConfiguredTargetValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/NonRuleConfiguredTargetValue.java
@@ -16,10 +16,8 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
-import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
 import com.google.devtools.build.lib.actions.BasicActionLookupValue;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
@@ -53,9 +51,8 @@
   @VisibleForSerialization
   NonRuleConfiguredTargetValue(
       ImmutableList<ActionAnalysisMetadata> actions,
-      ImmutableMap<Artifact, Integer> generatingActionIndex,
       ConfiguredTarget configuredTarget) {
-    super(actions, generatingActionIndex, /*nonceVersion=*/ null);
+    super(actions, /*nonceVersion=*/ null);
     this.configuredTarget = configuredTarget;
     // Transitive packages are not serialized.
     this.transitivePackagesForPackageRootResolution = null;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RuleConfiguredTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RuleConfiguredTargetValue.java
index 4c8a431..1542b9e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RuleConfiguredTargetValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RuleConfiguredTargetValue.java
@@ -16,10 +16,8 @@
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
-import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -41,7 +39,6 @@
   // clear(true) is called.
   @Nullable private RuleConfiguredTarget configuredTarget;
   private final ImmutableList<ActionAnalysisMetadata> actions;
-  private final ImmutableMap<Artifact, Integer> generatingActionIndex;
 
   // May be null either after clearing or because transitive packages are not tracked.
   @Nullable private NestedSet<Package> transitivePackagesForPackageRootResolution;
@@ -64,7 +61,6 @@
     this.transitivePackagesForPackageRootResolution = transitivePackagesForPackageRootResolution;
     // These are specifically *not* copied to save memory.
     this.actions = configuredTarget.getActions();
-    this.generatingActionIndex = configuredTarget.getGeneratingActionIndex();
   }
 
   @Override
@@ -79,11 +75,6 @@
   }
 
   @Override
-  protected ImmutableMap<Artifact, Integer> getGeneratingActionIndex() {
-    return generatingActionIndex;
-  }
-
-  @Override
   public NestedSet<Package> getTransitivePackagesForPackageRootResolution() {
     return Preconditions.checkNotNull(transitivePackagesForPackageRootResolution);
   }
@@ -100,7 +91,6 @@
   @Override
   public String toString() {
     return MoreObjects.toStringHelper(this)
-        .add("generatingActionIndex", generatingActionIndex)
         .add("actions", actions)
         .add("configuredTarget", configuredTarget)
         .toString();
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 e3cc635..f24127a 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
@@ -356,12 +356,9 @@
     ExecutorService executor = Executors.newFixedThreadPool(
         numJobs,
         new ThreadFactoryBuilder().setNameFormat("ActionLookupValue Processor %d").build());
-    Set<ActionAnalysisMetadata> registeredActions = Sets.newConcurrentHashSet();
     for (List<ActionLookupValue> shard : actionShards) {
       executor.execute(
-          wrapper.wrap(
-              actionRegistration(
-                  shard, actionGraph, artifactPathMap, badActionMap, registeredActions)));
+          wrapper.wrap(actionRegistration(shard, actionGraph, artifactPathMap, badActionMap)));
     }
     boolean interrupted = ExecutorUtil.interruptibleShutdown(executor);
     Throwables.propagateIfPossible(wrapper.getFirstThrownError());
@@ -375,31 +372,22 @@
       final List<ActionLookupValue> values,
       final MutableActionGraph actionGraph,
       final ConcurrentMap<PathFragment, Artifact> artifactPathMap,
-      final ConcurrentMap<ActionAnalysisMetadata, ConflictException> badActionMap,
-      final Set<ActionAnalysisMetadata> registeredActions) {
-    return new Runnable() {
-      @Override
-      public void run() {
-        for (ActionLookupValue value : values) {
-          for (Map.Entry<Artifact, ActionAnalysisMetadata> entry :
-              value.getMapForConsistencyCheck().entrySet()) {
-            ActionAnalysisMetadata action = entry.getValue();
-            // We have an entry for each <action, artifact> pair. Only try to register each action
-            // once.
-            if (registeredActions.add(action)) {
-              try {
-                actionGraph.registerAction(action);
-              } catch (ActionConflictException e) {
-                Exception oldException = badActionMap.put(action, new ConflictException(e));
-                Preconditions.checkState(
-                    oldException == null, "%s | %s | %s", action, e, oldException);
-                // We skip the rest of the loop, and do not add the path->artifact mapping for this
-                // artifact below -- we don't need to check it since this action is already in
-                // error.
-                continue;
-              }
-            }
-            artifactPathMap.put(entry.getKey().getExecPath(), entry.getKey());
+      final ConcurrentMap<ActionAnalysisMetadata, ConflictException> badActionMap) {
+    return () -> {
+      for (ActionLookupValue value : values) {
+        for (ActionAnalysisMetadata action : value.getActions()) {
+          try {
+            actionGraph.registerAction(action);
+          } catch (ActionConflictException e) {
+            Exception oldException = badActionMap.put(action, new ConflictException(e));
+            Preconditions.checkState(oldException == null, "%s | %s | %s", action, e, oldException);
+            // We skip the rest of the loop, and do not add the path->artifact mapping for this
+            // artifact below -- we don't need to check it since this action is already in
+            // error.
+            continue;
+          }
+          for (Artifact output : action.getOutputs()) {
+            artifactPathMap.put(output.getExecPath(), output);
           }
         }
       }
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 a8448c1..39e483e 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
@@ -44,11 +44,12 @@
 import com.google.devtools.build.lib.actions.ActionInputPrefetcher;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLogBufferPathGenerator;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SourceArtifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactPathResolver;
 import com.google.devtools.build.lib.actions.ArtifactResolver.ArtifactResolverSupplier;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
@@ -1113,8 +1114,8 @@
         : (WorkspaceStatusAction) workspaceStatusValue.getAction(0);
   }
 
-  public void injectCoverageReportData(ImmutableList<ActionAnalysisMetadata> actions) {
-    PrecomputedValue.COVERAGE_REPORT_KEY.set(injectable(), actions);
+  public void injectCoverageReportData(Actions.GeneratingActions actions) {
+    PrecomputedValue.COVERAGE_REPORT_KEY.set(injectable(), actions.getActions());
   }
 
   private void setDefaultVisibility(RuleVisibility defaultVisibility) {
@@ -2457,13 +2458,8 @@
       return null;
     }
 
-    ArtifactOwner artifactOwner = artifact.getArtifactOwner();
-    Preconditions.checkState(
-        artifactOwner instanceof ActionLookupValue.ActionLookupKey,
-        "%s %s",
-        artifact,
-        artifactOwner);
-    SkyKey actionLookupKey = (ActionLookupValue.ActionLookupKey) artifactOwner;
+    ActionLookupData generatingActionKey =
+        ((Artifact.DerivedArtifact) artifact).getGeneratingActionKey();
 
     synchronized (valueLookupLock) {
       // Note that this will crash (attempting to run a configured target value builder after
@@ -2472,13 +2468,18 @@
       // this action. We don't expect callers to query generating actions in such cases.
       EvaluationResult<ActionLookupValue> result =
           evaluate(
-              ImmutableList.of(actionLookupKey),
+              ImmutableList.of(generatingActionKey.getActionLookupKey()),
               /*keepGoing=*/ false,
               /*numThreads=*/ ResourceUsage.getAvailableProcessors(),
               eventHandler);
-      return result.hasError()
-          ? null
-          : result.get(actionLookupKey).getGeneratingActionDangerousReadJavadoc(artifact);
+      if (result.hasError()) {
+        return null;
+      }
+      ActionLookupValue actionLookupValue = result.get(generatingActionKey.getActionLookupKey());
+      int actionIndex = generatingActionKey.getActionIndex();
+      return actionLookupValue.isActionTemplate(actionIndex)
+          ? actionLookupValue.getActionTemplate(actionIndex)
+          : actionLookupValue.getAction(actionIndex);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionFunction.java
index 112fd7e..0524167 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionFunction.java
@@ -13,21 +13,15 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Multimap;
-import com.google.common.collect.Multimaps;
-import com.google.devtools.build.lib.actions.ActionLookupData;
-import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
 import com.google.devtools.build.lib.analysis.test.TestProvider;
-import com.google.devtools.build.lib.bugreport.BugReport;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.util.Map;
 
 /**
  * TestCompletionFunction builds all relevant test artifacts of a {@link
@@ -53,49 +47,17 @@
     ConfiguredTarget ct = ctValue.getConfiguredTarget();
     if (key.exclusiveTesting()) {
       // Request test execution iteratively if testing exclusively.
-      for (Artifact testArtifact : TestProvider.getTestStatusArtifacts(ct)) {
-        ActionLookupValue.ActionLookupKey actionLookupKey =
-            ArtifactFunction.getActionLookupKey(testArtifact);
-        ActionLookupValue actionLookupValue =
-            ArtifactFunction.getActionLookupValue(actionLookupKey, env, testArtifact);
-        if (actionLookupValue == null) {
-          BugReport.sendBugReport(
-              new IllegalStateException(
-                  "Unexpected absent value for "
-                      + actionLookupKey
-                      + " from "
-                      + testArtifact
-                      + " and "
-                      + ct
-                      + " for "
-                      + skyKey));
-          return null;
-        }
-        env.getValue(getActionLookupData(testArtifact, actionLookupKey, actionLookupValue));
+      for (Artifact.DerivedArtifact testArtifact : TestProvider.getTestStatusArtifacts(ct)) {
+        env.getValue(testArtifact.getGeneratingActionKey());
         if (env.valuesMissing()) {
           return null;
         }
       }
     } else {
-      Multimap<ActionLookupValue.ActionLookupKey, Artifact.DerivedArtifact> keyToArtifactMap =
-          Multimaps.index(
-              TestProvider.getTestStatusArtifacts(ct), ArtifactFunction::getActionLookupKey);
-      Map<SkyKey, SkyValue> actionLookupValues = env.getValues(keyToArtifactMap.keySet());
-      if (env.valuesMissing()) {
-        return null;
-      }
       env.getValues(
-          keyToArtifactMap
-              .entries()
-              .stream()
-              .map(
-                  entry ->
-                      getActionLookupData(
-                          entry.getValue(),
-                          entry.getKey(),
-                          (ActionLookupValue) actionLookupValues.get(entry.getKey())))
-              .distinct()
-              .collect(ImmutableSet.toImmutableSet()));
+          Iterables.transform(
+              TestProvider.getTestStatusArtifacts(ct),
+              Artifact.DerivedArtifact::getGeneratingActionKey));
       if (env.valuesMissing()) {
         return null;
       }
@@ -103,14 +65,6 @@
     return TestCompletionValue.TEST_COMPLETION_MARKER;
   }
 
-  private static ActionLookupData getActionLookupData(
-      Artifact artifact,
-      ActionLookupValue.ActionLookupKey actionLookupKey,
-      ActionLookupValue actionLookupValue) {
-    return ActionExecutionValue.key(
-        actionLookupKey, actionLookupValue.getGeneratingActionIndex(artifact));
-  }
-
   @Override
   public String extractTag(SkyKey skyKey) {
     return Label.print(((ConfiguredTargetKey) skyKey.argument()).getLabel());
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
index 55876e3..da22b10 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
@@ -39,7 +39,8 @@
       Artifact volatileArtifact,
       WorkspaceStatusAction workspaceStatusAction) {
     super(
-        Actions.GeneratingActions.fromSingleAction(workspaceStatusAction), /*nonceVersion=*/ null);
+        Actions.GeneratingActions.fromSingleAction(workspaceStatusAction, BUILD_INFO_KEY),
+        /*nonceVersion=*/ null);
     this.stableArtifact = stableArtifact;
     this.volatileArtifact = volatileArtifact;
   }
diff --git a/src/test/java/com/google/devtools/build/lib/BUILD b/src/test/java/com/google/devtools/build/lib/BUILD
index fff3bc9..603931e 100644
--- a/src/test/java/com/google/devtools/build/lib/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/BUILD
@@ -617,6 +617,7 @@
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils",
         "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs",
+        "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
         "//src/main/java/com/google/devtools/common/options",
         "//src/main/protobuf:action_cache_java_proto",
         "//third_party:jsr305",
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
index 1befe4c..5c0532b 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
@@ -226,6 +226,8 @@
         artifactFactory.getDerivedArtifact(fooRelative, outRoot, NULL_ARTIFACT_OWNER);
     Artifact.DerivedArtifact b =
         artifactFactory.getDerivedArtifact(barRelative, outRoot, NULL_ARTIFACT_OWNER);
+    a.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
+    b.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     MutableActionGraph actionGraph = new MapBasedActionGraph(actionKeyContext);
     Action originalAction = new ActionsTestUtil.NullAction(NULL_ACTION_OWNER, a);
     actionGraph.registerAction(originalAction);
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
index aef63fe..4dd23eb 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
@@ -37,6 +37,7 @@
 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.SkyFunctionName;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.List;
@@ -107,12 +108,6 @@
   }
 
   @Test
-  public void testEmptyLabelIsNone() {
-    Artifact artifact = ActionsTestUtil.createArtifact(rootDir, "src/a");
-    assertThat(artifact.getOwnerLabel()).isNull();
-  }
-
-  @Test
   public void testComparison() {
     PathFragment aPath = PathFragment.create("src/a");
     PathFragment bPath = PathFragment.create("src/b");
@@ -147,7 +142,7 @@
         NullPointerException.class,
         () ->
             new Artifact.DerivedArtifact(
-                null, f1.relativeTo(execDir), ArtifactOwner.NullArtifactOwner.INSTANCE));
+                null, f1.relativeTo(execDir), ActionsTestUtil.NULL_ARTIFACT_OWNER));
   }
 
   @Test
@@ -340,13 +335,15 @@
   public void testCodec() throws Exception {
     Artifact.DerivedArtifact artifact =
         (Artifact.DerivedArtifact) ActionsTestUtil.createArtifact(rootDir, "src/a");
+    artifact.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     ArtifactRoot anotherRoot =
         ArtifactRoot.asDerivedRoot(scratch.getFileSystem().getPath("/"), scratch.dir("/src"));
     Artifact.DerivedArtifact anotherArtifact =
         new Artifact.DerivedArtifact(
             anotherRoot,
             anotherRoot.getExecPath().getRelative("src/c"),
-            new LabelArtifactOwner(Label.parseAbsoluteUnchecked("//foo:bar")));
+            ActionsTestUtil.NULL_ARTIFACT_OWNER);
+    anotherArtifact.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     new SerializationTester(artifact, anotherArtifact)
         .addDependency(FileSystem.class, scratch.getFileSystem())
         .runTests();
@@ -443,12 +440,26 @@
   public void hashCodeAndEquals() throws IOException {
     Path execRoot = scratch.getFileSystem().getPath("/");
     ArtifactRoot root = ArtifactRoot.asDerivedRoot(execRoot, scratch.dir("/newRoot"));
-    ArtifactOwner firstOwner = () -> Label.parseAbsoluteUnchecked("//bar:bar");
-    ArtifactOwner secondOwner = () -> Label.parseAbsoluteUnchecked("//foo:foo");
-    Artifact derived1 =
+    ActionLookupValue.ActionLookupKey firstOwner =
+        new ActionLookupValue.ActionLookupKey() {
+          @Override
+          public SkyFunctionName functionName() {
+            return null;
+          }
+        };
+    ActionLookupValue.ActionLookupKey secondOwner =
+        new ActionLookupValue.ActionLookupKey() {
+          @Override
+          public SkyFunctionName functionName() {
+            return null;
+          }
+        };
+    Artifact.DerivedArtifact derived1 =
         new Artifact.DerivedArtifact(root, PathFragment.create("newRoot/shared"), firstOwner);
-    Artifact derived2 =
+    derived1.setGeneratingActionKey(ActionLookupData.create(firstOwner, 0));
+    Artifact.DerivedArtifact derived2 =
         new Artifact.DerivedArtifact(root, PathFragment.create("newRoot/shared"), secondOwner);
+    derived2.setGeneratingActionKey(ActionLookupData.create(secondOwner, 0));
     ArtifactRoot sourceRoot = ArtifactRoot.asSourceRoot(Root.fromPath(root.getRoot().asPath()));
     Artifact source1 = new SourceArtifact(sourceRoot, PathFragment.create("shared"), firstOwner);
     Artifact source2 = new SourceArtifact(sourceRoot, PathFragment.create("shared"), secondOwner);
diff --git a/src/test/java/com/google/devtools/build/lib/actions/CustomCommandLineTest.java b/src/test/java/com/google/devtools/build/lib/actions/CustomCommandLineTest.java
index 21ba9fc..88b840b 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/CustomCommandLineTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/CustomCommandLineTest.java
@@ -901,10 +901,12 @@
             .addPlaceholderTreeArtifactExecPath("--argTwo", treeArtifactTwo)
             .build();
 
-    TreeFileArtifact treeFileArtifactOne = createTreeFileArtifact(
-        treeArtifactOne, "children/child1");
-    TreeFileArtifact treeFileArtifactTwo = createTreeFileArtifact(
-        treeArtifactTwo, "children/child2");
+    TreeFileArtifact treeFileArtifactOne =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+            treeArtifactOne, "children/child1");
+    TreeFileArtifact treeFileArtifactTwo =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+            treeArtifactTwo, "children/child2");
 
     CustomCommandLine commandLine = commandLineTemplate.evaluateTreeFileArtifacts(
         ImmutableList.of(treeFileArtifactOne, treeFileArtifactTwo));
@@ -974,17 +976,10 @@
     return new SpecialArtifact(
         rootDir,
         rootDir.getExecPath().getRelative(relpath),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        ActionsTestUtil.NULL_ACTION_LOOKUP_DATA.getActionLookupKey(),
         SpecialArtifactType.TREE);
   }
 
-  private TreeFileArtifact createTreeFileArtifact(
-      SpecialArtifact inputTreeArtifact, String parentRelativePath) {
-    return ActionInputHelper.treeFileArtifact(
-        inputTreeArtifact,
-        PathFragment.create(parentRelativePath));
-  }
-
   private static <T> ImmutableList<T> list(T... objects) {
     return ImmutableList.<T>builder().addAll(Arrays.asList(objects)).build();
   }
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java b/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
index 7721533..1ae3dcb 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
@@ -124,10 +124,12 @@
     file.setExecutable(/*executable=*/ false);
     Artifact.DerivedArtifact input =
         (Artifact.DerivedArtifact) ActionsTestUtil.createArtifact(inputRoot, file);
+    input.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     Artifact.DerivedArtifact output =
         (Artifact.DerivedArtifact)
             ActionsTestUtil.createArtifact(
                 outputRoot, outputRoot.getRoot().getRelative("some-output"));
+    output.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     SymlinkAction action = SymlinkAction.toExecutable(NULL_ACTION_OWNER, input, output, "progress");
     new SerializationTester(action)
         .addDependency(FileSystem.class, scratch.getFileSystem())
diff --git a/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java b/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
index 863f4cd..347badc 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/util/ActionsTestUtil.java
@@ -36,6 +36,9 @@
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionInputPrefetcher;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -82,6 +85,7 @@
 import com.google.devtools.build.skyframe.EvaluationContext;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.ValueOrUntypedException;
@@ -224,7 +228,13 @@
   public static Artifact createArtifactWithExecPath(ArtifactRoot root, PathFragment execPath) {
     return root.isSourceRoot()
         ? new Artifact.SourceArtifact(root, execPath, ArtifactOwner.NullArtifactOwner.INSTANCE)
-        : new Artifact.DerivedArtifact(root, execPath, ArtifactOwner.NullArtifactOwner.INSTANCE);
+        : new Artifact.DerivedArtifact(root, execPath, NULL_ARTIFACT_OWNER);
+  }
+
+  public static TreeFileArtifact createTreeFileArtifactWithNoGeneratingAction(
+      SpecialArtifact parent, String relativePath) {
+    return ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+        parent, PathFragment.create(relativePath), parent.getArtifactOwner());
   }
 
   public static void assertNoArtifactEndingWith(RuleConfiguredTarget target, String path) {
@@ -306,7 +316,19 @@
     }
   }
 
-  @AutoCodec public static final ArtifactOwner NULL_ARTIFACT_OWNER = new NullArtifactOwner();
+  @AutoCodec
+  public static final ActionLookupKey NULL_ARTIFACT_OWNER =
+      new ActionLookupValue.ActionLookupKey() {
+        @Override
+        public SkyFunctionName functionName() {
+          return null;
+        }
+
+        @Override
+        public Label getLabel() {
+          return NULL_LABEL;
+        }
+      };
 
   public static final Artifact DUMMY_ARTIFACT =
       new Artifact.SourceArtifact(
@@ -326,6 +348,10 @@
           null,
           null);
 
+  @AutoCodec
+  public static final ActionLookupData NULL_ACTION_LOOKUP_DATA =
+      ActionLookupData.create(NULL_ARTIFACT_OWNER, 0);
+
   /** An unchecked exception class for action conflicts. */
   public static class UncheckedActionConflictException extends RuntimeException {
     public UncheckedActionConflictException(ActionConflictException e) {
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java
index 1bbcb9b..eddf680 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/ParamFileWriteActionTest.java
@@ -27,7 +27,6 @@
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.CommandLine;
 import com.google.devtools.build.lib.actions.Executor;
@@ -132,15 +131,16 @@
     return new SpecialArtifact(
         rootDir,
         rootDir.getExecPath().getRelative(relpath),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        ActionsTestUtil.NULL_ARTIFACT_OWNER,
         SpecialArtifactType.TREE);
   }
 
   private TreeFileArtifact createTreeFileArtifact(
       SpecialArtifact inputTreeArtifact, String parentRelativePath) {
-    return ActionInputHelper.treeFileArtifact(
+    return ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
         inputTreeArtifact,
-        PathFragment.create(parentRelativePath));
+        PathFragment.create(parentRelativePath),
+        inputTreeArtifact.getArtifactOwner());
   }
 
   private ParameterFileWriteAction createParameterFileWriteAction(
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplateTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplateTest.java
index 2bdaed0..56a0a10 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplateTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplateTest.java
@@ -24,7 +24,6 @@
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate.OutputPathMapper;
@@ -201,7 +200,7 @@
     List<SpawnAction> expandedActions =
         ImmutableList.copyOf(
             actionTemplate.generateActionForInputArtifacts(
-                inputTreeFileArtifacts, ArtifactOwner.NullArtifactOwner.INSTANCE));
+                inputTreeFileArtifacts, ActionsTestUtil.NULL_ARTIFACT_OWNER));
 
     assertThat(expandedActions).hasSize(3);
 
@@ -240,7 +239,7 @@
     List<SpawnAction> expandedActions =
         ImmutableList.copyOf(
             actionTemplate.generateActionForInputArtifacts(
-                inputTreeFileArtifacts, ArtifactOwner.NullArtifactOwner.INSTANCE));
+                inputTreeFileArtifacts, ActionsTestUtil.NULL_ARTIFACT_OWNER));
 
     for (int i = 0; i < expandedActions.size(); ++i) {
       assertThat(expandedActions.get(i).getInputs())
@@ -261,7 +260,7 @@
     List<SpawnAction> expandedActions =
         ImmutableList.copyOf(
             actionTemplate.generateActionForInputArtifacts(
-                inputTreeFileArtifacts, ArtifactOwner.NullArtifactOwner.INSTANCE));
+                inputTreeFileArtifacts, ActionsTestUtil.NULL_ARTIFACT_OWNER));
 
     assertThat(expandedActions).hasSize(3);
 
@@ -286,7 +285,7 @@
     List<SpawnAction> expandedActions =
         ImmutableList.copyOf(
             actionTemplate.generateActionForInputArtifacts(
-                inputTreeFileArtifacts, ArtifactOwner.NullArtifactOwner.INSTANCE));
+                inputTreeFileArtifacts, ActionsTestUtil.NULL_ARTIFACT_OWNER));
 
     assertThat(expandedActions).hasSize(3);
 
@@ -323,7 +322,7 @@
         IllegalArgumentException.class,
         () ->
             actionTemplate.generateActionForInputArtifacts(
-                inputTreeFileArtifacts, ArtifactOwner.NullArtifactOwner.INSTANCE));
+                inputTreeFileArtifacts, ActionsTestUtil.NULL_ARTIFACT_OWNER));
 
     mapper = new OutputPathMapper() {
       @Override
@@ -340,7 +339,7 @@
         IllegalArgumentException.class,
         () ->
             actionTemplate2.generateActionForInputArtifacts(
-                inputTreeFileArtifacts, ArtifactOwner.NullArtifactOwner.INSTANCE));
+                inputTreeFileArtifacts, ActionsTestUtil.NULL_ARTIFACT_OWNER));
   }
 
   private SpawnActionTemplate.Builder builder(
@@ -373,11 +372,14 @@
 
   private SpecialArtifact createTreeArtifact(String rootRelativePath) {
     PathFragment relpath = PathFragment.create(rootRelativePath);
-    return new SpecialArtifact(
-        root,
-        root.getExecPath().getRelative(relpath),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
-        SpecialArtifactType.TREE);
+    SpecialArtifact result =
+        new SpecialArtifact(
+            root,
+            root.getExecPath().getRelative(relpath),
+            ActionsTestUtil.NULL_ARTIFACT_OWNER,
+            SpecialArtifactType.TREE);
+    result.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
+    return result;
   }
 
   private Artifact createDerivedArtifact(String rootRelativePath) {
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
index 444eb68..cd81206 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
@@ -22,6 +22,7 @@
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Executor;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.exec.util.TestExecutorBuilder;
@@ -57,6 +58,7 @@
     FileSystemUtils.createDirectoryAndParents(linkedInput.getParentDirectory());
     linkedInput.createSymbolicLink(input);
     outputArtifact = getBinArtifactWithNoOwner("destination.txt");
+    outputArtifact.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     output = outputArtifact.getPath();
     FileSystemUtils.createDirectoryAndParents(output.getParentDirectory());
     action = SymlinkAction.toArtifact(NULL_ACTION_OWNER,
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 0a85f26..32824a5 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
@@ -41,6 +41,7 @@
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
+import com.google.devtools.build.lib.actions.Artifact.DerivedArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactPathResolver;
@@ -789,6 +790,9 @@
         mutableActionGraph.getGeneratingAction(artifact);
 
     if (actionAnalysisMetadata == null) {
+      if (artifact.isSourceArtifact() || !((DerivedArtifact) artifact).hasGeneratingActionKey()) {
+        return null;
+      }
       actionAnalysisMetadata = getActionGraph().getGeneratingAction(artifact);
     }
 
@@ -1214,11 +1218,13 @@
       } catch (InterruptedException e) {
         throw new IllegalStateException(e);
       }
-      for (ActionAnalysisMetadata action : actionLookupValue.getActions()) {
-        for (Artifact output : action.getOutputs()) {
-          if (output.getRootRelativePath().equals(rootRelativePath)
-              && output.getRoot().equals(root)) {
-            return (Artifact.DerivedArtifact) output;
+      if (actionLookupValue != null) {
+        for (ActionAnalysisMetadata action : actionLookupValue.getActions()) {
+          for (Artifact output : action.getOutputs()) {
+            if (output.getRootRelativePath().equals(rootRelativePath)
+                && output.getRoot().equals(root)) {
+              return (Artifact.DerivedArtifact) output;
+            }
           }
         }
       }
@@ -1228,31 +1234,20 @@
   }
 
   /**
-   * Gets a tree artifact, creating it if necessary. {@code ArtifactOwner} should be a genuine
-   * {@link ConfiguredTargetKey} corresponding to a {@link ConfiguredTarget}. If called from a test
-   * that does not exercise the analysis phase, the convenience methods {@link
-   * #getBinArtifactWithNoOwner} or {@link #getGenfilesArtifactWithNoOwner} should be used instead.
-   */
-  protected Artifact getTreeArtifact(
-      PathFragment rootRelativePath, ArtifactRoot root, ArtifactOwner owner) {
-    return view.getArtifactFactory().getTreeArtifact(rootRelativePath, root, owner);
-  }
-
-  /**
    * Gets a Tree Artifact for testing in the subdirectory of the {@link
    * BuildConfiguration#getBinDirectory} corresponding to the package of {@code owner}. So to
    * specify a file foo/foo.o owned by target //foo:foo, {@code packageRelativePath} should just be
    * "foo.o".
    */
   protected final Artifact getTreeArtifact(String packageRelativePath, ConfiguredTarget owner) {
-    return getPackageRelativeTreeArtifact(
-        packageRelativePath,
+    ActionLookupValue.ActionLookupKey actionLookupKey =
+        ConfiguredTargetKey.of(owner, owner.getConfigurationKey(), /*isHostConfiguration=*/ false);
+    return getDerivedArtifact(
+        owner.getLabel().getPackageFragment().getRelative(packageRelativePath),
         getConfiguration(owner).getBinDirectory(RepositoryName.MAIN),
-        ConfiguredTargetKey.of(
-            owner, skyframeExecutor.getConfiguration(reporter, owner.getConfigurationKey())));
+        actionLookupKey);
   }
 
-
   /**
    * Gets a derived Artifact for testing with path of the form
    * root/owner.getPackageFragment()/packageRelativePath.
@@ -1266,19 +1261,6 @@
         root, owner);
   }
 
-  /**
-   * Gets a tree Artifact for testing with path of the form
-   * root/owner.getPackageFragment()/packageRelativePath.
-   *
-   * @see #getDerivedArtifact(PathFragment, ArtifactRoot, ArtifactOwner)
-   */
-  private Artifact getPackageRelativeTreeArtifact(
-      String packageRelativePath, ArtifactRoot root, ArtifactOwner owner) {
-    return getTreeArtifact(
-        owner.getLabel().getPackageFragment().getRelative(packageRelativePath),
-        root, owner);
-  }
-
   /** Returns the input {@link Artifact}s to the given {@link Action} with the given exec paths. */
   protected List<Artifact> getInputs(Action owner, Collection<String> execPaths) {
     Set<String> expectedPaths = new HashSet<>(execPaths);
@@ -2164,38 +2146,28 @@
     return label.replace(':', '/').substring(1);
   }
 
-  protected Artifact getImplicitOutputArtifact(
+  protected final String getImplicitOutputPath(
       ConfiguredTarget target, SafeImplicitOutputsFunction outputFunction) {
-    return getImplicitOutputArtifact(target, getConfiguration(target), outputFunction);
-  }
-
-  protected final Artifact getImplicitOutputArtifact(
-      ConfiguredTarget target,
-      BuildConfiguration configuration,
-      SafeImplicitOutputsFunction outputFunction) {
     Rule rule;
     try {
       rule = (Rule) skyframeExecutor.getPackageManager().getTarget(reporter, target.getLabel());
     } catch (NoSuchPackageException | NoSuchTargetException | InterruptedException e) {
       throw new IllegalStateException(e);
     }
-    Rule associatedRule = rule.getAssociatedRule();
-    RepositoryName repository = associatedRule.getRepository();
+    RawAttributeMapper attr = RawAttributeMapper.of(rule.getAssociatedRule());
 
-    ArtifactRoot root;
-    if (associatedRule.hasBinaryOutput()) {
-      root = configuration.getBinDirectory(repository);
-    } else {
-      root = configuration.getGenfilesDirectory(repository);
-    }
-    ArtifactOwner owner = ConfiguredTargetKey.of(target.getLabel(), getConfiguration(target));
+    return Iterables.getOnlyElement(outputFunction.getImplicitOutputs(eventCollector, attr));
+  }
 
-    RawAttributeMapper attr = RawAttributeMapper.of(associatedRule);
-
-    String path = Iterables.getOnlyElement(outputFunction.getImplicitOutputs(eventCollector, attr));
-
-    return view.getArtifactFactory()
-        .getDerivedArtifact(target.getLabel().getPackageFragment().getRelative(path), root, owner);
+  /**
+   * Gets the artifact whose name is derived from {@code outputFunction}. Despite the name, this can
+   * be called for artifacts that are not declared as implicit outputs: it just finds the artifact
+   * inside the configured target by calling {@link #getBinArtifact(String, ConfiguredTarget)} on
+   * the result of the {@code outputFunction}.
+   */
+  protected final Artifact getImplicitOutputArtifact(
+      ConfiguredTarget target, SafeImplicitOutputsFunction outputFunction) {
+    return getBinArtifact(getImplicitOutputPath(target, outputFunction), target);
   }
 
   public Path getExecRoot() {
diff --git a/src/test/java/com/google/devtools/build/lib/exec/SpawnInputExpanderTest.java b/src/test/java/com/google/devtools/build/lib/exec/SpawnInputExpanderTest.java
index fb5e5ad..a9c22c2 100644
--- a/src/test/java/com/google/devtools/build/lib/exec/SpawnInputExpanderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/exec/SpawnInputExpanderTest.java
@@ -29,7 +29,6 @@
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactPathResolver;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.EmptyRunfilesSupplier;
@@ -235,8 +234,10 @@
   public void testRunfilesWithTreeArtifacts() throws Exception {
     SpecialArtifact treeArtifact = createTreeArtifact("treeArtifact");
     assertThat(treeArtifact.isTreeArtifact()).isTrue();
-    TreeFileArtifact file1 = ActionInputHelper.treeFileArtifact(treeArtifact, "file1");
-    TreeFileArtifact file2 = ActionInputHelper.treeFileArtifact(treeArtifact, "file2");
+    TreeFileArtifact file1 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(treeArtifact, "file1");
+    TreeFileArtifact file2 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(treeArtifact, "file2");
     FileSystemUtils.writeContentAsLatin1(file1.getPath(), "foo");
     FileSystemUtils.writeContentAsLatin1(file2.getPath(), "bar");
 
@@ -265,8 +266,10 @@
   public void testRunfilesWithTreeArtifactsInSymlinks() throws Exception {
     SpecialArtifact treeArtifact = createTreeArtifact("treeArtifact");
     assertThat(treeArtifact.isTreeArtifact()).isTrue();
-    TreeFileArtifact file1 = ActionInputHelper.treeFileArtifact(treeArtifact, "file1");
-    TreeFileArtifact file2 = ActionInputHelper.treeFileArtifact(treeArtifact, "file2");
+    TreeFileArtifact file1 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(treeArtifact, "file1");
+    TreeFileArtifact file2 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(treeArtifact, "file2");
     FileSystemUtils.writeContentAsLatin1(file1.getPath(), "foo");
     FileSystemUtils.writeContentAsLatin1(file2.getPath(), "bar");
     Runfiles runfiles =
@@ -298,8 +301,10 @@
   public void testTreeArtifactsInInputs() throws Exception {
     SpecialArtifact treeArtifact = createTreeArtifact("treeArtifact");
     assertThat(treeArtifact.isTreeArtifact()).isTrue();
-    TreeFileArtifact file1 = ActionInputHelper.treeFileArtifact(treeArtifact, "file1");
-    TreeFileArtifact file2 = ActionInputHelper.treeFileArtifact(treeArtifact, "file2");
+    TreeFileArtifact file1 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(treeArtifact, "file1");
+    TreeFileArtifact file2 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(treeArtifact, "file2");
     FileSystemUtils.writeContentAsLatin1(file1.getPath(), "foo");
     FileSystemUtils.writeContentAsLatin1(file2.getPath(), "bar");
 
@@ -329,7 +334,7 @@
     return new SpecialArtifact(
         derivedRoot,
         derivedRoot.getExecPath().getRelative(derivedRoot.getRoot().relativize(outputPath)),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        ActionsTestUtil.NULL_ARTIFACT_OWNER,
         SpecialArtifactType.TREE);
   }
 
@@ -399,7 +404,7 @@
     return new SpecialArtifact(
         rootDir,
         PathFragment.create(execPath),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        ActionsTestUtil.NULL_ARTIFACT_OWNER,
         SpecialArtifactType.FILESET);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/remote/AbstractRemoteActionCacheTests.java b/src/test/java/com/google/devtools/build/lib/remote/AbstractRemoteActionCacheTests.java
index 49fe5f3..2c4b95b 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/AbstractRemoteActionCacheTests.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/AbstractRemoteActionCacheTests.java
@@ -46,7 +46,6 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.ExecException;
 import com.google.devtools.build.lib.actions.FileArtifactValue.RemoteFileArtifactValue;
@@ -814,7 +813,7 @@
         new SpecialArtifact(
             artifactRoot,
             PathFragment.create("outputs/dir"),
-            ArtifactOwner.NullArtifactOwner.INSTANCE,
+            ActionsTestUtil.NULL_ARTIFACT_OWNER,
             SpecialArtifactType.TREE);
 
     MetadataInjector injector = mock(MetadataInjector.class);
@@ -882,7 +881,7 @@
         new SpecialArtifact(
             artifactRoot,
             PathFragment.create("outputs/dir"),
-            ArtifactOwner.NullArtifactOwner.INSTANCE,
+            ActionsTestUtil.NULL_ARTIFACT_OWNER,
             SpecialArtifactType.TREE);
     MetadataInjector injector = mock(MetadataInjector.class);
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/android/AndroidLibraryTest.java b/src/test/java/com/google/devtools/build/lib/rules/android/AndroidLibraryTest.java
index 59f60a4..96dd324 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/android/AndroidLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/android/AndroidLibraryTest.java
@@ -43,6 +43,7 @@
 import com.google.devtools.build.lib.analysis.config.CoreOptionConverters.StrictDepsMode;
 import com.google.devtools.build.lib.analysis.configuredtargets.FileConfiguredTarget;
 import com.google.devtools.build.lib.analysis.configuredtargets.OutputFileConfiguredTarget;
+import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -1881,7 +1882,6 @@
         getGeneratingSpawnAction(
             getImplicitOutputArtifact(
                 a.getConfiguredTarget(),
-                a.getConfiguration(),
                 AndroidRuleClasses.ANDROID_COMPILED_SYMBOLS));
     assertThat(compileAction).isNotNull();
 
@@ -1889,7 +1889,6 @@
         getGeneratingSpawnAction(
             getImplicitOutputArtifact(
                 a.getConfiguredTarget(),
-                a.getConfiguration(),
                 AndroidRuleClasses.ANDROID_RESOURCES_AAPT2_LIBRARY_APK));
     assertThat(linkAction).isNotNull();
 
@@ -1898,21 +1897,17 @@
             sdk.getConfiguredTarget().get(AndroidSdkProvider.PROVIDER).getAndroidJar(),
             getImplicitOutputArtifact(
                 a.getConfiguredTarget(),
-                a.getConfiguration(),
                 AndroidRuleClasses.ANDROID_COMPILED_SYMBOLS),
             getImplicitOutputArtifact(
                 b.getConfiguredTarget(),
-                a.getConfiguration(),
                 AndroidRuleClasses.ANDROID_COMPILED_SYMBOLS));
     assertThat(linkAction.getOutputs())
         .containsAtLeast(
             getImplicitOutputArtifact(
                 a.getConfiguredTarget(),
-                a.getConfiguration(),
                 AndroidRuleClasses.ANDROID_RESOURCES_AAPT2_R_TXT),
             getImplicitOutputArtifact(
                 a.getConfiguredTarget(),
-                a.getConfiguration(),
                 AndroidRuleClasses.ANDROID_RESOURCES_AAPT2_SOURCE_JAR));
   }
 
@@ -1927,16 +1922,11 @@
         "    resource_files = ['res/values/a.xml'],",
         ")");
 
-    ConfiguredTarget a = getConfiguredTarget("//java/a:a");
-    SpawnAction compileAction =
-        getGeneratingSpawnAction(
-            getImplicitOutputArtifact(a, AndroidRuleClasses.ANDROID_COMPILED_SYMBOLS));
-    assertThat(compileAction).isNull();
-
-    SpawnAction linkAction =
-        getGeneratingSpawnAction(
-            getImplicitOutputArtifact(a, AndroidRuleClasses.ANDROID_RESOURCES_AAPT2_LIBRARY_APK));
-    assertThat(linkAction).isNull();
+    RuleConfiguredTarget a = (RuleConfiguredTarget) getConfiguredTarget("//java/a:a");
+    ActionsTestUtil.assertNoArtifactEndingWith(
+        a, getImplicitOutputPath(a, AndroidRuleClasses.ANDROID_COMPILED_SYMBOLS));
+    ActionsTestUtil.assertNoArtifactEndingWith(
+        a, getImplicitOutputPath(a, AndroidRuleClasses.ANDROID_RESOURCES_AAPT2_LIBRARY_APK));
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
index 9992c70..d4c6d21 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
@@ -24,13 +24,11 @@
 import com.google.common.primitives.Ints;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
-import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.ResourceSet;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
@@ -901,7 +899,7 @@
     return new SpecialArtifact(
         ArtifactRoot.asDerivedRoot(execRoot, execRoot.getRelative("out")),
         execPath,
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        ActionsTestUtil.NULL_ARTIFACT_OWNER,
         SpecialArtifactType.TREE);
   }
 
@@ -919,8 +917,12 @@
 
     SpecialArtifact testTreeArtifact = createTreeArtifact("library_directory");
 
-    TreeFileArtifact library0 = ActionInputHelper.treeFileArtifact(testTreeArtifact, "library0.o");
-    TreeFileArtifact library1 = ActionInputHelper.treeFileArtifact(testTreeArtifact, "library1.o");
+    TreeFileArtifact library0 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+            testTreeArtifact, "library0.o");
+    TreeFileArtifact library1 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+            testTreeArtifact, "library1.o");
 
     ArtifactExpander expander =
         new ArtifactExpander() {
@@ -970,8 +972,12 @@
 
     SpecialArtifact testTreeArtifact = createTreeArtifact("library_directory");
 
-    TreeFileArtifact library0 = ActionInputHelper.treeFileArtifact(testTreeArtifact, "library0.o");
-    TreeFileArtifact library1 = ActionInputHelper.treeFileArtifact(testTreeArtifact, "library1.o");
+    TreeFileArtifact library0 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+            testTreeArtifact, "library0.o");
+    TreeFileArtifact library1 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+            testTreeArtifact, "library1.o");
 
     ArtifactExpander expander =
         (artifact, output) -> {
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscoveryTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscoveryTest.java
index 9c621f7..0e71f65 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscoveryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscoveryTest.java
@@ -21,7 +21,6 @@
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactResolver;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
@@ -78,7 +77,7 @@
     return new SpecialArtifact(
         artifactRoot,
         artifactRoot.getExecPath().getRelative(artifactRoot.getRoot().relativize(path)),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        ActionsTestUtil.NULL_ARTIFACT_OWNER,
         Artifact.SpecialArtifactType.TREE);
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java b/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java
index 388e5e6..16912f3 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/objc/BazelJ2ObjcLibraryTest.java
@@ -32,8 +32,8 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.CommandAction;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.actions.SpawnAction;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -1168,7 +1168,7 @@
     return ImmutableList.<CommandAction>builder()
         .addAll(
             template.generateActionForInputArtifacts(
-                ImmutableList.of(treeFileArtifact), ArtifactOwner.NullArtifactOwner.INSTANCE))
+                ImmutableList.of(treeFileArtifact), ActionsTestUtil.NULL_ARTIFACT_OWNER))
         .build();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/objc/HeaderThinningTest.java b/src/test/java/com/google/devtools/build/lib/rules/objc/HeaderThinningTest.java
index 50614c4..8004914 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/objc/HeaderThinningTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/objc/HeaderThinningTest.java
@@ -23,9 +23,9 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Artifact.DerivedArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactPathResolver;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.ExecException;
@@ -208,12 +208,12 @@
   }
 
   private Artifact getTreeArtifact(String name) {
-    Artifact treeArtifactBase =
+    DerivedArtifact treeArtifactBase =
         getDerivedArtifact(
             PathFragment.create(name),
             ArtifactRoot.asDerivedRoot(
                 directories.getExecRoot(), directories.getExecRoot().getChild("out")),
-            ArtifactOwner.NullArtifactOwner.INSTANCE);
+            ActionsTestUtil.NULL_ARTIFACT_OWNER);
     return new SpecialArtifact(
         treeArtifactBase.getRoot(),
         treeArtifactBase.getExecPath(),
diff --git a/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java b/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java
index aefb20d..3b3cec3 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java
@@ -23,6 +23,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.actions.util.LabelArtifactOwner;
 import com.google.devtools.build.lib.analysis.FilesToRunProvider;
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
@@ -144,8 +145,7 @@
             /* toolchainInvocations= */ ImmutableList.of(),
             "bazel-out",
             protoInfo(
-                /* directProtos */ ImmutableList.of(
-                    derivedArtifact("//:dont-care", "source_file.proto")),
+                /* directProtos */ ImmutableList.of(derivedArtifact("source_file.proto")),
                 /* transitiveProtos */ NestedSetBuilder.emptySet(STABLE_ORDER),
                 /* transitiveProtoSourceRoots= */ NestedSetBuilder.emptySet(STABLE_ORDER),
                 /* strictImportableProtoSourceRoots= */ NestedSetBuilder.create(
@@ -367,35 +367,31 @@
     assertThat(
             protoArgv(
                 null /* directDependencies */,
-                ImmutableList.of(derivedArtifact("//:dont-care", "foo.proto")),
+                ImmutableList.of(derivedArtifact("foo.proto")),
                 ImmutableList.of(".")))
         .containsExactly("-Ifoo.proto=out/foo.proto");
 
     assertThat(
             protoArgv(
                 ImmutableList.of() /* directDependencies */,
-                ImmutableList.of(derivedArtifact("//:dont-care", "foo.proto")),
+                ImmutableList.of(derivedArtifact("foo.proto")),
                 ImmutableList.of(".")))
         .containsExactly("-Ifoo.proto=out/foo.proto", "--direct_dependencies=");
 
     assertThat(
             protoArgv(
                 ImmutableList.of(
-                    Pair.of(
-                        derivedArtifact("//:dont-care", "foo.proto"),
-                        null)) /* directDependencies */,
-                ImmutableList.of(derivedArtifact("//:dont-care", "foo.proto")),
+                    Pair.of(derivedArtifact("foo.proto"), null)) /* directDependencies */,
+                ImmutableList.of(derivedArtifact("foo.proto")),
                 ImmutableList.of(".")))
         .containsExactly("-Ifoo.proto=out/foo.proto", "--direct_dependencies", "foo.proto");
 
     assertThat(
             protoArgv(
                 ImmutableList.of(
-                    Pair.of(derivedArtifact("//:dont-care", "foo.proto"), null),
-                    Pair.of(
-                        derivedArtifact("//:dont-care", "bar.proto"),
-                        null)) /* directDependencies */,
-                ImmutableList.of(derivedArtifact("//:dont-care", "foo.proto")),
+                    Pair.of(derivedArtifact("foo.proto"), null),
+                    Pair.of(derivedArtifact("bar.proto"), null)) /* directDependencies */,
+                ImmutableList.of(derivedArtifact("foo.proto")),
                 ImmutableList.of(".")))
         .containsExactly(
             "-Ifoo.proto=out/foo.proto", "--direct_dependencies", "foo.proto:bar.proto");
@@ -436,11 +432,14 @@
   }
 
   /** Creates a dummy artifact with the given path, that actually resides in /out/<path>. */
-  private Artifact derivedArtifact(String ownerLabel, String path) {
-    return new Artifact.DerivedArtifact(
-        derivedRoot,
-        derivedRoot.getExecPath().getRelative(path),
-        new LabelArtifactOwner(Label.parseAbsoluteUnchecked(ownerLabel)));
+  private Artifact derivedArtifact(String path) {
+    Artifact.DerivedArtifact derivedArtifact =
+        new Artifact.DerivedArtifact(
+            derivedRoot,
+            derivedRoot.getExecPath().getRelative(path),
+            ActionsTestUtil.NULL_ARTIFACT_OWNER);
+    derivedArtifact.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
+    return derivedArtifact;
   }
 
   private static Iterable<String> protoArgv(
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java
index 5fc2f17..6b578cd 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandlerTest.java
@@ -25,7 +25,6 @@
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactPathResolver;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
@@ -191,7 +190,7 @@
     PathFragment path = PathFragment.create("bin/foo/bar");
     SpecialArtifact treeArtifact =
         new SpecialArtifact(
-            outputRoot, path, ArtifactOwner.NullArtifactOwner.INSTANCE, SpecialArtifactType.TREE);
+            outputRoot, path, ActionsTestUtil.NULL_ARTIFACT_OWNER, SpecialArtifactType.TREE);
     Artifact artifact = new TreeFileArtifact(treeArtifact, PathFragment.create("baz"));
     ActionInputMap map = new ActionInputMap(1);
     ActionMetadataHandler handler = new ActionMetadataHandler(
@@ -210,7 +209,7 @@
     PathFragment path = PathFragment.create("bin/foo/bar");
     SpecialArtifact treeArtifact =
         new SpecialArtifact(
-            outputRoot, path, ArtifactOwner.NullArtifactOwner.INSTANCE, SpecialArtifactType.TREE);
+            outputRoot, path, ActionsTestUtil.NULL_ARTIFACT_OWNER, SpecialArtifactType.TREE);
     Artifact artifact = new TreeFileArtifact(treeArtifact, PathFragment.create("baz"));
     assertThat(artifact.getPath().exists()).isTrue();
     ActionInputMap map = new ActionInputMap(1);
@@ -229,7 +228,7 @@
     PathFragment path = PathFragment.create("bin/foo/bar");
     SpecialArtifact treeArtifact =
         new SpecialArtifact(
-            outputRoot, path, ArtifactOwner.NullArtifactOwner.INSTANCE, SpecialArtifactType.TREE);
+            outputRoot, path, ActionsTestUtil.NULL_ARTIFACT_OWNER, SpecialArtifactType.TREE);
     Artifact artifact = new TreeFileArtifact(treeArtifact, PathFragment.create("baz"));
     ActionInputMap map = new ActionInputMap(1);
     ActionMetadataHandler handler = new ActionMetadataHandler(
@@ -299,7 +298,8 @@
     PathFragment path = PathFragment.create("bin/dir");
     SpecialArtifact treeArtifact =
         new SpecialArtifact(
-            outputRoot, path, ArtifactOwner.NullArtifactOwner.INSTANCE, SpecialArtifactType.TREE);
+            outputRoot, path, ActionsTestUtil.NULL_ARTIFACT_OWNER, SpecialArtifactType.TREE);
+    treeArtifact.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     OutputStore store = new OutputStore();
     ActionMetadataHandler handler =
         new ActionMetadataHandler(
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
index 2596d8f..1ca6c08 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
@@ -21,7 +21,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Action;
-import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionTemplate;
@@ -213,7 +212,7 @@
       ActionTemplate<?> actionTemplate) {
     return new NonRuleConfiguredTargetValue(
         Mockito.mock(ConfiguredTarget.class),
-        Actions.GeneratingActions.fromSingleAction(actionTemplate),
+        Actions.GeneratingActions.fromSingleAction(actionTemplate, CTKEY),
         NestedSetBuilder.<Package>stableOrder().build(),
         /*nonceVersion=*/ null);
   }
@@ -223,7 +222,7 @@
     return new SpecialArtifact(
         ArtifactRoot.asDerivedRoot(rootDirectory, rootDirectory.getRelative("out")),
         execPath,
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        CTKEY,
         SpecialArtifactType.TREE);
   }
 
@@ -233,8 +232,9 @@
     Map<TreeFileArtifact, FileArtifactValue> treeFileArtifactMap = new LinkedHashMap<>();
 
     for (String childRelativePath : childRelativePaths) {
-      TreeFileArtifact treeFileArtifact = ActionInputHelper.treeFileArtifact(
-          treeArtifact, PathFragment.create(childRelativePath));
+      TreeFileArtifact treeFileArtifact =
+          ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+              treeArtifact, childRelativePath);
       scratch.file(treeFileArtifact.getPath().toString(), childRelativePath);
       // We do not care about the FileArtifactValues in this test.
       treeFileArtifactMap.put(treeFileArtifact, FileArtifactValue.create(treeFileArtifact));
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
index f6f8a8b..4ba23c3 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -32,7 +32,6 @@
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactFileMetadata;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.ArtifactSkyKey;
 import com.google.devtools.build.lib.actions.BasicActionLookupValue;
@@ -192,10 +191,8 @@
   @Test
   public void testActionTreeArtifactOutput() throws Throwable {
     SpecialArtifact artifact = createDerivedTreeArtifactWithAction("treeArtifact");
-    TreeFileArtifact treeFileArtifact1 =
-        createFakeTreeFileArtifact(artifact, ALL_OWNER, "child1", "hello1");
-    TreeFileArtifact treeFileArtifact2 =
-        createFakeTreeFileArtifact(artifact, ALL_OWNER, "child2", "hello2");
+    TreeFileArtifact treeFileArtifact1 = createFakeTreeFileArtifact(artifact, "child1", "hello1");
+    TreeFileArtifact treeFileArtifact2 = createFakeTreeFileArtifact(artifact, "child2", "hello2");
 
     TreeArtifactValue value = (TreeArtifactValue) evaluateArtifactValue(artifact);
     assertThat(value.getChildValues()).containsKey(treeFileArtifact1);
@@ -216,15 +213,11 @@
     TreeFileArtifact treeFileArtifact1 =
         createFakeTreeFileArtifact(
             artifact2,
-            ActionTemplateExpansionValue.ActionTemplateExpansionKey.of(
-                (ActionLookupValue.ActionLookupKey) artifact2.getArtifactOwner(), 1),
             "child1",
             "hello1");
     TreeFileArtifact treeFileArtifact2 =
         createFakeTreeFileArtifact(
             artifact2,
-            ActionTemplateExpansionValue.ActionTemplateExpansionKey.of(
-                (ActionLookupValue.ActionLookupKey) artifact2.getArtifactOwner(), 1),
             "child2",
             "hello2");
 
@@ -257,15 +250,11 @@
     TreeFileArtifact treeFileArtifact1 =
         createFakeTreeFileArtifact(
             artifact3,
-            ActionTemplateExpansionValue.ActionTemplateExpansionKey.of(
-                (ActionLookupValue.ActionLookupKey) artifact2.getArtifactOwner(), 2),
             "child1",
             "hello1");
     TreeFileArtifact treeFileArtifact2 =
         createFakeTreeFileArtifact(
             artifact3,
-            ActionTemplateExpansionValue.ActionTemplateExpansionKey.of(
-                (ActionLookupValue.ActionLookupKey) artifact2.getArtifactOwner(), 2),
             "child2",
             "hello2");
     actions.add(
@@ -280,17 +269,24 @@
 
   @Test
   public void actionExecutionValueSerialization() throws Exception {
-    Artifact artifact1 = createDerivedArtifact("one");
-    Artifact artifact2 = createDerivedArtifact("two");
+    ActionLookupData dummyData = ActionLookupData.create(ALL_OWNER, 0);
+    Artifact.DerivedArtifact artifact1 = createDerivedArtifact("one");
+    artifact1.setGeneratingActionKey(dummyData);
+    Artifact.DerivedArtifact artifact2 = createDerivedArtifact("two");
+    artifact2.setGeneratingActionKey(dummyData);
     ArtifactFileMetadata metadata1 =
         ActionMetadataHandler.fileMetadataFromArtifact(artifact1, null, null);
     SpecialArtifact treeArtifact = createDerivedTreeArtifactOnly("tree");
-    TreeFileArtifact treeFileArtifact =
-        createFakeTreeFileArtifact(treeArtifact, "subpath", "content");
+    treeArtifact.setGeneratingActionKey(dummyData);
+    TreeFileArtifact treeFileArtifact = ActionInputHelper.treeFileArtifact(treeArtifact, "subpath");
+    Path path = treeFileArtifact.getPath();
+    FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
+    writeFile(path, "contents");
     TreeArtifactValue treeArtifactValue =
         TreeArtifactValue.create(
             ImmutableMap.of(treeFileArtifact, FileArtifactValue.create(treeFileArtifact)));
-    Artifact artifact3 = createDerivedArtifact("three");
+    Artifact.DerivedArtifact artifact3 = createDerivedArtifact("three");
+    artifact3.setGeneratingActionKey(dummyData);
     FilesetOutputSymlink filesetOutputSymlink =
         FilesetOutputSymlink.createForTesting(
             PathFragment.EMPTY_FRAGMENT, PathFragment.EMPTY_FRAGMENT, PathFragment.EMPTY_FRAGMENT);
@@ -326,9 +322,9 @@
         ArtifactRoot.asSourceRoot(Root.fromPath(root)), PathFragment.create(path));
   }
 
-  private Artifact createDerivedArtifact(String path) {
+  private Artifact.DerivedArtifact createDerivedArtifact(String path) {
     PathFragment execPath = PathFragment.create("out").getRelative(path);
-    Artifact output =
+    Artifact.DerivedArtifact output =
         new Artifact.DerivedArtifact(
             ArtifactRoot.asDerivedRoot(root, root.getRelative("out")), execPath, ALL_OWNER);
     actions.add(new DummyAction(ImmutableList.<Artifact>of(), output));
@@ -358,24 +354,13 @@
   }
 
   private TreeFileArtifact createFakeTreeFileArtifact(
-      SpecialArtifact treeArtifact, String parentRelativePath, String content) throws Exception {
-    return createFakeTreeFileArtifact(
-        treeArtifact,
-        ActionTemplateExpansionValue.ActionTemplateExpansionKey.of(
-            (ActionLookupValue.ActionLookupKey) treeArtifact.getArtifactOwner(), 0),
-        parentRelativePath,
-        content);
-  }
-
-  private TreeFileArtifact createFakeTreeFileArtifact(
       SpecialArtifact treeArtifact,
-      ArtifactOwner artifactOwner,
       String parentRelativePath,
       String content)
       throws Exception {
     TreeFileArtifact treeFileArtifact =
-        ActionInputHelper.treeFileArtifact(
-            treeArtifact, PathFragment.create(parentRelativePath), artifactOwner);
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(
+            treeArtifact, parentRelativePath);
     Path path = treeFileArtifact.getPath();
     FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
     writeFile(path, content);
@@ -416,8 +401,11 @@
           ImmutableMap.of(
               ALL_OWNER,
               new BasicActionLookupValue(
-                  Actions.filterSharedActionsAndThrowActionConflict(
-                      actionKeyContext, ImmutableList.copyOf(actions)),
+                  Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
+                      actionKeyContext,
+                      ImmutableList.copyOf(actions),
+                      ALL_OWNER,
+                      /*outputFiles=*/ null),
                   /*nonceVersion=*/ null)));
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
index 1a9da7a..846d515 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -15,7 +15,6 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.common.truth.Truth.assertWithMessage;
-import static com.google.devtools.build.lib.actions.ActionInputHelper.treeFileArtifact;
 import static com.google.devtools.build.lib.testutil.MoreAsserts.assertThrows;
 
 import com.google.common.collect.ImmutableList;
@@ -25,13 +24,13 @@
 import com.google.common.util.concurrent.Runnables;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactFileMetadata;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
 import com.google.devtools.build.lib.actions.FileArtifactValue.RemoteFileArtifactValue;
@@ -378,8 +377,8 @@
             return SkyFunctionName.FOR_TESTING;
           }
         };
-    SkyKey actionKey1 = ActionExecutionValue.key(actionLookupKey, 0);
-    SkyKey actionKey2 = ActionExecutionValue.key(actionLookupKey, 1);
+    SkyKey actionKey1 = ActionLookupData.create(actionLookupKey, 0);
+    SkyKey actionKey2 = ActionLookupData.create(actionLookupKey, 1);
     differencer.inject(
         ImmutableMap.<SkyKey, SkyValue>of(
             actionKey1,
@@ -425,21 +424,23 @@
             batchStatter, ModifiedFileSet.NOTHING_MODIFIED)).isEmpty();
   }
 
-  public void checkDirtyTreeArtifactActions(BatchStat batchStatter)
-      throws Exception {
+  private void checkDirtyTreeArtifactActions(BatchStat batchStatter) throws Exception {
     // Normally, an Action specifies the contents of a TreeArtifact when it executes.
     // To decouple FileSystemValueTester checking from Action execution, we inject TreeArtifact
     // contents into ActionExecutionValues.
 
     SpecialArtifact out1 = createTreeArtifact("one");
-    TreeFileArtifact file11 = treeFileArtifact(out1, "fizz");
+    TreeFileArtifact file11 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(out1, "fizz");
     FileSystemUtils.createDirectoryAndParents(out1.getPath());
     FileSystemUtils.writeContentAsLatin1(file11.getPath(), "buzz");
 
     SpecialArtifact out2 = createTreeArtifact("two");
     FileSystemUtils.createDirectoryAndParents(out2.getPath().getChild("subdir"));
-    TreeFileArtifact file21 = treeFileArtifact(out2, "moony");
-    TreeFileArtifact file22 = treeFileArtifact(out2, "subdir/wormtail");
+    TreeFileArtifact file21 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(out2, "moony");
+    TreeFileArtifact file22 =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(out2, "subdir/wormtail");
     FileSystemUtils.writeContentAsLatin1(file21.getPath(), "padfoot");
     FileSystemUtils.writeContentAsLatin1(file22.getPath(), "prongs");
 
@@ -459,11 +460,11 @@
             return SkyFunctionName.FOR_TESTING;
           }
         };
-    SkyKey actionKey1 = ActionExecutionValue.key(actionLookupKey, 0);
-    SkyKey actionKey2 = ActionExecutionValue.key(actionLookupKey, 1);
-    SkyKey actionKeyEmpty = ActionExecutionValue.key(actionLookupKey, 2);
-    SkyKey actionKeyUnchanging = ActionExecutionValue.key(actionLookupKey, 3);
-    SkyKey actionKeyLast = ActionExecutionValue.key(actionLookupKey, 4);
+    SkyKey actionKey1 = ActionLookupData.create(actionLookupKey, 0);
+    SkyKey actionKey2 = ActionLookupData.create(actionLookupKey, 1);
+    SkyKey actionKeyEmpty = ActionLookupData.create(actionLookupKey, 2);
+    SkyKey actionKeyUnchanging = ActionLookupData.create(actionLookupKey, 3);
+    SkyKey actionKeyLast = ActionLookupData.create(actionLookupKey, 4);
     differencer.inject(
         ImmutableMap.<SkyKey, SkyValue>of(
             actionKey1,
@@ -540,11 +541,13 @@
         .containsExactly(actionKey1);
 
     // Test that directory contents (and nested contents) matter
-    Artifact out1new = treeFileArtifact(out1, "julius/caesar");
+    Artifact out1new =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(out1, "julius/caesar");
     FileSystemUtils.createDirectoryAndParents(out1.getPath().getChild("julius"));
     FileSystemUtils.writeContentAsLatin1(out1new.getPath(), "octavian");
     // even for empty directories
-    Artifact outEmptyNew = treeFileArtifact(outEmpty, "marcus");
+    Artifact outEmptyNew =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(outEmpty, "marcus");
     FileSystemUtils.writeContentAsLatin1(outEmptyNew.getPath(), "aurelius");
     // so does removing
     file21.getPath().delete();
@@ -636,7 +639,7 @@
     return new SpecialArtifact(
         derivedRoot,
         derivedRoot.getExecPath().getRelative(derivedRoot.getRoot().relativize(outputPath)),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
+        ActionsTestUtil.NULL_ARTIFACT_OWNER,
         SpecialArtifactType.TREE);
   }
 
@@ -802,7 +805,9 @@
         ImmutableMap.builder();
     for (Map.Entry<PathFragment, RemoteFileArtifactValue> child : children.entrySet()) {
       childFileValues.put(
-          ActionInputHelper.treeFileArtifact(output, child.getKey()), child.getValue());
+          ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+              output, child.getKey(), output.getArtifactOwner()),
+          child.getValue());
     }
     TreeArtifactValue treeArtifactValue = TreeArtifactValue.create(childFileValues.build());
     return ActionExecutionValue.create(
@@ -843,8 +848,8 @@
             return SkyFunctionName.FOR_TESTING;
           }
         };
-    SkyKey actionKey1 = ActionExecutionValue.key(actionLookupKey, 0);
-    SkyKey actionKey2 = ActionExecutionValue.key(actionLookupKey, 1);
+    SkyKey actionKey1 = ActionLookupData.create(actionLookupKey, 0);
+    SkyKey actionKey2 = ActionLookupData.create(actionLookupKey, 1);
 
     Artifact out1 = createDerivedArtifact("foo");
     Artifact out2 = createDerivedArtifact("bar");
@@ -897,7 +902,7 @@
             return SkyFunctionName.FOR_TESTING;
           }
         };
-    SkyKey actionKey = ActionExecutionValue.key(actionLookupKey, 0);
+    SkyKey actionKey = ActionLookupData.create(actionLookupKey, 0);
 
     SpecialArtifact treeArtifact = createTreeArtifact("dir");
     treeArtifact.getPath().createDirectoryAndParents();
@@ -929,7 +934,8 @@
         .isEmpty();
 
     // Create dir/foo on the local disk and test that it invalidates the associated sky key.
-    TreeFileArtifact fooArtifact = treeFileArtifact(treeArtifact, "foo");
+    TreeFileArtifact fooArtifact =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(treeArtifact, "foo");
     FileSystemUtils.writeContentAsLatin1(fooArtifact.getPath(), "new-foo-content");
     assertThat(
             new FilesystemValueChecker(/* tsgm= */ null, /* lastExecutionTimeRange= */ null)
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
index 7ab9ea3..1fc6492 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
@@ -28,12 +28,10 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
-import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
 import com.google.devtools.build.lib.actions.ArtifactSkyKey;
 import com.google.devtools.build.lib.actions.FileArtifactValue;
@@ -198,18 +196,20 @@
   }
 
   private SpecialArtifact treeArtifact(String path) {
-    SpecialArtifact treeArtifact = new SpecialArtifact(
-        ArtifactRoot.asDerivedRoot(rootDirectory, rootDirectory.getRelative("out")),
-        PathFragment.create("out/" + path),
-        ArtifactOwner.NullArtifactOwner.INSTANCE,
-        SpecialArtifactType.TREE);
+    SpecialArtifact treeArtifact =
+        new SpecialArtifact(
+            ArtifactRoot.asDerivedRoot(rootDirectory, rootDirectory.getRelative("out")),
+            PathFragment.create("out/" + path),
+            ActionsTestUtil.NULL_ARTIFACT_OWNER,
+            SpecialArtifactType.TREE);
     assertThat(treeArtifact.isTreeArtifact()).isTrue();
     return treeArtifact;
   }
 
   private void addNewTreeFileArtifact(SpecialArtifact parent, String relatedPath)
       throws IOException {
-    TreeFileArtifact treeFileArtifact = ActionInputHelper.treeFileArtifact(parent, relatedPath);
+    TreeFileArtifact treeFileArtifact =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(parent, relatedPath);
     artifactFunction.addNewTreeFileArtifact(treeFileArtifact);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
index ceeef9b..a9c3b74 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Executor;
@@ -436,7 +437,7 @@
         null);
 
     // Sanity check that our invalidation receiver is working correctly. We'll rely on it again.
-    SkyKey actionKey = ActionExecutionValue.key(ACTION_LOOKUP_KEY, 0);
+    SkyKey actionKey = ActionLookupData.create(ACTION_LOOKUP_KEY, 0);
     TrackingEvaluationProgressReceiver.EvaluatedEntry evaluatedAction =
         progressReceiver.getEvalutedEntry(actionKey);
     assertThat(evaluatedAction).isNotNull();
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 def08cd..e128bab 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
@@ -271,8 +271,11 @@
               ImmutableMap.of(
                   ACTION_LOOKUP_KEY,
                   new BasicActionLookupValue(
-                      Actions.filterSharedActionsAndThrowActionConflict(
-                          actionKeyContext, ImmutableList.copyOf(actions)),
+                      Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
+                          actionKeyContext,
+                          ImmutableList.copyOf(actions),
+                          ACTION_LOOKUP_KEY,
+                          /*outputFiles=*/ null),
                       /*nonceVersion=*/ null)));
         }
       }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
index b990867..98c0647 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
@@ -33,6 +33,8 @@
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionResult;
 import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -51,6 +53,7 @@
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.events.StoredEventHandler;
+import com.google.devtools.build.lib.skyframe.ActionTemplateExpansionValue.ActionTemplateExpansionKey;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.vfs.FileStatus;
@@ -106,17 +109,23 @@
     writeFile(in, "input_content");
 
     outOne = createTreeArtifact("outputOne");
-    outOneFileOne = treeFileArtifact(outOne, "out_one_file_one");
-    outOneFileTwo = treeFileArtifact(outOne, "out_one_file_two");
+    outOneFileOne =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(outOne, "out_one_file_one");
+    outOneFileTwo =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(outOne, "out_one_file_two");
 
     outTwo = createTreeArtifact("outputTwo");
-    outTwoFileOne = treeFileArtifact(outTwo, "out_one_file_one");
-    outTwoFileTwo = treeFileArtifact(outTwo, "out_one_file_two");
+    outTwoFileOne =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(outTwo, "out_one_file_one");
+    outTwoFileTwo =
+        ActionsTestUtil.createTreeFileArtifactWithNoGeneratingAction(outTwo, "out_one_file_two");
   }
 
   @Test
   public void testCodec() throws Exception {
-    new SerializationTester(outOne, outOneFileOne)
+    SpecialArtifact parent = createTreeArtifact("parent");
+    parent.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
+    new SerializationTester(parent, ActionInputHelper.treeFileArtifact(parent, "child"))
         .addDependency(FileSystem.class, scratch.getFileSystem())
         .runTests();
   }
@@ -185,9 +194,11 @@
   @Test
   public void testCacheCheckingForTreeArtifactsDoesNotCauseReexecution() throws Exception {
     SpecialArtifact outOne = createTreeArtifact("outputOne");
+    outOne.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
     Button buttonOne = new Button();
 
     SpecialArtifact outTwo = createTreeArtifact("outputTwo");
+    outTwo.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 1));
     Button buttonTwo = new Button();
 
     TouchingTestAction actionOne = new TouchingTestAction(
@@ -404,6 +415,10 @@
     reporter.removeHandler(failFastHandler);
     reporter.addHandler(storingEventHandler);
 
+    SpecialArtifact outOne = createTreeArtifact("outputOne");
+    outOne.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
+    TreeFileArtifact outOneFileOne = ActionInputHelper.treeFileArtifact(outOne, "out_one_file_one");
+    TreeFileArtifact outOneFileTwo = ActionInputHelper.treeFileArtifact(outOne, "out_one_file_two");
     TreeArtifactTestAction failureOne = new TreeArtifactTestAction(
         Runnables.doNothing(), outOneFileOne, outOneFileTwo) {
       @Override
@@ -428,6 +443,10 @@
     assertThat(errors.get(0).getMessage()).contains("not present on disk");
     assertThat(errors.get(1).getMessage()).contains("not all outputs were created or valid");
 
+    SpecialArtifact outTwo = createTreeArtifact("outputTwo");
+    outTwo.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 1));
+    TreeFileArtifact outTwoFileOne = ActionInputHelper.treeFileArtifact(outOne, "out_one_file_one");
+    TreeFileArtifact outTwoFileTwo = ActionInputHelper.treeFileArtifact(outOne, "out_one_file_two");
     TreeArtifactTestAction failureTwo = new TreeArtifactTestAction(
         Runnables.doNothing(), outTwoFileOne, outTwoFileTwo) {
       @Override
@@ -747,6 +766,7 @@
   public void testExpandedActionsBuildInActionTemplate() throws Throwable {
     // artifact1 is a tree artifact generated by a TouchingTestAction.
     SpecialArtifact artifact1 = createTreeArtifact("treeArtifact1");
+    artifact1.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
     TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
         artifact1, PathFragment.create("child1"));
     TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
@@ -761,10 +781,13 @@
 
     // We mock out the action template function to expand into two actions that just touch the
     // output files.
-    TreeFileArtifact expectedOutputTreeFileArtifact1 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child1"));
-    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child2"));
+    ActionTemplateExpansionKey secondOwner = ActionTemplateExpansionKey.of(ACTION_LOOKUP_KEY, 1);
+    TreeFileArtifact expectedOutputTreeFileArtifact1 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2, PathFragment.createAlreadyNormalized("child1"), secondOwner);
+    TreeFileArtifact expectedOutputTreeFileArtifact2 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2, PathFragment.createAlreadyNormalized("child2"), secondOwner);
     Action generateOutputAction = new DummyAction(
         ImmutableList.<Artifact>of(treeFileArtifactA), expectedOutputTreeFileArtifact1);
     Action noGenerateOutputAction = new DummyAction(
@@ -784,6 +807,7 @@
 
     // artifact1 is a tree artifact generated by a TouchingTestAction.
     SpecialArtifact artifact1 = createTreeArtifact("treeArtifact1");
+    artifact1.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
     TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
         artifact1, PathFragment.create("child1"));
     TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
@@ -799,10 +823,13 @@
     // We mock out the action template function to expand into two actions:
     // One Action that touches the output file.
     // The other action that does not generate the output file.
-    TreeFileArtifact expectedOutputTreeFileArtifact1 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child1"));
-    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child2"));
+    ActionTemplateExpansionKey secondOwner = ActionTemplateExpansionKey.of(ACTION_LOOKUP_KEY, 1);
+    TreeFileArtifact expectedOutputTreeFileArtifact1 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2, PathFragment.createAlreadyNormalized("child1"), secondOwner);
+    TreeFileArtifact expectedOutputTreeFileArtifact2 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2, PathFragment.createAlreadyNormalized("child2"), secondOwner);
     Action generateOutputAction = new DummyAction(
         ImmutableList.<Artifact>of(treeFileArtifactA), expectedOutputTreeFileArtifact1);
     Action noGenerateOutputAction = new NoOpDummyAction(
@@ -825,6 +852,7 @@
 
     // artifact1 is a tree artifact generated by a TouchingTestAction.
     SpecialArtifact artifact1 = createTreeArtifact("treeArtifact1");
+    artifact1.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
     TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
         artifact1, PathFragment.create("child1"));
     TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
@@ -840,10 +868,16 @@
     // We mock out the action template function to expand into two actions:
     // One Action that touches the output file.
     // The other action that just throws when executed.
-    TreeFileArtifact expectedOutputTreeFileArtifact1 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child1"));
-    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child2"));
+    TreeFileArtifact expectedOutputTreeFileArtifact1 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2,
+            PathFragment.createAlreadyNormalized("child1"),
+            ActionTemplateExpansionKey.of(artifact1.getArtifactOwner(), 1));
+    TreeFileArtifact expectedOutputTreeFileArtifact2 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2,
+            PathFragment.createAlreadyNormalized("child2"),
+            ActionTemplateExpansionKey.of(artifact1.getArtifactOwner(), 1));
     Action generateOutputAction = new DummyAction(
         ImmutableList.<Artifact>of(treeFileArtifactA), expectedOutputTreeFileArtifact1);
     Action throwingAction = new ThrowingDummyAction(
@@ -866,6 +900,7 @@
 
     // artifact1 is a tree artifact generated by a TouchingTestAction.
     SpecialArtifact artifact1 = createTreeArtifact("treeArtifact1");
+    artifact1.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
     TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
         artifact1, PathFragment.create("child1"));
     TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
@@ -879,10 +914,13 @@
     registerAction(actionTemplate);
 
     // We mock out the action template function to expand into two actions that throw when executed.
-    TreeFileArtifact expectedOutputTreeFileArtifact1 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child1"));
-    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
-        artifact2, PathFragment.create("child2"));
+    ActionTemplateExpansionKey secondOwner = ActionTemplateExpansionKey.of(ACTION_LOOKUP_KEY, 1);
+    TreeFileArtifact expectedOutputTreeFileArtifact1 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2, PathFragment.createAlreadyNormalized("child1"), secondOwner);
+    TreeFileArtifact expectedOutputTreeFileArtifact2 =
+        ActionInputHelper.treeFileArtifactWithNoGeneratingActionSet(
+            artifact2, PathFragment.createAlreadyNormalized("child2"), secondOwner);
     Action throwingAction = new ThrowingDummyAction(
         ImmutableList.<Artifact>of(treeFileArtifactA),
         ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact1));
@@ -1246,7 +1284,11 @@
     public SkyValue compute(SkyKey skyKey, Environment env) {
       try {
         return new ActionTemplateExpansionValue(
-            Actions.filterSharedActionsAndThrowActionConflict(actionKeyContext, actions));
+            Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
+                actionKeyContext,
+                actions,
+                (ActionLookupValue.ActionLookupKey) skyKey,
+                /*outputFiles=*/ null));
       } catch (ActionConflictException e) {
         throw new IllegalStateException(e);
       }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
index 1e1d151..2c27c62 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -255,8 +255,11 @@
           ImmutableMap.of(
               ALL_OWNER,
               new BasicActionLookupValue(
-                  Actions.filterSharedActionsAndThrowActionConflict(
-                      actionKeyContext, ImmutableList.copyOf(actions)),
+                  Actions.assignOwnersAndFilterSharedActionsAndThrowActionConflict(
+                      actionKeyContext,
+                      ImmutableList.copyOf(actions),
+                      ALL_OWNER,
+                      /*outputFiles=*/ null),
                   /*nonceVersion=*/ null)));
     }
   }