Skyframe changes to support SpawnActionTemplate.

1. Adds ActionTemplateExpansion{Function, Value} for ActionTemplate expansion.
2. Changes ArtifactFunction to support evaluating TreeFileArtifacts and TreeArtifacts generated by ActionTemplate.

--
MOS_MIGRATED_REVID=124160939

13 files changed, 988 insertions, 61 deletions

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 e56ef46f6d..4c3c6a2c93 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
@@ -14,9 +14,11 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Objects;
 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.ActionAnalysisMetadata.MiddlemanType;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -36,6 +38,15 @@ import javax.annotation.Nullable;
 @Immutable
 @ThreadSafe
 public class ActionExecutionValue implements SkyValue {
+
+  private static final Function<Action, SkyKey> TO_KEY =
+      new Function<Action, SkyKey>() {
+        @Override
+        public SkyKey apply(Action action) {
+          return key(action);
+        }
+      };
+
   /*
   Concerning the data in this class:
 
@@ -131,6 +142,10 @@ public class ActionExecutionValue implements SkyValue {
     return SkyKey.create(SkyFunctions.ACTION_EXECUTION, action);
   }
 
+  static Iterable<SkyKey> keys(Iterable<Action> actions) {
+    return Iterables.transform(actions, TO_KEY);
+  }
+
   /**
    * Returns whether the key corresponds to a ActionExecutionValue worth reporting status about.
    *
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
index 28f7d0c731..a72ef48557 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
@@ -103,16 +103,6 @@ public class ActionMetadataHandler implements MetadataHandler {
       new ConcurrentHashMap<>();
 
   /**
-   * Contains per-fragment FileArtifactValues when those values must be stored separately.
-   * Bona-fide Artifacts are stored in {@link #additionalOutputData} instead.
-   * See {@link #getAdditionalOutputData()} for details.
-   * Unlike additionalOutputData, this map is discarded (the relevant FileArtifactValues
-   * are stored in outputTreeArtifactData's values instead).
-   */
-  private final ConcurrentMap<TreeFileArtifact, FileArtifactValue> cachedTreeFileArtifactData =
-      new ConcurrentHashMap<>();
-
-  /**
    * Data for TreeArtifactValues, constructed from outputArtifactData and
    * additionalOutputFileData.
    */
@@ -287,8 +277,7 @@ public class ActionMetadataHandler implements MetadataHandler {
       // We are dealing with artifacts inside a tree artifact.
       FileArtifactValue value =
           FileArtifactValue.createWithDigest(artifact.getPath(), injectedDigest, data.getSize());
-      FileArtifactValue oldValue = cachedTreeFileArtifactData.putIfAbsent(
-          (TreeFileArtifact) artifact, value);
+      FileArtifactValue oldValue = additionalOutputData.putIfAbsent(artifact, value);
       checkInconsistentData(artifact, oldValue, value);
       return new Metadata(value.getDigest());
     }
@@ -375,7 +364,7 @@ public class ActionMetadataHandler implements MetadataHandler {
         Maps.newHashMapWithExpectedSize(contents.size());
 
     for (TreeFileArtifact treeFileArtifact : contents) {
-      FileArtifactValue cachedValue = cachedTreeFileArtifactData.get(treeFileArtifact);
+      FileArtifactValue cachedValue = additionalOutputData.get(treeFileArtifact);
       if (cachedValue == null) {
         FileValue fileValue = outputArtifactData.get(treeFileArtifact);
         // This is similar to what's present in getRealMetadataForArtifact, except
@@ -385,11 +374,11 @@ public class ActionMetadataHandler implements MetadataHandler {
         if (fileValue == null) {
           fileValue = constructFileValue(treeFileArtifact, /*statNoFollow=*/ null);
           // A minor hack: maybeStoreAdditionalData will force the data to be stored
-          // in cachedTreeFileArtifactData.
+          // in additionalOutputData.
           maybeStoreAdditionalData(treeFileArtifact, fileValue, null);
         }
         cachedValue = Preconditions.checkNotNull(
-            cachedTreeFileArtifactData.get(treeFileArtifact), treeFileArtifact);
+            additionalOutputData.get(treeFileArtifact), treeFileArtifact);
       }
 
       values.put(treeFileArtifact, cachedValue);
@@ -500,7 +489,6 @@ public class ActionMetadataHandler implements MetadataHandler {
     outputDirectoryListings.clear();
     outputTreeArtifactData.clear();
     additionalOutputData.clear();
-    cachedTreeFileArtifactData.clear();
   }
 
   @Override
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
new file mode 100644
index 0000000000..26d254b9eb
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
@@ -0,0 +1,88 @@
+// 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.skyframe;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
+import com.google.devtools.build.lib.actions.ArtifactPrefixConflictException;
+import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.skyframe.ActionTemplateExpansionValue.ActionTemplateExpansionKey;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionException;
+import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import javax.annotation.Nullable;
+
+/**
+ * The SkyFunction for {@link ActionTemplateExpansionValue}.
+ *
+ * <p>Given an action template, this function resolves its input TreeArtifact, then expands the
+ * action template into a list of actions using the expanded {@link TreeFileArtifact}s under the
+ * input TreeArtifact.
+ */
+public class ActionTemplateExpansionFunction implements SkyFunction {
+
+  @Override
+  public SkyValue compute(SkyKey skyKey, Environment env)
+      throws ActionTemplateExpansionFunctionException {
+    ActionTemplateExpansionKey key = (ActionTemplateExpansionKey) skyKey.argument();
+    SpawnActionTemplate actionTemplate = key.getActionTemplate();
+
+    // Requests the TreeArtifactValue object for the input TreeArtifact.
+    SkyKey artifactValueKey = ArtifactValue.key(actionTemplate.getInputTreeArtifact(), true);
+    TreeArtifactValue treeArtifactValue = (TreeArtifactValue) env.getValue(artifactValueKey);
+
+    // Input TreeArtifact is not ready yet.
+    if (env.valuesMissing()) {
+      return null;
+    }
+    Iterable<TreeFileArtifact> inputTreeFileArtifacts = treeArtifactValue.getChildren();
+    Iterable<Action> expandedActions;
+    try {
+      // Expand the action template using the list of expanded input TreeFileArtifacts.
+      expandedActions = ImmutableList.<Action>copyOf(
+          actionTemplate.generateActionForInputArtifacts(inputTreeFileArtifacts, key));
+    } catch (ActionConflictException e) {
+      e.reportTo(env.getListener());
+      throw new ActionTemplateExpansionFunctionException(e);
+    } catch (ArtifactPrefixConflictException e) {
+      env.getListener().handle(Event.error(e.getMessage()));
+      throw new ActionTemplateExpansionFunctionException(e);
+    }
+
+    return new ActionTemplateExpansionValue(expandedActions);
+  }
+
+  /** Exception thrown by {@link ActionTemplateExpansionFunction}. */
+  public static final class ActionTemplateExpansionFunctionException extends SkyFunctionException {
+    ActionTemplateExpansionFunctionException(ActionConflictException e) {
+      super(e, Transience.PERSISTENT);
+    }
+
+    ActionTemplateExpansionFunctionException(ArtifactPrefixConflictException e) {
+      super(e, Transience.PERSISTENT);
+    }
+  }
+
+  @Nullable
+  @Override
+  public String extractTag(SkyKey skyKey) {
+    return null;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
new file mode 100644
index 0000000000..fa429028b7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
@@ -0,0 +1,100 @@
+// 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.skyframe;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+
+/**
+ * Value that stores expanded actions from ActionTemplate.
+ */
+public final class ActionTemplateExpansionValue extends ActionLookupValue {
+  private final Iterable<Action> expandedActions;
+
+  ActionTemplateExpansionValue(Iterable<Action> expandedActions) {
+    super(ImmutableList.<ActionAnalysisMetadata>copyOf(expandedActions));
+    this.expandedActions = ImmutableList.copyOf(expandedActions);
+  }
+
+  Iterable<Action> getExpandedActions() {
+    return expandedActions;
+  }
+
+  static SkyKey key(SpawnActionTemplate actionTemplate) {
+    return SkyKey.create(
+        SkyFunctions.ACTION_TEMPLATE_EXPANSION,
+        createActionTemplateExpansionKey(actionTemplate));
+  }
+
+  static ActionTemplateExpansionKey createActionTemplateExpansionKey(
+      SpawnActionTemplate actionTemplate) {
+    return new ActionTemplateExpansionKey(actionTemplate);
+  }
+
+
+  static final class ActionTemplateExpansionKey extends ActionLookupKey {
+    private final SpawnActionTemplate actionTemplate;
+
+    ActionTemplateExpansionKey(SpawnActionTemplate actionTemplate) {
+      Preconditions.checkNotNull(
+          actionTemplate,
+          "Passed in action template cannot be null: %s",
+          actionTemplate);
+      this.actionTemplate = actionTemplate;
+    }
+
+    @Override
+    SkyFunctionName getType() {
+      return SkyFunctions.ACTION_TEMPLATE_EXPANSION;
+    }
+
+
+    @Override
+    public Label getLabel() {
+      return actionTemplate.getOwner().getLabel();
+    }
+
+    /** Returns the associated {@link SpawnActionTemplate} */
+    SpawnActionTemplate getActionTemplate() {
+      return actionTemplate;
+    }
+
+    @Override
+    public int hashCode() {
+      return actionTemplate.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+     if (this == obj) {
+       return true;
+     }
+      if (obj == null) {
+        return false;
+      }
+      if (!(obj instanceof ActionTemplateExpansionKey)) {
+        return false;
+      }
+      ActionTemplateExpansionKey other = (ActionTemplateExpansionKey) obj;
+      return actionTemplate.equals(other.actionTemplate);
+    }
+  }
+}
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 c8022d5e89..6404ed1f68 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
@@ -15,13 +15,17 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 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.MissingInputFileException;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
@@ -71,32 +75,84 @@ class ArtifactFunction implements SkyFunction {
       return null;
     }
 
-    Preconditions.checkState(
-        actionMetadata instanceof Action,
-        "%s is not a proper Action object and therefore cannot be executed",
-        actionMetadata);
-    Action action = (Action) actionMetadata;
-    ActionExecutionValue actionValue =
+    // If the action is an ActionTemplate, we need to expand the ActionTemplate into concrete
+    // actions, execute those actions in parallel and then aggregate the action execution results.
+    if (artifact.isTreeArtifact() && actionMetadata instanceof SpawnActionTemplate) {
+      return createTreeArtifactValueFromActionTemplate(
+          (SpawnActionTemplate) actionMetadata, artifact, env);
+    } else {
+      Preconditions.checkState(
+          actionMetadata instanceof Action,
+          "%s is not a proper Action object and therefore cannot be executed",
+          actionMetadata);
+      Action action = (Action) actionMetadata;
+      ActionExecutionValue actionValue =
         (ActionExecutionValue) env.getValue(ActionExecutionValue.key(action));
-    if (actionValue == null) {
+      if (actionValue == null) {
+        return null;
+      }
+
+      if (artifact.isTreeArtifact()) {
+        // We get a request for the whole tree artifact. We can just return the associated
+        // TreeArtifactValue.
+        return Preconditions.checkNotNull(actionValue.getTreeArtifactValue(artifact), artifact);
+      } else if (isAggregatingValue(action)) {
+        return createAggregatingValue(artifact, action,
+            actionValue.getArtifactValue(artifact), env);
+      } else {
+        return createSimpleFileArtifactValue(artifact, action, actionValue, env);
+      }
+    }
+  }
+
+  private TreeArtifactValue createTreeArtifactValueFromActionTemplate(
+      SpawnActionTemplate actionTemplate, Artifact treeArtifact, Environment env)
+      throws ArtifactFunctionException {
+    // Request the list of expanded actions from the ActionTemplate.
+    ActionTemplateExpansionValue expansionValue = (ActionTemplateExpansionValue) env.getValue(
+        ActionTemplateExpansionValue.key(actionTemplate));
+
+    // The expanded actions are not yet available.
+    if (env.valuesMissing()) {
       return null;
     }
 
-    if (artifact.isTreeArtifact()) {
-      return actionValue.getTreeArtifactValue(artifact);
-    } else if (!isAggregatingValue(action)) {
-      try {
-        return createSimpleValue(artifact, actionValue);
-      } catch (IOException e) {
-        ActionExecutionException ex = new ActionExecutionException(e, action,
-            /*catastrophe=*/false);
-        env.getListener().handle(Event.error(ex.getLocation(), ex.getMessage()));
-        // This is a transient error since we did the work that led to the IOException.
-        throw new ArtifactFunctionException(ex, Transience.TRANSIENT);
+    // Execute the expanded actions in parallel.
+    Iterable<SkyKey> expandedActionExecutionKeys = ActionExecutionValue.keys(
+        expansionValue.getExpandedActions());
+    Map<SkyKey, SkyValue> expandedActionValueMap = env.getValues(expandedActionExecutionKeys);
+
+    // The execution values of the expanded actions are not yet all available.
+    if (env.valuesMissing()) {
+      return null;
+    }
+
+    // Aggregate the ArtifactValues for individual TreeFileArtifacts into a TreeArtifactValue for
+    // the parent TreeArtifact.
+    ImmutableMap.Builder<TreeFileArtifact, FileArtifactValue> map = ImmutableMap.builder();
+    for (Map.Entry<SkyKey, SkyValue> entry : expandedActionValueMap.entrySet()) {
+      SkyKey expandedActionExecutionKey = entry.getKey();
+      ActionExecutionValue actionExecutionValue = (ActionExecutionValue) entry.getValue();
+      Action expandedAction = (Action) expandedActionExecutionKey.argument();
+
+      Iterable<TreeFileArtifact> treeFileArtifacts = findActionOutputsWithMatchingParent(
+          expandedAction, treeArtifact);
+
+      Preconditions.checkState(
+          !Iterables.isEmpty(treeFileArtifacts),
+          "Action %s does not output TreeFileArtifact under %s",
+          expandedAction,
+          treeArtifact);
+
+      for (TreeFileArtifact treeFileArtifact : treeFileArtifacts) {
+        FileArtifactValue value  = createSimpleFileArtifactValue(
+            treeFileArtifact, expandedAction, actionExecutionValue, env);
+        map.put(treeFileArtifact, value);
       }
-    } else {
-      return createAggregatingValue(artifact, action, actionValue.getArtifactValue(artifact), env);
     }
+
+    // Return the aggregated TreeArtifactValue.
+    return TreeArtifactValue.create(map.build());
   }
 
   private ArtifactValue createSourceValue(Artifact artifact, boolean mandatory, Environment env)
@@ -155,9 +211,10 @@ class ArtifactFunction implements SkyFunction {
 
   // Non-aggregating artifact -- should contain at most one piece of artifact data.
   // data may be null if and only if artifact is a middleman artifact.
-  private ArtifactValue createSimpleValue(Artifact artifact, ActionExecutionValue actionValue)
-      throws IOException {
-    ArtifactValue value = actionValue.getArtifactValue(artifact);
+  private static FileArtifactValue createSimpleFileArtifactValue(Artifact artifact,
+      Action generatingAction, ActionExecutionValue actionValue, Environment env)
+      throws ArtifactFunctionException {
+    FileArtifactValue value = actionValue.getArtifactValue(artifact);
     if (value != null) {
       return value;
     }
@@ -168,7 +225,16 @@ class ArtifactFunction implements SkyFunction {
         "%s %s", artifact, actionValue);
     Preconditions.checkNotNull(data.getDigest(),
           "Digest should already have been calculated for %s (%s)", artifact, data);
-    return FileArtifactValue.create(artifact, data);
+
+    try {
+      return FileArtifactValue.create(artifact, data);
+    } catch (IOException e) {
+      ActionExecutionException ex = new ActionExecutionException(e, generatingAction,
+          /*catastrophe=*/false);
+      env.getListener().handle(Event.error(ex.getLocation(), ex.getMessage()));
+      // This is a transient error since we did the work that led to the IOException.
+      throw new ArtifactFunctionException(ex, Transience.TRANSIENT);
+    }
   }
 
   private AggregatingArtifactValue createAggregatingValue(Artifact artifact,
@@ -222,8 +288,31 @@ class ArtifactFunction implements SkyFunction {
     // were created during the first analysis of a configured target.
     Preconditions.checkNotNull(value,
         "Owner %s of %s not in graph %s", artifactOwner, artifact, actionLookupKey);
-    return Preconditions.checkNotNull(value.getGeneratingAction(artifact),
-          "Value %s does not contain generating action of %s", value, artifact);
+
+    ActionAnalysisMetadata action = value.getGeneratingAction(artifact);
+    if (artifact.hasParent()) {
+      // We are trying to resolve the generating action for a TreeFileArtifact. It may not have
+      // a generating action in the action graph at analysis time. In that case, we get the
+      // generating action for its parent TreeArtifact, which contains this TreeFileArtifact.
+      if (action == null) {
+        action = value.getGeneratingAction(artifact.getParent());
+      }
+    }
+
+    return Preconditions.checkNotNull(action,
+        "Value %s does not contain generating action of %s", value, artifact);
+  }
+
+  private static Iterable<TreeFileArtifact> findActionOutputsWithMatchingParent(
+      Action action, Artifact treeArtifact) {
+    ImmutableList.Builder<TreeFileArtifact> matchingOutputs = ImmutableList.builder();
+    for (Artifact output : action.getOutputs()) {
+      Preconditions.checkState(output.hasParent(), "%s must be a TreeFileArtifact", output);
+      if (output.getParent().equals(treeArtifact)) {
+        matchingOutputs.add((TreeFileArtifact) output);
+      }
+    }
+    return matchingOutputs.build();
   }
 
   private static final class ArtifactFunctionException extends SkyFunctionException {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
index e6df1276e5..116d3ba11e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
@@ -100,6 +100,8 @@ public final class SkyFunctions {
       SkyFunctionName.create("REPOSITORY_DIRECTORY");
   public static final SkyFunctionName WORKSPACE_AST = SkyFunctionName.create("WORKSPACE_AST");
   public static final SkyFunctionName EXTERNAL_PACKAGE = SkyFunctionName.create("EXTERNAL_PACKAGE");
+  public static final SkyFunctionName ACTION_TEMPLATE_EXPANSION =
+      SkyFunctionName.create("ACTION_TEMPLATE_EXPANSION");
 
   public static Predicate<SkyKey> isSkyFunction(final SkyFunctionName functionName) {
     return new Predicate<SkyKey>() {
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 8dfa3d54d2..e33c7e8c8d 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
@@ -410,6 +410,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     map.put(SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL,
         new RecursiveFilesystemTraversalFunction());
     map.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction());
+    map.put(SkyFunctions.ACTION_TEMPLATE_EXPANSION, new ActionTemplateExpansionFunction());
     map.putAll(extraSkyFunctions);
     return map.build();
   }
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 0ba8f7a20c..f6782e4c32 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
@@ -32,6 +32,7 @@ import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionOwner;
 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.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.Executor;
 import com.google.devtools.build.lib.actions.MutableActionGraph;
@@ -39,6 +40,9 @@ import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictEx
 import com.google.devtools.build.lib.actions.ResourceSet;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.actions.cache.MetadataHandler;
+import com.google.devtools.build.lib.analysis.actions.CustomCommandLine;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate.OutputPathMapper;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.exec.SingleBuildFileCache;
@@ -525,4 +529,18 @@ public final class ActionsTestUtil {
       throw new UncheckedActionConflictException(e);
     }
   }
+
+  public static SpawnActionTemplate createDummySpawnActionTemplate(
+      Artifact inputTreeArtifact, Artifact outputTreeArtifact) {
+    return new SpawnActionTemplate.Builder(inputTreeArtifact, outputTreeArtifact)
+        .setCommandLineTemplate(CustomCommandLine.builder().build())
+        .setExecutable(new PathFragment("bin/executable"))
+        .setOutputPathMapper(new OutputPathMapper() {
+          @Override
+          public PathFragment parentRelativeOutputPath(TreeFileArtifact inputTreeFileArtifact) {
+            return inputTreeFileArtifact.getParentRelativePath();
+          }
+        })
+        .build(NULL_ACTION_OWNER);
+  }
 }
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
new file mode 100644
index 0000000000..790429a735
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
@@ -0,0 +1,245 @@
+// 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.skyframe;
+
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.fail;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.actions.Action;
+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.ArtifactPrefixConflictException;
+import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
+import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
+import com.google.devtools.build.lib.analysis.actions.CustomCommandLine;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate.OutputPathMapper;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.ArtifactValue.OwnedArtifact;
+import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
+import com.google.devtools.build.skyframe.MemoizingEvaluator;
+import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequentialBuildDriver;
+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 org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+
+/** Tests for {@link ActionTemplateExpansionFunction}. */
+@RunWith(JUnit4.class)
+public final class ActionTemplateExpansionFunctionTest extends FoundationTestCase  {
+  private Map<Artifact, ArtifactValue> artifactValueMap;
+  private SequentialBuildDriver driver;
+
+  @Before
+  public void setUp() throws Exception  {
+    artifactValueMap = new LinkedHashMap<>();
+    AtomicReference<PathPackageLocator> pkgLocator = new AtomicReference<>(new PathPackageLocator(
+        rootDirectory.getFileSystem().getPath("/outputbase"), ImmutableList.of(rootDirectory)));
+    RecordingDifferencer differencer = new RecordingDifferencer();
+    MemoizingEvaluator evaluator =
+        new InMemoryMemoizingEvaluator(
+            ImmutableMap.<SkyFunctionName, SkyFunction>builder()
+                .put(SkyFunctions.ARTIFACT,
+                    new DummyArtifactFunction(artifactValueMap))
+                .put(SkyFunctions.ACTION_TEMPLATE_EXPANSION, new ActionTemplateExpansionFunction())
+                .build(),
+            differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+  }
+
+  @Test
+  public void testActionTemplateExpansionFunction() throws Exception {
+    Artifact inputTreeArtifact = createAndPopulateTreeArtifact(
+        "inputTreeArtifact", "child0", "child1", "child2");
+    Artifact outputTreeArtifact = createTreeArtifact("outputTreeArtifact");
+
+    SpawnActionTemplate spawnActionTemplate = ActionsTestUtil.createDummySpawnActionTemplate(
+        inputTreeArtifact, outputTreeArtifact);
+    List<Action> actions = evaluate(spawnActionTemplate);
+    assertThat(actions).hasSize(3);
+
+    ArtifactOwner owner = ActionTemplateExpansionValue.createActionTemplateExpansionKey(
+        spawnActionTemplate);
+    int i = 0;
+    for (Action action : actions) {
+      String childName = "child" + i;
+      assertThat(Artifact.toExecPaths(action.getInputs())).contains(
+          "out/inputTreeArtifact/" + childName);
+      assertThat(Artifact.toExecPaths(action.getOutputs())).containsExactly(
+          "out/outputTreeArtifact/" + childName);
+      assertThat(Iterables.getOnlyElement(action.getOutputs()).getArtifactOwner()).isEqualTo(owner);
+      ++i;
+    }
+  }
+
+  @Test
+  public void testThrowsOnActionConflict() throws Exception {
+    Artifact inputTreeArtifact = createAndPopulateTreeArtifact(
+        "inputTreeArtifact", "child0", "child1", "child2");
+    Artifact outputTreeArtifact = createTreeArtifact("outputTreeArtifact");
+
+
+    OutputPathMapper mapper = new OutputPathMapper() {
+      @Override
+      public PathFragment parentRelativeOutputPath(TreeFileArtifact inputTreeFileArtifact) {
+        return new PathFragment("conflict_path");
+      }
+    };
+    SpawnActionTemplate spawnActionTemplate =
+        new SpawnActionTemplate.Builder(inputTreeArtifact, outputTreeArtifact)
+            .setExecutable(new PathFragment("/bin/cp"))
+            .setCommandLineTemplate(CustomCommandLine.builder().build())
+            .setOutputPathMapper(mapper)
+            .build(ActionsTestUtil.NULL_ACTION_OWNER);
+
+    try {
+       evaluate(spawnActionTemplate);
+       fail("Expected ActionConflictException");
+    } catch (ActionConflictException e) {
+       // Expected ActionConflictException
+    }
+  }
+
+  @Test
+  public void testThrowsOnArtifactPrefixConflict() throws Exception {
+    Artifact inputTreeArtifact = createAndPopulateTreeArtifact(
+        "inputTreeArtifact", "child0", "child1", "child2");
+    Artifact outputTreeArtifact = createTreeArtifact("outputTreeArtifact");
+
+    OutputPathMapper mapper = new OutputPathMapper() {
+      private int i = 0;
+      @Override
+      public PathFragment parentRelativeOutputPath(TreeFileArtifact inputTreeFileArtifact) {
+        PathFragment path;
+        switch (i) {
+          case 0:
+            path = new PathFragment("path_prefix");
+            break;
+          case 1:
+            path = new PathFragment("path_prefix/conflict");
+            break;
+          default:
+            path = inputTreeFileArtifact.getParentRelativePath();
+        }
+
+        ++i;
+        return path;
+      }
+    };
+    SpawnActionTemplate spawnActionTemplate =
+        new SpawnActionTemplate.Builder(inputTreeArtifact, outputTreeArtifact)
+            .setExecutable(new PathFragment("/bin/cp"))
+            .setCommandLineTemplate(CustomCommandLine.builder().build())
+            .setOutputPathMapper(mapper)
+            .build(ActionsTestUtil.NULL_ACTION_OWNER);
+
+    try {
+       evaluate(spawnActionTemplate);
+       fail("Expected ArtifactPrefixConflictException");
+    } catch (ArtifactPrefixConflictException e) {
+       // Expected ArtifactPrefixConflictException
+    }
+  }
+
+  private List<Action> evaluate(SpawnActionTemplate spawnActionTemplate) throws Exception {
+    SkyKey skyKey = ActionTemplateExpansionValue.key(spawnActionTemplate);
+    EvaluationResult<ActionTemplateExpansionValue> result = driver.evaluate(
+        ImmutableList.of(skyKey),
+        false,
+        SkyframeExecutor.DEFAULT_THREAD_COUNT,
+        NullEventHandler.INSTANCE);
+    if (result.hasError()) {
+      throw result.getError().getException();
+    }
+    return ImmutableList.copyOf(result.get(skyKey).getExpandedActions());
+  }
+
+  private Artifact createTreeArtifact(String path) {
+    PathFragment execPath = new PathFragment("out").getRelative(path);
+    Path fullPath = rootDirectory.getRelative(execPath);
+    return new SpecialArtifact(
+        fullPath,
+        Root.asDerivedRoot(rootDirectory, rootDirectory.getRelative("out")),
+        execPath,
+        ArtifactOwner.NULL_OWNER,
+        SpecialArtifactType.TREE);
+  }
+
+  private Artifact createAndPopulateTreeArtifact(String path, String... childRelativePaths)
+      throws Exception {
+    Artifact treeArtifact = createTreeArtifact(path);
+    Map<TreeFileArtifact, FileArtifactValue> treeFileArtifactMap = new LinkedHashMap<>();
+
+    for (String childRelativePath : childRelativePaths) {
+      TreeFileArtifact treeFileArtifact = ActionInputHelper.treeFileArtifact(
+          treeArtifact, new PathFragment(childRelativePath));
+      scratch.file(treeFileArtifact.getPath().toString(), childRelativePath);
+      // We do not care about the FileArtifactValues in this test.
+      treeFileArtifactMap.put(treeFileArtifact, FileArtifactValue.create(treeFileArtifact));
+    }
+
+    artifactValueMap.put(
+        treeArtifact, TreeArtifactValue.create(ImmutableMap.copyOf(treeFileArtifactMap)));
+
+    return treeArtifact;
+  }
+
+  /** Dummy ArtifactFunction that just returns injected values */
+  private static class DummyArtifactFunction implements SkyFunction {
+    private final Map<Artifact, ArtifactValue> artifactValueMap;
+
+    DummyArtifactFunction(Map<Artifact, ArtifactValue> artifactValueMap) {
+      this.artifactValueMap = artifactValueMap;
+    }
+    @Override
+    public SkyValue compute(SkyKey skyKey, Environment env) {
+      OwnedArtifact ownedArtifact = (OwnedArtifact) skyKey.argument();
+      Artifact artifact = ownedArtifact.getArtifact();
+      return Preconditions.checkNotNull(artifactValueMap.get(artifact));
+    }
+
+    @Override
+    public String extractTag(SkyKey skyKey) {
+      return null;
+    }
+  }
+}
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 d7433ac95c..789e2b1e1d 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
@@ -30,9 +30,14 @@ import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.actions.Action;
 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.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.MissingInputFileException;
 import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.actions.util.TestAction.DummyAction;
 import com.google.devtools.build.lib.events.NullEventHandler;
 import com.google.devtools.build.lib.util.Pair;
@@ -169,7 +174,7 @@ public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
         new DummyAction(
             ImmutableList.of(input1, input2), output, MiddlemanType.AGGREGATING_MIDDLEMAN);
     // Overwrite default generating action with this one.
-    for (Iterator<Action> it = actions.iterator(); it.hasNext(); ) {
+    for (Iterator<ActionAnalysisMetadata> it = actions.iterator(); it.hasNext(); ) {
       if (it.next().getOutputs().contains(output)) {
         it.remove();
         break;
@@ -324,6 +329,70 @@ public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
         .testEquals();
   }
 
+  @Test
+  public void testActionTreeArtifactOutput() throws Throwable {
+    Artifact artifact = createDerivedTreeArtifactWithAction("treeArtifact");
+    TreeFileArtifact treeFileArtifact1 = createFakeTreeFileArtifact(artifact, "child1", "hello1");
+    TreeFileArtifact treeFileArtifact2 = createFakeTreeFileArtifact(artifact, "child2", "hello2");
+
+    TreeArtifactValue value = (TreeArtifactValue) evaluateArtifactValue(artifact);
+    assertNotNull(value.getChildValue(treeFileArtifact1));
+    assertNotNull(value.getChildValue(treeFileArtifact2));
+    assertNotNull(value.getChildValue(treeFileArtifact1).getDigest());
+    assertNotNull(value.getChildValue(treeFileArtifact2).getDigest());
+  }
+
+  @Test
+  public void testSpawnActionTemplate() throws Throwable {
+    // artifact1 is a tree artifact generated by normal action.
+    Artifact artifact1 = createDerivedTreeArtifactWithAction("treeArtifact1");
+    createFakeTreeFileArtifact(artifact1, "child1", "hello1");
+    createFakeTreeFileArtifact(artifact1, "child2", "hello2");
+
+
+    // artifact2 is a tree artifact generated by action template.
+    Artifact artifact2 = createDerivedTreeArtifactOnly("treeArtifact2");
+    TreeFileArtifact treeFileArtifact1 = createFakeTreeFileArtifact(artifact2, "child1", "hello1");
+    TreeFileArtifact treeFileArtifact2 = createFakeTreeFileArtifact(artifact2, "child2", "hello2");
+
+    actions.add(
+        ActionsTestUtil.createDummySpawnActionTemplate(artifact1, artifact2));
+
+    TreeArtifactValue value = (TreeArtifactValue) evaluateArtifactValue(artifact2);
+    assertNotNull(value.getChildValue(treeFileArtifact1));
+    assertNotNull(value.getChildValue(treeFileArtifact2));
+    assertNotNull(value.getChildValue(treeFileArtifact1).getDigest());
+    assertNotNull(value.getChildValue(treeFileArtifact2).getDigest());
+  }
+
+  @Test
+  public void testConsecutiveSpawnActionTemplates() throws Throwable {
+    // artifact1 is a tree artifact generated by normal action.
+    Artifact artifact1 = createDerivedTreeArtifactWithAction("treeArtifact1");
+    createFakeTreeFileArtifact(artifact1, "child1", "hello1");
+    createFakeTreeFileArtifact(artifact1, "child2", "hello2");
+
+    // artifact2 is a tree artifact generated by action template.
+    Artifact artifact2 = createDerivedTreeArtifactOnly("treeArtifact2");
+    createFakeTreeFileArtifact(artifact2, "child1", "hello1");
+    createFakeTreeFileArtifact(artifact2, "child2", "hello2");
+    actions.add(
+        ActionsTestUtil.createDummySpawnActionTemplate(artifact1, artifact2));
+
+    // artifact3 is a tree artifact generated by action template.
+    Artifact artifact3 = createDerivedTreeArtifactOnly("treeArtifact3");
+    TreeFileArtifact treeFileArtifact1 = createFakeTreeFileArtifact(artifact3, "child1", "hello1");
+    TreeFileArtifact treeFileArtifact2 = createFakeTreeFileArtifact(artifact3, "child2", "hello2");
+    actions.add(
+        ActionsTestUtil.createDummySpawnActionTemplate(artifact2, artifact3));
+
+    TreeArtifactValue value = (TreeArtifactValue) evaluateArtifactValue(artifact3);
+    assertNotNull(value.getChildValue(treeFileArtifact1));
+    assertNotNull(value.getChildValue(treeFileArtifact2));
+    assertNotNull(value.getChildValue(treeFileArtifact1).getDigest());
+    assertNotNull(value.getChildValue(treeFileArtifact2).getDigest());
+  }
+
   private void file(Path path, String contents) throws Exception {
     FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
     writeFile(path, contents);
@@ -343,6 +412,33 @@ public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
     return output;
   }
 
+  private Artifact createDerivedTreeArtifactWithAction(String path) {
+    Artifact treeArtifact = createDerivedTreeArtifactOnly(path);
+    actions.add(new DummyAction(ImmutableList.<Artifact>of(), treeArtifact));
+    return treeArtifact;
+  }
+
+  private Artifact createDerivedTreeArtifactOnly(String path) {
+    PathFragment execPath = new PathFragment("out").getRelative(path);
+    Path fullPath = root.getRelative(execPath);
+    return new SpecialArtifact(
+        fullPath,
+        Root.asDerivedRoot(root, root.getRelative("out")),
+        execPath,
+        ALL_OWNER,
+        SpecialArtifactType.TREE);
+  }
+
+  private TreeFileArtifact createFakeTreeFileArtifact(Artifact treeArtifact,
+      String parentRelativePath, String content) throws Exception {
+    TreeFileArtifact treeFileArtifact = ActionInputHelper.treeFileArtifact(
+        treeArtifact, new PathFragment(parentRelativePath));
+    Path path = treeFileArtifact.getPath();
+    FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
+    writeFile(path, content);
+    return treeFileArtifact;
+  }
+
   private void assertValueMatches(FileStatus file, byte[] digest, FileArtifactValue value)
       throws IOException {
     assertEquals(file.getSize(), value.getSize());
@@ -384,35 +480,46 @@ public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
       throws InterruptedException {
     setGeneratingActions();
     return driver.evaluate(
-        Arrays.asList(keys), /*keepGoing=*/
-        false,
+        Arrays.asList(keys),
+        /*keepGoing=*/false,
         SkyframeExecutor.DEFAULT_THREAD_COUNT,
         NullEventHandler.INSTANCE);
   }
 
   /** Value Builder for actions that just stats and stores the output file (which must exist). */
-  private class SimpleActionExecutionFunction implements SkyFunction {
+  private static class SimpleActionExecutionFunction implements SkyFunction {
     @Override
     public SkyValue compute(SkyKey skyKey, Environment env) {
       Map<Artifact, FileValue> artifactData = new HashMap<>();
+      Map<Artifact, TreeArtifactValue> treeArtifactData = new HashMap<>();
+      Map<Artifact, FileArtifactValue> additionalOutputData = new HashMap<>();
       Action action = (Action) skyKey.argument();
       Artifact output = Iterables.getOnlyElement(action.getOutputs());
-      FileArtifactValue value;
-      if (action.getActionType() == MiddlemanType.NORMAL) {
-        try {
+
+      try {
+        if (output.isTreeArtifact()) {
+          TreeFileArtifact treeFileArtifact1 = ActionInputHelper.treeFileArtifact(
+              output, new PathFragment("child1"));
+          TreeFileArtifact treeFileArtifact2 = ActionInputHelper.treeFileArtifact(
+              output, new PathFragment("child2"));
+          TreeArtifactValue treeArtifactValue = TreeArtifactValue.create(ImmutableMap.of(
+              treeFileArtifact1, FileArtifactValue.create(treeFileArtifact1),
+              treeFileArtifact2, FileArtifactValue.create(treeFileArtifact2)));
+          treeArtifactData.put(output, treeArtifactValue);
+        } else if (action.getActionType() == MiddlemanType.NORMAL) {
           FileValue fileValue = ActionMetadataHandler.fileValueFromArtifact(output, null, null);
           artifactData.put(output, fileValue);
-          value = FileArtifactValue.create(output, fileValue);
-        } catch (IOException e) {
-          throw new IllegalStateException(e);
+          additionalOutputData.put(output, FileArtifactValue.create(output, fileValue));
+       } else {
+          additionalOutputData.put(output, FileArtifactValue.DEFAULT_MIDDLEMAN);
         }
-      } else {
-        value = FileArtifactValue.DEFAULT_MIDDLEMAN;
+      } catch (IOException e) {
+        throw new IllegalStateException(e);
       }
       return new ActionExecutionValue(
           artifactData,
-          ImmutableMap.<Artifact, TreeArtifactValue>of(),
-          ImmutableMap.of(output, value));
+          treeArtifactData,
+          additionalOutputData);
     }
 
     @Override
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
index aa3fba5875..d964e2ddd5 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
@@ -17,7 +17,7 @@ import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
@@ -54,7 +54,7 @@ abstract class ArtifactFunctionTestCase {
 
   protected Predicate<PathFragment> allowedMissingInputsPredicate = Predicates.alwaysFalse();
 
-  protected Set<Action> actions;
+  protected Set<ActionAnalysisMetadata> actions;
   protected boolean fastDigest = false;
   protected RecordingDifferencer differencer = new RecordingDifferencer();
   protected SequentialBuildDriver driver;
@@ -101,6 +101,8 @@ abstract class ArtifactFunctionTestCase {
                         new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
                         directories))
                 .put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction())
+                .put(SkyFunctions.ACTION_TEMPLATE_EXPANSION,
+                     new ActionTemplateExpansionFunction())
                 .build(),
             differencer);
     driver = new SequentialBuildDriver(evaluator);
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 9f6bf6c544..9c51cb1d5a 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
@@ -65,6 +65,7 @@ import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
@@ -99,7 +100,7 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
   protected Clock clock = BlazeClock.instance();
   protected TimestampGranularityMonitor tsgm;
   protected RecordingDifferencer differencer = new RecordingDifferencer();
-  private Set<Action> actions;
+  private Set<ActionAnalysisMetadata> actions;
 
   protected AtomicReference<EventBus> eventBusRef = new AtomicReference<>();
 
@@ -109,13 +110,14 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
     tsgm = new TimestampGranularityMonitor(clock);
     ResourceManager.instance().setAvailableResources(ResourceSet.createWithRamCpuIo(100, 1, 1));
     actions = new HashSet<>();
+    actionTemplateExpansionFunction = new ActionTemplateExpansionFunction();
   }
 
   protected void clearActions() {
     actions.clear();
   }
 
-  protected <T extends Action> T registerAction(T action) {
+  protected <T extends ActionAnalysisMetadata> T registerAction(T action) {
     actions.add(action);
     return action;
   }
@@ -182,6 +184,8 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
                         new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
                         directories))
                 .put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction())
+                .put(SkyFunctions.ACTION_TEMPLATE_EXPANSION,
+                     new DelegatingActionTemplateExpansionFunction())
                 .build(),
             differencer,
             evaluationProgressReceiver);
@@ -194,7 +198,7 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
         if (evaluator.getExistingValueForTesting(OWNER_KEY) == null) {
           differencer.inject(ImmutableMap.of(
               OWNER_KEY,
-              new ActionLookupValue(ImmutableList.<ActionAnalysisMetadata>copyOf(actions))));
+              new ActionLookupValue(ImmutableList.copyOf(actions))));
         }
       }
 
@@ -248,6 +252,8 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
   /** A non-persistent cache. */
   protected InMemoryActionCache inMemoryCache;
 
+  protected SkyFunction actionTemplateExpansionFunction;
+
   /** A class that records an event. */
   protected static class Button implements Runnable {
     protected boolean pressed = false;
@@ -401,4 +407,17 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
       throw new UnsupportedOperationException();
     }
   }
+
+  private class DelegatingActionTemplateExpansionFunction implements SkyFunction {
+    @Override
+    public SkyValue compute(SkyKey skyKey, Environment env)
+        throws SkyFunctionException, InterruptedException {
+      return actionTemplateExpansionFunction.compute(skyKey, env);
+    }
+
+    @Override
+    public String extractTag(SkyKey skyKey) {
+      return actionTemplateExpansionFunction.extractTag(skyKey);
+    }   
+  }
 }
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 7304462046..66cacfd938 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
@@ -24,9 +24,12 @@ import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.Collections2;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.Lists;
+import com.google.common.collect.Multimap;
 import com.google.common.hash.Hashing;
 import com.google.common.util.concurrent.Runnables;
+import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.ActionInput;
@@ -35,10 +38,15 @@ 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.BuildFailedException;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.actions.cache.InjectedStat;
 import com.google.devtools.build.lib.actions.cache.MetadataHandler;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.actions.util.TestAction;
+import com.google.devtools.build.lib.actions.util.TestAction.DummyAction;
+import com.google.devtools.build.lib.analysis.actions.SpawnActionTemplate;
+import com.google.devtools.build.lib.skyframe.ActionTemplateExpansionValue.ActionTemplateExpansionKey;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileSystem;
@@ -46,6 +54,9 @@ import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Symlinks;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
 
 import org.junit.Before;
 import org.junit.Test;
@@ -481,6 +492,199 @@ public class TreeArtifactBuildTest extends TimestampBuilderTestCase {
     buildArtifact(action.getSoleOutput());
   }
 
+  @Test
+  public void testExpandedActionsBuildInActionTemplate() throws Throwable {
+    // artifact1 is a tree artifact generated by a TouchingTestAction.
+    Artifact artifact1 = createTreeArtifact("treeArtifact1");
+    TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child1"));
+    TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child2"));
+    registerAction(new TouchingTestAction(treeFileArtifactA, treeFileArtifactB));
+
+    // artifact2 is a tree artifact generated by an action template.
+    Artifact artifact2 = createTreeArtifact("treeArtifact2");
+    SpawnActionTemplate actionTemplate = ActionsTestUtil.createDummySpawnActionTemplate(
+        artifact1, artifact2);
+    registerAction(actionTemplate);
+
+    // We mock out the action template function to expand into two actions that just touch the
+    // output files.
+    TreeFileArtifact expectedOutputTreeFileArtifact1 = ActionInputHelper.treeFileArtifact(
+        artifact2, new PathFragment("child1"));
+    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
+        artifact2, new PathFragment("child2"));
+    Action generateOutputAction = new DummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactA), expectedOutputTreeFileArtifact1);
+    Action noGenerateOutputAction = new DummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactB), expectedOutputTreeFileArtifact2);
+
+    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
+        ImmutableMultimap.of(
+            actionTemplate, generateOutputAction,
+            actionTemplate, noGenerateOutputAction));
+
+    buildArtifact(artifact2);
+  }
+
+  @Test
+  public void testExpandedActionDoesNotGenerateOutputInActionTemplate() throws Throwable {
+    // expect errors
+    reporter.removeHandler(failFastHandler);
+
+    // artifact1 is a tree artifact generated by a TouchingTestAction.
+    Artifact artifact1 = createTreeArtifact("treeArtifact1");
+    TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child1"));
+    TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child2"));
+    registerAction(new TouchingTestAction(treeFileArtifactA, treeFileArtifactB));
+
+    // artifact2 is a tree artifact generated by an action template.
+    Artifact artifact2 = createTreeArtifact("treeArtifact2");
+    SpawnActionTemplate actionTemplate = ActionsTestUtil.createDummySpawnActionTemplate(
+        artifact1, artifact2);
+    registerAction(actionTemplate);
+
+    // 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, new PathFragment("child1"));
+    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
+        artifact2, new PathFragment("child2"));
+    Action generateOutputAction = new DummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactA), expectedOutputTreeFileArtifact1);
+    Action noGenerateOutputAction = new NoOpDummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactB),
+        ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact2));
+
+    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
+        ImmutableMultimap.of(
+            actionTemplate, generateOutputAction,
+            actionTemplate, noGenerateOutputAction));
+
+    try {
+      buildArtifact(artifact2);
+      fail("Expected BuildFailedException");
+    } catch (BuildFailedException e) {
+      assertThat(e.getMessage()).contains("not all outputs were created");
+    }
+  }
+
+  @Test
+  public void testOneExpandedActionThrowsInActionTemplate() throws Throwable {
+    // expect errors
+    reporter.removeHandler(failFastHandler);
+
+    // artifact1 is a tree artifact generated by a TouchingTestAction.
+    Artifact artifact1 = createTreeArtifact("treeArtifact1");
+    TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child1"));
+    TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child2"));
+    registerAction(new TouchingTestAction(treeFileArtifactA, treeFileArtifactB));
+
+    // artifact2 is a tree artifact generated by an action template.
+    Artifact artifact2 = createTreeArtifact("treeArtifact2");
+    SpawnActionTemplate actionTemplate = ActionsTestUtil.createDummySpawnActionTemplate(
+        artifact1, artifact2);
+    registerAction(actionTemplate);
+
+    // 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, new PathFragment("child1"));
+    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
+        artifact2, new PathFragment("child2"));
+    Action generateOutputAction = new DummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactA), expectedOutputTreeFileArtifact1);
+    Action throwingAction = new ThrowingDummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactB),
+        ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact2));
+    
+    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
+        ImmutableMultimap.of(
+            actionTemplate, generateOutputAction,
+            actionTemplate, throwingAction));
+
+    try {
+      buildArtifact(artifact2);
+      fail("Expected BuildFailedException");
+    } catch (BuildFailedException e) {
+      assertThat(e.getMessage()).contains("Throwing dummy action");
+    }
+  }
+
+  @Test
+  public void testAllExpandedActionsThrowInActionTemplate() throws Throwable {
+    // expect errors
+    reporter.removeHandler(failFastHandler);
+
+    // artifact1 is a tree artifact generated by a TouchingTestAction.
+    Artifact artifact1 = createTreeArtifact("treeArtifact1");
+    TreeFileArtifact treeFileArtifactA = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child1"));
+    TreeFileArtifact treeFileArtifactB = ActionInputHelper.treeFileArtifact(
+        artifact1, new PathFragment("child2"));
+    registerAction(new TouchingTestAction(treeFileArtifactA, treeFileArtifactB));
+
+    // artifact2 is a tree artifact generated by an action template.
+    Artifact artifact2 = createTreeArtifact("treeArtifact2");
+    SpawnActionTemplate actionTemplate = ActionsTestUtil.createDummySpawnActionTemplate(
+        artifact1, artifact2);
+    registerAction(actionTemplate);
+
+    // We mock out the action template function to expand into two actions that throw when executed.
+    TreeFileArtifact expectedOutputTreeFileArtifact1 = ActionInputHelper.treeFileArtifact(
+        artifact2, new PathFragment("child1"));
+    TreeFileArtifact expectedOutputTreeFileArtifact2 = ActionInputHelper.treeFileArtifact(
+        artifact2, new PathFragment("child2"));
+    Action throwingAction = new ThrowingDummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactA),
+        ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact1));
+    Action anotherThrowingAction = new ThrowingDummyAction(
+        ImmutableList.<Artifact>of(treeFileArtifactB),
+        ImmutableList.<Artifact>of(expectedOutputTreeFileArtifact2));
+    
+    actionTemplateExpansionFunction = new DummyActionTemplateExpansionFunction(
+        ImmutableMultimap.of(
+            actionTemplate, throwingAction,
+            actionTemplate, anotherThrowingAction));
+
+    try {
+      buildArtifact(artifact2);
+      fail("Expected BuildFailedException");
+    } catch (BuildFailedException e) {
+      assertThat(e.getMessage()).contains("Throwing dummy action");
+    }
+  }
+
+  @Test
+  public void testInputTreeArtifactCreationFailedInActionTemplate() throws Throwable {
+    // expect errors
+    reporter.removeHandler(failFastHandler);
+
+    // artifact1 is created by a action that throws.
+    Artifact artifact1 = createTreeArtifact("treeArtifact1");
+    registerAction(
+        new ThrowingDummyAction(ImmutableList.<Artifact>of(), ImmutableList.of(artifact1)));
+
+    // artifact2 is a tree artifact generated by an action template.
+    Artifact artifact2 = createTreeArtifact("treeArtifact2");
+    SpawnActionTemplate actionTemplate = ActionsTestUtil.createDummySpawnActionTemplate(
+        artifact1, artifact2);
+    registerAction(actionTemplate);
+
+    try {
+      buildArtifact(artifact2);
+      fail("Expected BuildFailedException");
+    } catch (BuildFailedException e) {
+      assertThat(e.getMessage()).contains("Throwing dummy action");
+    }
+  }
+
   /**
    * A generic test action that takes at most one input TreeArtifact,
    * exactly one output TreeArtifact, and some path fragment inputs/outputs.
@@ -766,4 +970,53 @@ public class TreeArtifactBuildTest extends TimestampBuilderTestCase {
       path.delete();
     }
   }
+
+  /** A dummy action template expansion function that just returns the injected actions */
+  private static class DummyActionTemplateExpansionFunction implements SkyFunction {
+    private final Multimap<SpawnActionTemplate, Action> actionTemplateToActionMap;
+
+    DummyActionTemplateExpansionFunction(
+        Multimap<SpawnActionTemplate, Action> actionTemplateToActionMap) {
+      this.actionTemplateToActionMap = actionTemplateToActionMap;
+    }
+
+    @Override
+    public SkyValue compute(SkyKey skyKey, Environment env) {
+      ActionTemplateExpansionKey key = (ActionTemplateExpansionKey) skyKey.argument();
+      SpawnActionTemplate actionTemplate = key.getActionTemplate();
+      return new ActionTemplateExpansionValue(
+          Preconditions.checkNotNull(actionTemplateToActionMap.get(actionTemplate)));
+    }
+
+    @Override
+    public String extractTag(SkyKey skyKey) {
+      return null;
+    }
+  }
+
+  /** No-op action that does not generate the action outputs. */
+  private static class NoOpDummyAction extends TestAction {
+    public NoOpDummyAction(Collection<Artifact> inputs, Collection<Artifact> outputs) {
+      super(NO_EFFECT, inputs, outputs);
+    }
+
+    /** Do nothing */
+    @Override
+    public void execute(ActionExecutionContext actionExecutionContext)
+        throws ActionExecutionException {}
+  }
+
+  /** No-op action that throws when executed */
+  private static class ThrowingDummyAction extends TestAction {
+    public ThrowingDummyAction(Collection<Artifact> inputs, Collection<Artifact> outputs) {
+      super(NO_EFFECT, inputs, outputs);
+    }
+
+    /** Throws */
+    @Override
+    public void execute(ActionExecutionContext actionExecutionContext)
+        throws ActionExecutionException {
+      throw new ActionExecutionException("Throwing dummy action", this, true);
+    }
+  }
 }