Support for handling TreeArtifact metadata and returning TreeArtifacts from ArtifactFunction.

--
MOS_MIGRATED_REVID=114174899

15 files changed, 956 insertions, 210 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
index 964fc7389e..e75ab9adbb 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
@@ -15,6 +15,7 @@ package com.google.devtools.build.lib.actions.cache;
 
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.actions.MiddlemanAction;
 import com.google.devtools.build.lib.vfs.FileStatus;
 
@@ -49,6 +50,13 @@ public interface MetadataHandler {
   void setDigestForVirtualArtifact(Artifact artifact, Digest digest);
 
   /**
+   * Registers the given output as contents of a TreeArtifact, without injecting its digest.
+   * Prefer {@link #injectDigest} when the digest is available.
+   * @throws IllegalStateException if the given output does not have a TreeArtifact parent.
+   */
+  void addExpandedTreeOutput(ArtifactFile output) throws IllegalStateException;
+
+  /**
    * Injects provided digest into the metadata handler, simultaneously caching lstat() data as well.
    */
   void injectDigest(ActionInput output, FileStatus statNoFollow, byte[] digest);
@@ -75,14 +83,14 @@ public interface MetadataHandler {
   boolean artifactOmitted(Artifact artifact);
 
   /**
-   * @return Whether the artifact's data was injected.
-   * @throws IOException if implementation tried to stat artifact which threw an exception.
+   * @return Whether the ArtifactFile's data was injected.
+   * @throws IOException if implementation tried to stat the ArtifactFile which threw an exception.
    *         Technically, this means that the artifact could not have been injected, but by throwing
    *         here we save the caller trying to stat this file on their own and throwing the same
    *         exception. Implementations are not guaranteed to throw in this case if they are able to
    *         determine that the artifact is not injected without statting it.
    */
-  boolean isInjected(Artifact artifact) throws IOException;
+  boolean isInjected(ArtifactFile file) throws IOException;
 
   /**
    * Discards all known output artifact metadata, presumably because outputs will be modified.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index c79fd134d1..0a210149d1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.base.Function;
 import com.google.common.base.Predicates;
 import com.google.common.collect.Collections2;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
@@ -335,7 +336,8 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
     if (state.token == null) {
       // We got a hit from the action cache -- no need to execute.
       return new ActionExecutionValue(
-          metadataHandler.getOutputData(),
+          metadataHandler.getOutputArtifactFileData(),
+          ImmutableMap.<Artifact, TreeArtifactValue>of(),
           metadataHandler.getAdditionalOutputData());
     }
 
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 187b4a4166..b0b9c51c42 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
@@ -20,6 +20,7 @@ import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.Action.MiddlemanType;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -36,19 +37,51 @@ import javax.annotation.Nullable;
 @Immutable
 @ThreadSafe
 public class ActionExecutionValue implements SkyValue {
-  private final ImmutableMap<Artifact, FileValue> artifactData;
+  /*
+  Concerning the data in this class:
+
+  We want to track all output data from an ActionExecutionValue. However, we want to separate
+  quickly-accessible Filesystem data from other kinds of data. We use FileValues
+  to represent data that may be quickly accessed, TreeArtifactValues to give us directory contents,
+  and FileArtifactValues inside TreeArtifactValues or the additionalOutputData map
+  to give us full mtime/digest information on all output files.
+
+  The reason for this separation is so that FileSystemValueChecker remains fast. When it checks
+  the validity of an ActionExecutionValue, it only checks the quickly-accessible data stored
+  in FileValues and TreeArtifactValues.
+   */
+
+  /**
+   * The FileValues of all files for this ActionExecutionValue. These FileValues can be
+   * read and checked quickly from the filesystem, unlike FileArtifactValues.
+   */
+  private final ImmutableMap<ArtifactFile, FileValue> artifactFileData;
+
+  /** The TreeArtifactValue of all TreeArtifacts output by this Action. */
+  private final ImmutableMap<Artifact, TreeArtifactValue> treeArtifactData;
+
+  /**
+   * Contains all remaining data that weren't in the above maps. See
+   * {@link ActionMetadataHandler#getAdditionalOutputData}.
+   */
   private final ImmutableMap<Artifact, FileArtifactValue> additionalOutputData;
 
   /**
-   * @param artifactData Map from Artifacts to corresponding FileValues.
+   * @param artifactFileData Map from Artifacts to corresponding FileValues.
+   * @param treeArtifactData All tree artifact data.
    * @param additionalOutputData Map from Artifacts to values if the FileArtifactValue for this
    *     artifact cannot be derived from the corresponding FileValue (see {@link
    *     ActionMetadataHandler#getAdditionalOutputData} for when this is necessary).
+   *     These output data are not used by the {@link FilesystemValueChecker}
+   *     to invalidate ActionExecutionValues.
    */
-  ActionExecutionValue(Map<Artifact, FileValue> artifactData,
+  ActionExecutionValue(
+      Map<? extends ArtifactFile, FileValue> artifactFileData,
+      Map<Artifact, TreeArtifactValue> treeArtifactData,
       Map<Artifact, FileArtifactValue> additionalOutputData) {
-    this.artifactData = ImmutableMap.copyOf(artifactData);
+    this.artifactFileData = ImmutableMap.<ArtifactFile, FileValue>copyOf(artifactFileData);
     this.additionalOutputData = ImmutableMap.copyOf(additionalOutputData);
+    this.treeArtifactData = ImmutableMap.copyOf(treeArtifactData);
   }
 
   /**
@@ -65,18 +98,32 @@ public class ActionExecutionValue implements SkyValue {
    * @return The data for each non-middleman output of this action, in the form of the {@link
    * FileValue} that would be created for the file if it were to be read from disk.
    */
-  FileValue getData(Artifact artifact) {
-    Preconditions.checkState(!additionalOutputData.containsKey(artifact),
-        "Should not be requesting data for already-constructed FileArtifactValue: %s", artifact);
-    return artifactData.get(artifact);
+  FileValue getData(ArtifactFile file) {
+    Preconditions.checkState(!additionalOutputData.containsKey(file),
+        "Should not be requesting data for already-constructed FileArtifactValue: %s", file);
+    return artifactFileData.get(file);
+  }
+
+  TreeArtifactValue getTreeArtifactValue(Artifact artifact) {
+    Preconditions.checkArgument(artifact.isTreeArtifact());
+    return treeArtifactData.get(artifact);
+  }
+
+  /**
+   * @return The map from {@link ArtifactFile}s to the corresponding {@link FileValue}s that would
+   * be returned by {@link #getData}. Should only be needed by {@link FilesystemValueChecker}.
+   */
+  ImmutableMap<ArtifactFile, FileValue> getAllFileValues() {
+    return artifactFileData;
   }
 
   /**
-   * @return The map from {@link Artifact} to the corresponding {@link FileValue} that would be
-   * returned by {@link #getData}. Should only be needed by {@link FilesystemValueChecker}.
+   * @return The map from {@link Artifact}s to the corresponding {@link TreeArtifactValue}s that
+   * would be returned by {@link #getTreeArtifactValue}. Should only be needed by
+   * {@link FilesystemValueChecker}.
    */
-  ImmutableMap<Artifact, FileValue> getAllOutputArtifactData() {
-    return artifactData;
+  ImmutableMap<Artifact, TreeArtifactValue> getAllTreeArtifactValues() {
+    return treeArtifactData;
   }
 
   @ThreadSafe
@@ -111,7 +158,8 @@ public class ActionExecutionValue implements SkyValue {
   @Override
   public String toString() {
     return MoreObjects.toStringHelper(this)
-        .add("artifactData", artifactData)
+        .add("artifactFileData", artifactFileData)
+        .add("treeArtifactData", treeArtifactData)
         .add("additionalOutputData", additionalOutputData)
         .toString();
   }
@@ -125,12 +173,13 @@ public class ActionExecutionValue implements SkyValue {
       return false;
     }
     ActionExecutionValue o = (ActionExecutionValue) obj;
-    return artifactData.equals(o.artifactData)
+    return artifactFileData.equals(o.artifactFileData)
+        && treeArtifactData.equals(o.treeArtifactData)
         && additionalOutputData.equals(o.additionalOutputData);
   }
 
   @Override
   public int hashCode() {
-    return Objects.hashCode(artifactData, additionalOutputData);
+    return Objects.hashCode(artifactFileData, treeArtifactData, additionalOutputData);
   }
 }
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 be264f768d..3d845f6858 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
@@ -16,10 +16,12 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.common.io.BaseEncoding;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.actions.cache.Digest;
 import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.actions.cache.Metadata;
@@ -30,12 +32,15 @@ import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileStatusWithDigest;
 import com.google.devtools.build.lib.vfs.FileStatusWithDigestAdapter;
 import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.lib.vfs.Symlinks;
 
 import java.io.FileNotFoundException;
 import java.io.IOException;
 import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
@@ -54,22 +59,67 @@ import javax.annotation.Nullable;
  * ways. First, it is served as requested during action execution, primarily by the {@code
  * ActionCacheChecker} when determining if the action must be rerun, and then after the action is
  * run, to gather information about the outputs. Second, it is accessed by {@link
- * ArtifactFunction}s in order to construct {@link ArtifactValue}s. Third, the {@link
+ * ArtifactFunction}s in order to construct {@link ArtifactValue}, and by this class itself to
+ * generate {@link TreeArtifactValue}s. Third, the {@link
  * FilesystemValueChecker} uses it to determine the set of output files to check for inter-build
  * modifications. Because all these use cases are slightly different, we must occasionally store two
- * versions of the data for a value (see {@link #getAdditionalOutputData} for more.
+ * versions of the data for a value. See {@link #getAdditionalOutputData} for elaboration on
+ * the difference between these cases, and see the javadoc for the various internal maps to see
+ * what is stored where.
  */
 @VisibleForTesting
 public class ActionMetadataHandler implements MetadataHandler {
-  /** This should never be read directly. Use {@link #getInputFileArtifactValue} instead. */
+
+  /**
+   * Data for input artifacts. Immutable.
+   *
+   * <p>This should never be read directly. Use {@link #getInputFileArtifactValue} instead.</p>
+   */
   private final Map<Artifact, FileArtifactValue> inputArtifactData;
-  private final ConcurrentMap<Artifact, FileValue> outputArtifactData =
+
+  /** FileValues for each output ArtifactFile. */
+  private final ConcurrentMap<ArtifactFile, FileValue> outputArtifactFileData =
       new ConcurrentHashMap<>();
+
+  /**
+   * Maps output TreeArtifacts to their contents. These maps are either injected or read
+   * directly from the filesystem.
+   * If the value is null, this means nothing was injected, and the output TreeArtifact
+   * is to have its values read from disk instead.
+   */
+  private final ConcurrentMap<Artifact, Set<ArtifactFile>> outputDirectoryListings =
+      new ConcurrentHashMap<>();
+
+  /** Outputs that are to be omitted. */
   private final Set<Artifact> omittedOutputs = Sets.newConcurrentHashSet();
-  // See #getAdditionalOutputData for documentation of this field.
+
+  /**
+   * Contains RealArtifactValues when those values must be stored separately.
+   * See {@link #getAdditionalOutputData()} for details.
+   */
   private final ConcurrentMap<Artifact, FileArtifactValue> additionalOutputData =
       new ConcurrentHashMap<>();
-  private final Set<Artifact> injectedArtifacts = Sets.newConcurrentHashSet();
+
+  /**
+   * 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<ArtifactFile, FileArtifactValue> cachedTreeArtifactFileData =
+      new ConcurrentHashMap<>();
+
+  /**
+   * Data for TreeArtifactValues, constructed from outputArtifactFileData and
+   * additionalOutputFileData.
+   */
+  private final ConcurrentMap<Artifact, TreeArtifactValue> outputTreeArtifactData =
+      new ConcurrentHashMap<>();
+
+  /** Tracks which ArtifactFiles have had metadata injected. */
+  private final Set<ArtifactFile> injectedFiles = Sets.newConcurrentHashSet();
+
   private final ImmutableSet<Artifact> outputs;
   private final TimestampGranularityMonitor tsgm;
 
@@ -121,7 +171,11 @@ public class ActionMetadataHandler implements MetadataHandler {
   }
 
   /**
-   * We cache data for constant-metadata artifacts, even though it is technically unnecessary,
+   * Get the real (viz. on-disk) metadata for an Artifact.
+   * A key assumption is that getRealMetadata() will be called for every Artifact in this
+   * ActionMetadataHandler, to populate additionalOutputData and outputTreeArtifactData.
+   *
+   * <p>We cache data for constant-metadata artifacts, even though it is technically unnecessary,
    * because the data stored in this cache is consumed by various parts of Blaze via the {@link
    * ActionExecutionValue} (for now, {@link FilesystemValueChecker} and {@link ArtifactFunction}).
    * It is simpler for those parts if every output of the action is present in the cache. However,
@@ -148,8 +202,17 @@ public class ActionMetadataHandler implements MetadataHandler {
       FileArtifactValue oldValue = additionalOutputData.putIfAbsent(artifact, value);
       checkInconsistentData(artifact, oldValue, value);
       return metadataFromValue(value);
+    } else if (artifact.isTreeArtifact()) {
+      TreeArtifactValue setValue = getTreeArtifactValue(artifact);
+      if (setValue != null && setValue != TreeArtifactValue.MISSING_TREE_ARTIFACT) {
+        return setValue.getMetadata();
+      }
+      // We use FileNotFoundExceptions to determine if an Artifact was or wasn't found.
+      // Calling code depends on this particular exception.
+      throw new FileNotFoundException(artifact + " not found");
     }
-    FileValue fileValue = outputArtifactData.get(artifact);
+    // It's an ordinary artifact.
+    FileValue fileValue = outputArtifactFileData.get(artifact);
     if (fileValue != null) {
       // Non-middleman artifacts should only have additionalOutputData if they have
       // outputArtifactData. We don't assert this because of concurrency possibilities, but at least
@@ -167,23 +230,21 @@ public class ActionMetadataHandler implements MetadataHandler {
     }
     // We do not cache exceptions besides nonexistence here, because it is unlikely that the file
     // will be requested from this cache too many times.
-    fileValue = fileValueFromArtifact(artifact, null, tsgm);
-    FileValue oldFileValue = outputArtifactData.putIfAbsent(artifact, fileValue);
-    checkInconsistentData(artifact, oldFileValue, value);
+    fileValue = constructFileValue(artifact, null);
     return maybeStoreAdditionalData(artifact, fileValue, null);
   }
 
   /**
-   * Check that the new {@code data} we just calculated for an {@code artifact} agrees with the
+   * Check that the new {@code data} we just calculated for an {@link ArtifactFile} agrees with the
    * {@code oldData} (presumably calculated concurrently), if it was present.
    */
   // Not private only because used by SkyframeActionExecutor's metadata handler.
-  static void checkInconsistentData(Artifact artifact,
+  static void checkInconsistentData(ArtifactFile file,
       @Nullable Object oldData, Object data) throws IOException {
     if (oldData != null && !oldData.equals(data)) {
       // Another thread checked this file since we looked at the map, and got a different answer
       // than we did. Presumably the user modified the file between reads.
-      throw new IOException("Data for " + artifact.prettyPrint() + " changed to " + data
+      throw new IOException("Data for " + file.prettyPrint() + " changed to " + data
           + " after it was calculated as " + oldData);
     }
   }
@@ -193,63 +254,145 @@ public class ActionMetadataHandler implements MetadataHandler {
    * for normal (non-middleman) artifacts.
    */
   @Nullable
-  private Metadata maybeStoreAdditionalData(Artifact artifact, FileValue data,
+  private Metadata maybeStoreAdditionalData(ArtifactFile file, FileValue data,
       @Nullable byte[] injectedDigest) throws IOException {
     if (!data.exists()) {
       // Nonexistent files should only occur before executing an action.
-      throw new FileNotFoundException(artifact.prettyPrint() + " does not exist");
+      throw new FileNotFoundException(file.prettyPrint() + " does not exist");
     }
-    boolean isFile = data.isFile();
-    boolean useDigest = DigestUtils.useFileDigest(isFile, isFile ? data.getSize() : 0);
-    if (useDigest && data.getDigest() != null) {
-      // We do not need to store the FileArtifactValue separately -- the digest is in the file value
-      // and that is all that is needed for this file's metadata.
-      return new Metadata(data.getDigest());
+    if (file instanceof Artifact) {
+      // Artifacts may use either the "real" digest or the mtime, if the file is size 0.
+      boolean isFile = data.isFile();
+      boolean useDigest = DigestUtils.useFileDigest(isFile, isFile ? data.getSize() : 0);
+      if (useDigest && data.getDigest() != null) {
+        // We do not need to store the FileArtifactValue separately -- the digest is in the
+        // file value and that is all that is needed for this file's metadata.
+        return new Metadata(data.getDigest());
+      }
+      // Unfortunately, the FileValue does not contain enough information for us to calculate the
+      // corresponding FileArtifactValue -- either the metadata must use the modified time, which we
+      // do not expose in the FileValue, or the FileValue didn't store the digest So we store the
+      // metadata separately.
+      // Use the FileValue's digest if no digest was injected, or if the file can't be digested.
+      injectedDigest = injectedDigest != null || !isFile ? injectedDigest : data.getDigest();
+      FileArtifactValue value =
+          FileArtifactValue.create(
+              (Artifact) file, isFile, isFile ? data.getSize() : 0, injectedDigest);
+      FileArtifactValue oldValue = additionalOutputData.putIfAbsent((Artifact) file, value);
+      checkInconsistentData(file, oldValue, value);
+      return metadataFromValue(value);
+    } else {
+      // Non-Artifact ArtifactFiles are always "real" files, and always use the real digest.
+      // When null, createWithDigest() will pull the digest from the filesystem.
+      FileArtifactValue value =
+          FileArtifactValue.createWithDigest(file.getPath(), injectedDigest, data.getSize());
+      FileArtifactValue oldValue = cachedTreeArtifactFileData.putIfAbsent(file, value);
+      checkInconsistentData(file, oldValue, value);
+      return new Metadata(value.getDigest());
     }
-    // Unfortunately, the FileValue does not contain enough information for us to calculate the
-    // corresponding FileArtifactValue -- either the metadata must use the modified time, which we
-    // do not expose in the FileValue, or the FileValue didn't store the digest So we store the
-    // metadata separately.
-    // Use the FileValue's digest if no digest was injected, or if the file can't be digested.
-    injectedDigest = injectedDigest != null || !isFile ? injectedDigest : data.getDigest();
-    FileArtifactValue value =
-        FileArtifactValue.create(artifact, isFile, isFile ? data.getSize() : 0, injectedDigest);
-    FileArtifactValue oldValue = additionalOutputData.putIfAbsent(artifact, value);
-    checkInconsistentData(artifact, oldValue, value);
-    return metadataFromValue(value);
   }
 
   @Override
   public void setDigestForVirtualArtifact(Artifact artifact, Digest digest) {
-    Preconditions.checkState(artifact.isMiddlemanArtifact(), artifact);
+    Preconditions.checkArgument(artifact.isMiddlemanArtifact(), artifact);
     Preconditions.checkNotNull(digest, artifact);
     additionalOutputData.put(artifact,
-        FileArtifactValue.createMiddleman(digest.asMetadata().digest));
+        FileArtifactValue.createProxy(digest.asMetadata().digest));
+  }
+
+  private Set<ArtifactFile> getTreeArtifactContents(Artifact artifact) {
+    Preconditions.checkArgument(artifact.isTreeArtifact(), artifact);
+    Set<ArtifactFile> contents = outputDirectoryListings.get(artifact);
+    if (contents == null) {
+      // Unfortunately, there is no such thing as a ConcurrentHashSet.
+      contents = Collections.newSetFromMap(new ConcurrentHashMap<ArtifactFile, Boolean>());
+      Set<ArtifactFile> oldContents = outputDirectoryListings.putIfAbsent(artifact, contents);
+      // Avoid a race condition.
+      if (oldContents != null) {
+        contents = oldContents;
+      }
+    }
+    return contents;
+  }
+
+  private TreeArtifactValue getTreeArtifactValue(Artifact artifact) throws IOException {
+    TreeArtifactValue value = outputTreeArtifactData.get(artifact);
+    if (value != null) {
+      return value;
+    }
+
+    Set<ArtifactFile> contents = outputDirectoryListings.get(artifact);
+    if (contents != null) {
+      value = constructTreeArtifactValue(contents);
+    } else {
+      // Functionality is planned to construct the TreeArtifactValue from disk here.
+      throw new UnsupportedOperationException();
+    }
+
+    TreeArtifactValue oldValue = outputTreeArtifactData.putIfAbsent(artifact, value);
+    checkInconsistentData(artifact, oldValue, value);
+    return value;
+  }
+
+  private TreeArtifactValue constructTreeArtifactValue(Collection<ArtifactFile> contents)
+      throws IOException {
+    Map<PathFragment, FileArtifactValue> values = Maps.newHashMapWithExpectedSize(contents.size());
+
+    for (ArtifactFile file : contents) {
+      FileArtifactValue cachedValue = cachedTreeArtifactFileData.get(file);
+      if (cachedValue == null) {
+        FileValue fileValue = outputArtifactFileData.get(file);
+        // This is similar to what's present in getRealMetadataForArtifactFile, except
+        // we get back the FileValue, not the metadata.
+        // We do not cache exceptions besides nonexistence here, because it is unlikely that the
+        // file will be requested from this cache too many times.
+        if (fileValue == null) {
+          fileValue = constructFileValue(file, /*statNoFollow=*/ null);
+          // A minor hack: maybeStoreAdditionalData will force the data to be stored
+          // in cachedTreeArtifactFileData.
+          maybeStoreAdditionalData(file, fileValue, null);
+        }
+        cachedValue = Preconditions.checkNotNull(cachedTreeArtifactFileData.get(file), file);
+      }
+
+      values.put(file.getParentRelativePath(), cachedValue);
+    }
+
+    return TreeArtifactValue.create(values);
+  }
+
+  @Override
+  public void addExpandedTreeOutput(ArtifactFile output) {
+    Preconditions.checkArgument(output.getParent().isTreeArtifact(),
+        "Expanded set output must belong to a TreeArtifact");
+    Set<ArtifactFile> values = getTreeArtifactContents(output.getParent());
+    values.add(output);
   }
 
   @Override
   public void injectDigest(ActionInput output, FileStatus statNoFollow, byte[] digest) {
-    if (output instanceof Artifact) {
-      Artifact artifact = (Artifact) output;
-      Preconditions.checkState(injectedArtifacts.add(artifact), artifact);
+    // Assumption: any non-ArtifactFile output is 'virtual' and should be ignored here.
+    if (output instanceof ArtifactFile) {
+      final ArtifactFile file = (ArtifactFile) output;
+      Preconditions.checkState(injectedFiles.add(file), file);
       FileValue fileValue;
       try {
         // This call may do an unnecessary call to Path#getFastDigest to see if the digest is
         // readily available. We cannot pass the digest in, though, because if it is not available
         // from the filesystem, this FileValue will not compare equal to another one created for the
         // same file, because the other one will be missing its digest.
-        fileValue = fileValueFromArtifact(artifact, FileStatusWithDigestAdapter.adapt(statNoFollow),
-            tsgm);
+        fileValue = fileValueFromArtifactFile(file,
+            FileStatusWithDigestAdapter.adapt(statNoFollow), tsgm);
         // Ensure the digest supplied matches the actual digest if it exists.
         byte[] fileDigest = fileValue.getDigest();
         if (fileDigest != null && !Arrays.equals(digest, fileDigest)) {
           BaseEncoding base16 = BaseEncoding.base16();
           String digestString = (digest != null) ? base16.encode(digest) : "null";
-          String fileDigestString = (fileDigest != null) ? base16.encode(fileDigest) : "null";
+          String fileDigestString = base16.encode(fileDigest);
           throw new IllegalStateException("Expected digest " + digestString + " for artifact "
-              + artifact + ", but got " + fileDigestString + " (" + fileValue + ")");
+              + file + ", but got " + fileDigestString + " (" + fileValue + ")");
         }
-        outputArtifactData.put(artifact, fileValue);
+        outputArtifactFileData.put(file, fileValue);
       } catch (IOException e) {
         // Do nothing - we just failed to inject metadata. Real error handling will be done later,
         // when somebody will try to access that file.
@@ -259,14 +402,14 @@ public class ActionMetadataHandler implements MetadataHandler {
       // the filesystem does not support fast digests. Since we usually only inject digests when
       // running with a filesystem that supports fast digests, this is fairly unlikely.
       try {
-        maybeStoreAdditionalData(artifact, fileValue, digest);
+        maybeStoreAdditionalData(file, fileValue, digest);
       } catch (IOException e) {
         if (fileValue.getSize() != 0) {
           // Empty files currently have their mtimes examined, and so could throw. No other files
           // should throw, since all filesystem access has already been done.
           throw new IllegalStateException(
               "Filesystem should not have been accessed while injecting data for "
-                  + artifact.prettyPrint(), e);
+                  + file.prettyPrint(), e);
         }
         // Ignore exceptions for empty files, as above.
       }
@@ -289,12 +432,15 @@ public class ActionMetadataHandler implements MetadataHandler {
 
   @Override
   public void discardOutputMetadata() {
-    Preconditions.checkState(injectedArtifacts.isEmpty(),
-        "Artifacts cannot be injected before action execution: %s", injectedArtifacts);
+    Preconditions.checkState(injectedFiles.isEmpty(),
+        "Files cannot be injected before action execution: %s", injectedFiles);
     Preconditions.checkState(omittedOutputs.isEmpty(),
         "Artifacts cannot be marked omitted before action execution: %s", omittedOutputs);
-    outputArtifactData.clear();
+    outputArtifactFileData.clear();
+    outputDirectoryListings.clear();
+    outputTreeArtifactData.clear();
     additionalOutputData.clear();
+    cachedTreeArtifactFileData.clear();
   }
 
   @Override
@@ -315,21 +461,26 @@ public class ActionMetadataHandler implements MetadataHandler {
   }
 
   @Override
-  public boolean isInjected(Artifact artifact) {
-    return injectedArtifacts.contains(artifact);
+  public boolean isInjected(ArtifactFile file) {
+    return injectedFiles.contains(file);
+  }
+
+  /** @return data for output files that was computed during execution. */
+  Map<ArtifactFile, FileValue> getOutputArtifactFileData() {
+    return outputArtifactFileData;
   }
 
   /**
-   * @return data for output files that was computed during execution. Should include data for all
-   * non-middleman artifacts.
+   * @return data for TreeArtifacts that was computed during execution. May contain copies of
+   * {@link TreeArtifactValue#MISSING_TREE_ARTIFACT}.
    */
-  Map<Artifact, FileValue> getOutputData() {
-    return outputArtifactData;
+  Map<Artifact, TreeArtifactValue> getOutputTreeArtifactData() {
+    return outputTreeArtifactData;
   }
 
   /**
    * Returns data for any output files whose metadata was not computable from the corresponding
-   * entry in {@link #getOutputData}.
+   * entry in {@link #getOutputArtifactFileData}.
    *
    * <p>There are three reasons why we might not be able to compute metadata for an artifact from
    * the FileValue. First, middleman artifacts have no corresponding FileValues. Second, if
@@ -346,12 +497,22 @@ public class ActionMetadataHandler implements MetadataHandler {
     return additionalOutputData;
   }
 
-  static FileValue fileValueFromArtifact(Artifact artifact,
+  /** Constructs a new FileValue, saves it, and checks inconsistent data. */
+  FileValue constructFileValue(ArtifactFile file, @Nullable FileStatusWithDigest statNoFollow)
+      throws IOException {
+    FileValue value = fileValueFromArtifactFile(file, statNoFollow, tsgm);
+    FileValue oldFsValue = outputArtifactFileData.putIfAbsent(file, value);
+    checkInconsistentData(file, oldFsValue, null);
+    return value;
+  }
+
+  @VisibleForTesting
+  static FileValue fileValueFromArtifactFile(ArtifactFile file,
       @Nullable FileStatusWithDigest statNoFollow, TimestampGranularityMonitor tsgm)
       throws IOException {
-    Path path = artifact.getPath();
+    Path path = file.getPath();
     RootedPath rootedPath =
-        RootedPath.toRootedPath(artifact.getRoot().getPath(), artifact.getRootRelativePath());
+        RootedPath.toRootedPath(file.getRoot().getPath(), file.getRootRelativePath());
     if (statNoFollow == null) {
       statNoFollow = FileStatusWithDigestAdapter.adapt(path.statIfFound(Symlinks.NOFOLLOW));
       if (statNoFollow == null) {
@@ -371,7 +532,7 @@ public class ActionMetadataHandler implements MetadataHandler {
       }
     }
     RootedPath realRootedPath = RootedPath.toRootedPathMaybeUnderRoot(realPath,
-        ImmutableList.of(artifact.getRoot().getPath()));
+        ImmutableList.of(file.getRoot().getPath()));
     FileStateValue fileStateValue;
     FileStateValue realFileStateValue;
     try {
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 ae5231a95e..312feefcef 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
@@ -76,7 +76,9 @@ class ArtifactFunction implements SkyFunction {
       return null;
     }
 
-    if (!isAggregatingValue(action)) {
+    if (artifact.isTreeArtifact()) {
+      return actionValue.getTreeArtifactValue(artifact);
+    } else if (!isAggregatingValue(action)) {
       try {
         return createSimpleValue(artifact, actionValue);
       } catch (IOException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java
index fd046e1ddd..8114ba9ebc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactValue.java
@@ -29,10 +29,11 @@ import java.util.Collection;
  * A value representing an artifact. Source artifacts are checked for existence, while output
  * artifacts imply creation of the output file.
  *
- * <p>There are effectively two kinds of output artifact values. The first corresponds to an
+ * <p>There are effectively three kinds of output artifact values. The first corresponds to an
  * ordinary artifact {@link FileArtifactValue}. It stores the relevant data for the artifact --
- * digest/mtime and size. The second corresponds to an "aggregating" artifact -- the output of an
- * aggregating middleman action. It stores the relevant data of all its inputs.
+ * digest/mtime and size. The second corresponds to either an "aggregating" artifact -- the output
+ * of an aggregating middleman action -- or a TreeArtifact. It stores the relevant data of all its
+ * inputs, as well as a combined digest for itself.
  */
 @Immutable
 @ThreadSafe
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java
index f7bbfc57ec..b55639eb94 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java
@@ -27,9 +27,21 @@ import java.util.Arrays;
 import javax.annotation.Nullable;
 
 /**
- * Stores the data of an artifact corresponding to a file. This file may be an ordinary file, in
- * which case we would expect to see a digest and size; a directory, in which case we would expect
- * to see an mtime; or an empty file, where we would expect to see a size (=0), mtime, and digest
+ * Stores the actual metadata data of a file. We have the following cases:
+ * <ul><li>
+ *   an ordinary file, in which case we would expect to see a digest and size;
+ * </li><li>
+ *   a directory, in which case we would expect to see an mtime;
+ * </li><li>
+ *   an empty file corresponding to an Artifact, where we would expect to see a size (=0), mtime,
+ *   and digest;
+ * </li><li>
+ *   an intentionally omitted file which the build system is aware of but doesn't actually exist,
+ *   where all access methods are unsupported;
+ * </li><li>
+ *   The "self data" of a middleman artifact or TreeArtifact, where we would expect to see a digest
+ *   representing the artifact's contents, and a size of 1.
+ * </li></ul>
  */
 public class FileArtifactValue extends ArtifactValue {
   /** Data for Middleman artifacts that did not have data specified. */
@@ -44,7 +56,7 @@ public class FileArtifactValue extends ArtifactValue {
   };
 
   /**
-   * Represents an omitted file- we are aware of it but it doesn't exist. All access methods
+   * Represents an omitted file -- we are aware of it but it doesn't exist. All access methods
    * are unsupported.
    */
   static final FileArtifactValue OMITTED_FILE_MARKER = new FileArtifactValue(null, 2, 0) {
@@ -62,7 +74,6 @@ public class FileArtifactValue extends ArtifactValue {
   private final long size;
 
   private FileArtifactValue(byte[] digest, long size) {
-    Preconditions.checkState(size >= 0, "size must be non-negative: %s %s", digest, size);
     this.digest = Preconditions.checkNotNull(digest, size);
     this.size = size;
     this.mtime = -1;
@@ -109,7 +120,23 @@ public class FileArtifactValue extends ArtifactValue {
     return new FileArtifactValue(digest, size);
   }
 
-  static FileArtifactValue createMiddleman(byte[] digest) {
+  /** Returns a FileArtifactValue with the given digest, even for empty files (size = 0). */
+  static FileArtifactValue createWithDigest(Path path, byte[] digest, long size)
+      throws IOException {
+    // Eventually, we want to migrate everything away from using mtimes instead of digests.
+    // But right now, some cases always use digests (TreeArtifacts) and some don't.
+    // So we have different constructors.
+    if (digest == null) {
+      digest = DigestUtils.getDigestOrFail(path, size);
+    }
+    return new FileArtifactValue(digest, size);
+  }
+
+  /**
+   * Creates a FileArtifactValue used as a 'proxy' input for other ArtifactValues.
+   * These are used in {@link com.google.devtools.build.lib.actions.ActionCacheChecker}.
+   */
+  static FileArtifactValue createProxy(byte[] digest) {
     Preconditions.checkNotNull(digest);
     // The Middleman artifact values have size 1 because we want their digests to be used. This hack
     // can be removed once empty files are digested.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
index 0067dc8b2d..6b4bc3c0e9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
@@ -21,6 +21,7 @@ import com.google.common.collect.Range;
 import com.google.common.collect.Sets;
 import com.google.common.util.concurrent.ThreadFactoryBuilder;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.concurrent.ExecutorUtil;
 import com.google.devtools.build.lib.concurrent.Sharder;
 import com.google.devtools.build.lib.concurrent.ThrowableRecordingRunnableWrapper;
@@ -219,9 +220,13 @@ public class FilesystemValueChecker {
           if (actionValue == null) {
             dirtyKeys.add(keyAndValue.getFirst());
           } else {
-            for (Artifact artifact : actionValue.getAllOutputArtifactData().keySet()) {
-              if (shouldCheckArtifact(knownModifiedOutputFiles, artifact)) {
-                artifactToKeyAndValue.put(artifact, keyAndValue);
+            for (ArtifactFile file : actionValue.getAllFileValues().keySet()) {
+              // File system value checking for non-Artifacts is not yet implemented.
+              if (file instanceof Artifact) {
+                Artifact artifact = (Artifact) file;
+                if (shouldCheckArtifact(knownModifiedOutputFiles, artifact)) {
+                  artifactToKeyAndValue.put(artifact, keyAndValue);
+                }
               }
             }
           }
@@ -231,7 +236,7 @@ public class FilesystemValueChecker {
         List<FileStatusWithDigest> stats;
         try {
           stats = batchStatter.batchStat(/*includeDigest=*/true, /*includeLinks=*/true,
-                                         Artifact.asPathFragments(artifacts));
+              Artifact.asPathFragments(artifacts));
         } catch (IOException e) {
           // Batch stat did not work. Log an exception and fall back on system calls.
           LoggingUtil.logToRemote(Level.WARNING, "Unable to process batch stat", e);
@@ -250,9 +255,10 @@ public class FilesystemValueChecker {
           Pair<SkyKey, ActionExecutionValue> keyAndValue = artifactToKeyAndValue.get(artifact);
           ActionExecutionValue actionValue = keyAndValue.getSecond();
           SkyKey key = keyAndValue.getFirst();
-          FileValue lastKnownData = actionValue.getAllOutputArtifactData().get(artifact);
+          FileValue lastKnownData = actionValue.getAllFileValues().get(artifact);
           try {
-            FileValue newData = ActionMetadataHandler.fileValueFromArtifact(artifact, stat, tsgm);
+            FileValue newData = ActionMetadataHandler.fileValueFromArtifactFile(artifact, stat,
+                tsgm);
             if (!newData.equals(lastKnownData)) {
               updateIntraBuildModifiedCounter(stat != null ? stat.getLastChangeTime() : -1,
                   lastKnownData.isSymlink(), newData.isSymlink());
@@ -310,13 +316,13 @@ public class FilesystemValueChecker {
   private boolean actionValueIsDirtyWithDirectSystemCalls(ActionExecutionValue actionValue,
       ImmutableSet<PathFragment> knownModifiedOutputFiles) {
     boolean isDirty = false;
-    for (Map.Entry<Artifact, FileValue> entry :
-        actionValue.getAllOutputArtifactData().entrySet()) {
-      Artifact artifact = entry.getKey();
+    for (Map.Entry<ArtifactFile, FileValue> entry : actionValue.getAllFileValues().entrySet()) {
+      ArtifactFile file = entry.getKey();
       FileValue lastKnownData = entry.getValue();
-      if (shouldCheckArtifact(knownModifiedOutputFiles, artifact)) {
+      if (shouldCheckArtifact(knownModifiedOutputFiles, file)) {
         try {
-          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifact(artifact, null, tsgm);
+          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifactFile(file, null,
+              tsgm);
           if (!fileValue.equals(lastKnownData)) {
             updateIntraBuildModifiedCounter(fileValue.exists()
                 ? fileValue.realRootedPath().asPath().getLastModifiedTime()
@@ -335,9 +341,9 @@ public class FilesystemValueChecker {
   }
 
   private static boolean shouldCheckArtifact(ImmutableSet<PathFragment> knownModifiedOutputFiles,
-      Artifact artifact) {
+      ArtifactFile file) {
     return knownModifiedOutputFiles == null
-        || knownModifiedOutputFiles.contains(artifact.getExecPath());
+        || knownModifiedOutputFiles.contains(file.getExecPath());
   }
 
   private BatchDirtyResult getDirtyValues(ValueFetcher fetcher,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index 5e2ba5d73b..27310f0a4a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -615,7 +615,9 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
             "%s %s", actionExecutionContext.getMetadataHandler(), metadataHandler);
         prepareScheduleExecuteAndCompleteAction(action, actionExecutionContext, actionStartTime);
         return new ActionExecutionValue(
-            metadataHandler.getOutputData(), metadataHandler.getAdditionalOutputData());
+            metadataHandler.getOutputArtifactFileData(),
+            ImmutableMap.<Artifact, TreeArtifactValue>of(),
+            metadataHandler.getAdditionalOutputData());
       } finally {
         profiler.completeTask(ProfilerTask.ACTION);
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
new file mode 100644
index 0000000000..043edc2c3b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
@@ -0,0 +1,163 @@
+// 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.annotations.VisibleForTesting;
+import com.google.common.base.MoreObjects;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
+import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.ArtifactFile;
+import com.google.devtools.build.lib.actions.cache.Digest;
+import com.google.devtools.build.lib.actions.cache.Metadata;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.Arrays;
+import java.util.Map;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+/**
+ * Value for TreeArtifacts, which contains a digest and the {@link FileArtifactValue}s
+ * of its child {@link ArtifactFile}s.
+ */
+public class TreeArtifactValue extends ArtifactValue {
+  private final byte[] digest;
+  private final Map<PathFragment, FileArtifactValue> childData;
+
+  private TreeArtifactValue(byte[] digest, Map<PathFragment, FileArtifactValue> childData) {
+    this.digest = digest;
+    this.childData = ImmutableMap.copyOf(childData);
+  }
+
+  /**
+   * Returns a TreeArtifactValue out of the given Artifact-relative path fragments
+   * and their corresponding FileArtifactValues.
+   */
+  @VisibleForTesting
+  public static TreeArtifactValue create(Map<PathFragment, FileArtifactValue> childFileValues) {
+    Map<String, Metadata> digestBuilder =
+        Maps.newHashMapWithExpectedSize(childFileValues.size());
+    for (Map.Entry<PathFragment, FileArtifactValue> e : childFileValues.entrySet()) {
+      digestBuilder.put(e.getKey().getPathString(), new Metadata(e.getValue().getDigest()));
+    }
+
+    return new TreeArtifactValue(
+        Digest.fromMetadata(digestBuilder).asMetadata().digest,
+        ImmutableMap.copyOf(childFileValues));
+  }
+
+  public FileArtifactValue getSelfData() {
+    return FileArtifactValue.createProxy(digest);
+  }
+
+  /** Returns the inputs that this artifact expands to, in no particular order. */
+  Iterable<ArtifactFile> getChildren(final Artifact base) {
+    return ActionInputHelper.asArtifactFiles(base, childData.keySet());
+  }
+
+  public Metadata getMetadata() {
+    return new Metadata(digest.clone());
+  }
+
+  public Set<PathFragment> getChildPaths() {
+    return childData.keySet();
+  }
+
+  @Nullable
+  public byte[] getDigest() {
+    return digest.clone();
+  }
+
+  @Override
+  public int hashCode() {
+    return Arrays.hashCode(digest);
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    }
+
+    if (!(other instanceof TreeArtifactValue)) {
+      return false;
+    }
+
+    TreeArtifactValue that = (TreeArtifactValue) other;
+    if (that.digest != digest) {
+      return false;
+    }
+
+    return childData.equals(that.childData);
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(TreeArtifactValue.class)
+        .add("digest", digest)
+        .add("childData", childData)
+        .toString();
+  }
+
+  /**
+   * A TreeArtifactValue that represents a missing TreeArtifact.
+   * This is occasionally useful because Java's concurrent collections disallow null members.
+   */
+  static final TreeArtifactValue MISSING_TREE_ARTIFACT = new TreeArtifactValue(null,
+      ImmutableMap.<PathFragment, FileArtifactValue>of()) {
+    @Override
+    public FileArtifactValue getSelfData() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    Iterable<ArtifactFile> getChildren(Artifact base) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public Metadata getMetadata() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public Set<PathFragment> getChildPaths() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Nullable
+    @Override
+    public byte[] getDigest() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public int hashCode() {
+      return 24; // my favorite number
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      return this == other;
+    }
+
+    @Override
+    public String toString() {
+      return "MISSING_TREE_ARTIFACT";
+    }
+  };
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index 739618a5ea..e5e8e6c322 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -1065,7 +1065,8 @@ public final class ParallelEvaluator implements Evaluator {
       // just order it to be built.
       if (newDirectDeps.isEmpty()) {
         // TODO(bazel-team): This means a bug in the SkyFunction. What to do?
-        Preconditions.checkState(!env.childErrorInfos.isEmpty(), "%s %s", skyKey, state);
+        Preconditions.checkState(!env.childErrorInfos.isEmpty(),
+            "Evaluation of SkyKey failed and no dependencies were requested: %s %s", skyKey, state);
         env.commit(/*enqueueParents=*/keepGoing);
         if (!keepGoing) {
           throw SchedulerException.ofError(state.getErrorInfo(), skyKey);
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 10d05ff96e..2d5a9b3782 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
@@ -33,28 +33,14 @@ import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.MissingInputFileException;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.actions.util.TestAction.DummyAction;
-import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.events.NullEventHandler;
-import com.google.devtools.build.lib.packages.PackageFactory;
-import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
-import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
-import com.google.devtools.build.lib.testutil.TestUtils;
-import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.util.Pair;
-import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.FileStatus;
 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.inmemoryfs.InMemoryFileSystem;
 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;
 
@@ -68,78 +54,27 @@ import java.nio.charset.StandardCharsets;
 import java.security.MessageDigest;
 import java.util.Arrays;
 import java.util.HashMap;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;
-import java.util.Set;
-import java.util.UUID;
-import java.util.concurrent.atomic.AtomicReference;
 
 /**
  * Tests for {@link ArtifactFunction}.
  */
 // Doesn't actually need any particular Skyframe, but is only relevant to Skyframe full mode.
 @RunWith(JUnit4.class)
-public class ArtifactFunctionTest {
-  private static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
-  private static final ActionLookupKey ALL_OWNER = new SingletonActionLookupKey();
+public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
 
   private PathFragment allowedMissingInput = null;
-  private Predicate<PathFragment> allowedMissingInputsPredicate = new Predicate<PathFragment>() {
-    @Override
-    public boolean apply(PathFragment input) {
-      return input.equals(allowedMissingInput);
-    }
-  };
-
-  private Set<Action> actions;
-  private boolean fastDigest = false;
-  private RecordingDifferencer differencer = new RecordingDifferencer();
-  private SequentialBuildDriver driver;
-  private MemoizingEvaluator evaluator;
-  private Path root;
-  private TimestampGranularityMonitor tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
 
   @Before
   public final void setUp() throws Exception  {
-    setupRoot(new CustomInMemoryFs());
-    AtomicReference<PathPackageLocator> pkgLocator = new AtomicReference<>(new PathPackageLocator(
-        root.getFileSystem().getPath("/outputbase"), ImmutableList.of(root)));
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
-    differencer = new RecordingDifferencer();
-    evaluator =
-        new InMemoryMemoizingEvaluator(
-            ImmutableMap.<SkyFunctionName, SkyFunction>builder()
-                .put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper))
-                .put(SkyFunctions.FILE, new FileFunction(pkgLocator))
-                .put(SkyFunctions.ARTIFACT, new ArtifactFunction(allowedMissingInputsPredicate))
-                .put(SkyFunctions.ACTION_EXECUTION, new SimpleActionExecutionFunction())
-                .put(
-                    SkyFunctions.PACKAGE,
-                    new PackageFunction(null, null, null, null, null, null, null))
-                .put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(null))
-                .put(
-                    SkyFunctions.WORKSPACE_AST,
-                    new WorkspaceASTFunction(TestRuleClassProvider.getRuleClassProvider()))
-                .put(
-                    SkyFunctions.WORKSPACE_FILE,
-                    new WorkspaceFileFunction(
-                        TestRuleClassProvider.getRuleClassProvider(),
-                        new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
-                        new BlazeDirectories(root, root, root)))
-                .put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction())
-                .build(),
-            differencer);
-    driver = new SequentialBuildDriver(evaluator);
-    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
-    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
-    actions = new HashSet<>();
-  }
-
-  private void setupRoot(CustomInMemoryFs fs) throws IOException {
-    root = fs.getPath(TestUtils.tmpDir());
-    FileSystemUtils.createDirectoryAndParents(root);
-    FileSystemUtils.createEmptyFile(root.getRelative("WORKSPACE"));
+    delegateActionExecutionFunction = new SimpleActionExecutionFunction();
+    allowedMissingInputsPredicate = new Predicate<PathFragment>() {
+      @Override
+      public boolean apply(PathFragment input) {
+        return input.equals(allowedMissingInput);
+      }
+    };
   }
 
   private void assertFileArtifactValueMatches(boolean expectDigest) throws Throwable {
@@ -452,23 +387,6 @@ public class ArtifactFunctionTest {
         NullEventHandler.INSTANCE);
   }
 
-  private static void writeFile(Path path, String contents) throws IOException {
-    FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
-    FileSystemUtils.writeContentAsLatin1(path, contents);
-  }
-
-  private static class SingletonActionLookupKey extends ActionLookupKey {
-    @Override
-    SkyKey getSkyKey() {
-      return OWNER_KEY;
-    }
-
-    @Override
-    SkyFunctionName getType() {
-      throw new UnsupportedOperationException();
-    }
-  }
-
   /** Value Builder for actions that just stats and stores the output file (which must exist). */
   private class SimpleActionExecutionFunction implements SkyFunction {
     @Override
@@ -479,7 +397,7 @@ public class ArtifactFunctionTest {
       FileArtifactValue value;
       if (action.getActionType() == MiddlemanType.NORMAL) {
         try {
-          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifact(output, null, tsgm);
+          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifactFile(output, null, tsgm);
           artifactData.put(output, fileValue);
           value = FileArtifactValue.create(output, fileValue);
         } catch (IOException e) {
@@ -488,7 +406,10 @@ public class ArtifactFunctionTest {
       } else {
         value = FileArtifactValue.DEFAULT_MIDDLEMAN;
       }
-      return new ActionExecutionValue(artifactData, ImmutableMap.of(output, value));
+      return new ActionExecutionValue(
+          artifactData,
+          ImmutableMap.<Artifact, TreeArtifactValue>of(),
+          ImmutableMap.of(output, value));
     }
 
     @Override
@@ -496,17 +417,4 @@ public class ArtifactFunctionTest {
       return null;
     }
   }
-
-  /** InMemoryFileSystem that can pretend to do a fast digest. */
-  private class CustomInMemoryFs extends InMemoryFileSystem {
-    @Override
-    protected String getFastDigestFunctionType(Path path) {
-      return fastDigest ? "MD5" : null;
-    }
-
-    @Override
-    protected byte[] getFastDigest(Path path) throws IOException {
-      return fastDigest ? getMD5Digest(path) : null;
-    }
-  }
 }
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
new file mode 100644
index 0000000000..2f75f40fdf
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
@@ -0,0 +1,158 @@
+// Copyright 2015 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.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.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.packages.PackageFactory;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
+import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
+import com.google.devtools.build.lib.testutil.TestUtils;
+import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+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.inmemoryfs.InMemoryFileSystem;
+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.SkyFunctionException;
+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 java.io.IOException;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+
+abstract class ArtifactFunctionTestCase {
+  protected static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
+  protected static final ActionLookupKey ALL_OWNER = new SingletonActionLookupKey();
+
+  protected Predicate<PathFragment> allowedMissingInputsPredicate = Predicates.alwaysFalse();
+
+  protected Set<Action> actions;
+  protected boolean fastDigest = false;
+  protected RecordingDifferencer differencer = new RecordingDifferencer();
+  protected SequentialBuildDriver driver;
+  protected MemoizingEvaluator evaluator;
+  protected Path root;
+  protected TimestampGranularityMonitor tsgm =
+      new TimestampGranularityMonitor(BlazeClock.instance());
+
+  /**
+   * The test action execution function. The Skyframe evaluator's action execution function
+   * delegates to this one.
+   */
+  protected SkyFunction delegateActionExecutionFunction;
+
+  @Before
+  public void baseSetUp() throws Exception  {
+    setupRoot(new CustomInMemoryFs());
+    AtomicReference<PathPackageLocator> pkgLocator = new AtomicReference<>(new PathPackageLocator(
+        root.getFileSystem().getPath("/outputbase"), ImmutableList.of(root)));
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
+    differencer = new RecordingDifferencer();
+    evaluator =
+        new InMemoryMemoizingEvaluator(
+            ImmutableMap.<SkyFunctionName, SkyFunction>builder()
+                .put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper))
+                .put(SkyFunctions.FILE, new FileFunction(pkgLocator))
+                .put(SkyFunctions.ARTIFACT,
+                    new ArtifactFunction(allowedMissingInputsPredicate))
+                .put(SkyFunctions.ACTION_EXECUTION, new SimpleActionExecutionFunction())
+                .put(
+                    SkyFunctions.PACKAGE,
+                    new PackageFunction(null, null, null, null, null, null, null))
+                .put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(null))
+                .put(
+                    SkyFunctions.WORKSPACE_AST,
+                    new WorkspaceASTFunction(TestRuleClassProvider.getRuleClassProvider()))
+                .put(
+                    SkyFunctions.WORKSPACE_FILE,
+                    new WorkspaceFileFunction(
+                        TestRuleClassProvider.getRuleClassProvider(),
+                        new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
+                        new BlazeDirectories(root, root, root)))
+                .put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction())
+                .build(),
+            differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+    actions = new HashSet<>();
+  }
+
+  protected void setupRoot(CustomInMemoryFs fs) throws IOException {
+    root = fs.getPath(TestUtils.tmpDir());
+    FileSystemUtils.createDirectoryAndParents(root);
+    FileSystemUtils.createEmptyFile(root.getRelative("WORKSPACE"));
+  }
+
+  protected static void writeFile(Path path, String contents) throws IOException {
+    FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(path, contents);
+  }
+
+  /** ActionExecutionFunction that delegates to our delegate. */
+  private class SimpleActionExecutionFunction implements SkyFunction {
+    @Override
+    public SkyValue compute(SkyKey skyKey, Environment env)
+        throws SkyFunctionException, InterruptedException {
+      return delegateActionExecutionFunction.compute(skyKey, env);
+    }
+
+    @Override
+    public String extractTag(SkyKey skyKey) {
+      return delegateActionExecutionFunction.extractTag(skyKey);
+    }
+  }
+
+  private static class SingletonActionLookupKey extends ActionLookupKey {
+    @Override
+    SkyKey getSkyKey() {
+      return OWNER_KEY;
+    }
+
+    @Override
+    SkyFunctionName getType() {
+      throw new UnsupportedOperationException();
+    }
+  }
+
+  /** InMemoryFileSystem that can pretend to do a fast digest. */
+  protected class CustomInMemoryFs extends InMemoryFileSystem {
+    @Override
+    protected String getFastDigestFunctionType(Path path) {
+      return fastDigest ? "MD5" : null;
+    }
+
+    @Override
+    protected byte[] getFastDigest(Path path) throws IOException {
+      return fastDigest ? getMD5Digest(path) : null;
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
index 95cb020ab6..d695780c00 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -453,12 +453,16 @@ public class FilesystemValueCheckerTest {
         Path path = output.getPath();
         FileStatusWithDigest stat =
             forceDigest ? statWithDigest(path, path.statIfFound(Symlinks.NOFOLLOW)) : null;
-        artifactData.put(output, ActionMetadataHandler.fileValueFromArtifact(output, stat, tsgm));
+        artifactData.put(output,
+            ActionMetadataHandler.fileValueFromArtifactFile(output, stat, tsgm));
       } catch (IOException e) {
         throw new IllegalStateException(e);
       }
     }
-    return new ActionExecutionValue(artifactData, ImmutableMap.<Artifact, FileArtifactValue>of());
+    return new ActionExecutionValue(
+        artifactData,
+        ImmutableMap.<Artifact, TreeArtifactValue>of(),
+        ImmutableMap.<Artifact, FileArtifactValue>of());
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
new file mode 100644
index 0000000000..a57576cc5d
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -0,0 +1,254 @@
+// 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 com.google.devtools.build.lib.actions.ActionInputHelper.asArtifactFiles;
+import static org.junit.Assert.fail;
+
+import com.google.common.base.Throwables;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+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.ArtifactFile;
+import com.google.devtools.build.lib.actions.MissingInputFileException;
+import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.actions.cache.Digest;
+import com.google.devtools.build.lib.actions.cache.DigestUtils;
+import com.google.devtools.build.lib.actions.cache.Metadata;
+import com.google.devtools.build.lib.actions.util.TestAction.DummyAction;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.vfs.FileStatus;
+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.skyframe.EvaluationResult;
+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 org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Test the behavior of ActionMetadataHandler and ArtifactFunction
+ * with respect to TreeArtifacts.
+ */
+@RunWith(JUnit4.class)
+public class TreeArtifactMetadataTest extends ArtifactFunctionTestCase {
+
+  // A list of subpaths for the SetArtifact created by our custom ActionExecutionFunction.
+  private List<PathFragment> testTreeArtifactContents;
+
+  @Before
+  public final void setUp() throws Exception  {
+    delegateActionExecutionFunction = new TreeArtifactExecutionFunction();
+  }
+
+  private TreeArtifactValue evaluateTreeArtifact(Artifact treeArtifact,
+      Iterable<PathFragment> children)
+    throws Exception {
+    testTreeArtifactContents = ImmutableList.copyOf(children);
+    for (PathFragment child : children) {
+      file(treeArtifact.getPath().getRelative(child), child.toString());
+    }
+    return (TreeArtifactValue) evaluateArtifactValue(treeArtifact, /*mandatory=*/ true);
+  }
+
+  private TreeArtifactValue doTestTreeArtifacts(Iterable<PathFragment> children) throws Exception {
+    Artifact output = createTreeArtifact("output");
+    return doTestTreeArtifacts(output, children);
+  }
+
+  private TreeArtifactValue doTestTreeArtifacts(Artifact tree,
+      Iterable<PathFragment> children)
+      throws Exception {
+    TreeArtifactValue value = evaluateTreeArtifact(tree, children);
+    assertThat(value.getChildPaths()).containsExactlyElementsIn(ImmutableSet.copyOf(children));
+    assertThat(value.getChildren(tree)).containsExactlyElementsIn(
+        asArtifactFiles(tree, children));
+
+    // Assertions about digest. As of this writing this logic is essentially the same
+    // as that in TreeArtifact, but it's good practice to unit test anyway to guard against
+    // breaking changes.
+    Map<String, Metadata> digestBuilder = new HashMap<>();
+    for (PathFragment child : children) {
+      Metadata subdigest = new Metadata(tree.getPath().getRelative(child).getMD5Digest());
+      digestBuilder.put(child.getPathString(), subdigest);
+    }
+    assertThat(Digest.fromMetadata(digestBuilder).asMetadata().digest).isEqualTo(value.getDigest());
+    return value;
+  }
+
+  @Test
+  public void testEmptyTreeArtifacts() throws Exception {
+    TreeArtifactValue value = doTestTreeArtifacts(ImmutableList.<PathFragment>of());
+    // Additional test, only for this test method: we expect the Metadata is equal to
+    // the digest [0, 0, ...]
+    assertThat(value.getMetadata().digest).isEqualTo(value.getDigest());
+    // Java zero-fills arrays.
+    assertThat(value.getDigest()).isEqualTo(new byte[16]);
+  }
+
+  @Test
+  public void testTreeArtifactsWithDigests() throws Exception {
+    fastDigest = true;
+    doTestTreeArtifacts(ImmutableList.of(new PathFragment("one")));
+  }
+
+  @Test
+  public void testTreeArtifactsWithoutDigests() throws Exception {
+    fastDigest = false;
+    doTestTreeArtifacts(ImmutableList.of(new PathFragment("one")));
+  }
+
+  @Test
+  public void testTreeArtifactMultipleDigests() throws Exception {
+    doTestTreeArtifacts(ImmutableList.of(new PathFragment("one"), new PathFragment("two")));
+  }
+
+  @Test
+  public void testIdenticalTreeArtifactsProduceTheSameDigests() throws Exception {
+    // Make sure different root dirs for set artifacts don't produce different digests.
+    Artifact one = createTreeArtifact("outOne");
+    Artifact two = createTreeArtifact("outTwo");
+    ImmutableList<PathFragment> children =
+        ImmutableList.of(new PathFragment("one"), new PathFragment("two"));
+    TreeArtifactValue valueOne = evaluateTreeArtifact(one, children);
+    TreeArtifactValue valueTwo = evaluateTreeArtifact(two, children);
+    assertThat(valueOne.getDigest()).isEqualTo(valueTwo.getDigest());
+  }
+
+  /**
+   * Tests that ArtifactFunction rethrows transitive {@link IOException}s as
+   * {@link MissingInputFileException}s.
+   */
+  @Test
+  public void testIOExceptionEndToEnd() throws Throwable {
+    final IOException exception = new IOException("boop");
+    setupRoot(
+        new CustomInMemoryFs() {
+          @Override
+          public FileStatus stat(Path path, boolean followSymlinks) throws IOException {
+            if (path.getBaseName().equals("one")) {
+              throw exception;
+            }
+            return super.stat(path, followSymlinks);
+          }
+        });
+    try {
+      Artifact artifact = createTreeArtifact("outOne");
+      TreeArtifactValue value = evaluateTreeArtifact(artifact,
+          ImmutableList.of(new PathFragment("one")));
+      fail("MissingInputFileException expected, got " + value);
+    } catch (Exception e) {
+      assertThat(Throwables.getRootCause(e).getMessage()).contains(exception.getMessage());
+    }
+  }
+
+  private void file(Path path, String contents) throws Exception {
+    FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
+    writeFile(path, contents);
+  }
+
+  private Artifact createTreeArtifact(String path) throws IOException {
+    PathFragment execPath = new PathFragment("out").getRelative(path);
+    Path fullPath = root.getRelative(execPath);
+    Artifact output =
+        new SpecialArtifact(
+            fullPath, Root.asDerivedRoot(root, root.getRelative("out")), execPath, ALL_OWNER,
+            SpecialArtifactType.TREE);
+    actions.add(new DummyAction(ImmutableList.<Artifact>of(), output));
+    FileSystemUtils.createDirectoryAndParents(fullPath);
+    return output;
+  }
+
+  private ArtifactValue evaluateArtifactValue(Artifact artifact, boolean mandatory)
+      throws Exception {
+    SkyKey key = ArtifactValue.key(artifact, mandatory);
+    EvaluationResult<ArtifactValue> result = evaluate(key);
+    if (result.hasError()) {
+      throw result.getError().getException();
+    }
+    return result.get(key);
+  }
+
+  private void setGeneratingActions() {
+    if (evaluator.getExistingValueForTesting(OWNER_KEY) == null) {
+      differencer.inject(ImmutableMap.of(OWNER_KEY, new ActionLookupValue(actions)));
+    }
+  }
+
+  private <E extends SkyValue> EvaluationResult<E> evaluate(SkyKey... keys)
+      throws InterruptedException {
+    setGeneratingActions();
+    return driver.evaluate(
+        Arrays.asList(keys), /*keepGoing=*/
+        false,
+        SkyframeExecutor.DEFAULT_THREAD_COUNT,
+        NullEventHandler.INSTANCE);
+  }
+
+  private class TreeArtifactExecutionFunction implements SkyFunction {
+    @Override
+    public SkyValue compute(SkyKey skyKey, Environment env) throws SkyFunctionException {
+      Map<ArtifactFile, FileValue> fileData = new HashMap<>();
+      Map<PathFragment, FileArtifactValue> treeArtifactData = new HashMap<>();
+      Action action = (Action) skyKey.argument();
+      Artifact output = Iterables.getOnlyElement(action.getOutputs());
+      for (PathFragment subpath : testTreeArtifactContents) {
+        try {
+          ArtifactFile suboutput = ActionInputHelper.artifactFile(output, subpath);
+          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifactFile(
+              suboutput, null, tsgm);
+          fileData.put(suboutput, fileValue);
+          // Ignore FileValue digests--correctness of these digests is not part of this tests.
+          byte[] digest = DigestUtils.getDigestOrFail(suboutput.getPath(), 1);
+          treeArtifactData.put(suboutput.getParentRelativePath(),
+              FileArtifactValue.createWithDigest(suboutput.getPath(), digest, fileValue.getSize()));
+        } catch (IOException e) {
+          throw new SkyFunctionException(e, Transience.TRANSIENT) {};
+        }
+      }
+
+      TreeArtifactValue treeArtifactValue = TreeArtifactValue.create(treeArtifactData);
+
+      return new ActionExecutionValue(
+          fileData,
+          ImmutableMap.of(output, treeArtifactValue),
+          ImmutableMap.<Artifact, FileArtifactValue>of());
+    }
+
+    @Override
+    public String extractTag(SkyKey skyKey) {
+      return null;
+    }
+  }
+}