Update FileSystemValueChecker to handle TreeArtifact values.

--
MOS_MIGRATED_REVID=114202845

3 files changed, 365 insertions, 22 deletions

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 6b4bc3c0e9..833306dd70 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
@@ -28,6 +28,7 @@ import com.google.devtools.build.lib.concurrent.ThrowableRecordingRunnableWrappe
 import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.profiler.AutoProfiler.ElapsedTimeReceiver;
 import com.google.devtools.build.lib.skyframe.SkyValueDirtinessChecker.DirtyResult;
+import com.google.devtools.build.lib.skyframe.TreeArtifactValue.TreeArtifactException;
 import com.google.devtools.build.lib.util.LoggingUtil;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -35,6 +36,7 @@ import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.BatchStat;
 import com.google.devtools.build.lib.vfs.FileStatusWithDigest;
 import com.google.devtools.build.lib.vfs.ModifiedFileSet;
+import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.Differencer;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -214,29 +216,37 @@ public class FilesystemValueChecker {
     return new Runnable() {
       @Override
       public void run() {
-        Map<Artifact, Pair<SkyKey, ActionExecutionValue>> artifactToKeyAndValue = new HashMap<>();
+        Map<ArtifactFile, Pair<SkyKey, ActionExecutionValue>> fileToKeyAndValue = new HashMap<>();
+        Map<Artifact, Pair<SkyKey, ActionExecutionValue>> treeArtifactsToKeyAndValue =
+            new HashMap<>();
         for (Pair<SkyKey, ActionExecutionValue> keyAndValue : shard) {
           ActionExecutionValue actionValue = keyAndValue.getSecond();
           if (actionValue == null) {
             dirtyKeys.add(keyAndValue.getFirst());
           } else {
             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);
-                }
+              if (shouldCheckFile(knownModifiedOutputFiles, file)) {
+                fileToKeyAndValue.put(file, keyAndValue);
               }
             }
+
+            // TreeArtifacts are always checked because we can't match modified files to modified
+            // TreeArtifacts. We could construct a sorted map to do this, but it's unclear
+            // whether this is a performance savings, since we expect the ratio of ordinary
+            // files to TreeArtifacts directories and subdirectories to be rather high.
+            // TODO(bazel-team): Investigate whether we can use modified output file awareness
+            // to speed this up.
+            for (Artifact artifact : actionValue.getAllTreeArtifactValues().keySet()) {
+              treeArtifactsToKeyAndValue.put(artifact, keyAndValue);
+            }
           }
         }
 
-        List<Artifact> artifacts = ImmutableList.copyOf(artifactToKeyAndValue.keySet());
+        List<ArtifactFile> files = ImmutableList.copyOf(fileToKeyAndValue.keySet());
         List<FileStatusWithDigest> stats;
         try {
           stats = batchStatter.batchStat(/*includeDigest=*/true, /*includeLinks=*/true,
-              Artifact.asPathFragments(artifacts));
+              Artifact.asPathFragments(files));
         } 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);
@@ -247,17 +257,17 @@ public class FilesystemValueChecker {
           return;
         }
 
-        Preconditions.checkState(artifacts.size() == stats.size(),
-            "artifacts.size() == %s stats.size() == %s", artifacts.size(), stats.size());
-        for (int i = 0; i < artifacts.size(); i++) {
-          Artifact artifact = artifacts.get(i);
+        Preconditions.checkState(files.size() == stats.size(),
+            "artifacts.size() == %s stats.size() == %s", files.size(), stats.size());
+        for (int i = 0; i < files.size(); i++) {
+          ArtifactFile file = files.get(i);
           FileStatusWithDigest stat = stats.get(i);
-          Pair<SkyKey, ActionExecutionValue> keyAndValue = artifactToKeyAndValue.get(artifact);
+          Pair<SkyKey, ActionExecutionValue> keyAndValue = fileToKeyAndValue.get(file);
           ActionExecutionValue actionValue = keyAndValue.getSecond();
           SkyKey key = keyAndValue.getFirst();
-          FileValue lastKnownData = actionValue.getAllFileValues().get(artifact);
+          FileValue lastKnownData = actionValue.getAllFileValues().get(file);
           try {
-            FileValue newData = ActionMetadataHandler.fileValueFromArtifactFile(artifact, stat,
+            FileValue newData = ActionMetadataHandler.fileValueFromArtifactFile(file, stat,
                 tsgm);
             if (!newData.equals(lastKnownData)) {
               updateIntraBuildModifiedCounter(stat != null ? stat.getLastChangeTime() : -1,
@@ -271,6 +281,29 @@ public class FilesystemValueChecker {
             dirtyKeys.add(key);
           }
         }
+
+        // Unfortunately, there exists no facility to batch list directories.
+        // We must use direct filesystem calls.
+        for (Map.Entry<Artifact, Pair<SkyKey, ActionExecutionValue>> entry :
+            treeArtifactsToKeyAndValue.entrySet()) {
+          Artifact artifact = entry.getKey();
+          if (treeArtifactIsDirty(
+              entry.getKey(), entry.getValue().getSecond().getTreeArtifactValue(artifact))) {
+            Path path = artifact.getPath();
+            // Count the changed directory as one "file".
+            // TODO(bazel-team): There are no tests for this codepath.
+            try {
+              updateIntraBuildModifiedCounter(path.exists()
+                  ? path.getLastModifiedTime()
+                  : -1, false, path.isSymbolicLink());
+            } catch (IOException e) {
+              // Do nothing here.
+            }
+
+            modifiedOutputFilesCounter.getAndIncrement();
+            dirtyKeys.add(entry.getValue().getFirst());
+          }
+        }
       }
     };
   }
@@ -285,8 +318,8 @@ public class FilesystemValueChecker {
   }
 
   private Runnable outputStatJob(final Collection<SkyKey> dirtyKeys,
-          final List<Pair<SkyKey, ActionExecutionValue>> shard,
-          final ImmutableSet<PathFragment> knownModifiedOutputFiles) {
+      final List<Pair<SkyKey, ActionExecutionValue>> shard,
+      final ImmutableSet<PathFragment> knownModifiedOutputFiles) {
     return new Runnable() {
       @Override
       public void run() {
@@ -313,13 +346,30 @@ public class FilesystemValueChecker {
     return modifiedOutputFilesIntraBuildCounter.get();
   }
 
+  private boolean treeArtifactIsDirty(Artifact artifact, TreeArtifactValue value) {
+    if (artifact.getPath().isSymbolicLink()) {
+      // TreeArtifacts may not be symbolic links.
+      return true;
+    }
+
+    // There doesn't appear to be any facility to batch list directories... we must
+    // do things the 'slow' way.
+    try {
+      Set<PathFragment> currentDirectoryValue = TreeArtifactValue.explodeDirectory(artifact);
+      Set<PathFragment> valuePaths = value.getChildPaths();
+      return !currentDirectoryValue.equals(valuePaths);
+    } catch (IOException | TreeArtifactException e) {
+      return true;
+    }
+  }
+
   private boolean actionValueIsDirtyWithDirectSystemCalls(ActionExecutionValue actionValue,
       ImmutableSet<PathFragment> knownModifiedOutputFiles) {
     boolean isDirty = false;
     for (Map.Entry<ArtifactFile, FileValue> entry : actionValue.getAllFileValues().entrySet()) {
       ArtifactFile file = entry.getKey();
       FileValue lastKnownData = entry.getValue();
-      if (shouldCheckArtifact(knownModifiedOutputFiles, file)) {
+      if (shouldCheckFile(knownModifiedOutputFiles, file)) {
         try {
           FileValue fileValue = ActionMetadataHandler.fileValueFromArtifactFile(file, null,
               tsgm);
@@ -337,10 +387,30 @@ public class FilesystemValueChecker {
         }
       }
     }
+
+    for (Map.Entry<Artifact, TreeArtifactValue> entry :
+        actionValue.getAllTreeArtifactValues().entrySet()) {
+      Artifact artifact = entry.getKey();
+      if (treeArtifactIsDirty(artifact, entry.getValue())) {
+        Path path = artifact.getPath();
+        // Count the changed directory as one "file".
+        try {
+          updateIntraBuildModifiedCounter(path.exists()
+              ? path.getLastModifiedTime()
+              : -1, false, path.isSymbolicLink());
+        } catch (IOException e) {
+          // Do nothing here.
+        }
+
+        modifiedOutputFilesCounter.getAndIncrement();
+        isDirty = true;
+      }
+    }
+
     return isDirty;
   }
 
-  private static boolean shouldCheckArtifact(ImmutableSet<PathFragment> knownModifiedOutputFiles,
+  private static boolean shouldCheckFile(ImmutableSet<PathFragment> knownModifiedOutputFiles,
       ArtifactFile file) {
     return knownModifiedOutputFiles == null
         || knownModifiedOutputFiles.contains(file.getExecPath());
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
index 043edc2c3b..a60ad09733 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
@@ -16,14 +16,18 @@ 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.ImmutableSet;
 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.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
+import java.io.IOException;
+
 import java.util.Arrays;
 import java.util.Map;
 import java.util.Set;
@@ -160,4 +164,49 @@ public class TreeArtifactValue extends ArtifactValue {
       return "MISSING_TREE_ARTIFACT";
     }
   };
+
+  /**
+   * Exception used when the contents of a directory do not form a valid SetArtifact.
+   * (We cannot use IOException because ActionMetadataHandler, in some code paths,
+   * interprets IOExceptions as missing files.)
+   */
+  static class TreeArtifactException extends Exception {
+    TreeArtifactException(String message) {
+      super(message);
+    }
+  }
+
+  private static void explodeDirectory(Artifact rootArtifact,
+      PathFragment pathToExplode, ImmutableSet.Builder<PathFragment> valuesBuilder)
+      throws IOException, TreeArtifactException {
+    for (Path subpath : rootArtifact.getPath().getRelative(pathToExplode).getDirectoryEntries()) {
+      PathFragment canonicalSubpathFragment =
+          pathToExplode.getChild(subpath.getBaseName()).normalize();
+      if (subpath.isDirectory()) {
+        explodeDirectory(rootArtifact,
+            pathToExplode.getChild(subpath.getBaseName()), valuesBuilder);
+      } else if (subpath.isSymbolicLink()) {
+        throw new TreeArtifactException(
+            "A SetArtifact may not contain a symlink, found " + subpath);
+      } else if (subpath.isFile()) {
+        valuesBuilder.add(canonicalSubpathFragment);
+      } else {
+        // We shouldn't ever reach here.
+        throw new IllegalStateException("Could not determine type of file " + subpath);
+      }
+    }
+  }
+
+  /**
+   * Recursively get all child files in a directory
+   * (excluding child directories themselves, but including all files in them).
+   * @throws IOException if one was thrown reading directory contents from disk.
+   * @throws TreeArtifactException if the on-disk directory is not a valid TreeArtifact.
+   */
+  static Set<PathFragment> explodeDirectory(Artifact rootArtifact)
+      throws IOException, TreeArtifactException {
+    ImmutableSet.Builder<PathFragment> explodedDirectory = ImmutableSet.builder();
+    explodeDirectory(rootArtifact, PathFragment.EMPTY_FRAGMENT, explodedDirectory);
+    return explodedDirectory.build();
+  }
 }
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 d695780c00..5f46eedd6e 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
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.actions.ActionInputHelper.artifactFile;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
@@ -26,7 +27,12 @@ import com.google.common.collect.Iterables;
 import com.google.common.util.concurrent.Runnables;
 import com.google.devtools.build.lib.actions.Action;
 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.ArtifactOwner;
 import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.actions.util.TestAction;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
@@ -36,6 +42,7 @@ import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.skyframe.DirtinessCheckerUtils.BasicFilesystemDirtinessChecker;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.BatchStat;
 import com.google.devtools.build.lib.vfs.FileStatus;
@@ -344,10 +351,10 @@ public class FilesystemValueCheckerTest {
 
     Action action1 =
         new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.<Artifact>of(out1));
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out1));
     Action action2 =
         new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.<Artifact>of(out2));
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out2));
     differencer.inject(
         ImmutableMap.<SkyKey, SkyValue>of(
             ActionExecutionValue.key(action1), actionValue(action1, forceDigests),
@@ -381,6 +388,136 @@ public class FilesystemValueCheckerTest {
             batchStatter, ModifiedFileSet.NOTHING_MODIFIED)).isEmpty();
   }
 
+  public void checkDirtyTreeArtifactActions(BatchStat batchStatter)
+      throws Exception {
+    // Normally, an Action specifies the contents of a TreeArtifact when it executes.
+    // To decouple FileSystemValueTester checking from Action execution, we inject TreeArtifact
+    // contents into ActionExecutionValues.
+
+    Artifact out1 = createTreeArtifact("one");
+    ArtifactFile file11 = artifactFile(out1, "fizz");
+    FileSystemUtils.createDirectoryAndParents(out1.getPath());
+    FileSystemUtils.writeContentAsLatin1(file11.getPath(), "buzz");
+
+    Artifact out2 = createTreeArtifact("two");
+    FileSystemUtils.createDirectoryAndParents(out2.getPath().getChild("subdir"));
+    ArtifactFile file21 = artifactFile(out2, "moony");
+    ArtifactFile file22 = artifactFile(out2, "subdir/wormtail");
+    FileSystemUtils.writeContentAsLatin1(file21.getPath(), "padfoot");
+    FileSystemUtils.writeContentAsLatin1(file22.getPath(), "prongs");
+
+    Artifact outEmpty = createTreeArtifact("empty");
+    FileSystemUtils.createDirectoryAndParents(outEmpty.getPath());
+
+    Artifact outUnchanging = createTreeArtifact("untouched");
+    FileSystemUtils.createDirectoryAndParents(outUnchanging.getPath());
+
+    Action action1 =
+        new TestAction(
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out1));
+    Action action2 =
+        new TestAction(
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out2));
+    Action actionEmpty =
+        new TestAction(
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(outEmpty));
+    Action actionUnchanging =
+        new TestAction(
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(outUnchanging));
+    differencer.inject(
+        ImmutableMap.<SkyKey, SkyValue>of(
+            ActionExecutionValue.key(action1),
+            actionValueWithTreeArtifacts(ImmutableList.of(file11)),
+            ActionExecutionValue.key(action2),
+            actionValueWithTreeArtifacts(ImmutableList.of(file21, file22)),
+            ActionExecutionValue.key(actionEmpty),
+            actionValueWithEmptyDirectory(outEmpty),
+            ActionExecutionValue.key(actionUnchanging),
+            actionValueWithEmptyDirectory(outUnchanging)));
+
+    assertFalse(
+        driver
+            .evaluate(ImmutableList.<SkyKey>of(), false, 1, NullEventHandler.INSTANCE)
+            .hasError());
+    assertThat(new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+        batchStatter, ModifiedFileSet.EVERYTHING_MODIFIED)).isEmpty();
+
+    // Touching the TreeArtifact directory should have no effect
+    FileSystemUtils.touchFile(out1.getPath());
+    assertThat(
+        new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+            batchStatter, ModifiedFileSet.EVERYTHING_MODIFIED)).isEmpty();
+    // Neither should touching a subdirectory.
+    FileSystemUtils.touchFile(out2.getPath().getChild("subdir"));
+    assertThat(
+        new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+            batchStatter, ModifiedFileSet.EVERYTHING_MODIFIED)).isEmpty();
+
+    /* **** Tests for directories **** */
+
+    // Removing a directory (even if empty) should have an effect
+    outEmpty.getPath().delete();
+    assertThat(new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+        batchStatter,
+        new ModifiedFileSet.Builder().modify(outEmpty.getExecPath()).build()))
+        .containsExactly(ActionExecutionValue.key(actionEmpty));
+    // Symbolic links should count as dirty
+    Path dummyEmptyDir = fs.getPath("/bin").getRelative("symlink");
+    FileSystemUtils.createDirectoryAndParents(dummyEmptyDir);
+    FileSystemUtils.ensureSymbolicLink(outEmpty.getPath(), dummyEmptyDir);
+    assertThat(new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+        batchStatter,
+        new ModifiedFileSet.Builder().modify(outEmpty.getExecPath()).build()))
+        .containsExactly(ActionExecutionValue.key(actionEmpty));
+
+    // We're done fiddling with this... restore the original state
+    outEmpty.getPath().delete();
+    FileSystemUtils.deleteTree(dummyEmptyDir);
+    FileSystemUtils.createDirectoryAndParents(outEmpty.getPath());
+
+    /* **** Tests for files and directory contents ****/
+
+    // Test that file contents matter. This is covered by existing tests already,
+    // so it's just a sanity check.
+    FileSystemUtils.writeContentAsLatin1(file11.getPath(), "goodbye");
+    assertEquals(
+        ActionExecutionValue.key(action1),
+        Iterables.getOnlyElement(
+            new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+                batchStatter,
+                new ModifiedFileSet.Builder().modify(file11.getExecPath()).build())));
+
+    // Test that directory contents (and nested contents) matter
+    ArtifactFile out1new = artifactFile(out1, "julius/caesar");
+    FileSystemUtils.createDirectoryAndParents(out1.getPath().getChild("julius"));
+    FileSystemUtils.writeContentAsLatin1(out1new.getPath(), "octavian");
+    // even for empty directories
+    ArtifactFile outEmptyNew = artifactFile(outEmpty, "marcus");
+    FileSystemUtils.writeContentAsLatin1(outEmptyNew.getPath(), "aurelius");
+    // so does removing
+    file21.getPath().delete();
+    // now, let's test our changes are actually visible
+    assertThat(new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+            batchStatter, ModifiedFileSet.EVERYTHING_MODIFIED))
+        .containsExactly(ActionExecutionValue.key(action1), ActionExecutionValue.key(action2),
+            ActionExecutionValue.key(actionEmpty));
+    assertThat(
+        new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+            batchStatter,
+            new ModifiedFileSet.Builder()
+                .modify(file21.getExecPath())
+                .modify(out1new.getExecPath())
+                .modify(outEmptyNew.getExecPath())
+                .build()))
+        .containsExactly(ActionExecutionValue.key(action1), ActionExecutionValue.key(action2),
+            ActionExecutionValue.key(actionEmpty));
+    // We add a test for NOTHING_MODIFIED, because FileSystemValueChecker doesn't
+    // pay attention to file sets for TreeArtifact directory listings.
+    assertThat(
+        new FilesystemValueChecker(tsgm, null).getDirtyActionValues(evaluator.getValues(),
+            batchStatter, ModifiedFileSet.NOTHING_MODIFIED)).isEmpty();
+  }
+
   private Artifact createDerivedArtifact(String relPath) throws IOException {
     Path outputPath = fs.getPath("/bin");
     outputPath.createDirectory();
@@ -388,6 +525,16 @@ public class FilesystemValueCheckerTest {
         outputPath.getRelative(relPath), Root.asDerivedRoot(fs.getPath("/"), outputPath));
   }
 
+  private Artifact createTreeArtifact(String relPath) throws IOException {
+    Path outputDir = fs.getPath("/bin");
+    Path outputPath = outputDir.getRelative(relPath);
+    outputDir.createDirectory();
+    Root derivedRoot = Root.asDerivedRoot(fs.getPath("/"), outputDir);
+    return new SpecialArtifact(outputPath, derivedRoot,
+        derivedRoot.getExecPath().getRelative(outputPath.relativeTo(derivedRoot.getPath())),
+        ArtifactOwner.NULL_OWNER, SpecialArtifactType.TREE);
+  }
+
   @Test
   public void testDirtyActions() throws Exception {
     checkDirtyActions(null, false);
@@ -446,6 +593,33 @@ public class FilesystemValueCheckerTest {
         false);
   }
 
+  @Test
+  public void testDirtyTreeArtifactActions() throws Exception {
+    checkDirtyTreeArtifactActions(null);
+  }
+
+  @Test
+  public void testDirtyTreeArtifactActionsBatchStat() throws Exception {
+    checkDirtyTreeArtifactActions(
+        new BatchStat() {
+          @Override
+          public List<FileStatusWithDigest> batchStat(
+              boolean useDigest, boolean includeLinks, Iterable<PathFragment> paths)
+              throws IOException {
+            List<FileStatusWithDigest> stats = new ArrayList<>();
+            for (PathFragment pathFrag : paths) {
+              stats.add(
+                  FileStatusWithDigestAdapter.adapt(
+                      fs.getRootDirectory().getRelative(pathFrag).statIfFound(Symlinks.NOFOLLOW)));
+            }
+            return stats;
+          }
+        });
+  }
+
+  // TODO(bazel-team): Add some tests for FileSystemValueChecker#changedKeys*() methods.
+  // Presently these appear to be untested.
+
   private ActionExecutionValue actionValue(Action action, boolean forceDigest) {
     Map<Artifact, FileValue> artifactData = new HashMap<>();
     for (Artifact output : action.getOutputs()) {
@@ -465,6 +639,56 @@ public class FilesystemValueCheckerTest {
         ImmutableMap.<Artifact, FileArtifactValue>of());
   }
 
+  private ActionExecutionValue actionValueWithEmptyDirectory(Artifact emptyDir) {
+    TreeArtifactValue emptyValue = TreeArtifactValue.create
+        (ImmutableMap.<PathFragment, FileArtifactValue>of());
+
+    return new ActionExecutionValue(
+        ImmutableMap.<ArtifactFile, FileValue>of(),
+        ImmutableMap.of(emptyDir, emptyValue),
+        ImmutableMap.<Artifact, FileArtifactValue>of());
+  }
+
+  private ActionExecutionValue actionValueWithTreeArtifacts(List<ArtifactFile> contents) {
+    Map<ArtifactFile, FileValue> fileData = new HashMap<>();
+    Map<Artifact, Map<ArtifactFile, FileArtifactValue>> directoryData = new HashMap<>();
+
+    for (ArtifactFile output : contents) {
+      Preconditions.checkState(!(output instanceof Artifact));
+      try {
+        Map<ArtifactFile, FileArtifactValue> dirDatum =
+            directoryData.get(output.getParent());
+        if (dirDatum == null) {
+          dirDatum = new HashMap<>();
+          directoryData.put(output.getParent(), dirDatum);
+        }
+        FileValue fileValue = ActionMetadataHandler.fileValueFromArtifactFile(output, null, tsgm);
+        // Always test with digests. TreeArtifact checking behavior doesn't depend on the
+        // presence/absence of digests. FileValue checking w/o digests is already tested.
+        byte[] digest = DigestUtils.getDigestOrFail(output.getPath(), 1);
+        dirDatum.put(output, FileArtifactValue.createWithDigest(
+            output.getPath(), digest, fileValue.getSize()));
+        fileData.put(output, fileValue);
+      } catch (IOException e) {
+        throw new IllegalStateException(e);
+      }
+    }
+
+    Map<Artifact, TreeArtifactValue> treeArtifactData = new HashMap<>();
+    for (Map.Entry<Artifact, Map<ArtifactFile, FileArtifactValue>> dirDatum :
+        directoryData.entrySet()) {
+      Map<PathFragment, FileArtifactValue> artifactValues = new HashMap<>();
+      for (Map.Entry<ArtifactFile, FileArtifactValue> dirEntry : dirDatum.getValue().entrySet()) {
+        ArtifactFile file = dirEntry.getKey();
+        artifactValues.put(file.getParentRelativePath(), dirEntry.getValue());
+      }
+      treeArtifactData.put(dirDatum.getKey(), TreeArtifactValue.create(artifactValues));
+    }
+
+    return new ActionExecutionValue(fileData, treeArtifactData,
+        ImmutableMap.<Artifact, FileArtifactValue>of());
+  }
+
   @Test
   public void testPropagatesRuntimeExceptions() throws Exception {
     Collection<SkyKey> values =