Introducing SpawnActionTemplate, a stub action for TreeArtifacts at analysis time that can expand into a list of SpawnActions operating on associated TreeFileArtifacts inside TreeArtifacts at execution time.

--
MOS_MIGRATED_REVID=122056131

5 files changed, 797 insertions, 59 deletions

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 9d74e3b30d..d98fdd2d25 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
@@ -29,6 +29,9 @@ import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.SortedMap;
+import java.util.TreeMap;
+
+import javax.annotation.Nullable;
 
 /**
  * Helper class for actions.
@@ -77,6 +80,20 @@ public final class Actions {
     return true;
   }
 
+  /**
+   * Finds action conflicts. An action conflict happens if two actions generate the same output
+   * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
+   *
+   * @param actions a list of actions to check for action conflicts
+   * @return a map between generated artifacts and their associated generating actions. If there is
+   *     more than one action generating the same output artifact, only one action is chosen.
+   * @throws ActionConflictException iff there are two actions generate the same output
+   */
+  public static Map<Artifact, ActionAnalysisMetadata> findAndThrowActionConflict(
+      Iterable<ActionAnalysisMetadata> actions) throws ActionConflictException {
+    return Actions.maybeFilterSharedActionsAndThrowIfConflict(
+        actions, /*allowSharedAction=*/ false);
+  }
 
   /**
    * Finds action conflicts. An action conflict happens if two actions generate the same output
@@ -116,6 +133,27 @@ public final class Actions {
    * 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();
+    for (Artifact artifact : generatingActions.keySet()) {
+      artifactPathMap.put(artifact.getExecPath(), artifact);
+    }
+
+    return findArtifactPrefixConflicts(
+        new MapBasedImmutableActionGraph(generatingActions), artifactPathMap);
+  }
+
+  /**
+   * 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 actionGraph the {@link ActionGraph} to query for artifact conflicts
    * @param artifactPathMap a map mapping generated artifacts to their exec paths
    * @return A map between actions that generated the conflicting artifacts and their associated
@@ -185,4 +223,18 @@ public final class Actions {
   public static String escapeLabel(Label label) {
     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
+    public ActionAnalysisMetadata getGeneratingAction(Artifact artifact) {
+      return generatingActions.get(artifact);
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java
index 7113370339..3ee894640f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java
@@ -14,17 +14,22 @@
 
 package com.google.devtools.build.lib.analysis.actions;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.ArrayList;
 import java.util.List;
+import java.util.Map;
 
 /**
  * A customizable, serializable class for building memory efficient command lines.
@@ -36,6 +41,26 @@ public final class CustomCommandLine extends CommandLine {
     abstract void eval(ImmutableList.Builder<String> builder);
   }
 
+
+  /**
+   * A command line argument for {@link TreeFileArtifact}.
+   *
+   * <p>Since {@link TreeFileArtifact} is not known or available at analysis time, subclasses should
+   * enclose its parent TreeFileArtifact instead at analysis time. This interface provides method
+   * {@link #substituteTreeArtifact} to generate another argument object that replaces the enclosed
+   * TreeArtifact with one of its {@link TreeFileArtifact} at execution time.
+   */
+  private abstract static class TreeFileArtifactArgvFragment {
+    /**
+     * Substitutes this ArgvFragment with another arg object, with the original TreeArtifacts
+     * contained in this ArgvFragment replaced by their associated TreeFileArtifacts.
+     *
+     * @param substitutionMap A map between TreeArtifacts and their associated TreeFileArtifacts
+     *     used to replace them.
+     */
+    abstract Object substituteTreeArtifact(Map<Artifact, TreeFileArtifact> substitutionMap);
+  }
+
   // It's better to avoid anonymous classes if we want to serialize command lines
   private static final class JoinExecPathsArg extends ArgvFragment {
 
@@ -70,6 +95,39 @@ public final class CustomCommandLine extends CommandLine {
     }
   }
 
+  /**
+   * An argument object that evaluates to a formatted string for {@link TreeFileArtifact} exec
+   * paths, enclosing the associated string format template and {@link TreeFileArtifact}s.
+   */
+  private static final class TreeFileArtifactExecPathWithTemplateArg
+      extends TreeFileArtifactArgvFragment {
+
+    private final String template;
+    private final Artifact[] placeHolderTreeArtifacts;
+
+    private TreeFileArtifactExecPathWithTemplateArg(
+        String template, Artifact... artifacts) {
+      for (Artifact artifact : artifacts) {
+        Preconditions.checkArgument(artifact.isTreeArtifact(), "%s must be a TreeArtifact",
+            artifact);
+      }
+      this.template = template;
+      this.placeHolderTreeArtifacts = artifacts;
+    }
+
+    @Override
+    ArgvFragment substituteTreeArtifact(Map<Artifact, TreeFileArtifact> substitutionMap) {
+      ImmutableList.Builder<PathFragment> argBuilder = ImmutableList.builder();
+      for (Artifact placeHolderTreeArtifact : placeHolderTreeArtifacts) {
+        Artifact artifact = substitutionMap.get(placeHolderTreeArtifact);
+        Preconditions.checkNotNull(artifact, "Artifact to substitute: %s", placeHolderTreeArtifact);
+        argBuilder.add(artifact.getExecPath());
+      }
+      return new PathWithTemplateArg(
+          template, argBuilder.build().toArray(new PathFragment[0]));
+    }
+  }
+
   // TODO(bazel-team): CustomArgv and CustomMultiArgv is  going to be difficult to expose
   // in Skylark. Maybe we can get rid of them by refactoring JavaCompileAction. It also
   // raises immutability / serialization issues.
@@ -191,6 +249,27 @@ public final class CustomCommandLine extends CommandLine {
     }
   }
 
+
+  /**
+   * An argument object that evaluates to the exec path of a {@link TreeFileArtifact}, enclosing
+   * the associated {@link TreeFileArtifact}.
+   */
+  private static final class TreeFileArtifactExecPathArg extends TreeFileArtifactArgvFragment {
+    private final Artifact placeHolderTreeArtifact;
+
+    private TreeFileArtifactExecPathArg(Artifact artifact) {
+      Preconditions.checkArgument(artifact.isTreeArtifact(), "%s must be a TreeArtifact", artifact);
+      placeHolderTreeArtifact = artifact;
+    }
+
+    @Override
+    Object substituteTreeArtifact(Map<Artifact, TreeFileArtifact> substitutionMap) {
+      Artifact artifact = substitutionMap.get(placeHolderTreeArtifact);
+      Preconditions.checkNotNull(artifact, "Artifact to substitute: %s", placeHolderTreeArtifact);
+      return artifact.getExecPath();
+    }
+  }
+
   /**
    * A Builder class for CustomCommandLine with the appropriate methods.
    *
@@ -265,6 +344,34 @@ public final class CustomCommandLine extends CommandLine {
       return this;
     }
 
+    /**
+     * Adds a exec path flag of a {@link TreeFileArtifact} inside the given TreeArtifact.
+     *
+     * @param arg the name of the argument
+     * @param artifact the TreeArtifact that will be evaluated to one of its child
+     *     {@link TreeFileArtifact} at execution time
+     */
+    public Builder addTreeFileArtifactExecPath(String arg, Artifact artifact) {
+      if (arg != null && artifact != null) {
+        arguments.add(arg);
+        arguments.add(new TreeFileArtifactExecPathArg(artifact));
+      }
+      return this;
+    }
+
+    /**
+     * Adds the exec path of a {@link TreeFileArtifact} inside the given TreeArtifact.
+     *
+     * @param artifact the TreeArtifact that will be evaluated to one of its child
+     *     {@link TreeFileArtifact} at execution time
+     */
+    public Builder addTreeFileArtifactExecPath(Artifact artifact) {
+      if (artifact != null) {
+        arguments.add(new TreeFileArtifactExecPathArg(artifact));
+      }
+      return this;
+    }
+
     public Builder addJoinStrings(String arg, String delimiter, Iterable<String> strings) {
       if (arg != null && strings != null) {
         arguments.add(arg);
@@ -295,6 +402,21 @@ public final class CustomCommandLine extends CommandLine {
       return this;
     }
 
+    /**
+     * Adds a formatted string containing the exec paths of {@link TreeFileArtifact}s inside the
+     * given TreeArtifacts.
+     *
+     * @param template the string format template
+     * @param artifacts the TreeArtifact that will be evaluated to one of their child
+     *     {@link TreeFileArtifact} at execution time
+     */
+    public Builder addTreeFileArtifactExecPaths(String template, Artifact... artifacts) {
+      if (template != null && artifacts != null) {
+        arguments.add(new TreeFileArtifactExecPathWithTemplateArg(template, artifacts));
+      }
+      return this;
+    }
+
     public Builder addJoinPaths(String delimiter, Iterable<PathFragment> paths) {
       if (delimiter != null && paths != null) {
         arguments.add(new JoinPathsArg(delimiter, paths));
@@ -355,20 +477,69 @@ public final class CustomCommandLine extends CommandLine {
 
   private final ImmutableList<Object> arguments;
 
+
+  /**
+   * A map between enclosed TreeArtifacts and their associated {@link TreeFileArtifacts} for
+   * substitution.
+   *
+   * <p> This map is used to support TreeArtifact substitutions in
+   * {@link TreeFileArtifactArgvFragment}s.
+   */
+  private final Map<Artifact, TreeFileArtifact> substitutionMap;
+
   private CustomCommandLine(List<Object> arguments) {
     this.arguments = ImmutableList.copyOf(arguments);
+    this.substitutionMap = null;
+  }
+
+  private CustomCommandLine(
+      List<Object> arguments, Map<Artifact, TreeFileArtifact> substitutionMap) {
+    this.arguments = ImmutableList.copyOf(arguments);
+    this.substitutionMap = ImmutableMap.copyOf(substitutionMap);
+  }
+
+  /**
+   * Given the list of {@link TreeFileArtifact}s, returns another CustomCommandLine that replaces
+   * their parent TreeArtifacts with the TreeFileArtifacts in all
+   * {@link TreeFileArtifactArgvFragment} argument objects.
+   */
+  @VisibleForTesting
+  public CustomCommandLine evaluateTreeFileArtifacts(Iterable<TreeFileArtifact> treeFileArtifacts) {
+    ImmutableMap.Builder<Artifact, TreeFileArtifact> substitutionMap = ImmutableMap.builder();
+    for (TreeFileArtifact treeFileArtifact : treeFileArtifacts) {
+      substitutionMap.put(treeFileArtifact.getParent(), treeFileArtifact);
+    }
+
+    return new CustomCommandLine(arguments, substitutionMap.build());
   }
 
   @Override
   public Iterable<String> arguments() {
     ImmutableList.Builder<String> builder = ImmutableList.builder();
     for (Object arg : arguments) {
-      if (arg instanceof ArgvFragment) {
-        ((ArgvFragment) arg).eval(builder);
+      Object substitutedArg = substituteTreeFileArtifactArgvFragment(arg);
+      if (substitutedArg instanceof ArgvFragment) {
+        ((ArgvFragment) substitutedArg).eval(builder);
       } else {
-        builder.add(arg.toString());
+        builder.add(substitutedArg.toString());
       }
     }
     return builder.build();
   }
+
+  /**
+   * If the given arg is a {@link TreeFileArtifactArgvFragment} and we have its associated
+   * TreeArtifact substitution map, returns another argument object that has its enclosing
+   * TreeArtifact substituted by one of its {@link TreeFileArtifact}. Otherwise, returns the given
+   * arg unmodified.
+   */
+  private Object substituteTreeFileArtifactArgvFragment(Object arg) {
+    if (arg instanceof TreeFileArtifactArgvFragment) {
+      TreeFileArtifactArgvFragment argvFragment = (TreeFileArtifactArgvFragment) arg;
+      return argvFragment.substituteTreeArtifact(
+          Preconditions.checkNotNull(substitutionMap, argvFragment));
+    } else {
+      return arg;
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
index 21052e1f27..ab83c5ebb4 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
@@ -22,7 +22,6 @@ import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ParameterFile;
 import com.google.devtools.build.lib.analysis.AnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
-import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.List;
@@ -84,35 +83,41 @@ public final class ParamFileHelper {
    * <p>Call this with the result of {@link #getParamsFileMaybe} if it is not null.
    *
    * @param executableArgs leading arguments that should never be wrapped in a parameter file
-   * @param arguments arguments to the command (in addition to executableArgs), OR
-   * @param commandLine a {@link CommandLine} that provides the arguments (in addition to
-   *        executableArgs)
    * @param isShellCommand true if this is a shell command
-   * @param owner owner of the action
    * @param paramFileInfo parameter file information
+   * @param parameterFile the output parameter file artifact
    */
   public static CommandLine createWithParamsFile(
       List<String> executableArgs,
-      @Nullable Iterable<String> arguments,
-      @Nullable CommandLine commandLine,
       boolean isShellCommand,
-      ActionOwner owner,
-      List<Action> requiredActions,
       ParamFileInfo paramFileInfo,
       Artifact parameterFile) {
-    Preconditions.checkNotNull(parameterFile);
-    if (commandLine != null && arguments != null && !Iterables.isEmpty(arguments)) {
-      throw new IllegalStateException("must provide either commandLine or arguments: " + arguments);
-    }
+    String pathWithFlag = paramFileInfo.getFlag() + parameterFile.getExecPathString();
+    Iterable<String> commandArgv = Iterables.concat(executableArgs, ImmutableList.of(pathWithFlag));
+    return CommandLine.ofInternal(commandArgv, isShellCommand);
+  }
 
+  /**
+   * Creates an action to write the parameter file.
+   *
+   * @param arguments arguments to the command (in addition to executableArgs), OR
+   * @param commandLine a {@link CommandLine} that provides the arguments (in addition to
+   *        executableArgs)
+   * @param owner owner of the action
+   * @param parameterFile the output parameter file artifact
+   * @param paramFileInfo parameter file information
+   */
+  public static Action createParameterFileWriteAction(
+      @Nullable Iterable<String> arguments,
+      @Nullable CommandLine commandLine,
+      ActionOwner owner,
+      Artifact parameterFile,
+      ParamFileInfo paramFileInfo) {
     CommandLine paramFileContents =
         (commandLine != null) ? commandLine : CommandLine.ofInternal(arguments, false);
-    requiredActions.add(new ParameterFileWriteAction(owner, parameterFile, paramFileContents,
-        paramFileInfo.getFileType(), paramFileInfo.getCharset()));
 
-    String pathWithFlag = paramFileInfo.getFlag() + parameterFile.getExecPathString();
-    Iterable<String> commandArgv = Iterables.concat(executableArgs, ImmutableList.of(pathWithFlag));
-    return CommandLine.ofInternal(commandArgv, isShellCommand);
+    return new ParameterFileWriteAction(owner, parameterFile, paramFileContents,
+        paramFileInfo.getFileType(), paramFileInfo.getCharset());
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
index e364d9e535..75624beca5 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
@@ -60,6 +60,7 @@ import java.util.List;
 import java.util.Map;
 
 import javax.annotation.CheckReturnValue;
+import javax.annotation.Nullable;
 
 /**
  * An Action representing an arbitrary subprocess to be forked and exec'd.
@@ -483,8 +484,9 @@ public class SpawnAction extends AbstractAction implements ExecutionInfoSpecifie
     }
 
     /**
-     * Builds the SpawnAction using the passed in action configuration and returns it and all
-     * dependent actions. The first item of the returned array is always the SpawnAction itself.
+     * Builds the SpawnAction and ParameterFileWriteAction (if param file is used) using the passed-
+     * in action configuration. The first item of the returned array is always the SpawnAction
+     * itself.
      *
      * <p>This method makes a copy of all the collections, so it is safe to reuse the builder after
      * this method returns.
@@ -507,32 +509,65 @@ public class SpawnAction extends AbstractAction implements ExecutionInfoSpecifie
     @VisibleForTesting @CheckReturnValue
     public Action[] build(ActionOwner owner, AnalysisEnvironment analysisEnvironment,
         BuildConfiguration configuration) {
-      if (isShellCommand && executable == null) {
-        executable = configuration.getShExecutable();
-      }
-      Preconditions.checkNotNull(executable);
-      Preconditions.checkNotNull(executableArgs);
-
-      if (useDefaultShellEnvironment) {
-        this.environment = configuration.getLocalShellEnvironment();
+      Iterable<String> arguments = argumentsBuilder.build();
+      // Check to see if we need to use param file.
+      Artifact paramsFile = ParamFileHelper.getParamsFileMaybe(
+          buildExecutableArgs(configuration.getShExecutable()),
+          arguments,
+          commandLine,
+          paramFileInfo,
+          configuration,
+          analysisEnvironment,
+          outputs);
+
+      List<Action> actions = new ArrayList<>(2);
+
+      // Set up the SpawnAction itself.
+      actions.add(buildSpawnAction(owner, configuration.getLocalShellEnvironment(),
+          configuration.getShExecutable(), paramsFile));
+
+      // If param file is to be used, set up the param file write action as well.
+      if (paramsFile != null) {
+        actions.add(ParamFileHelper.createParameterFileWriteAction(
+            arguments,
+            commandLine,
+            owner,
+            paramsFile,
+            paramFileInfo));
       }
 
-      ImmutableList<String> argv = ImmutableList.<String>builder()
-          .add(executable.getPathString())
-          .addAll(executableArgs)
-          .build();
+      return actions.toArray(new Action[actions.size()]);
+    }
 
+    /**
+     * Builds the SpawnAction using the passed-in action configuration.
+     *
+     * <p>This method makes a copy of all the collections, so it is safe to reuse the builder after
+     * this method returns.
+     *
+     * <p>This method is invoked by {@link SpawnActionTemplate} in the execution phase. It is
+     * important that analysis-phase objects (RuleContext, Configuration, etc.) are not directly
+     * referenced in this function to prevent them from bleeding into the execution phase.
+     *
+     * @param owner the {@link ActionOwner} for the SpawnAction
+     * @param defaultShellEnvironment the default shell environment to use. May be null if not used.
+     * @param defaultShellExecutable the default shell executable path. May be null if not used.
+     * @param paramsFile the parameter file for the SpawnAction. May be null if not used.
+     * @return the SpawnAction and any actions required by it, with the first item always being the
+     *      SpawnAction itself.
+     */
+    SpawnAction buildSpawnAction(
+        ActionOwner owner,
+        @Nullable Map<String, String> defaultShellEnvironment,
+        @Nullable PathFragment defaultShellExecutable,
+        @Nullable Artifact paramsFile) {
+      List<String> argv = buildExecutableArgs(defaultShellExecutable);
       Iterable<String> arguments = argumentsBuilder.build();
-
-      Artifact paramsFile = ParamFileHelper.getParamsFileMaybe(argv, arguments, commandLine,
-          paramFileInfo, configuration, analysisEnvironment, outputs);
-
-      List<Action> actions = new ArrayList<>();
       CommandLine actualCommandLine;
       if (paramsFile != null) {
-        actualCommandLine = ParamFileHelper.createWithParamsFile(argv, arguments, commandLine,
-            isShellCommand, owner, actions, paramFileInfo, paramsFile);
         inputsBuilder.add(paramsFile);
+        actualCommandLine = ParamFileHelper.createWithParamsFile(argv, isShellCommand,
+            paramFileInfo, paramsFile);
       } else {
         actualCommandLine = ParamFileHelper.createWithoutParamsFile(argv, arguments, commandLine,
             isShellCommand);
@@ -551,23 +586,41 @@ public class SpawnAction extends AbstractAction implements ExecutionInfoSpecifie
           new LinkedHashMap<>(inputManifests);
       inputAndToolManifests.putAll(toolManifests);
 
-      actions.add(
-          0,
-          new SpawnAction(
-              owner,
-              tools,
-              inputsAndTools,
-              ImmutableList.copyOf(outputs),
-              resourceSet,
-              actualCommandLine,
-              environment,
-              executionInfo,
-              progressMessage,
-              ImmutableMap.copyOf(inputAndToolManifests),
-              mnemonic,
-              executeUnconditionally,
-              extraActionInfoSupplier));
-      return actions.toArray(new Action[actions.size()]);
+      Map<String, String> env;
+      if (useDefaultShellEnvironment) {
+        env = Preconditions.checkNotNull(defaultShellEnvironment);
+      } else {
+        env = this.environment;
+      }
+
+      return new SpawnAction(
+          owner,
+          tools,
+          inputsAndTools,
+          ImmutableList.copyOf(outputs),
+          resourceSet,
+          actualCommandLine,
+          ImmutableMap.copyOf(env),
+          executionInfo,
+          progressMessage,
+          ImmutableMap.copyOf(inputAndToolManifests),
+          mnemonic,
+          executeUnconditionally,
+          extraActionInfoSupplier);
+    }
+
+    private List<String> buildExecutableArgs(@Nullable PathFragment defaultShellExecutable) {
+      if (isShellCommand && executable == null) {
+        Preconditions.checkNotNull(defaultShellExecutable);
+        executable = defaultShellExecutable;
+      }
+      Preconditions.checkNotNull(executable);
+      Preconditions.checkNotNull(executableArgs);
+
+      return ImmutableList.<String>builder()
+          .add(executable.getPathString())
+          .addAll(executableArgs)
+          .build();
     }
 
     /**
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
new file mode 100644
index 0000000000..9cd414fb0c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnActionTemplate.java
@@ -0,0 +1,457 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.analysis.actions;
+
+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.ActionAnalysisMetadata.MiddlemanType;
+import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.ActionOwner;
+import com.google.devtools.build.lib.actions.Actions;
+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.ArtifactPrefixConflictException;
+import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
+import com.google.devtools.build.lib.analysis.FilesToRunProvider;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.Map;
+
+/**
+ * A placeholder action that, at execution time, expands into a list of {@link SpawnAction}s that
+ * will be executed.
+ *
+ * <p>SpawnActionTemplate is for users who want to dynamically register SpawnActions operating on
+ * individual {@link TreeFileArtifact} inside input and output TreeArtifacts at execution time.
+ *
+ * <p>It takes in one TreeArtifact and generates one TreeArtifact. The following happens at
+ * execution time for SpawnActionTemplate:
+ * <ol>
+ *   <li>Input TreeArtifact is resolved.
+ *   <li>For each individual {@link TreeFileArtifact} inside input TreeArtifact, generate an output
+ *       {@link TreeFileArtifact} inside output TreeArtifact at the parent-relative path provided by
+ *       {@link OutputPathMapper}.
+ *   <li>For each pair of input and output {@link TreeFileArtifact}s, generate an associated
+ *       {@link SpawnAction}.
+ *   <li>All expanded {@link SpawnAction}s are executed and their output {@link TreeFileArtifact}s
+ *       collected.
+ *   <li>Output TreeArtifact is resolved.
+ * </ol>
+ */
+public final class SpawnActionTemplate implements ActionAnalysisMetadata {
+  private final Artifact inputTreeArtifact;
+  private final Artifact outputTreeArtifact;
+  private final NestedSet<Artifact> commonInputs;
+  private final NestedSet<Artifact> allInputs;
+  private final NestedSet<Artifact> commonTools;
+  private final ActionOwner actionOwner;
+  private final String mnemonic;
+  private final OutputPathMapper outputPathMapper;
+  private final SpawnAction.Builder spawnActionBuilder;
+  private final CustomCommandLine commandLineTemplate;
+
+  /**
+   * Interface providing mapping between expanded input files under the input TreeArtifact and
+   * parent-relative paths of their associated output file under the output TreeArtifact.
+   *
+   * <p>Users of SpawnActionTemplate must provide a mapper object implementing this interface.
+   * SpawnActionTemplate uses the mapper to query for the path of output artifact associated with
+   * each input {@link TreeFileArtifact} resolved at execution time.
+   */
+  public interface OutputPathMapper {
+   /**
+    * Given the input {@link TreeFileArtifact}, returns the parent-relative path of the associated
+    * output {@link TreeFileArtifact}.
+    *
+    * @param input the input {@link TreeFileArtifact}
+    */
+    PathFragment parentRelativeOutputPath(TreeFileArtifact input);
+  }
+
+  private SpawnActionTemplate(
+      ActionOwner actionOwner,
+      Artifact inputTreeArtifact,
+      Artifact outputTreeArtifact,
+      NestedSet<Artifact> commonInputs,
+      NestedSet<Artifact> commonTools,
+      OutputPathMapper outputPathMapper,
+      CustomCommandLine commandLineTemplate,
+      String mnemonic,
+      SpawnAction.Builder spawnActionBuilder) {
+    this.inputTreeArtifact = inputTreeArtifact;
+    this.outputTreeArtifact = outputTreeArtifact;
+    this.commonTools = commonTools;
+    this.commonInputs = NestedSetBuilder.<Artifact>stableOrder()
+        .addTransitive(commonInputs)
+        .addTransitive(commonTools)
+        .build();
+    this.allInputs = NestedSetBuilder.<Artifact>stableOrder()
+        .add(inputTreeArtifact)
+        .addTransitive(this.commonInputs)
+        .build();
+    this.outputPathMapper = outputPathMapper;
+    this.actionOwner = actionOwner;
+    this.mnemonic = mnemonic;
+    this.spawnActionBuilder = spawnActionBuilder;
+    this.commandLineTemplate = commandLineTemplate;
+  }
+
+  /**
+   * Given a list of input TreeFileArtifacts resolved at execution time, returns a list of expanded
+   * SpawnActions to be executed.
+   *
+   * @param inputTreeFileArtifacts the list of {@link TreeFileArtifact}s inside input TreeArtifact
+   *     resolved at execution time
+   * @param artifactOwner the {@link ArtifactOwner} of the generated output
+   *     {@link TreeFileArtifact}s
+   * @return a list of expanded {@link SpawnAction}s to execute, one for each input
+   *     {@link TreeFileArtifact}
+   * @throws ActionConflictException if the expanded actions have duplicated outputs
+   * @throws ArtifactPrefixConflictException if there is prefix conflict among the outputs of
+   *     expanded actions
+   */
+  public Iterable<SpawnAction> generateActionForInputArtifacts(
+      Iterable<TreeFileArtifact> inputTreeFileArtifacts, ArtifactOwner artifactOwner)
+      throws ActionConflictException,  ArtifactPrefixConflictException {
+    ImmutableList.Builder<SpawnAction> expandedActions = new ImmutableList.Builder<>();
+    for (TreeFileArtifact inputTreeFileArtifact : inputTreeFileArtifacts) {
+      PathFragment parentRelativeOutputPath =
+          outputPathMapper.parentRelativeOutputPath(inputTreeFileArtifact);
+
+      TreeFileArtifact outputTreeFileArtifact = createTreeFileArtifact(
+          outputTreeArtifact,
+          checkOutputParentRelativePath(parentRelativeOutputPath),
+          artifactOwner);
+
+      expandedActions.add(createAction(inputTreeFileArtifact, outputTreeFileArtifact));
+    }
+
+    Iterable<SpawnAction> actions = expandedActions.build();
+    checkActionAndArtifactConflicts(ImmutableList.<ActionAnalysisMetadata>copyOf(actions));
+    return actions;
+  }
+
+  /**
+   * Returns a SpawnAction that takes inputTreeFileArtifact as input and generates
+   * outputTreeFileArtifact.
+   */
+  private SpawnAction createAction(
+      TreeFileArtifact inputTreeFileArtifact, TreeFileArtifact outputTreeFileArtifact) {
+    SpawnAction.Builder actionBuilder = new SpawnAction.Builder(spawnActionBuilder);
+    actionBuilder.addInput(inputTreeFileArtifact);
+    actionBuilder.addOutput(outputTreeFileArtifact);
+
+    CommandLine commandLine = commandLineTemplate.evaluateTreeFileArtifacts(
+        ImmutableList.of(inputTreeFileArtifact, outputTreeFileArtifact));
+    actionBuilder.setCommandLine(commandLine);
+
+    // Note that we pass in nulls below because SpawnActionTemplate does not support param file, and
+    // it does not use any default value for executable or shell environment. They must be set
+    // explicitly via builder method #setExecutable and #setEnvironment.
+    return actionBuilder.buildSpawnAction(
+        getOwner(),
+        /*defaultShellEnvironment=*/ null,
+        /*defaultShellExecutable=*/ null,
+        /*paramsFile=*/ null);
+  }
+
+  private static void checkActionAndArtifactConflicts(Iterable<ActionAnalysisMetadata> actions)
+      throws ActionConflictException,  ArtifactPrefixConflictException {
+    Map<Artifact, ActionAnalysisMetadata> generatingActions =
+        Actions.findAndThrowActionConflict(actions);
+    Map<ActionAnalysisMetadata, ArtifactPrefixConflictException> artifactPrefixConflictMap =
+        Actions.findArtifactPrefixConflicts(generatingActions);
+
+    if (!artifactPrefixConflictMap.isEmpty()) {
+      throw artifactPrefixConflictMap.values().iterator().next();
+    }
+
+    return;
+  }
+
+  private static PathFragment checkOutputParentRelativePath(PathFragment parentRelativeOutputPath) {
+    Preconditions.checkArgument(
+        parentRelativeOutputPath.isNormalized() && !parentRelativeOutputPath.isAbsolute(),
+        "%s is not a proper relative path",
+        parentRelativeOutputPath);
+    return parentRelativeOutputPath;
+  }
+
+  private static TreeFileArtifact createTreeFileArtifact(Artifact parentTreeArtifact,
+      PathFragment parentRelativeOutputPath, ArtifactOwner artifactOwner) {
+    return ActionInputHelper.treeFileArtifact(
+        parentTreeArtifact,
+        parentRelativeOutputPath,
+        artifactOwner);
+  }
+
+
+  /**
+   * Returns the input TreeArtifact.
+   *
+   * <p>This method is called by Skyframe to expand the input TreeArtifact into child
+   * TreeFileArtifacts. Skyframe then expands this SpawnActionTemplate with the TreeFileArtifacts
+   * through {@link #generateActionForInputArtifacts}.
+   */
+  public Artifact getInputTreeArtifact() {
+    return inputTreeArtifact;
+  }
+
+  /** Returns the output TreeArtifact. */
+  public Artifact getOutputTreeArtifact() {
+    return outputTreeArtifact;
+  }
+
+  @Override
+  public ActionOwner getOwner() {
+    return actionOwner;
+  }
+
+
+  @Override
+  public final String getMnemonic() {
+    return mnemonic;
+  }
+
+  @Override
+  public Iterable<Artifact> getTools() {
+    return commonTools;
+  }
+
+  @Override
+  public Iterable<Artifact> getInputs() {
+    return allInputs;
+  }
+
+  @Override
+  public ImmutableSet<Artifact> getOutputs() {
+    return ImmutableSet.of(outputTreeArtifact);
+  }
+
+  @Override
+  public Iterable<Artifact> getMandatoryInputs() {
+    return getInputs();
+  }
+
+  @Override
+  public ImmutableSet<Artifact> getMandatoryOutputs() {
+    return ImmutableSet.of();
+  }
+
+  @Override
+  public Artifact getPrimaryInput() {
+    return inputTreeArtifact;
+  }
+
+  @Override
+  public Artifact getPrimaryOutput() {
+    return outputTreeArtifact;
+  }
+
+  @Override
+  public boolean shouldReportPathPrefixConflict(ActionAnalysisMetadata action) {
+    return this != action;
+  }
+
+  @Override
+  public MiddlemanType getActionType() {
+    return MiddlemanType.NORMAL;
+  }
+
+  @Override
+  public String prettyPrint() {
+    return String.format("action template with output TreeArtifact %s",
+        outputTreeArtifact.prettyPrint());
+  }
+
+  /** Builder class to construct {@link SpawnActionTemplate} instances. */
+  public static class Builder {
+    private String actionTemplateMnemonic = "Unknown";
+    private OutputPathMapper outputPathMapper;
+    private CustomCommandLine commandLineTemplate;
+    private PathFragment executable;
+
+    private final Artifact inputTreeArtifact;
+    private final Artifact outputTreeArtifact;
+    private final NestedSetBuilder<Artifact> inputsBuilder = NestedSetBuilder.stableOrder();
+    private final NestedSetBuilder<Artifact> toolsBuilder = NestedSetBuilder.stableOrder();
+    private final SpawnAction.Builder spawnActionBuilder;
+
+    /**
+     * Creates a {@link SpawnActionTemplate} builder.
+     * 
+     * @param inputTreeArtifact the required input TreeArtifact.
+     * @param outputTreeArtifact the required output TreeArtifact.
+     */
+    public Builder(Artifact inputTreeArtifact, Artifact outputTreeArtifact) {
+      Preconditions.checkState(
+          inputTreeArtifact.isTreeArtifact() && outputTreeArtifact.isTreeArtifact(),
+          "Either %s or %s is not a TreeArtifact",
+          inputTreeArtifact,
+          outputTreeArtifact);
+      this.inputTreeArtifact = inputTreeArtifact;
+      this.outputTreeArtifact = outputTreeArtifact;
+      this.spawnActionBuilder = new SpawnAction.Builder();
+    }
+
+
+    /**
+     * Sets the mnemonics for both the {@link SpawnActionTemplate} and expanded {@link SpawnAction}.
+     */
+    public Builder setMnemonics(String actionTemplateMnemonic, String expandedActionMnemonic) {
+      this.actionTemplateMnemonic = actionTemplateMnemonic;
+      spawnActionBuilder.setMnemonic(expandedActionMnemonic);
+      return this;
+    }
+
+    /**
+     * Adds common tool artifacts. All common tool artifacts will be added as tool artifacts for
+     * expanded actions.
+     */
+    public Builder addCommonTools(Iterable<Artifact> artifacts) {
+      toolsBuilder.addAll(artifacts);
+      spawnActionBuilder.addTools(artifacts);
+      return this;
+    }
+
+    /**
+     * Adds common tool artifacts. All common tool artifacts will be added as input tool artifacts
+     * for expanded actions.
+     */
+    public Builder addCommonTool(FilesToRunProvider tool) {
+      toolsBuilder.addAll(tool.getFilesToRun());
+      spawnActionBuilder.addTool(tool);
+      return this;
+    }
+
+    /**
+     * Adds common input artifacts. All common input artifacts will be added as input artifacts for
+     * expanded actions.
+     */
+    public Builder addCommonInputs(Iterable<Artifact> artifacts) {
+      inputsBuilder.addAll(artifacts);
+      spawnActionBuilder.addInputs(artifacts);
+      return this;
+    }
+
+    /**
+     * Adds transitive common input artifacts. All common input artifacts will be added as input
+     * artifacts for expanded actions.
+     */
+    public Builder addCommonTransitiveInputs(NestedSet<Artifact> artifacts) {
+      inputsBuilder.addTransitive(artifacts);
+      spawnActionBuilder.addTransitiveInputs(artifacts);
+      return this;
+    }
+
+    /** Sets the map of environment variables for expanded actions. */
+    public Builder setEnvironment(Map<String, String> environment) {
+      spawnActionBuilder.setEnvironment(environment);
+      return this;
+    }
+
+    /**
+     * Sets the map of execution info for expanded actions.
+     */
+    public Builder setExecutionInfo(Map<String, String> executionInfo) {
+      spawnActionBuilder.setExecutionInfo(executionInfo);
+      return this;
+    }
+
+    /**
+     * Sets the executable used by expanded actions as a configured target. Automatically adds the
+     * files to run to the tools and uses the executable of the target as the executable.
+     *
+     * <p>Calling this method overrides any previous values set via calls to
+     * {@link #setExecutable(Artifact)} and {@link #setExecutable(PathFragment)}.
+     */
+    public Builder setExecutable(FilesToRunProvider executableProvider) {
+      Preconditions.checkArgument(
+          executableProvider.getExecutable() != null, "The target does not have an executable");
+      spawnActionBuilder.setExecutable(executableProvider);
+      addCommonTool(executableProvider);
+      this.executable = executableProvider.getExecutable().getExecPath();
+      return this;
+    }
+
+    /**
+     * Sets the executable path used by expanded actions. The path is interpreted relative to the
+     * execution root.
+     *
+     * <p>Calling this method overrides any previous values set via calls to
+     * {@link #setExecutable(Artifact)} and {@link #setExecutable(FilesToRunProvider)}.
+     */
+    public Builder setExecutable(PathFragment executable) {
+      spawnActionBuilder.setExecutable(executable);
+      this.executable = executable;
+      return this;
+    }
+
+    /**
+     * Sets the executable artifact used by expanded actions. The path is interpreted relative to
+     * the execution root.
+     *
+     * <p>Calling this method overrides any previous values set via calls to
+     * {@link #setExecutable(FilesToRunProvider)} and {@link #setExecutable(PathFragment)}.
+     */
+    public Builder setExecutable(Artifact artifact) {
+      spawnActionBuilder.setExecutable(artifact);
+      addCommonTools(ImmutableList.of(artifact));
+      this.executable = artifact.getExecPath();
+      return this;
+    }
+
+    /**
+     * Sets the command line template used to expand actions.
+     */
+    public Builder setCommandLineTemplate(CustomCommandLine commandLineTemplate) {
+      this.commandLineTemplate = commandLineTemplate;
+      return this;
+    }
+
+    /**
+     * Sets the {@link OutputPathMapper} object used to get the parent-relative paths of output
+     * {@link TreeFileArtifact}.
+     */
+    public Builder setOutputPathMapper(OutputPathMapper outputPathMapper) {
+      this.outputPathMapper = outputPathMapper;
+      return this;
+    }
+
+    /**
+     * Builds and returns the {@link SpawnActionTemplate} using the accumulated builder information.
+     *
+     * @param actionOwner the action owner of the SpawnActionTemplate to be built.
+     */
+    public SpawnActionTemplate build(ActionOwner actionOwner) {
+      Preconditions.checkNotNull(executable);
+
+      return new SpawnActionTemplate(
+          actionOwner,
+          Preconditions.checkNotNull(inputTreeArtifact),
+          Preconditions.checkNotNull(outputTreeArtifact),
+          inputsBuilder.build(),
+          toolsBuilder.build(),
+          Preconditions.checkNotNull(outputPathMapper),
+          Preconditions.checkNotNull(commandLineTemplate),
+          actionTemplateMnemonic,
+          spawnActionBuilder);
+    }
+  }
+}