Open source some skyframe/bazel tests.

--
MOS_MIGRATED_REVID=106308990

20 files changed, 6745 insertions, 0 deletions

diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionDataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionDataTest.java
new file mode 100644
index 0000000000..be903de440
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionDataTest.java
@@ -0,0 +1,173 @@
+// 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.collect.ImmutableList;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.actions.AbstractAction;
+import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionExecutionContext;
+import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.Actions;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Executor;
+import com.google.devtools.build.lib.actions.ResourceSet;
+import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
+import com.google.devtools.build.lib.actions.util.DummyExecutor;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+
+import java.io.IOException;
+import java.util.Collection;
+import java.util.Set;
+
+/**
+ * Tests that the data passed from the application to the Builder is passed
+ * down to each Action executed.
+ */
+public class ActionDataTest extends TimestampBuilderTestCase {
+
+  public void testArgumentToBuildArtifactsIsPassedDownToAction() throws Exception {
+
+    class MyAction extends AbstractAction {
+
+      Object executor = null;
+
+      public MyAction(Collection<Artifact> outputs) {
+        super(ActionsTestUtil.NULL_ACTION_OWNER, ImmutableList.<Artifact>of(), outputs);
+      }
+
+      @Override
+      public void execute(ActionExecutionContext actionExecutionContext)
+          throws ActionExecutionException {
+        this.executor = actionExecutionContext.getExecutor();
+        try {
+          FileSystemUtils.createEmptyFile(getPrimaryOutput().getPath());
+        } catch (IOException e) {
+          throw new ActionExecutionException("failed: ", e, this, false);
+        }
+      }
+
+      @Override
+      public ResourceSet estimateResourceConsumption(Executor executor) {
+        return ResourceSet.ZERO;
+      }
+
+      @Override
+      protected String computeKey() {
+        return "MyAction";
+      }
+
+      @Override
+      public String describeStrategy(Executor executor) {
+        return "";
+      }
+
+      @Override
+      public String getMnemonic() {
+        return "MyAction";
+      }
+    }
+
+    Artifact output = createDerivedArtifact("foo");
+    Set<Artifact> outputs = Sets.newHashSet(output);
+
+    MyAction action = new MyAction(outputs);
+    registerAction(action);
+
+    Executor executor = new DummyExecutor(scratch.dir("/"));
+    amnesiacBuilder()
+        .buildArtifacts(
+            reporter, outputs, null, null, null, null, executor, null, /*explain=*/ false, null);
+    assertSame(executor, action.executor);
+
+    executor = new DummyExecutor(scratch.dir("/"));
+    amnesiacBuilder()
+        .buildArtifacts(
+            reporter, outputs, null, null, null, null, executor, null, /*explain=*/ false, null);
+    assertSame(executor, action.executor);
+  }
+
+  private static class InputDiscoveringAction extends AbstractAction {
+    private final Collection<Artifact> discoveredInputs;
+
+    public InputDiscoveringAction(Artifact output, Collection<Artifact> discoveredInputs) {
+      super(
+          ActionsTestUtil.NULL_ACTION_OWNER,
+          ImmutableList.<Artifact>of(),
+          ImmutableList.of(output));
+      this.discoveredInputs = discoveredInputs;
+    }
+
+    @Override
+    public boolean discoversInputs() {
+      return true;
+    }
+
+    @Override
+    public boolean inputsKnown() {
+      return true;
+    }
+
+    @Override
+    public Iterable<Artifact> getMandatoryInputs() {
+      return ImmutableList.of();
+    }
+
+    @Override
+    public Iterable<Artifact> getInputs() {
+      return discoveredInputs;
+    }
+
+    @Override
+    public void execute(ActionExecutionContext actionExecutionContext) {
+      throw new IllegalStateException();
+    }
+
+    @Override
+    public String describeStrategy(Executor executor) {
+      return "";
+    }
+
+    @Override
+    public String getMnemonic() {
+      return "InputDiscovering";
+    }
+
+    @Override
+    protected String computeKey() {
+      return "";
+    }
+
+    @Override
+    public ResourceSet estimateResourceConsumption(Executor executor) {
+      return ResourceSet.ZERO;
+    }
+  }
+
+  public void testActionSharabilityAndDiscoveredInputs() throws Exception {
+    Artifact output =
+        new Artifact(
+            scratch.file("/out/output"), Root.asDerivedRoot(scratch.dir("/"), scratch.dir("/out")));
+    Artifact discovered =
+        new Artifact(
+            scratch.file("/bin/discovered"),
+            Root.asDerivedRoot(scratch.dir("/"), scratch.dir("/bin")));
+
+    Action a = new InputDiscoveringAction(output, ImmutableList.of(discovered));
+    Action b = new InputDiscoveringAction(output, ImmutableList.<Artifact>of());
+
+    assertTrue(Actions.canBeShared(a, b));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionExecutionInactivityWatchdogTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionExecutionInactivityWatchdogTest.java
new file mode 100644
index 0000000000..8c15b6c8d9
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionExecutionInactivityWatchdogTest.java
@@ -0,0 +1,167 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.devtools.build.lib.skyframe.ActionExecutionInactivityWatchdog.InactivityMonitor;
+import com.google.devtools.build.lib.skyframe.ActionExecutionInactivityWatchdog.InactivityReporter;
+import com.google.devtools.build.lib.testutil.MoreAsserts;
+
+import junit.framework.TestCase;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Tests for ActionExecutionInactivityWatchdog. */
+public final class ActionExecutionInactivityWatchdogTest extends TestCase {
+
+  private void assertInactivityWatchdogReports(final boolean shouldReport) throws Exception {
+    // The monitor implementation below is a state machine. This variable indicates which state
+    // it is in.
+    final int[] monitorState = new int[] {0};
+
+    // Object that the test thread will wait on.
+    final Object monitorFinishedIndicator = new Object();
+
+    // Reported number of action completions in each call to waitForNextCompletion.
+    final int[] actionCompletions = new int[] {1, 0, 3, 0, 0, 0, 0, 2};
+
+    // Simulated delay of action completions in each call to waitForNextCompletion.
+    final int[] waits = new int[] {5, 10, 3, 10, 30, 60, 60, 1};
+
+    // Log of all Sleep.sleep and InactivityMonitor.waitForNextCompletion calls.
+    final List<String> sleepsAndWaits = new ArrayList<>();
+
+    // Mock monitor for this test.
+    InactivityMonitor monitor =
+        new InactivityMonitor() {
+          @Override
+          public int waitForNextCompletion(int timeoutMilliseconds) throws InterruptedException {
+            // Simulate the following sequence of events (see actionCompletions):
+            // 1. return in 5s (within timeout), 1 action completed; caller will sleep
+            // 2. return in 10s (after timeout), 0 action completed; caller will wait
+            // 3. return in 3s (within timeout), 3 actions completed (this is possible, since the
+            //    waiting (thread doesn't necessarily wake up immediately); caller will sleep
+            // 4. return in 10s (after timeout), 0 action completed; caller will wait 30s
+            // 5. return in 30s (after timeout), 0 action completed still; caller will wait 60s
+            // 6. return in 60s (after timeout), 0 action completed still; caller will wait 60s
+            // 7. return in 60s (after timeout), 0 action completed still; caller will wait 60s
+            // 8. return in 1s (within timeout), 2 actions completed; caller will sleep, but we
+            //    won't record that, because monitorState reached its maximum
+            synchronized (monitorFinishedIndicator) {
+              if (monitorState[0] >= actionCompletions.length) {
+                // Notify the test thread that the test is over.
+                monitorFinishedIndicator.notify();
+                return 1;
+              } else {
+                int index = monitorState[0];
+                sleepsAndWaits.add("wait:" + waits[index]);
+                ++monitorState[0];
+                return actionCompletions[index];
+              }
+            }
+          }
+
+          @Override
+          public boolean hasStarted() {
+            return true;
+          }
+
+          @Override
+          public int getPending() {
+            int index = monitorState[0];
+            if (index >= actionCompletions.length) {
+              return 0;
+            }
+            int result = actionCompletions[index];
+            while (result == 0) {
+              ++index;
+              result = actionCompletions[index];
+            }
+            return result;
+          }
+        };
+
+    final boolean[] didReportInactivity = new boolean[] {false};
+    InactivityReporter reporter =
+        new InactivityReporter() {
+          @Override
+          public void maybeReportInactivity() {
+            if (shouldReport) {
+              didReportInactivity[0] = true;
+            }
+          }
+        };
+
+    // Mock sleep object; just logs how much the caller's thread would've slept.
+    ActionExecutionInactivityWatchdog.Sleep sleep =
+        new ActionExecutionInactivityWatchdog.Sleep() {
+          @Override
+          public void sleep(int durationMilliseconds) throws InterruptedException {
+            if (monitorState[0] < actionCompletions.length) {
+              sleepsAndWaits.add("sleep:" + durationMilliseconds);
+            }
+          }
+        };
+
+    ActionExecutionInactivityWatchdog watchdog =
+        new ActionExecutionInactivityWatchdog(monitor, reporter, 0, sleep);
+    try {
+      synchronized (monitorFinishedIndicator) {
+        watchdog.start();
+
+        long startTime = System.currentTimeMillis();
+        boolean done = false;
+        while (!done) {
+          try {
+            monitorFinishedIndicator.wait(5000);
+            done = true;
+            MoreAsserts.assertLessThan(
+                "test didn't finish under 5 seconds",
+                5000L,
+                System.currentTimeMillis() - startTime);
+          } catch (InterruptedException ie) {
+            // so-called Spurious Wakeup; ignore
+          }
+        }
+      }
+    } finally {
+      watchdog.stop();
+    }
+
+    assertEquals(shouldReport, didReportInactivity[0]);
+    assertThat(sleepsAndWaits)
+        .containsExactly(
+            "wait:5",
+            "sleep:1000",
+            "wait:10",
+            "wait:3",
+            "sleep:1000",
+            "wait:10",
+            "wait:30",
+            "wait:60",
+            "wait:60",
+            "wait:1")
+        .inOrder();
+  }
+
+  public void testInactivityWatchdogReportsWhenItShould() throws Exception {
+    assertInactivityWatchdogReports(true);
+  }
+
+  public void testInactivityWatchdogDoesNotReportWhenItShouldNot() throws Exception {
+    assertInactivityWatchdogReports(false);
+  }
+}
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
new file mode 100644
index 0000000000..e9efdfd81a
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -0,0 +1,417 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.skyframe.FileArtifactValue.create;
+import static org.junit.Assert.assertArrayEquals;
+
+import com.google.common.base.Predicates;
+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.common.testing.EqualsTester;
+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.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.events.NullEventHandler;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
+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;
+
+import junit.framework.TestCase;
+
+import java.io.IOException;
+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.
+public class ArtifactFunctionTest extends TestCase {
+  private static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
+  private static final ActionLookupKey ALL_OWNER = new SingletonActionLookupKey();
+
+  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());
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    setupRoot(new CustomInMemoryFs());
+    AtomicReference<PathPackageLocator> pkgLocator =
+        new AtomicReference<>(new PathPackageLocator());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    differencer = new RecordingDifferencer();
+    evaluator =
+        new InMemoryMemoizingEvaluator(
+            ImmutableMap.of(
+                SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper),
+                SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper),
+                SkyFunctions.ARTIFACT, new ArtifactFunction(Predicates.<PathFragment>alwaysFalse()),
+                SkyFunctions.ACTION_EXECUTION, new SimpleActionExecutionFunction()),
+            differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    actions = new HashSet<>();
+  }
+
+  private void setupRoot(CustomInMemoryFs fs) {
+    root = fs.getPath(TestUtils.tmpDir());
+  }
+
+  private void assertFileArtifactValueMatches(boolean expectDigest) throws Throwable {
+    Artifact output = createDerivedArtifact("output");
+    Path path = output.getPath();
+    file(path, "contents");
+    assertValueMatches(path.stat(), expectDigest ? path.getMD5Digest() : null, evaluateFAN(output));
+  }
+
+  public void testBasicArtifact() throws Throwable {
+    fastDigest = false;
+    assertFileArtifactValueMatches(/*expectDigest=*/ true);
+  }
+
+  public void testBasicArtifactWithXattr() throws Throwable {
+    fastDigest = true;
+    assertFileArtifactValueMatches(/*expectDigest=*/ true);
+  }
+
+  public void testMissingNonMandatoryArtifact() throws Throwable {
+    Artifact input = createSourceArtifact("input1");
+    assertNotNull(evaluateArtifactValue(input, /*mandatory=*/ false));
+  }
+
+  public void testMissingMandatoryArtifact() throws Throwable {
+    Artifact input = createSourceArtifact("input1");
+    try {
+      evaluateArtifactValue(input, /*mandatory=*/ true);
+      fail();
+    } catch (MissingInputFileException ex) {
+      // Expected.
+    }
+  }
+
+  public void testMiddlemanArtifact() throws Throwable {
+    Artifact output = createDerivedArtifact("output");
+    Artifact input1 = createSourceArtifact("input1");
+    Artifact input2 = createDerivedArtifact("input2");
+    Action action =
+        new DummyAction(
+            ImmutableList.of(input1, input2), output, MiddlemanType.AGGREGATING_MIDDLEMAN);
+    // Overwrite default generating action with this one.
+    for (Iterator<Action> it = actions.iterator(); it.hasNext(); ) {
+      if (it.next().getOutputs().contains(output)) {
+        it.remove();
+        break;
+      }
+    }
+    actions.add(action);
+    file(input2.getPath(), "contents");
+    file(input1.getPath(), "source contents");
+    evaluate(
+        Iterables.toArray(
+            ArtifactValue.mandatoryKeys(ImmutableSet.of(input2, input1, input2)), SkyKey.class));
+    ArtifactValue value = evaluateArtifactValue(output);
+    assertThat(((AggregatingArtifactValue) value).getInputs())
+        .containsExactly(Pair.of(input1, create(input1)), Pair.of(input2, create(input2)));
+  }
+
+  public void testIOException() throws Exception {
+    fastDigest = false;
+    final IOException exception = new IOException("beep");
+    setupRoot(
+        new CustomInMemoryFs() {
+          @Override
+          public byte[] getMD5Digest(Path path) throws IOException {
+            throw exception;
+          }
+        });
+    Artifact artifact = createDerivedArtifact("no-read");
+    writeFile(artifact.getPath(), "content");
+    try {
+      create(createDerivedArtifact("no-read"));
+      fail();
+    } catch (IOException e) {
+      assertSame(exception, e);
+    }
+  }
+
+  /**
+   * Tests that ArtifactFunction rethrows transitive {@link IOException}s as
+   * {@link MissingInputFileException}s.
+   */
+  public void testIOException_EndToEnd() throws Throwable {
+    final IOException exception = new IOException("beep");
+    setupRoot(
+        new CustomInMemoryFs() {
+          @Override
+          public FileStatus stat(Path path, boolean followSymlinks) throws IOException {
+            if (path.getBaseName().equals("bad")) {
+              throw exception;
+            }
+            return super.stat(path, followSymlinks);
+          }
+        });
+    try {
+      evaluateArtifactValue(createSourceArtifact("bad"));
+      fail();
+    } catch (MissingInputFileException e) {
+      assertThat(e.getMessage()).contains(exception.getMessage());
+    }
+  }
+
+  public void testNoMtimeIfNonemptyFile() throws Exception {
+    Artifact artifact = createDerivedArtifact("no-digest");
+    Path path = artifact.getPath();
+    writeFile(path, "hello"); //Non-empty file.
+    FileArtifactValue value = create(artifact);
+    assertArrayEquals(path.getMD5Digest(), value.getDigest());
+    try {
+      value.getModifiedTime();
+      fail("mtime for non-empty file should not be stored.");
+    } catch (IllegalStateException e) {
+      // Expected.
+    }
+  }
+
+  public void testDirectory() throws Exception {
+    Artifact artifact = createDerivedArtifact("dir");
+    Path path = artifact.getPath();
+    FileSystemUtils.createDirectoryAndParents(path);
+    path.setLastModifiedTime(1L);
+    FileArtifactValue value = create(artifact);
+    assertNull(value.getDigest());
+    assertEquals(1L, value.getModifiedTime());
+  }
+
+  // Empty files need to store their mtimes, so touching an empty file
+  // can be used to trigger rebuilds.
+  public void testEmptyFile() throws Exception {
+    Artifact artifact = createDerivedArtifact("empty");
+    Path path = artifact.getPath();
+    writeFile(path, "");
+    path.setLastModifiedTime(1L);
+    FileArtifactValue value = create(artifact);
+    assertArrayEquals(path.getMD5Digest(), value.getDigest());
+    assertEquals(1L, value.getModifiedTime());
+    assertEquals(0L, value.getSize());
+  }
+
+  public void testEquality() throws Exception {
+    Artifact artifact1 = createDerivedArtifact("artifact1");
+    Artifact artifact2 = createDerivedArtifact("artifact2");
+    Artifact diffDigest = createDerivedArtifact("diffDigest");
+    Artifact diffMtime = createDerivedArtifact("diffMtime");
+    Artifact empty1 = createDerivedArtifact("empty1");
+    Artifact empty2 = createDerivedArtifact("empty2");
+    Artifact empty3 = createDerivedArtifact("empty3");
+    Artifact dir1 = createDerivedArtifact("dir1");
+    Artifact dir2 = createDerivedArtifact("dir2");
+    Artifact dir3 = createDerivedArtifact("dir3");
+    Path path1 = artifact1.getPath();
+    Path path2 = artifact2.getPath();
+    Path digestPath = diffDigest.getPath();
+    Path mtimePath = diffMtime.getPath();
+    writeFile(artifact1.getPath(), "content");
+    writeFile(artifact2.getPath(), "content");
+    path1.setLastModifiedTime(0);
+    path2.setLastModifiedTime(0);
+    writeFile(diffDigest.getPath(), "1234567"); // Same size as artifact1.
+    digestPath.setLastModifiedTime(0);
+    writeFile(mtimePath, "content");
+    mtimePath.setLastModifiedTime(1);
+    Path emptyPath1 = empty1.getPath();
+    Path emptyPath2 = empty2.getPath();
+    Path emptyPath3 = empty3.getPath();
+    writeFile(emptyPath1, "");
+    writeFile(emptyPath2, "");
+    writeFile(emptyPath3, "");
+    emptyPath1.setLastModifiedTime(0L);
+    emptyPath2.setLastModifiedTime(1L);
+    emptyPath3.setLastModifiedTime(1L);
+    Path dirPath1 = dir1.getPath();
+    Path dirPath2 = dir2.getPath();
+    Path dirPath3 = dir3.getPath();
+    FileSystemUtils.createDirectoryAndParents(dirPath1);
+    FileSystemUtils.createDirectoryAndParents(dirPath2);
+    FileSystemUtils.createDirectoryAndParents(dirPath3);
+    dirPath1.setLastModifiedTime(0L);
+    dirPath2.setLastModifiedTime(1L);
+    dirPath3.setLastModifiedTime(1L);
+    EqualsTester equalsTester = new EqualsTester();
+    equalsTester
+        .addEqualityGroup(create(artifact1), create(artifact2), create(diffMtime))
+        .addEqualityGroup(create(empty1))
+        .addEqualityGroup(create(empty2), create(empty3))
+        .addEqualityGroup(create(dir1))
+        .addEqualityGroup(create(dir2), create(dir3))
+        .testEquals();
+  }
+
+  private void file(Path path, String contents) throws Exception {
+    FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
+    writeFile(path, contents);
+  }
+
+  private Artifact createSourceArtifact(String path) {
+    return new Artifact(new PathFragment(path), Root.asSourceRoot(root));
+  }
+
+  private Artifact createDerivedArtifact(String path) {
+    PathFragment execPath = new PathFragment("out").getRelative(path);
+    Path fullPath = root.getRelative(execPath);
+    Artifact output =
+        new Artifact(
+            fullPath, Root.asDerivedRoot(root, root.getRelative("out")), execPath, ALL_OWNER);
+    actions.add(new DummyAction(ImmutableList.<Artifact>of(), output));
+    return output;
+  }
+
+  private void assertValueMatches(FileStatus file, byte[] digest, FileArtifactValue value)
+      throws IOException {
+    assertEquals(file.getSize(), value.getSize());
+    if (digest == null) {
+      assertNull(value.getDigest());
+      assertEquals(file.getLastModifiedTime(), value.getModifiedTime());
+    } else {
+      assertArrayEquals(digest, value.getDigest());
+    }
+  }
+
+  private FileArtifactValue evaluateFAN(Artifact artifact) throws Throwable {
+    return ((FileArtifactValue) evaluateArtifactValue(artifact));
+  }
+
+  private ArtifactValue evaluateArtifactValue(Artifact artifact) throws Throwable {
+    return evaluateArtifactValue(artifact, /*isMandatory=*/ true);
+  }
+
+  private ArtifactValue evaluateArtifactValue(Artifact artifact, boolean mandatory)
+      throws Throwable {
+    SkyKey key = ArtifactValue.key(artifact, mandatory);
+    EvaluationResult<ArtifactValue> result = evaluate(ImmutableList.of(key).toArray(new SkyKey[0]));
+    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 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
+    public SkyValue compute(SkyKey skyKey, Environment env) {
+      Map<Artifact, FileValue> artifactData = new HashMap<>();
+      Action action = (Action) skyKey.argument();
+      Artifact output = Iterables.getOnlyElement(action.getOutputs());
+      FileArtifactValue value;
+      if (action.getActionType() == MiddlemanType.NORMAL) {
+        try {
+          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifact(output, null, tsgm);
+          artifactData.put(output, fileValue);
+          value = FileArtifactValue.create(output, fileValue);
+        } catch (IOException e) {
+          throw new IllegalStateException(e);
+        }
+      } else {
+        value = FileArtifactValue.DEFAULT_MIDDLEMAN;
+      }
+      return new ActionExecutionValue(artifactData, ImmutableMap.of(output, value));
+    }
+
+    @Override
+    public String extractTag(SkyKey skyKey) {
+      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/ContainingPackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
new file mode 100644
index 0000000000..c7c7d5bc4f
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
@@ -0,0 +1,126 @@
+// 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.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.testing.EqualsTester;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+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 java.util.HashMap;
+import java.util.Map;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+
+/**
+ * Tests for {@link ContainingPackageLookupFunction}.
+ */
+public class ContainingPackageLookupFunctionTest extends FoundationTestCase {
+
+  private AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages;
+  private MemoizingEvaluator evaluator;
+  private SequentialBuildDriver driver;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    AtomicReference<PathPackageLocator> pkgLocator =
+        new AtomicReference<>(new PathPackageLocator(rootDirectory));
+    deletedPackages = new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    TimestampGranularityMonitor tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
+
+    Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
+    skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));
+    skyFunctions.put(SkyFunctions.CONTAINING_PACKAGE_LOOKUP, new ContainingPackageLookupFunction());
+    skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    RecordingDifferencer differencer = new RecordingDifferencer();
+    evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+  }
+
+  private ContainingPackageLookupValue lookupContainingPackage(String packageName)
+      throws InterruptedException {
+    SkyKey key =
+        ContainingPackageLookupValue.key(PackageIdentifier.createInDefaultRepo(packageName));
+    return driver
+        .<ContainingPackageLookupValue>evaluate(
+            ImmutableList.of(key),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE)
+        .get(key);
+  }
+
+  public void testNoContainingPackage() throws Exception {
+    ContainingPackageLookupValue value = lookupContainingPackage("a/b");
+    assertFalse(value.hasContainingPackage());
+  }
+
+  public void testContainingPackageIsParent() throws Exception {
+    scratch.file("a/BUILD");
+    ContainingPackageLookupValue value = lookupContainingPackage("a/b");
+    assertTrue(value.hasContainingPackage());
+    assertEquals(PackageIdentifier.createInDefaultRepo("a"), value.getContainingPackageName());
+    assertEquals(rootDirectory, value.getContainingPackageRoot());
+  }
+
+  public void testContainingPackageIsSelf() throws Exception {
+    scratch.file("a/b/BUILD");
+    ContainingPackageLookupValue value = lookupContainingPackage("a/b");
+    assertTrue(value.hasContainingPackage());
+    assertEquals(PackageIdentifier.createInDefaultRepo("a/b"), value.getContainingPackageName());
+    assertEquals(rootDirectory, value.getContainingPackageRoot());
+  }
+
+  public void testEqualsAndHashCodeContract() throws Exception {
+    ContainingPackageLookupValue valueA1 = ContainingPackageLookupValue.NONE;
+    ContainingPackageLookupValue valueA2 = ContainingPackageLookupValue.NONE;
+    ContainingPackageLookupValue valueB1 =
+        ContainingPackageLookupValue.withContainingPackage(
+            PackageIdentifier.createInDefaultRepo("b"), rootDirectory);
+    ContainingPackageLookupValue valueB2 =
+        ContainingPackageLookupValue.withContainingPackage(
+            PackageIdentifier.createInDefaultRepo("b"), rootDirectory);
+    PackageIdentifier cFrag = PackageIdentifier.createInDefaultRepo("c");
+    ContainingPackageLookupValue valueC1 =
+        ContainingPackageLookupValue.withContainingPackage(cFrag, rootDirectory);
+    ContainingPackageLookupValue valueC2 =
+        ContainingPackageLookupValue.withContainingPackage(cFrag, rootDirectory);
+    ContainingPackageLookupValue valueCOther =
+        ContainingPackageLookupValue.withContainingPackage(
+            cFrag, rootDirectory.getRelative("other_root"));
+    new EqualsTester()
+        .addEqualityGroup(valueA1, valueA2)
+        .addEqualityGroup(valueB1, valueB2)
+        .addEqualityGroup(valueC1, valueC2)
+        .addEqualityGroup(valueCOther)
+        .testEquals();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/DiffAwarenessManagerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/DiffAwarenessManagerTest.java
new file mode 100644
index 0000000000..bd28c33fec
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/DiffAwarenessManagerTest.java
@@ -0,0 +1,266 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Maps;
+import com.google.devtools.build.lib.events.util.EventCollectionApparatus;
+import com.google.devtools.build.lib.skyframe.DiffAwarenessManager.ProcessableModifiedFileSet;
+import com.google.devtools.build.lib.vfs.FileSystem;
+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.lib.vfs.inmemoryfs.InMemoryFileSystem;
+
+import junit.framework.TestCase;
+
+import java.util.List;
+import java.util.Map;
+
+import javax.annotation.Nullable;
+
+/**
+ * Unit tests for {@link DiffAwarenessManager}, especially of the fact that it works in a sequential
+ * manner and of its correctness in the presence of unprocesed diffs.
+ */
+public class DiffAwarenessManagerTest extends TestCase {
+
+  private FileSystem fs;
+  private Path root;
+  protected EventCollectionApparatus events;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    fs = new InMemoryFileSystem();
+    root = fs.getRootDirectory();
+    events = new EventCollectionApparatus();
+    events.setFailFast(false);
+  }
+
+  public void testEverythingModifiedIfNoDiffAwareness() throws Exception {
+    Path pathEntry = root.getRelative("pathEntry");
+    DiffAwarenessFactoryStub factory = new DiffAwarenessFactoryStub();
+    DiffAwarenessManager manager = new DiffAwarenessManager(ImmutableList.of(factory));
+    assertEquals(
+        "Expected EVERYTHING_MODIFIED since there are no factories",
+        ModifiedFileSet.EVERYTHING_MODIFIED,
+        manager.getDiff(events.reporter(), pathEntry).getModifiedFileSet());
+    events.assertNoWarningsOrErrors();
+  }
+
+  public void testResetAndSetPathEntriesCallClose() throws Exception {
+    Path pathEntry = root.getRelative("pathEntry");
+    ModifiedFileSet diff = ModifiedFileSet.NOTHING_MODIFIED;
+    DiffAwarenessStub diffAwareness1 = new DiffAwarenessStub(ImmutableList.of(diff));
+    DiffAwarenessStub diffAwareness2 = new DiffAwarenessStub(ImmutableList.of(diff));
+    DiffAwarenessFactoryStub factory = new DiffAwarenessFactoryStub();
+    factory.inject(pathEntry, diffAwareness1);
+    DiffAwarenessManager manager = new DiffAwarenessManager(ImmutableList.of(factory));
+    manager.getDiff(events.reporter(), pathEntry);
+    assertFalse("diffAwareness1 shouldn't have been closed yet", diffAwareness1.closed());
+    manager.reset();
+    assertTrue("diffAwareness1 should have been closed by reset", diffAwareness1.closed());
+    factory.inject(pathEntry, diffAwareness2);
+    manager.getDiff(events.reporter(), pathEntry);
+    assertFalse("diffAwareness2 shouldn't have been closed yet", diffAwareness2.closed());
+    events.assertNoWarningsOrErrors();
+  }
+
+  public void testHandlesUnprocessedDiffs() throws Exception {
+    Path pathEntry = root.getRelative("pathEntry");
+    ModifiedFileSet diff1 = ModifiedFileSet.builder().modify(new PathFragment("file1")).build();
+    ModifiedFileSet diff2 = ModifiedFileSet.builder().modify(new PathFragment("file2")).build();
+    ModifiedFileSet diff3 = ModifiedFileSet.builder().modify(new PathFragment("file3")).build();
+    DiffAwarenessStub diffAwareness =
+        new DiffAwarenessStub(ImmutableList.of(diff1, diff2, diff3, DiffAwarenessStub.BROKEN_DIFF));
+    DiffAwarenessFactoryStub factory = new DiffAwarenessFactoryStub();
+    factory.inject(pathEntry, diffAwareness);
+    DiffAwarenessManager manager = new DiffAwarenessManager(ImmutableList.of(factory));
+    ProcessableModifiedFileSet firstProcessableDiff = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(
+        "Expected EVERYTHING_MODIFIED on first call to getDiff",
+        ModifiedFileSet.EVERYTHING_MODIFIED,
+        firstProcessableDiff.getModifiedFileSet());
+    firstProcessableDiff.markProcessed();
+    ProcessableModifiedFileSet processableDiff1 = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(diff1, processableDiff1.getModifiedFileSet());
+    ProcessableModifiedFileSet processableDiff2 = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(ModifiedFileSet.union(diff1, diff2), processableDiff2.getModifiedFileSet());
+    processableDiff2.markProcessed();
+    ProcessableModifiedFileSet processableDiff3 = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(diff3, processableDiff3.getModifiedFileSet());
+    events.assertNoWarningsOrErrors();
+    ProcessableModifiedFileSet processableDiff4 = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(ModifiedFileSet.EVERYTHING_MODIFIED, processableDiff4.getModifiedFileSet());
+    events.assertContainsWarning("error");
+  }
+
+  public void testHandlesBrokenDiffs() throws Exception {
+    Path pathEntry = root.getRelative("pathEntry");
+    DiffAwarenessFactoryStub factory1 = new DiffAwarenessFactoryStub();
+    DiffAwarenessStub diffAwareness1 =
+        new DiffAwarenessStub(ImmutableList.<ModifiedFileSet>of(), 1);
+    factory1.inject(pathEntry, diffAwareness1);
+    DiffAwarenessFactoryStub factory2 = new DiffAwarenessFactoryStub();
+    ModifiedFileSet diff2 = ModifiedFileSet.builder().modify(new PathFragment("file2")).build();
+    DiffAwarenessStub diffAwareness2 =
+        new DiffAwarenessStub(ImmutableList.of(diff2, DiffAwarenessStub.BROKEN_DIFF));
+    factory2.inject(pathEntry, diffAwareness2);
+    DiffAwarenessFactoryStub factory3 = new DiffAwarenessFactoryStub();
+    ModifiedFileSet diff3 = ModifiedFileSet.builder().modify(new PathFragment("file3")).build();
+    DiffAwarenessStub diffAwareness3 = new DiffAwarenessStub(ImmutableList.of(diff3));
+    factory3.inject(pathEntry, diffAwareness3);
+    DiffAwarenessManager manager =
+        new DiffAwarenessManager(ImmutableList.of(factory1, factory2, factory3));
+
+    ProcessableModifiedFileSet processableDiff = manager.getDiff(events.reporter(), pathEntry);
+    events.assertNoWarningsOrErrors();
+    assertEquals(
+        "Expected EVERYTHING_MODIFIED on first call to getDiff for diffAwareness1",
+        ModifiedFileSet.EVERYTHING_MODIFIED,
+        processableDiff.getModifiedFileSet());
+    processableDiff.markProcessed();
+
+    processableDiff = manager.getDiff(events.reporter(), pathEntry);
+    events.assertContainsEventWithFrequency("error in getCurrentView", 1);
+    assertEquals(
+        "Expected EVERYTHING_MODIFIED because of broken getCurrentView",
+        ModifiedFileSet.EVERYTHING_MODIFIED,
+        processableDiff.getModifiedFileSet());
+    processableDiff.markProcessed();
+    factory1.remove(pathEntry);
+
+    processableDiff = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(
+        "Expected EVERYTHING_MODIFIED on first call to getDiff for diffAwareness2",
+        ModifiedFileSet.EVERYTHING_MODIFIED,
+        processableDiff.getModifiedFileSet());
+    processableDiff.markProcessed();
+
+    processableDiff = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(diff2, processableDiff.getModifiedFileSet());
+    processableDiff.markProcessed();
+
+    processableDiff = manager.getDiff(events.reporter(), pathEntry);
+    events.assertContainsEventWithFrequency("error in getDiff", 1);
+    assertEquals(
+        "Expected EVERYTHING_MODIFIED because of broken getDiff",
+        ModifiedFileSet.EVERYTHING_MODIFIED,
+        processableDiff.getModifiedFileSet());
+    processableDiff.markProcessed();
+    factory2.remove(pathEntry);
+
+    processableDiff = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(
+        "Expected EVERYTHING_MODIFIED on first call to getDiff for diffAwareness3",
+        ModifiedFileSet.EVERYTHING_MODIFIED,
+        processableDiff.getModifiedFileSet());
+    processableDiff.markProcessed();
+
+    processableDiff = manager.getDiff(events.reporter(), pathEntry);
+    assertEquals(diff3, processableDiff.getModifiedFileSet());
+    processableDiff.markProcessed();
+  }
+
+  private static class DiffAwarenessFactoryStub implements DiffAwareness.Factory {
+
+    private Map<Path, DiffAwareness> diffAwarenesses = Maps.newHashMap();
+
+    public void inject(Path pathEntry, DiffAwareness diffAwareness) {
+      diffAwarenesses.put(pathEntry, diffAwareness);
+    }
+
+    public void remove(Path pathEntry) {
+      diffAwarenesses.remove(pathEntry);
+    }
+
+    @Override
+    @Nullable
+    public DiffAwareness maybeCreate(Path pathEntry) {
+      return diffAwarenesses.get(pathEntry);
+    }
+  }
+
+  private static class DiffAwarenessStub implements DiffAwareness {
+
+    public static final ModifiedFileSet BROKEN_DIFF =
+        ModifiedFileSet.builder().modify(new PathFragment("special broken marker")).build();
+
+    private boolean closed = false;
+    private int curSequenceNum = 0;
+    private final List<ModifiedFileSet> sequentialDiffs;
+    private final int brokenViewNum;
+
+    public DiffAwarenessStub(List<ModifiedFileSet> sequentialDiffs) {
+      this(sequentialDiffs, -1);
+    }
+
+    public DiffAwarenessStub(List<ModifiedFileSet> sequentialDiffs, int brokenViewNum) {
+      this.sequentialDiffs = sequentialDiffs;
+      this.brokenViewNum = brokenViewNum;
+    }
+
+    private static class ViewStub implements DiffAwareness.View {
+      private final int sequenceNum;
+
+      public ViewStub(int sequenceNum) {
+        this.sequenceNum = sequenceNum;
+      }
+    }
+
+    @Override
+    public View getCurrentView() throws BrokenDiffAwarenessException {
+      if (curSequenceNum == brokenViewNum) {
+        throw new BrokenDiffAwarenessException("error in getCurrentView");
+      }
+      return new ViewStub(curSequenceNum++);
+    }
+
+    @Override
+    public ModifiedFileSet getDiff(View oldView, View newView) throws BrokenDiffAwarenessException {
+      assertThat(oldView).isInstanceOf(ViewStub.class);
+      assertThat(newView).isInstanceOf(ViewStub.class);
+      ViewStub oldViewStub = (ViewStub) oldView;
+      ViewStub newViewStub = (ViewStub) newView;
+      Preconditions.checkState(newViewStub.sequenceNum >= oldViewStub.sequenceNum);
+      ModifiedFileSet diff = ModifiedFileSet.NOTHING_MODIFIED;
+      for (int num = oldViewStub.sequenceNum; num < newViewStub.sequenceNum; num++) {
+        ModifiedFileSet incrementalDiff = sequentialDiffs.get(num);
+        if (incrementalDiff == BROKEN_DIFF) {
+          throw new BrokenDiffAwarenessException("error in getDiff");
+        }
+        diff = ModifiedFileSet.union(diff, incrementalDiff);
+      }
+      return diff;
+    }
+
+    @Override
+    public String name() {
+      return "testingstub";
+    }
+
+    @Override
+    public void close() {
+      closed = true;
+    }
+
+    public boolean closed() {
+      return closed;
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunctionTest.java
new file mode 100644
index 0000000000..edfc2c54de
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunctionTest.java
@@ -0,0 +1,46 @@
+// 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.collect.ImmutableList;
+import com.google.common.testing.EqualsTester;
+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.inmemoryfs.InMemoryFileSystem;
+
+import junit.framework.TestCase;
+
+public class FileSymlinkCycleUniquenessFunctionTest extends TestCase {
+
+  public void testHashCodeAndEqualsContract() throws Exception {
+    Path root = new InMemoryFileSystem().getRootDirectory().getRelative("root");
+    RootedPath p1 = RootedPath.toRootedPath(root, new PathFragment("p1"));
+    RootedPath p2 = RootedPath.toRootedPath(root, new PathFragment("p2"));
+    RootedPath p3 = RootedPath.toRootedPath(root, new PathFragment("p3"));
+    ImmutableList<RootedPath> cycleA1 = ImmutableList.of(p1);
+    ImmutableList<RootedPath> cycleB1 = ImmutableList.of(p2);
+    ImmutableList<RootedPath> cycleC1 = ImmutableList.of(p1, p2, p3);
+    ImmutableList<RootedPath> cycleC2 = ImmutableList.of(p2, p3, p1);
+    ImmutableList<RootedPath> cycleC3 = ImmutableList.of(p3, p1, p2);
+    new EqualsTester()
+        .addEqualityGroup(FileSymlinkCycleUniquenessFunction.key(cycleA1))
+        .addEqualityGroup(FileSymlinkCycleUniquenessFunction.key(cycleB1))
+        .addEqualityGroup(
+            FileSymlinkCycleUniquenessFunction.key(cycleC1),
+            FileSymlinkCycleUniquenessFunction.key(cycleC2),
+            FileSymlinkCycleUniquenessFunction.key(cycleC3))
+        .testEquals();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
new file mode 100644
index 0000000000..e699f0ae29
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
@@ -0,0 +1,853 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+import static com.google.common.truth.Truth.assertWithMessage;
+import static com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode.CROSS;
+import static com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode.DONT_CROSS;
+import static com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode.REPORT_ERROR;
+
+import com.google.common.base.Function;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Collections2;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.FilesetOutputSymlink;
+import com.google.devtools.build.lib.actions.FilesetTraversalParams;
+import com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode;
+import com.google.devtools.build.lib.actions.FilesetTraversalParamsFactory;
+import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.packages.FilesetEntry.SymlinkBehavior;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.util.Fingerprint;
+import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+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.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
+import com.google.devtools.build.skyframe.MemoizingEvaluator;
+import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+
+import javax.annotation.Nullable;
+
+/** Tests for {@link FilesetEntryFunction}. */
+public final class FilesetEntryFunctionTest extends FoundationTestCase {
+
+  private TimestampGranularityMonitor tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
+  private MemoizingEvaluator evaluator;
+  private SequentialBuildDriver driver;
+  private RecordingDifferencer differencer;
+  private AtomicReference<PathPackageLocator> pkgLocator;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+
+    pkgLocator = new AtomicReference<>(new PathPackageLocator(rootDirectory));
+    AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages =
+        new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+
+    Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
+
+    skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
+    skyFunctions.put(
+        SkyFunctions.DIRECTORY_LISTING_STATE,
+        new DirectoryListingStateFunction(externalFilesHelper));
+    skyFunctions.put(
+        SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL, new RecursiveFilesystemTraversalFunction());
+    skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));
+    skyFunctions.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction());
+
+    differencer = new RecordingDifferencer();
+    evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+  }
+
+  private Artifact getSourceArtifact(String path) throws Exception {
+    return new Artifact(new PathFragment(path), Root.asSourceRoot(rootDirectory));
+  }
+
+  private Artifact createSourceArtifact(String path) throws Exception {
+    Artifact result = getSourceArtifact(path);
+    createFile(result, "foo");
+    return result;
+  }
+
+  private static RootedPath rootedPath(Artifact artifact) {
+    return RootedPath.toRootedPath(artifact.getRoot().getPath(), artifact.getRootRelativePath());
+  }
+
+  private static RootedPath childOf(Artifact artifact, String relative) {
+    return RootedPath.toRootedPath(
+        artifact.getRoot().getPath(), artifact.getRootRelativePath().getRelative(relative));
+  }
+
+  private static RootedPath siblingOf(Artifact artifact, String relative) {
+    PathFragment parent =
+        Preconditions.checkNotNull(artifact.getRootRelativePath().getParentDirectory());
+    return RootedPath.toRootedPath(artifact.getRoot().getPath(), parent.getRelative(relative));
+  }
+
+  private void createFile(Path path, String... contents) throws Exception {
+    if (!path.getParentDirectory().exists()) {
+      scratch.dir(path.getParentDirectory().getPathString());
+    }
+    scratch.file(path.getPathString(), contents);
+  }
+
+  private void createFile(Artifact artifact, String... contents) throws Exception {
+    createFile(artifact.getPath(), contents);
+  }
+
+  private RootedPath createFile(RootedPath path, String... contents) throws Exception {
+    createFile(path.asPath(), contents);
+    return path;
+  }
+
+  private <T extends SkyValue> EvaluationResult<T> eval(SkyKey key) throws Exception {
+    return driver.evaluate(
+        ImmutableList.of(key),
+        false,
+        SkyframeExecutor.DEFAULT_THREAD_COUNT,
+        NullEventHandler.INSTANCE);
+  }
+
+  private FilesetEntryValue evalFilesetTraversal(FilesetTraversalParams params) throws Exception {
+    SkyKey key = FilesetEntryValue.key(params);
+    EvaluationResult<FilesetEntryValue> result = eval(key);
+    assertThat(result.hasError()).isFalse();
+    return result.get(key);
+  }
+
+  private static FilesetOutputSymlink symlink(String from, Artifact to) {
+    return new FilesetOutputSymlink(new PathFragment(from), to.getPath().asFragment());
+  }
+
+  private static FilesetOutputSymlink symlink(String from, String to) {
+    return new FilesetOutputSymlink(new PathFragment(from), new PathFragment(to));
+  }
+
+  private static FilesetOutputSymlink symlink(String from, RootedPath to) {
+    return new FilesetOutputSymlink(new PathFragment(from), to.asPath().asFragment());
+  }
+
+  private void assertSymlinksInOrder(
+      FilesetTraversalParams request, FilesetOutputSymlink... expectedSymlinks) throws Exception {
+    List<FilesetOutputSymlink> expected = Arrays.asList(expectedSymlinks);
+    Collection<FilesetOutputSymlink> actual =
+        Collections2.transform(
+            evalFilesetTraversal(request).getSymlinks(),
+            // Strip the metadata from the actual results.
+            new Function<FilesetOutputSymlink, FilesetOutputSymlink>() {
+              @Override
+              public FilesetOutputSymlink apply(FilesetOutputSymlink input) {
+                return new FilesetOutputSymlink(input.name, input.target);
+              }
+            });
+    assertThat(actual).containsExactlyElementsIn(expected).inOrder();
+  }
+
+  private static Label label(String label) throws Exception {
+    return Label.parseAbsolute(label);
+  }
+
+  public void testFileTraversalForFile() throws Exception {
+    Artifact file = createSourceArtifact("foo/file.real");
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*fileToTraverse=*/ file,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    assertSymlinksInOrder(params, symlink("output-name", file));
+  }
+
+  private void assertFileTraversalForFileSymlink(SymlinkBehavior symlinks) throws Exception {
+    Artifact file = createSourceArtifact("foo/file.real");
+    Artifact symlink = getSourceArtifact("foo/file.sym");
+    symlink.getPath().createSymbolicLink(new PathFragment("file.real"));
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*fileToTraverse=*/ symlink,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ symlinks,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    switch (symlinks) {
+      case COPY:
+        assertSymlinksInOrder(params, symlink("output-name", "file.real"));
+        break;
+      case DEREFERENCE:
+        assertSymlinksInOrder(params, symlink("output-name", file));
+        break;
+      default:
+        throw new IllegalStateException(symlinks.toString());
+    }
+  }
+
+  public void testFileTraversalForFileSymlinkNoFollow() throws Exception {
+    assertFileTraversalForFileSymlink(SymlinkBehavior.COPY);
+  }
+
+  public void testFileTraversalForFileSymlinkFollow() throws Exception {
+    assertFileTraversalForFileSymlink(SymlinkBehavior.DEREFERENCE);
+  }
+
+  public void testFileTraversalForDirectory() throws Exception {
+    Artifact dir = getSourceArtifact("foo/dir_real");
+    RootedPath fileA = createFile(childOf(dir, "file.a"), "hello");
+    RootedPath fileB = createFile(childOf(dir, "sub/file.b"), "world");
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*fileToTraverse=*/ dir,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    assertSymlinksInOrder(
+        params, symlink("output-name/file.a", fileA), symlink("output-name/sub/file.b", fileB));
+  }
+
+  private void assertFileTraversalForDirectorySymlink(SymlinkBehavior symlinks) throws Exception {
+    Artifact dir = getSourceArtifact("foo/dir_real");
+    Artifact symlink = getSourceArtifact("foo/dir_sym");
+    createFile(childOf(dir, "file.a"), "hello");
+    createFile(childOf(dir, "sub/file.b"), "world");
+    symlink.getPath().createSymbolicLink(new PathFragment("dir_real"));
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*fileToTraverse=*/ symlink,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ symlinks,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    switch (symlinks) {
+      case COPY:
+        assertSymlinksInOrder(params, symlink("output-name", "dir_real"));
+        break;
+      case DEREFERENCE:
+        assertSymlinksInOrder(params, symlink("output-name", dir));
+        break;
+      default:
+        throw new IllegalStateException(symlinks.toString());
+    }
+  }
+
+  public void testFileTraversalForDirectorySymlinkFollow() throws Exception {
+    assertFileTraversalForDirectorySymlink(SymlinkBehavior.COPY);
+  }
+
+  public void testFileTraversalForDirectorySymlinkNoFollow() throws Exception {
+    assertFileTraversalForDirectorySymlink(SymlinkBehavior.DEREFERENCE);
+  }
+
+  private void assertRecursiveTraversalForDirectory(
+      SymlinkBehavior symlinks, PackageBoundaryMode pkgBoundaryMode) throws Exception {
+    Artifact dir = getSourceArtifact("foo/dir");
+    RootedPath fileA = createFile(childOf(dir, "file.a"), "blah");
+    RootedPath fileAsym = childOf(dir, "subdir/file.a.sym");
+    RootedPath buildFile = createFile(childOf(dir, "subpkg/BUILD"), "blah");
+    RootedPath fileB = createFile(childOf(dir, "subpkg/file.b"), "blah");
+    fileAsym.asPath().getParentDirectory().createDirectory();
+    fileAsym.asPath().createSymbolicLink(new PathFragment("../file.a"));
+
+    FilesetOutputSymlink outA = symlink("output-name/file.a", childOf(dir, "file.a"));
+    FilesetOutputSymlink outAsym = null;
+    FilesetOutputSymlink outBuild = symlink("output-name/subpkg/BUILD", buildFile);
+    FilesetOutputSymlink outB = symlink("output-name/subpkg/file.b", fileB);
+    switch (symlinks) {
+      case COPY:
+        outAsym = symlink("output-name/subdir/file.a.sym", "../file.a");
+        break;
+      case DEREFERENCE:
+        outAsym = symlink("output-name/subdir/file.a.sym", fileA);
+        break;
+      default:
+        throw new IllegalStateException(symlinks.toString());
+    }
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.recursiveTraversalOfDirectory(
+            /*ownerLabel=*/ label("//foo"),
+            /*directoryToTraverse=*/ dir,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*excludes=*/ null,
+            /*symlinkBehaviorMode=*/ symlinks,
+            /*pkgBoundaryMode=*/ pkgBoundaryMode);
+    switch (pkgBoundaryMode) {
+      case CROSS:
+        assertSymlinksInOrder(params, outA, outAsym, outBuild, outB);
+        break;
+      case DONT_CROSS:
+        assertSymlinksInOrder(params, outA, outAsym);
+        break;
+      case REPORT_ERROR:
+        SkyKey key = FilesetEntryValue.key(params);
+        EvaluationResult<SkyValue> result = eval(key);
+        assertThat(result.hasError()).isTrue();
+        assertThat(result.getError(key).getException().getMessage())
+            .contains("'foo/dir' crosses package boundary into package rooted at foo/dir/subpkg");
+        break;
+      default:
+        throw new IllegalStateException(pkgBoundaryMode.toString());
+    }
+  }
+
+  public void testRecursiveTraversalForDirectoryCrossNoFollow() throws Exception {
+    assertRecursiveTraversalForDirectory(SymlinkBehavior.COPY, CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectoryDontCrossNoFollow() throws Exception {
+    assertRecursiveTraversalForDirectory(SymlinkBehavior.COPY, DONT_CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectoryReportErrorNoFollow() throws Exception {
+    assertRecursiveTraversalForDirectory(SymlinkBehavior.COPY, REPORT_ERROR);
+  }
+
+  public void testRecursiveTraversalForDirectoryCrossFollow() throws Exception {
+    assertRecursiveTraversalForDirectory(SymlinkBehavior.DEREFERENCE, CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectoryDontCrossFollow() throws Exception {
+    assertRecursiveTraversalForDirectory(SymlinkBehavior.DEREFERENCE, DONT_CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectoryReportErrorFollow() throws Exception {
+    assertRecursiveTraversalForDirectory(SymlinkBehavior.DEREFERENCE, REPORT_ERROR);
+  }
+
+  private void assertRecursiveTraversalForDirectorySymlink(
+      SymlinkBehavior symlinks, PackageBoundaryMode pkgBoundaryMode) throws Exception {
+    Artifact dir = getSourceArtifact("foo/dir_real");
+    Artifact symlink = getSourceArtifact("foo/dir_sym");
+    createFile(childOf(dir, "file.a"), "blah");
+    RootedPath fileAsym = childOf(dir, "subdir/file.a.sym");
+    createFile(childOf(dir, "subpkg/BUILD"), "blah");
+    createFile(childOf(dir, "subpkg/file.b"), "blah");
+    fileAsym.asPath().getParentDirectory().createDirectory();
+    fileAsym.asPath().createSymbolicLink(new PathFragment("../file.a"));
+    symlink.getPath().createSymbolicLink(new PathFragment("dir_real"));
+
+    FilesetOutputSymlink outA = symlink("output-name/file.a", childOf(symlink, "file.a"));
+    FilesetOutputSymlink outASym = null;
+    FilesetOutputSymlink outBuild =
+        symlink("output-name/subpkg/BUILD", childOf(symlink, "subpkg/BUILD"));
+    FilesetOutputSymlink outB =
+        symlink("output-name/subpkg/file.b", childOf(symlink, "subpkg/file.b"));
+    switch (symlinks) {
+      case COPY:
+        outASym = symlink("output-name/subdir/file.a.sym", "../file.a");
+        break;
+      case DEREFERENCE:
+        outASym = symlink("output-name/subdir/file.a.sym", childOf(dir, "file.a"));
+        break;
+      default:
+        throw new IllegalStateException(symlinks.toString());
+    }
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.recursiveTraversalOfDirectory(
+            /*ownerLabel=*/ label("//foo"),
+            /*directoryToTraverse=*/ symlink,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*excludes=*/ null,
+            /*symlinkBehaviorMode=*/ symlinks,
+            /*pkgBoundaryMode=*/ pkgBoundaryMode);
+    switch (pkgBoundaryMode) {
+      case CROSS:
+        assertSymlinksInOrder(params, outA, outASym, outBuild, outB);
+        break;
+      case DONT_CROSS:
+        assertSymlinksInOrder(params, outA, outASym);
+        break;
+      case REPORT_ERROR:
+        SkyKey key = FilesetEntryValue.key(params);
+        EvaluationResult<SkyValue> result = eval(key);
+        assertThat(result.hasError()).isTrue();
+        assertThat(result.getError(key).getException().getMessage())
+            .contains(
+                "'foo/dir_sym' crosses package boundary into package rooted at foo/dir_sym/subpkg");
+        break;
+      default:
+        throw new IllegalStateException(pkgBoundaryMode.toString());
+    }
+  }
+
+  public void testRecursiveTraversalForDirectorySymlinkNoFollowCross() throws Exception {
+    assertRecursiveTraversalForDirectorySymlink(SymlinkBehavior.COPY, CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectorySymlinkNoFollowDontCross() throws Exception {
+    assertRecursiveTraversalForDirectorySymlink(SymlinkBehavior.COPY, DONT_CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectorySymlinkNoFollowReportError() throws Exception {
+    assertRecursiveTraversalForDirectorySymlink(SymlinkBehavior.COPY, REPORT_ERROR);
+  }
+
+  public void testRecursiveTraversalForDirectorySymlinkFollowCross() throws Exception {
+    assertRecursiveTraversalForDirectorySymlink(SymlinkBehavior.DEREFERENCE, CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectorySymlinkFollowDontCross() throws Exception {
+    assertRecursiveTraversalForDirectorySymlink(SymlinkBehavior.DEREFERENCE, DONT_CROSS);
+  }
+
+  public void testRecursiveTraversalForDirectorySymlinkFollowReportError() throws Exception {
+    assertRecursiveTraversalForDirectorySymlink(SymlinkBehavior.DEREFERENCE, REPORT_ERROR);
+  }
+
+  private void assertRecursiveTraversalForPackage(
+      SymlinkBehavior symlinks, PackageBoundaryMode pkgBoundaryMode) throws Exception {
+    Artifact buildFile = createSourceArtifact("foo/BUILD");
+    Artifact subpkgBuildFile = createSourceArtifact("foo/subpkg/BUILD");
+    Artifact subpkgSymlink = getSourceArtifact("foo/subpkg_sym");
+
+    RootedPath fileA = createFile(siblingOf(buildFile, "file.a"), "blah");
+    RootedPath fileAsym = siblingOf(buildFile, "subdir/file.a.sym");
+    RootedPath fileB = createFile(siblingOf(subpkgBuildFile, "file.b"), "blah");
+
+    scratch.dir(fileAsym.asPath().getParentDirectory().getPathString());
+    fileAsym.asPath().createSymbolicLink(new PathFragment("../file.a"));
+    subpkgSymlink.getPath().createSymbolicLink(new PathFragment("subpkg"));
+
+    FilesetOutputSymlink outBuild = symlink("output-name/BUILD", buildFile);
+    FilesetOutputSymlink outA = symlink("output-name/file.a", fileA);
+    FilesetOutputSymlink outAsym = null;
+    FilesetOutputSymlink outSubpkgBuild = symlink("output-name/subpkg/BUILD", subpkgBuildFile);
+    FilesetOutputSymlink outSubpkgB = symlink("output-name/subpkg/file.b", fileB);
+    FilesetOutputSymlink outSubpkgSymBuild;
+    switch (symlinks) {
+      case COPY:
+        outAsym = symlink("output-name/subdir/file.a.sym", "../file.a");
+        outSubpkgSymBuild = symlink("output-name/subpkg_sym", "subpkg");
+        break;
+      case DEREFERENCE:
+        outAsym = symlink("output-name/subdir/file.a.sym", fileA);
+        outSubpkgSymBuild = symlink("output-name/subpkg_sym", getSourceArtifact("foo/subpkg"));
+        break;
+      default:
+        throw new IllegalStateException(symlinks.toString());
+    }
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.recursiveTraversalOfPackage(
+            /*ownerLabel=*/ label("//foo"),
+            /*directoryToTraverse=*/ buildFile,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*excludes=*/ null,
+            /*symlinkBehaviorMode=*/ symlinks,
+            /*pkgBoundaryMode=*/ pkgBoundaryMode);
+    switch (pkgBoundaryMode) {
+      case CROSS:
+        assertSymlinksInOrder(
+            params, outBuild, outA, outSubpkgSymBuild, outAsym, outSubpkgBuild, outSubpkgB);
+        break;
+      case DONT_CROSS:
+        assertSymlinksInOrder(params, outBuild, outA, outAsym);
+        break;
+      case REPORT_ERROR:
+        SkyKey key = FilesetEntryValue.key(params);
+        EvaluationResult<SkyValue> result = eval(key);
+        assertThat(result.hasError()).isTrue();
+        assertThat(result.getError(key).getException().getMessage())
+            .contains("'foo' crosses package boundary into package rooted at foo/subpkg");
+        break;
+      default:
+        throw new IllegalStateException(pkgBoundaryMode.toString());
+    }
+  }
+
+  public void testRecursiveTraversalForPackageNoFollowCross() throws Exception {
+    assertRecursiveTraversalForPackage(SymlinkBehavior.COPY, CROSS);
+  }
+
+  public void testRecursiveTraversalForPackageNoFollowDontCross() throws Exception {
+    assertRecursiveTraversalForPackage(SymlinkBehavior.COPY, DONT_CROSS);
+  }
+
+  public void testRecursiveTraversalForPackageNoFollowReportError() throws Exception {
+    assertRecursiveTraversalForPackage(SymlinkBehavior.COPY, REPORT_ERROR);
+  }
+
+  public void testRecursiveTraversalForPackageFollowCross() throws Exception {
+    assertRecursiveTraversalForPackage(SymlinkBehavior.DEREFERENCE, CROSS);
+  }
+
+  public void testRecursiveTraversalForPackageFollowDontCross() throws Exception {
+    assertRecursiveTraversalForPackage(SymlinkBehavior.DEREFERENCE, DONT_CROSS);
+  }
+
+  public void testRecursiveTraversalForPackageFollowReportError() throws Exception {
+    assertRecursiveTraversalForPackage(SymlinkBehavior.DEREFERENCE, REPORT_ERROR);
+  }
+
+  public void testNestedFileFilesetTraversal() throws Exception {
+    Artifact path = getSourceArtifact("foo/bar.file");
+    createFile(path, "blah");
+    FilesetTraversalParams inner =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*fileToTraverse=*/ path,
+            /*destPath=*/ new PathFragment("inner-out"),
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    FilesetTraversalParams outer =
+        FilesetTraversalParamsFactory.nestedTraversal(
+            /*ownerLabel=*/ label("//foo:bar"),
+            /*nested=*/ inner,
+            /*destDir=*/ new PathFragment("outer-out"),
+            /*excludes=*/ null);
+    assertSymlinksInOrder(outer, symlink("outer-out/inner-out", rootedPath(path)));
+  }
+
+  private void assertNestedRecursiveFilesetTraversal(boolean useInnerDir) throws Exception {
+    Artifact dir = getSourceArtifact("foo/dir");
+    RootedPath fileA = createFile(childOf(dir, "file.a"), "hello");
+    RootedPath fileB = createFile(childOf(dir, "file.b"), "hello");
+    RootedPath fileC = createFile(childOf(dir, "sub/file.c"), "world");
+
+    FilesetTraversalParams inner =
+        FilesetTraversalParamsFactory.recursiveTraversalOfDirectory(
+            /*ownerLabel=*/ label("//foo"),
+            /*directoryToTraverse=*/ dir,
+            /*destPath=*/ new PathFragment(useInnerDir ? "inner-dir" : ""),
+            /*excludes=*/ null,
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    FilesetTraversalParams outer =
+        FilesetTraversalParamsFactory.nestedTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*nested=*/ inner,
+            /*destDir=*/ new PathFragment("outer-dir"),
+            ImmutableSet.<String>of("file.a", "sub/file.c"));
+
+    if (useInnerDir) {
+      assertSymlinksInOrder(
+          outer,
+          // no file is excluded, since no files from "inner" are top-level in the outer Fileset
+          symlink("outer-dir/inner-dir/file.a", fileA),
+          symlink("outer-dir/inner-dir/file.b", fileB),
+          symlink("outer-dir/inner-dir/sub/file.c", fileC)); // only top-level files are excluded
+    } else {
+      assertSymlinksInOrder(
+          outer,
+          // file.a can be excluded because it's top-level (there's no output directory for "inner")
+          symlink("outer-dir/file.b", fileB),
+          symlink("outer-dir/sub/file.c", fileC)); // only top-level files could be excluded
+    }
+  }
+
+  public void testNestedRecursiveFilesetTraversalWithInnerDestDir() throws Exception {
+    assertNestedRecursiveFilesetTraversal(true);
+  }
+
+  public void testNestedRecursiveFilesetTraversalWithoutInnerDestDir() throws Exception {
+    assertNestedRecursiveFilesetTraversal(false);
+  }
+
+  public void testFileTraversalForDanglingSymlink() throws Exception {
+    Artifact linkName = getSourceArtifact("foo/dangling.sym");
+    RootedPath linkTarget = createFile(siblingOf(linkName, "target.file"), "blah");
+    linkName.getPath().createSymbolicLink(new PathFragment("target.file"));
+    linkTarget.asPath().delete();
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*fileToTraverse=*/ linkName,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    assertSymlinksInOrder(params); // expect empty results
+  }
+
+  public void testFileTraversalForNonExistentFile() throws Exception {
+    Artifact path = getSourceArtifact("foo/non-existent");
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//foo"),
+            /*fileToTraverse=*/ path,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    assertSymlinksInOrder(params); // expect empty results
+  }
+
+  public void testRecursiveTraversalForDanglingSymlink() throws Exception {
+    Artifact linkName = getSourceArtifact("foo/dangling.sym");
+    RootedPath linkTarget = createFile(siblingOf(linkName, "target.file"), "blah");
+    linkName.getPath().createSymbolicLink(new PathFragment("target.file"));
+    linkTarget.asPath().delete();
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.recursiveTraversalOfDirectory(
+            /*ownerLabel=*/ label("//foo"),
+            /*directoryToTraverse=*/ linkName,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*excludes=*/ null,
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    assertSymlinksInOrder(params); // expect empty results
+  }
+
+  public void testRecursiveTraversalForNonExistentFile() throws Exception {
+    Artifact path = getSourceArtifact("foo/non-existent");
+
+    FilesetTraversalParams params =
+        FilesetTraversalParamsFactory.recursiveTraversalOfDirectory(
+            /*ownerLabel=*/ label("//foo"),
+            /*directoryToTraverse=*/ path,
+            /*destPath=*/ new PathFragment("output-name"),
+            /*excludes=*/ null,
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+    assertSymlinksInOrder(params); // expect empty results
+  }
+
+  /**
+   * Tests that the fingerprint is a function of all arguments of the factory method.
+   *
+   * <p>Implementations must provide:
+   * <ul>
+   * <li>two different values (a domain) for each argument of the factory method and whether or not
+   * it is expected to influence the fingerprint
+   * <li>a way to instantiate {@link FilesetTraversalParams} with a given set of arguments from the
+   * specified domains
+   * </ul>
+   *
+   * <p>The tests will instantiate pairs of {@link FilesetTraversalParams} objects with only a given
+   * attribute differing, and observe whether the fingerprints differ (if they are expected to) or
+   * are the same (otherwise).
+   */
+  private abstract static class FingerprintTester {
+    private final Map<String, Domain> domains;
+
+    FingerprintTester(Map<String, Domain> domains) {
+      this.domains = domains;
+    }
+
+    abstract FilesetTraversalParams create(Map<String, ?> kwArgs) throws Exception;
+
+    private Map<String, ?> getDefaultArgs() {
+      return getKwArgs(null);
+    }
+
+    private Map<String, ?> getKwArgs(@Nullable String useAlternateFor) {
+      Map<String, Object> values = new HashMap<>();
+      for (Map.Entry<String, Domain> d : domains.entrySet()) {
+        values.put(
+            d.getKey(),
+            d.getKey().equals(useAlternateFor) ? d.getValue().valueA : d.getValue().valueB);
+      }
+      return values;
+    }
+
+    public void doTest() throws Exception {
+      Fingerprint fp = new Fingerprint();
+
+      create(getDefaultArgs()).fingerprint(fp);
+      String primary = fp.hexDigestAndReset();
+
+      for (String argName : domains.keySet()) {
+        create(getKwArgs(argName)).fingerprint(fp);
+        String secondary = fp.hexDigestAndReset();
+
+        if (domains.get(argName).includedInFingerprint) {
+          assertWithMessage(
+                  "Argument '"
+                      + argName
+                      + "' was expected to be included in the"
+                      + " fingerprint, but wasn't")
+              .that(primary)
+              .isNotEqualTo(secondary);
+        } else {
+          assertWithMessage(
+                  "Argument '"
+                      + argName
+                      + "' was expected not to be included in the"
+                      + " fingerprint, but was")
+              .that(primary)
+              .isEqualTo(secondary);
+        }
+      }
+    }
+  }
+
+  private static final class Domain {
+    boolean includedInFingerprint;
+    Object valueA;
+    Object valueB;
+
+    Domain(boolean includedInFingerprint, Object valueA, Object valueB) {
+      this.includedInFingerprint = includedInFingerprint;
+      this.valueA = valueA;
+      this.valueB = valueB;
+    }
+  }
+
+  private static Domain partOfFingerprint(Object valueA, Object valueB) {
+    return new Domain(true, valueA, valueB);
+  }
+
+  private static Domain notPartOfFingerprint(Object valueA, Object valueB) {
+    return new Domain(false, valueA, valueB);
+  }
+
+  public void testFingerprintOfFileTraversal() throws Exception {
+    new FingerprintTester(
+        ImmutableMap.<String, Domain>of(
+            "ownerLabel", notPartOfFingerprint("//foo", "//bar"),
+            "fileToTraverse", partOfFingerprint("foo/file.a", "bar/file.b"),
+            "destPath", partOfFingerprint("out1", "out2"),
+            "symlinkBehaviorMode",
+                partOfFingerprint(SymlinkBehavior.COPY, SymlinkBehavior.DEREFERENCE),
+            "pkgBoundaryMode", partOfFingerprint(CROSS, DONT_CROSS))) {
+      @Override
+      FilesetTraversalParams create(Map<String, ?> kwArgs) throws Exception {
+        return FilesetTraversalParamsFactory.fileTraversal(
+            label((String) kwArgs.get("ownerLabel")),
+            getSourceArtifact((String) kwArgs.get("fileToTraverse")),
+            new PathFragment((String) kwArgs.get("destPath")),
+            ((SymlinkBehavior) kwArgs.get("symlinkBehaviorMode")),
+            (PackageBoundaryMode) kwArgs.get("pkgBoundaryMode"));
+      }
+    }.doTest();
+  }
+
+  public void testFingerprintOfDirectoryTraversal() throws Exception {
+    new FingerprintTester(
+        ImmutableMap.<String, Domain>builder()
+            .put("ownerLabel", notPartOfFingerprint("//foo", "//bar"))
+            .put("directoryToTraverse", partOfFingerprint("foo/dir_a", "bar/dir_b"))
+            .put("destPath", partOfFingerprint("out1", "out2"))
+            .put(
+                "excludes",
+                partOfFingerprint(ImmutableSet.<String>of(), ImmutableSet.<String>of("blah")))
+            .put(
+                "symlinkBehaviorMode",
+                partOfFingerprint(SymlinkBehavior.COPY, SymlinkBehavior.DEREFERENCE))
+            .put("pkgBoundaryMode", partOfFingerprint(CROSS, DONT_CROSS))
+            .build()) {
+      @SuppressWarnings("unchecked")
+      @Override
+      FilesetTraversalParams create(Map<String, ?> kwArgs) throws Exception {
+        return FilesetTraversalParamsFactory.recursiveTraversalOfDirectory(
+            label((String) kwArgs.get("ownerLabel")),
+            getSourceArtifact((String) kwArgs.get("directoryToTraverse")),
+            new PathFragment((String) kwArgs.get("destPath")),
+            (Set<String>) kwArgs.get("excludes"),
+            ((SymlinkBehavior) kwArgs.get("symlinkBehaviorMode")),
+            (PackageBoundaryMode) kwArgs.get("pkgBoundaryMode"));
+      }
+    }.doTest();
+  }
+
+  public void testFingerprintOfPackageTraversal() throws Exception {
+    new FingerprintTester(
+        ImmutableMap.<String, Domain>builder()
+            .put("ownerLabel", notPartOfFingerprint("//foo", "//bar"))
+            .put("buildFile", partOfFingerprint("foo/BUILD", "bar/BUILD"))
+            .put("destPath", partOfFingerprint("out1", "out2"))
+            .put(
+                "excludes",
+                partOfFingerprint(ImmutableSet.<String>of(), ImmutableSet.<String>of("blah")))
+            .put(
+                "symlinkBehaviorMode",
+                partOfFingerprint(SymlinkBehavior.COPY, SymlinkBehavior.DEREFERENCE))
+            .put("pkgBoundaryMode", partOfFingerprint(CROSS, DONT_CROSS))
+            .build()) {
+      @SuppressWarnings("unchecked")
+      @Override
+      FilesetTraversalParams create(Map<String, ?> kwArgs) throws Exception {
+        return FilesetTraversalParamsFactory.recursiveTraversalOfPackage(
+            label((String) kwArgs.get("ownerLabel")),
+            getSourceArtifact((String) kwArgs.get("buildFile")),
+            new PathFragment((String) kwArgs.get("destPath")),
+            (Set<String>) kwArgs.get("excludes"),
+            ((SymlinkBehavior) kwArgs.get("symlinkBehaviorMode")),
+            (PackageBoundaryMode) kwArgs.get("pkgBoundaryMode"));
+      }
+    }.doTest();
+  }
+
+  public void testFingerprintOfNestedTraversal() throws Exception {
+    FilesetTraversalParams n1 =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//blah"),
+            /*fileToTraverse=*/ getSourceArtifact("blah/file.a"),
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+
+    FilesetTraversalParams n2 =
+        FilesetTraversalParamsFactory.fileTraversal(
+            /*ownerLabel=*/ label("//blah"),
+            /*fileToTraverse=*/ getSourceArtifact("meow/file.b"),
+            /*destPath=*/ new PathFragment("output-name"),
+            /*symlinkBehaviorMode=*/ SymlinkBehavior.COPY,
+            /*pkgBoundaryMode=*/ DONT_CROSS);
+
+    new FingerprintTester(
+        ImmutableMap.<String, Domain>of(
+            "ownerLabel", notPartOfFingerprint("//foo", "//bar"),
+            "nested", partOfFingerprint(n1, n2),
+            "destDir", partOfFingerprint("out1", "out2"),
+            "excludes",
+                partOfFingerprint(ImmutableSet.<String>of(), ImmutableSet.<String>of("x")))) {
+      @SuppressWarnings("unchecked")
+      @Override
+      FilesetTraversalParams create(Map<String, ?> kwArgs) throws Exception {
+        return FilesetTraversalParamsFactory.nestedTraversal(
+            label((String) kwArgs.get("ownerLabel")),
+            (FilesetTraversalParams) kwArgs.get("nested"),
+            new PathFragment((String) kwArgs.get("destDir")),
+            (Set<String>) kwArgs.get("excludes"));
+      }
+    }.doTest();
+  }
+}
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
new file mode 100644
index 0000000000..d917c8eef5
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -0,0 +1,526 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+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.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.Root;
+import com.google.devtools.build.lib.actions.util.TestAction;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.DirtinessCheckerUtils.BasicFilesystemDirtinessChecker;
+import com.google.devtools.build.lib.util.BlazeClock;
+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;
+import com.google.devtools.build.lib.vfs.FileStatusWithDigest;
+import com.google.devtools.build.lib.vfs.FileStatusWithDigestAdapter;
+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.RootedPath;
+import com.google.devtools.build.lib.vfs.Symlinks;
+import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
+import com.google.devtools.build.skyframe.Differencer.Diff;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
+import com.google.devtools.build.skyframe.MemoizingEvaluator;
+import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import junit.framework.TestCase;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+
+import javax.annotation.Nullable;
+
+/**
+ * Tests for {@link FilesystemValueChecker}.
+ */
+public class FilesystemValueCheckerTest extends TestCase {
+
+  private RecordingDifferencer differencer;
+  private MemoizingEvaluator evaluator;
+  private SequentialBuildDriver driver;
+  private MockFileSystem fs;
+  private Path pkgRoot;
+  private TimestampGranularityMonitor tsgm;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+
+    ImmutableMap.Builder<SkyFunctionName, SkyFunction> skyFunctions = ImmutableMap.builder();
+
+    fs = new MockFileSystem();
+    pkgRoot = fs.getPath("/testroot");
+
+    tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
+    AtomicReference<PathPackageLocator> pkgLocator =
+        new AtomicReference<>(new PathPackageLocator());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(
+        SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, new FileSymlinkCycleUniquenessFunction());
+    skyFunctions.put(
+        SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS,
+        new FileSymlinkInfiniteExpansionUniquenessFunction());
+    differencer = new RecordingDifferencer();
+    evaluator = new InMemoryMemoizingEvaluator(skyFunctions.build(), differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+  }
+
+  @Override
+  protected void tearDown() throws Exception {
+    super.tearDown();
+  }
+
+  public void testEmpty() throws Exception {
+    FilesystemValueChecker checker = new FilesystemValueChecker(evaluator, tsgm, null);
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+  }
+
+  public void testSimple() throws Exception {
+    FilesystemValueChecker checker = new FilesystemValueChecker(evaluator, tsgm, null);
+
+    Path path = fs.getPath("/foo");
+    FileSystemUtils.createEmptyFile(path);
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+
+    SkyKey skyKey =
+        FileStateValue.key(RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("foo")));
+    EvaluationResult<SkyValue> result =
+        driver.evaluate(
+            ImmutableList.of(skyKey),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertFalse(result.hasError());
+
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+
+    FileSystemUtils.writeContentAsLatin1(path, "hello");
+    assertDiffWithNewValues(getDirtyFilesystemKeys(checker), skyKey);
+
+    // The dirty bits are not reset until the FileValues are actually revalidated.
+    assertDiffWithNewValues(getDirtyFilesystemKeys(checker), skyKey);
+
+    differencer.invalidate(ImmutableList.of(skyKey));
+    result =
+        driver.evaluate(
+            ImmutableList.of(skyKey),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertFalse(result.hasError());
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+  }
+
+  /**
+   * Tests that an already-invalidated value can still be marked changed: symlink points at sym1.
+   * Invalidate symlink by changing sym1 from pointing at path to point to sym2. This only dirties
+   * (rather than changes) symlink because sym2 still points at path, so all symlink stats remain
+   * the same. Then do a null build, change sym1 back to point at path, and change symlink to not be
+   * a symlink anymore. The fact that it is not a symlink should be detected.
+   */
+  public void testDirtySymlink() throws Exception {
+    FilesystemValueChecker checker = new FilesystemValueChecker(evaluator, tsgm, null);
+
+    Path path = fs.getPath("/foo");
+    FileSystemUtils.writeContentAsLatin1(path, "foo contents");
+    // We need the intermediate sym1 and sym2 so that we can dirty a child of symlink without
+    // actually changing the FileValue calculated for symlink (if we changed the contents of foo,
+    // the the FileValue created for symlink would notice, since it stats foo).
+    Path sym1 = fs.getPath("/sym1");
+    Path sym2 = fs.getPath("/sym2");
+    Path symlink = fs.getPath("/bar");
+    FileSystemUtils.ensureSymbolicLink(symlink, sym1);
+    FileSystemUtils.ensureSymbolicLink(sym1, path);
+    FileSystemUtils.ensureSymbolicLink(sym2, path);
+    SkyKey fooKey =
+        FileValue.key(RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("foo")));
+    RootedPath symlinkRootedPath =
+        RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("bar"));
+    SkyKey symlinkKey = FileValue.key(symlinkRootedPath);
+    SkyKey symlinkFileStateKey = FileStateValue.key(symlinkRootedPath);
+    RootedPath sym1RootedPath =
+        RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("sym1"));
+    SkyKey sym1FileStateKey = FileStateValue.key(sym1RootedPath);
+    Iterable<SkyKey> allKeys = ImmutableList.of(symlinkKey, fooKey);
+
+    // First build -- prime the graph.
+    EvaluationResult<FileValue> result =
+        driver.evaluate(
+            allKeys, false, SkyframeExecutor.DEFAULT_THREAD_COUNT, NullEventHandler.INSTANCE);
+    assertFalse(result.hasError());
+    FileValue symlinkValue = result.get(symlinkKey);
+    FileValue fooValue = result.get(fooKey);
+    assertTrue(symlinkValue.toString(), symlinkValue.isSymlink());
+    // Digest is not always available, so use size as a proxy for contents.
+    assertEquals(fooValue.getSize(), symlinkValue.getSize());
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+
+    // Before second build, move sym1 to point to sym2.
+    assertTrue(sym1.delete());
+    FileSystemUtils.ensureSymbolicLink(sym1, sym2);
+    assertDiffWithNewValues(getDirtyFilesystemKeys(checker), sym1FileStateKey);
+
+    differencer.invalidate(ImmutableList.of(sym1FileStateKey));
+    result =
+        driver.evaluate(
+            ImmutableList.<SkyKey>of(),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertFalse(result.hasError());
+    assertDiffWithNewValues(getDirtyFilesystemKeys(checker), sym1FileStateKey);
+
+    // Before third build, move sym1 back to original (so change pruning will prevent signaling of
+    // its parents, but change symlink for real.
+    assertTrue(sym1.delete());
+    FileSystemUtils.ensureSymbolicLink(sym1, path);
+    assertTrue(symlink.delete());
+    FileSystemUtils.writeContentAsLatin1(symlink, "new symlink contents");
+    assertDiffWithNewValues(getDirtyFilesystemKeys(checker), symlinkFileStateKey);
+    differencer.invalidate(ImmutableList.of(symlinkFileStateKey));
+    result =
+        driver.evaluate(
+            allKeys, false, SkyframeExecutor.DEFAULT_THREAD_COUNT, NullEventHandler.INSTANCE);
+    assertFalse(result.hasError());
+    symlinkValue = result.get(symlinkKey);
+    assertFalse(symlinkValue.toString(), symlinkValue.isSymlink());
+    assertEquals(fooValue, result.get(fooKey));
+    assertThat(symlinkValue.getSize()).isNotEqualTo(fooValue.getSize());
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+  }
+
+  public void testExplicitFiles() throws Exception {
+    FilesystemValueChecker checker = new FilesystemValueChecker(evaluator, tsgm, null);
+
+    Path path1 = fs.getPath("/foo1");
+    Path path2 = fs.getPath("/foo2");
+    FileSystemUtils.createEmptyFile(path1);
+    FileSystemUtils.createEmptyFile(path2);
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+
+    SkyKey key1 =
+        FileStateValue.key(
+            RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("foo1")));
+    SkyKey key2 =
+        FileStateValue.key(
+            RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("foo2")));
+    Iterable<SkyKey> skyKeys = ImmutableList.of(key1, key2);
+    EvaluationResult<SkyValue> result =
+        driver.evaluate(
+            skyKeys, false, SkyframeExecutor.DEFAULT_THREAD_COUNT, NullEventHandler.INSTANCE);
+    assertFalse(result.hasError());
+
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+
+    FileSystemUtils.writeContentAsLatin1(path1, "hello1");
+    FileSystemUtils.writeContentAsLatin1(path1, "hello2");
+    path1.setLastModifiedTime(27);
+    path2.setLastModifiedTime(42);
+    assertDiffWithNewValues(getDirtyFilesystemKeys(checker), key1, key2);
+
+    differencer.invalidate(skyKeys);
+    result =
+        driver.evaluate(
+            skyKeys, false, SkyframeExecutor.DEFAULT_THREAD_COUNT, NullEventHandler.INSTANCE);
+    assertFalse(result.hasError());
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+  }
+
+  public void testFileWithIOExceptionNotConsideredDirty() throws Exception {
+    Path path = fs.getPath("/testroot/foo");
+    path.getParentDirectory().createDirectory();
+    path.createSymbolicLink(new PathFragment("bar"));
+
+    fs.readlinkThrowsIoException = true;
+    SkyKey fileKey = FileStateValue.key(RootedPath.toRootedPath(pkgRoot, new PathFragment("foo")));
+    EvaluationResult<SkyValue> result =
+        driver.evaluate(
+            ImmutableList.of(fileKey),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertTrue(result.hasError());
+
+    fs.readlinkThrowsIoException = false;
+    FilesystemValueChecker checker = new FilesystemValueChecker(evaluator, tsgm, null);
+    Diff diff = getDirtyFilesystemKeys(checker);
+    assertThat(diff.changedKeysWithoutNewValues()).isEmpty();
+    assertThat(diff.changedKeysWithNewValues()).isEmpty();
+  }
+
+  public void testFilesInCycleNotConsideredDirty() throws Exception {
+    Path path1 = pkgRoot.getRelative("foo1");
+    Path path2 = pkgRoot.getRelative("foo2");
+    Path path3 = pkgRoot.getRelative("foo3");
+    FileSystemUtils.ensureSymbolicLink(path1, path2);
+    FileSystemUtils.ensureSymbolicLink(path2, path3);
+    FileSystemUtils.ensureSymbolicLink(path3, path1);
+    SkyKey fileKey1 = FileValue.key(RootedPath.toRootedPath(pkgRoot, path1));
+
+    EvaluationResult<SkyValue> result =
+        driver.evaluate(
+            ImmutableList.of(fileKey1),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertTrue(result.hasError());
+
+    FilesystemValueChecker checker = new FilesystemValueChecker(evaluator, tsgm, null);
+    Diff diff = getDirtyFilesystemKeys(checker);
+    assertThat(diff.changedKeysWithoutNewValues()).isEmpty();
+    assertThat(diff.changedKeysWithNewValues()).isEmpty();
+  }
+
+  public void checkDirtyActions(BatchStat batchStatter, boolean forceDigests) throws Exception {
+    Artifact out1 = createDerivedArtifact("fiz");
+    Artifact out2 = createDerivedArtifact("pop");
+
+    FileSystemUtils.writeContentAsLatin1(out1.getPath(), "hello");
+    FileSystemUtils.writeContentAsLatin1(out2.getPath(), "fizzlepop");
+
+    Action action1 =
+        new TestAction(
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.<Artifact>of(out1));
+    Action action2 =
+        new TestAction(
+            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.<Artifact>of(out2));
+    differencer.inject(
+        ImmutableMap.<SkyKey, SkyValue>of(
+            ActionExecutionValue.key(action1), actionValue(action1, forceDigests),
+            ActionExecutionValue.key(action2), actionValue(action2, forceDigests)));
+    assertFalse(
+        driver
+            .evaluate(ImmutableList.<SkyKey>of(), false, 1, NullEventHandler.INSTANCE)
+            .hasError());
+    assertThat(new FilesystemValueChecker(evaluator, tsgm, null).getDirtyActionValues(batchStatter))
+        .isEmpty();
+
+    FileSystemUtils.writeContentAsLatin1(out1.getPath(), "goodbye");
+    assertEquals(
+        ActionExecutionValue.key(action1),
+        Iterables.getOnlyElement(
+            new FilesystemValueChecker(evaluator, tsgm, null).getDirtyActionValues(batchStatter)));
+  }
+
+  private Artifact createDerivedArtifact(String relPath) throws IOException {
+    Path outputPath = fs.getPath("/bin");
+    outputPath.createDirectory();
+    return new Artifact(
+        outputPath.getRelative(relPath), Root.asDerivedRoot(fs.getPath("/"), outputPath));
+  }
+
+  public void testDirtyActions() throws Exception {
+    checkDirtyActions(null, false);
+  }
+
+  public void testDirtyActionsBatchStat() throws Exception {
+    checkDirtyActions(
+        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;
+          }
+        },
+        false);
+  }
+
+  public void testDirtyActionsBatchStatWithDigest() throws Exception {
+    checkDirtyActions(
+        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) {
+              final Path path = fs.getRootDirectory().getRelative(pathFrag);
+              stats.add(statWithDigest(path, path.statIfFound(Symlinks.NOFOLLOW)));
+            }
+            return stats;
+          }
+        },
+        true);
+  }
+
+  public void testDirtyActionsBatchStatFallback() throws Exception {
+    checkDirtyActions(
+        new BatchStat() {
+          @Override
+          public List<FileStatusWithDigest> batchStat(
+              boolean useDigest, boolean includeLinks, Iterable<PathFragment> paths)
+              throws IOException {
+            throw new IOException("try again");
+          }
+        },
+        false);
+  }
+
+  private ActionExecutionValue actionValue(Action action, boolean forceDigest) {
+    Map<Artifact, FileValue> artifactData = new HashMap<>();
+    for (Artifact output : action.getOutputs()) {
+      try {
+        Path path = output.getPath();
+        FileStatusWithDigest stat =
+            forceDigest ? statWithDigest(path, path.statIfFound(Symlinks.NOFOLLOW)) : null;
+        artifactData.put(output, ActionMetadataHandler.fileValueFromArtifact(output, stat, tsgm));
+      } catch (IOException e) {
+        throw new IllegalStateException(e);
+      }
+    }
+    return new ActionExecutionValue(artifactData, ImmutableMap.<Artifact, FileArtifactValue>of());
+  }
+
+  public void testPropagatesRuntimeExceptions() throws Exception {
+    Collection<SkyKey> values =
+        ImmutableList.of(FileValue.key(RootedPath.toRootedPath(pkgRoot, new PathFragment("foo"))));
+    driver.evaluate(
+        values, false, SkyframeExecutor.DEFAULT_THREAD_COUNT, NullEventHandler.INSTANCE);
+    FilesystemValueChecker checker = new FilesystemValueChecker(evaluator, tsgm, null);
+
+    assertEmptyDiff(getDirtyFilesystemKeys(checker));
+
+    fs.statThrowsRuntimeException = true;
+    try {
+      getDirtyFilesystemKeys(checker);
+      fail();
+    } catch (RuntimeException e) {
+      assertThat(e).hasMessage("bork");
+    }
+  }
+
+  private static void assertEmptyDiff(Diff diff) {
+    assertDiffWithNewValues(diff);
+  }
+
+  private static void assertDiffWithNewValues(Diff diff, SkyKey... keysWithNewValues) {
+    assertThat(diff.changedKeysWithoutNewValues()).isEmpty();
+    assertThat(diff.changedKeysWithNewValues().keySet())
+        .containsExactlyElementsIn(Arrays.asList(keysWithNewValues));
+  }
+
+  private class MockFileSystem extends InMemoryFileSystem {
+
+    boolean statThrowsRuntimeException;
+    boolean readlinkThrowsIoException;
+
+    MockFileSystem() {
+      super();
+    }
+
+    @Override
+    public FileStatus stat(Path path, boolean followSymlinks) throws IOException {
+      if (statThrowsRuntimeException) {
+        throw new RuntimeException("bork");
+      }
+      return super.stat(path, followSymlinks);
+    }
+
+    @Override
+    protected PathFragment readSymbolicLink(Path path) throws IOException {
+      if (readlinkThrowsIoException) {
+        throw new IOException("readlink failed");
+      }
+      return super.readSymbolicLink(path);
+    }
+  }
+
+  private static FileStatusWithDigest statWithDigest(final Path path, final FileStatus stat) {
+    return new FileStatusWithDigest() {
+      @Nullable
+      @Override
+      public byte[] getDigest() throws IOException {
+        return path.getMD5Digest();
+      }
+
+      @Override
+      public boolean isFile() {
+        return stat.isFile();
+      }
+
+      @Override
+      public boolean isSpecialFile() {
+        return stat.isSpecialFile();
+      }
+
+      @Override
+      public boolean isDirectory() {
+        return stat.isDirectory();
+      }
+
+      @Override
+      public boolean isSymbolicLink() {
+        return stat.isSymbolicLink();
+      }
+
+      @Override
+      public long getSize() throws IOException {
+        return stat.getSize();
+      }
+
+      @Override
+      public long getLastModifiedTime() throws IOException {
+        return stat.getLastModifiedTime();
+      }
+
+      @Override
+      public long getLastChangeTime() throws IOException {
+        return stat.getLastChangeTime();
+      }
+
+      @Override
+      public long getNodeId() throws IOException {
+        return stat.getNodeId();
+      }
+    };
+  }
+
+  private static Diff getDirtyFilesystemKeys(FilesystemValueChecker checker)
+      throws InterruptedException {
+    return checker.getDirtyKeys(new BasicFilesystemDirtinessChecker());
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
new file mode 100644
index 0000000000..d70b98ae9e
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
@@ -0,0 +1,666 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Functions;
+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.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.testing.EqualsTester;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.GlobValue.InvalidGlobPatternException;
+import com.google.devtools.build.lib.testutil.ManualClock;
+import com.google.devtools.build.lib.testutil.MoreAsserts;
+import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.Dirent;
+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.RootedPath;
+import com.google.devtools.build.lib.vfs.UnixGlob;
+import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
+import com.google.devtools.build.skyframe.ErrorInfo;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
+import com.google.devtools.build.skyframe.MemoizingEvaluator;
+import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import junit.framework.TestCase;
+
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+
+import javax.annotation.Nullable;
+
+/**
+ * Tests for {@link GlobFunction}.
+ */
+public abstract class GlobFunctionTest extends TestCase {
+  public static class GlobFunctionAlwaysUseDirListingTest extends GlobFunctionTest {
+    @Override
+    protected boolean alwaysUseDirListing() {
+      return true;
+    }
+  }
+
+  public static class RegularGlobFunctionTest extends GlobFunctionTest {
+    @Override
+    protected boolean alwaysUseDirListing() {
+      return false;
+    }
+  }
+
+  private CustomInMemoryFs fs;
+  private MemoizingEvaluator evaluator;
+  private SequentialBuildDriver driver;
+  private RecordingDifferencer differencer;
+  private Path root;
+  private Path pkgPath;
+  private AtomicReference<PathPackageLocator> pkgLocator;
+  private TimestampGranularityMonitor tsgm;
+
+  private static final PackageIdentifier PKG_PATH_ID = PackageIdentifier.createInDefaultRepo("pkg");
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    fs = new CustomInMemoryFs(new ManualClock());
+    root = fs.getRootDirectory().getRelative("root/workspace");
+    pkgPath = root.getRelative(PKG_PATH_ID.getPackageFragment());
+
+    pkgLocator = new AtomicReference<>(new PathPackageLocator(root));
+    tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
+
+    differencer = new RecordingDifferencer();
+    evaluator = new InMemoryMemoizingEvaluator(createFunctionMap(), differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+
+    createTestFiles();
+  }
+
+  private Map<SkyFunctionName, SkyFunction> createFunctionMap() {
+    AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages =
+        new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+
+    Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
+    skyFunctions.put(SkyFunctions.GLOB, new GlobFunction(alwaysUseDirListing()));
+    skyFunctions.put(
+        SkyFunctions.DIRECTORY_LISTING_STATE,
+        new DirectoryListingStateFunction(externalFilesHelper));
+    skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
+    skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));
+    skyFunctions.put(
+        SkyFunctions.FILE_STATE,
+        new FileStateFunction(
+            new TimestampGranularityMonitor(BlazeClock.instance()), externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    return skyFunctions;
+  }
+
+  protected abstract boolean alwaysUseDirListing();
+
+  private void createTestFiles() throws IOException {
+    FileSystemUtils.createDirectoryAndParents(pkgPath);
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("BUILD"));
+    for (String dir :
+        ImmutableList.of(
+            "foo/bar/wiz", "foo/barnacle/wiz", "food/barnacle/wiz", "fool/barnacle/wiz")) {
+      FileSystemUtils.createDirectoryAndParents(pkgPath.getRelative(dir));
+    }
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("foo/bar/wiz/file"));
+
+    // Used for testing the behavior of globbing into nested subpackages.
+    for (String dir : ImmutableList.of("a1/b1/c", "a2/b2/c")) {
+      FileSystemUtils.createDirectoryAndParents(pkgPath.getRelative(dir));
+    }
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("a2/b2/BUILD"));
+  }
+
+  public void testSimple() throws Exception {
+    assertGlobMatches("food", /* => */ "food");
+  }
+
+  public void testStartsWithStar() throws Exception {
+    assertGlobMatches("*oo", /* => */ "foo");
+  }
+
+  public void testStartsWithStarWithMiddleStar() throws Exception {
+    assertGlobMatches("*f*o", /* => */ "foo");
+  }
+
+  public void testSingleMatchEqual() throws Exception {
+    assertGlobsEqual("*oo", "*f*o"); // both produce "foo"
+  }
+
+  public void testEndsWithStar() throws Exception {
+    assertGlobMatches("foo*", /* => */ "foo", "food", "fool");
+  }
+
+  public void testEndsWithStarWithMiddleStar() throws Exception {
+    assertGlobMatches("f*oo*", /* => */ "foo", "food", "fool");
+  }
+
+  public void testMultipleMatchesEqual() throws Exception {
+    assertGlobsEqual("foo*", "f*oo*"); // both produce "foo", "food", "fool"
+  }
+
+  public void testMiddleStar() throws Exception {
+    assertGlobMatches("f*o", /* => */ "foo");
+  }
+
+  public void testTwoMiddleStars() throws Exception {
+    assertGlobMatches("f*o*o", /* => */ "foo");
+  }
+
+  public void testSingleStarPatternWithNamedChild() throws Exception {
+    assertGlobMatches("*/bar", /* => */ "foo/bar");
+  }
+
+  public void testDeepSubpackages() throws Exception {
+    assertGlobMatches("*/*/c", /* => */ "a1/b1/c");
+  }
+
+  public void testSingleStarPatternWithChildGlob() throws Exception {
+    assertGlobMatches(
+        "*/bar*", /* => */ "foo/bar", "foo/barnacle", "food/barnacle", "fool/barnacle");
+  }
+
+  public void testSingleStarAsChildGlob() throws Exception {
+    assertGlobMatches("foo/*/wiz", /* => */ "foo/bar/wiz", "foo/barnacle/wiz");
+  }
+
+  public void testNoAsteriskAndFilesDontExist() throws Exception {
+    // Note un-UNIX like semantics:
+    assertGlobMatches("ceci/n'est/pas/une/globbe" /* => nothing */);
+  }
+
+  public void testSingleAsteriskUnderNonexistentDirectory() throws Exception {
+    // Note un-UNIX like semantics:
+    assertGlobMatches("not-there/*" /* => nothing */);
+  }
+
+  public void testDifferentGlobsSameResultEqual() throws Exception {
+    // Once the globs are run, it doesn't matter what pattern ran; only the output.
+    assertGlobsEqual("not-there/*", "syzygy/*"); // Both produce nothing.
+  }
+
+  public void testGlobUnderFile() throws Exception {
+    assertGlobMatches("foo/bar/wiz/file/*" /* => nothing */);
+  }
+
+  public void testGlobEqualsHashCode() throws Exception {
+    // Each "equality group" forms a set of elements that are all equals() to one another,
+    // and also produce the same hashCode.
+    new EqualsTester()
+        .addEqualityGroup(runGlob(false, "no-such-file")) // Matches nothing.
+        .addEqualityGroup(runGlob(false, "BUILD"), runGlob(true, "BUILD")) // Matches BUILD.
+        .addEqualityGroup(runGlob(false, "**")) // Matches lots of things.
+        .addEqualityGroup(
+            runGlob(false, "f*o/bar*"),
+            runGlob(false, "foo/bar*")) // Matches foo/bar and foo/barnacle.
+        .testEquals();
+  }
+
+  public void testGlobMissingPackage() throws Exception {
+    // This is a malformed value key, because "missing" is not a package. Nevertheless, we have a
+    // sanity check that building the corresponding GlobValue fails loudly. The test depends on
+    // implementation details of ParallelEvaluator and GlobFunction.
+    SkyKey skyKey =
+        GlobValue.key(
+            PackageIdentifier.createInDefaultRepo("missing"),
+            "foo",
+            false,
+            PathFragment.EMPTY_FRAGMENT);
+    try {
+      driver.evaluate(
+          ImmutableList.of(skyKey),
+          false,
+          SkyframeExecutor.DEFAULT_THREAD_COUNT,
+          NullEventHandler.INSTANCE);
+      fail();
+    } catch (RuntimeException e) {
+      assertThat(e.getMessage())
+          .contains("Unrecoverable error while evaluating node '" + skyKey + "'");
+      Throwable cause = e.getCause();
+      assertThat(cause).isInstanceOf(IllegalStateException.class);
+      assertThat(cause.getMessage()).contains("isn't an existing package");
+    }
+  }
+
+  public void testGlobDoesNotCrossPackageBoundary() throws Exception {
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("foo/BUILD"));
+    // "foo/bar" should not be in the results because foo is a separate package.
+    assertGlobMatches("f*/*", /* => */ "food/barnacle", "fool/barnacle");
+  }
+
+  public void testGlobDirectoryMatchDoesNotCrossPackageBoundary() throws Exception {
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("foo/bar/BUILD"));
+    // "foo/bar" should not be in the results because foo/bar is a separate package.
+    assertGlobMatches("foo/*", /* => */ "foo/barnacle");
+  }
+
+  public void testStarStarDoesNotCrossPackageBoundary() throws Exception {
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("foo/bar/BUILD"));
+    // "foo/bar" should not be in the results because foo/bar is a separate package.
+    assertGlobMatches("foo/**", /* => */ "foo", "foo/barnacle", "foo/barnacle/wiz");
+  }
+
+  private void assertGlobMatches(String pattern, String... expecteds) throws Exception {
+    assertGlobMatches(false, pattern, expecteds);
+  }
+
+  private void assertGlobWithoutDirsMatches(String pattern, String... expecteds) throws Exception {
+    assertGlobMatches(true, pattern, expecteds);
+  }
+
+  private void assertGlobMatches(boolean excludeDirs, String pattern, String... expecteds)
+      throws Exception {
+    MoreAsserts.assertSameContents(
+        ImmutableList.copyOf(expecteds),
+        Iterables.transform(
+            runGlob(excludeDirs, pattern).getMatches(), Functions.toStringFunction()));
+  }
+
+  private void assertGlobsEqual(String pattern1, String pattern2) throws Exception {
+    GlobValue value1 = runGlob(false, pattern1);
+    GlobValue value2 = runGlob(false, pattern2);
+    assertEquals(
+        "GlobValues "
+            + value1.getMatches()
+            + " and "
+            + value2.getMatches()
+            + " should be equal. "
+            + "Patterns: "
+            + pattern1
+            + ","
+            + pattern2,
+        value1,
+        value2);
+    // Just to be paranoid:
+    assertEquals(value1, value1);
+    assertEquals(value2, value2);
+  }
+
+  private GlobValue runGlob(boolean excludeDirs, String pattern) throws Exception {
+    SkyKey skyKey = GlobValue.key(PKG_PATH_ID, pattern, excludeDirs, PathFragment.EMPTY_FRAGMENT);
+    EvaluationResult<SkyValue> result =
+        driver.evaluate(
+            ImmutableList.of(skyKey),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    if (result.hasError()) {
+      throw result.getError().getException();
+    }
+    return (GlobValue) result.get(skyKey);
+  }
+
+  public void testGlobWithoutWildcards() throws Exception {
+    String pattern = "foo/bar/wiz/file";
+
+    assertGlobMatches(pattern, "foo/bar/wiz/file");
+    // Ensure that the glob depends on the FileValue and not on the DirectoryListingValue.
+    pkgPath.getRelative("foo/bar/wiz/file").delete();
+    // Nothing has been invalidated yet, so the cached result is returned.
+    assertGlobMatches(pattern, "foo/bar/wiz/file");
+
+    if (alwaysUseDirListing()) {
+      differencer.invalidate(
+          ImmutableList.of(
+              FileStateValue.key(
+                  RootedPath.toRootedPath(root, pkgPath.getRelative("foo/bar/wiz/file")))));
+      // The result should not rely on the FileStateValue, so it's still a cache hit.
+      assertGlobMatches(pattern, "foo/bar/wiz/file");
+
+      differencer.invalidate(
+          ImmutableList.of(
+              DirectoryListingStateValue.key(
+                  RootedPath.toRootedPath(root, pkgPath.getRelative("foo/bar/wiz")))));
+      // This should have invalidated the glob result.
+      assertGlobMatches(pattern /* => nothing */);
+    } else {
+      differencer.invalidate(
+          ImmutableList.of(
+              DirectoryListingStateValue.key(
+                  RootedPath.toRootedPath(root, pkgPath.getRelative("foo/bar/wiz")))));
+      // The result should not rely on the DirectoryListingValue, so it's still a cache hit.
+      assertGlobMatches(pattern, "foo/bar/wiz/file");
+
+      differencer.invalidate(
+          ImmutableList.of(
+              FileStateValue.key(
+                  RootedPath.toRootedPath(root, pkgPath.getRelative("foo/bar/wiz/file")))));
+      // This should have invalidated the glob result.
+      assertGlobMatches(pattern /* => nothing */);
+    }
+  }
+
+  public void testIllegalPatterns() throws Exception {
+    assertIllegalPattern("(illegal) pattern");
+    assertIllegalPattern("[illegal pattern");
+    assertIllegalPattern("}illegal pattern");
+    assertIllegalPattern("foo**bar");
+    assertIllegalPattern("?");
+    assertIllegalPattern("");
+    assertIllegalPattern(".");
+    assertIllegalPattern("/foo");
+    assertIllegalPattern("./foo");
+    assertIllegalPattern("foo/");
+    assertIllegalPattern("foo/./bar");
+    assertIllegalPattern("../foo/bar");
+    assertIllegalPattern("foo//bar");
+  }
+
+  public void testIllegalRecursivePatterns() throws Exception {
+    for (String prefix : Lists.newArrayList("", "*/", "**/", "ba/")) {
+      String suffix = ("/" + prefix).substring(0, prefix.length());
+      for (String pattern : Lists.newArrayList("**fo", "fo**", "**fo**", "fo**fo", "fo**fo**fo")) {
+        assertIllegalPattern(prefix + pattern);
+        assertIllegalPattern(pattern + suffix);
+      }
+    }
+  }
+
+  private void assertIllegalPattern(String pattern) {
+    try {
+      GlobValue.key(PKG_PATH_ID, pattern, false, PathFragment.EMPTY_FRAGMENT);
+      fail("invalid pattern not detected: " + pattern);
+    } catch (InvalidGlobPatternException e) {
+      // Expected.
+    }
+  }
+
+  /**
+   * Tests that globs can contain Java regular expression special characters
+   */
+  public void testSpecialRegexCharacter() throws Exception {
+    Path aDotB = pkgPath.getChild("a.b");
+    FileSystemUtils.createEmptyFile(aDotB);
+    FileSystemUtils.createEmptyFile(pkgPath.getChild("aab"));
+    // Note: this contains two asterisks because otherwise a RE is not built,
+    // as an optimization.
+    assertThat(UnixGlob.forPath(pkgPath).addPattern("*a.b*").globInterruptible())
+        .containsExactly(aDotB);
+  }
+
+  public void testMatchesCallWithNoCache() {
+    assertTrue(UnixGlob.matches("*a*b", "CaCb", null));
+  }
+
+  public void testHiddenFiles() throws Exception {
+    for (String dir : ImmutableList.of(".hidden", "..also.hidden", "not.hidden")) {
+      FileSystemUtils.createDirectoryAndParents(pkgPath.getRelative(dir));
+    }
+    // Note that these are not in the result: ".", ".."
+    assertGlobMatches(
+        "*", "a1", "a2", "not.hidden", "foo", "fool", "food", "BUILD", ".hidden", "..also.hidden");
+    assertGlobMatches("*.hidden", "not.hidden");
+  }
+
+  public void testDoubleStar() throws Exception {
+    assertGlobMatches(
+        "**",
+        "",
+        "BUILD",
+        "a1",
+        "a1/b1",
+        "a1/b1/c",
+        "a2",
+        "foo",
+        "foo/bar",
+        "foo/bar/wiz",
+        "foo/bar/wiz/file",
+        "foo/barnacle",
+        "foo/barnacle/wiz",
+        "food",
+        "food/barnacle",
+        "food/barnacle/wiz",
+        "fool",
+        "fool/barnacle",
+        "fool/barnacle/wiz");
+  }
+
+  public void testDoubleStarExcludeDirs() throws Exception {
+    assertGlobWithoutDirsMatches("**", "BUILD", "foo/bar/wiz/file");
+  }
+
+  public void testDoubleDoubleStar() throws Exception {
+    assertGlobMatches(
+        "**/**",
+        "",
+        "BUILD",
+        "a1",
+        "a1/b1",
+        "a1/b1/c",
+        "a2",
+        "foo",
+        "foo/bar",
+        "foo/bar/wiz",
+        "foo/bar/wiz/file",
+        "foo/barnacle",
+        "foo/barnacle/wiz",
+        "food",
+        "food/barnacle",
+        "food/barnacle/wiz",
+        "fool",
+        "fool/barnacle",
+        "fool/barnacle/wiz");
+  }
+
+  public void testDirectoryWithDoubleStar() throws Exception {
+    assertGlobMatches(
+        "foo/**",
+        "foo",
+        "foo/bar",
+        "foo/bar/wiz",
+        "foo/bar/wiz/file",
+        "foo/barnacle",
+        "foo/barnacle/wiz");
+  }
+
+  public void testDoubleStarPatternWithNamedChild() throws Exception {
+    assertGlobMatches("**/bar", "foo/bar");
+  }
+
+  public void testDoubleStarPatternWithChildGlob() throws Exception {
+    assertGlobMatches("**/ba*", "foo/bar", "foo/barnacle", "food/barnacle", "fool/barnacle");
+  }
+
+  public void testDoubleStarAsChildGlob() throws Exception {
+    FileSystemUtils.createEmptyFile(pkgPath.getRelative("foo/barnacle/wiz/wiz"));
+    FileSystemUtils.createDirectoryAndParents(pkgPath.getRelative("foo/barnacle/baz/wiz"));
+
+    assertGlobMatches(
+        "foo/**/wiz",
+        "foo/bar/wiz",
+        "foo/barnacle/baz/wiz",
+        "foo/barnacle/wiz",
+        "foo/barnacle/wiz/wiz");
+  }
+
+  public void testDoubleStarUnderNonexistentDirectory() throws Exception {
+    assertGlobMatches("not-there/**" /* => nothing */);
+  }
+
+  public void testDoubleStarUnderFile() throws Exception {
+    assertGlobMatches("foo/bar/wiz/file/**" /* => nothing */);
+  }
+
+  /** Regression test for b/13319874: Directory listing crash. */
+  public void testResilienceToFilesystemInconsistencies_DirectoryExistence() throws Exception {
+    long nodeId = pkgPath.getRelative("BUILD").stat().getNodeId();
+    // Our custom filesystem says "pkgPath/BUILD" exists but "pkgPath" does not exist.
+    fs.stubStat(pkgPath, null);
+    RootedPath pkgRootedPath = RootedPath.toRootedPath(root, pkgPath);
+    FileStateValue pkgDirFileStateValue = FileStateValue.create(pkgRootedPath, tsgm);
+    FileValue pkgDirValue =
+        FileValue.value(pkgRootedPath, pkgDirFileStateValue, pkgRootedPath, pkgDirFileStateValue);
+    differencer.inject(ImmutableMap.of(FileValue.key(pkgRootedPath), pkgDirValue));
+    String expectedMessage =
+        "Some filesystem operations implied /root/workspace/pkg/BUILD was a "
+            + "regular file with size of 0 and mtime of 0 and nodeId of "
+            + nodeId
+            + " and mtime of 0 "
+            + "but others made us think it was a nonexistent path";
+    SkyKey skyKey = GlobValue.key(PKG_PATH_ID, "*/foo", false, PathFragment.EMPTY_FRAGMENT);
+    EvaluationResult<GlobValue> result =
+        driver.evaluate(
+            ImmutableList.of(skyKey),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    assertThat(errorInfo.getException()).isInstanceOf(InconsistentFilesystemException.class);
+    assertThat(errorInfo.getException().getMessage()).contains(expectedMessage);
+  }
+
+  public void testResilienceToFilesystemInconsistencies_SubdirectoryExistence() throws Exception {
+    // Our custom filesystem says directory "pkgPath/foo/bar" contains a subdirectory "wiz" but a
+    // direct stat on "pkgPath/foo/bar/wiz" says it does not exist.
+    Path fooBarDir = pkgPath.getRelative("foo/bar");
+    fs.stubStat(fooBarDir.getRelative("wiz"), null);
+    RootedPath fooBarDirRootedPath = RootedPath.toRootedPath(root, fooBarDir);
+    SkyValue fooBarDirListingValue =
+        DirectoryListingStateValue.createForTesting(
+            ImmutableList.of(new Dirent("wiz", Dirent.Type.DIRECTORY)));
+    differencer.inject(
+        ImmutableMap.of(
+            DirectoryListingStateValue.key(fooBarDirRootedPath), fooBarDirListingValue));
+    String expectedMessage = "/root/workspace/pkg/foo/bar/wiz is no longer an existing directory.";
+    SkyKey skyKey = GlobValue.key(PKG_PATH_ID, "**/wiz", false, PathFragment.EMPTY_FRAGMENT);
+    EvaluationResult<GlobValue> result =
+        driver.evaluate(
+            ImmutableList.of(skyKey),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    assertThat(errorInfo.getException()).isInstanceOf(InconsistentFilesystemException.class);
+    assertThat(errorInfo.getException().getMessage()).contains(expectedMessage);
+  }
+
+  public void testResilienceToFilesystemInconsistencies_SymlinkType() throws Exception {
+    RootedPath wizRootedPath = RootedPath.toRootedPath(root, pkgPath.getRelative("foo/bar/wiz"));
+    RootedPath fileRootedPath =
+        RootedPath.toRootedPath(root, pkgPath.getRelative("foo/bar/wiz/file"));
+    final FileStatus realStat = fileRootedPath.asPath().stat();
+    fs.stubStat(
+        fileRootedPath.asPath(),
+        new FileStatus() {
+
+          @Override
+          public boolean isFile() {
+            // The stat says foo/bar/wiz/file is a real file, not a symlink.
+            return true;
+          }
+
+          @Override
+          public boolean isSpecialFile() {
+            return false;
+          }
+
+          @Override
+          public boolean isDirectory() {
+            return false;
+          }
+
+          @Override
+          public boolean isSymbolicLink() {
+            return false;
+          }
+
+          @Override
+          public long getSize() throws IOException {
+            return realStat.getSize();
+          }
+
+          @Override
+          public long getLastModifiedTime() throws IOException {
+            return realStat.getLastModifiedTime();
+          }
+
+          @Override
+          public long getLastChangeTime() throws IOException {
+            return realStat.getLastChangeTime();
+          }
+
+          @Override
+          public long getNodeId() throws IOException {
+            return realStat.getNodeId();
+          }
+        });
+    // But the dir listing say foo/bar/wiz/file is a symlink.
+    SkyValue wizDirListingValue =
+        DirectoryListingStateValue.createForTesting(
+            ImmutableList.of(new Dirent("file", Dirent.Type.SYMLINK)));
+    differencer.inject(
+        ImmutableMap.of(DirectoryListingStateValue.key(wizRootedPath), wizDirListingValue));
+    String expectedMessage =
+        "readdir and stat disagree about whether " + fileRootedPath.asPath() + " is a symlink";
+    SkyKey skyKey = GlobValue.key(PKG_PATH_ID, "foo/bar/wiz/*", false, PathFragment.EMPTY_FRAGMENT);
+    EvaluationResult<GlobValue> result =
+        driver.evaluate(
+            ImmutableList.of(skyKey),
+            false,
+            SkyframeExecutor.DEFAULT_THREAD_COUNT,
+            NullEventHandler.INSTANCE);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    assertThat(errorInfo.getException()).isInstanceOf(InconsistentFilesystemException.class);
+    assertThat(errorInfo.getException().getMessage()).contains(expectedMessage);
+  }
+
+  private class CustomInMemoryFs extends InMemoryFileSystem {
+
+    private Map<Path, FileStatus> stubbedStats = Maps.newHashMap();
+
+    public CustomInMemoryFs(ManualClock manualClock) {
+      super(manualClock);
+    }
+
+    public void stubStat(Path path, @Nullable FileStatus stubbedResult) {
+      stubbedStats.put(path, stubbedResult);
+    }
+
+    @Override
+    public FileStatus stat(Path path, boolean followSymlinks) throws IOException {
+      if (stubbedStats.containsKey(path)) {
+        return stubbedStats.get(path);
+      }
+      return super.stat(path, followSymlinks);
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java
new file mode 100644
index 0000000000..bfa2d8a084
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java
@@ -0,0 +1,122 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.WalkableGraph;
+
+import java.io.IOException;
+
+/** Tests for {@link PrepareDepsOfPatternsFunction}. */
+public class PrepareDepsOfPatternsFunctionSmartNegationTest extends BuildViewTestCase {
+
+  private static SkyKey getKeyForLabel(Label label) {
+    // Note that these tests used to look for TargetMarker SkyKeys before TargetMarker was
+    // inlined in TransitiveTraversalFunction. Because TargetMarker is now inlined, it doesn't
+    // appear in the graph. Instead, these tests now look for TransitiveTraversal keys.
+    return TransitiveTraversalValue.key(label);
+  }
+
+  public void testRecursiveEvaluationFailsOnBadBuildFile() throws Exception {
+    // Given a well-formed package "//foo" and a malformed package "//foo/foo",
+    createFooAndFooFoo();
+
+    // Given a target pattern sequence consisting of a recursive pattern for "//foo/...",
+    ImmutableList<String> patternSequence = ImmutableList.of("//foo/...");
+
+    // When PrepareDepsOfPatternsFunction completes evaluation (with no error because it was
+    // recovered from),
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(
+            patternSequence, /*successExpected=*/ true, /*keepGoing=*/ true);
+
+    // Then the graph contains package values for "//foo" and "//foo/foo",
+    assertTrue(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("foo"))));
+    assertTrue(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("foo/foo"))));
+
+    // But the graph does not contain a value for the target "//foo/foo:foofoo".
+    assertFalse(walkableGraph.exists(getKeyForLabel(Label.create("foo/foo", "foofoo"))));
+  }
+
+  public void testNegativePatternBlocksPatternEvaluation() throws Exception {
+    // Given a well-formed package "//foo" and a malformed package "//foo/foo",
+    createFooAndFooFoo();
+
+    // Given a target pattern sequence consisting of a recursive pattern for "//foo/..." followed
+    // by a negative pattern for the malformed package,
+    ImmutableList<String> patternSequence = ImmutableList.of("//foo/...", "-//foo/foo/...");
+
+    // When PrepareDepsOfPatternsFunction completes evaluation (successfully),
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(
+            patternSequence, /*successExpected=*/ true, /*keepGoing=*/ true);
+
+    // Then the graph contains a package value for "//foo",
+    assertTrue(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("foo"))));
+
+    // But no package value for "//foo/foo",
+    assertFalse(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("foo/foo"))));
+
+    // And the graph does not contain a value for the target "//foo/foo:foofoo".
+    Label label = Label.create("foo/foo", "foofoo");
+    assertFalse(walkableGraph.exists(getKeyForLabel(label)));
+  }
+
+  public void testNegativeNonTBDPatternsAreSkippedWithWarnings() throws Exception {
+    // Given a target pattern sequence with a negative non-TBD pattern,
+    ImmutableList<String> patternSequence = ImmutableList.of("-//foo/bar");
+
+    // When PrepareDepsOfPatternsFunction completes evaluation,
+    getGraphFromPatternsEvaluation(patternSequence, /*successExpected=*/ true, /*keepGoing=*/ true);
+
+    // Then a event is published that says that negative non-TBD patterns are skipped.
+    assertContainsEvent(
+        "Skipping '-//foo/bar': Negative target patterns of types other than \"targets below "
+            + "directory\" are not permitted.");
+  }
+
+  // Helpers:
+
+  private WalkableGraph getGraphFromPatternsEvaluation(
+      ImmutableList<String> patternSequence, boolean successExpected, boolean keepGoing)
+      throws InterruptedException {
+    SkyKey independentTarget = PrepareDepsOfPatternsValue.key(patternSequence, "");
+    ImmutableList<SkyKey> singletonTargetPattern = ImmutableList.of(independentTarget);
+
+    // When PrepareDepsOfPatternsFunction completes evaluation,
+    EvaluationResult<SkyValue> evaluationResult =
+        getSkyframeExecutor()
+            .getDriverForTesting()
+            .evaluate(singletonTargetPattern, keepGoing, LOADING_PHASE_THREADS, eventCollector);
+    // The evaluation has no errors if success was expected.
+    assertThat(evaluationResult.hasError()).isNotEqualTo(successExpected);
+    return Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
+  }
+
+  private void createFooAndFooFoo() throws IOException {
+    scratch.file(
+        "foo/BUILD", "genrule(name = 'foo',", "    outs = ['out.txt'],", "    cmd = 'touch $@')");
+    scratch.file(
+        "foo/foo/BUILD", "genrule(name = 'foofoo',", "    This isn't even remotely grammatical.)");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java
new file mode 100644
index 0000000000..d7b9e5fefb
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java
@@ -0,0 +1,273 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.WalkableGraph;
+
+import java.io.IOException;
+
+/** Tests for {@link com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternsFunction}. */
+public class PrepareDepsOfPatternsFunctionTest extends BuildViewTestCase {
+
+  private static SkyKey getKeyForLabel(Label label) {
+    // Note that these tests used to look for TargetMarker SkyKeys before TargetMarker was
+    // inlined in TransitiveTraversalFunction. Because TargetMarker is now inlined, it doesn't
+    // appear in the graph. Instead, these tests now look for TransitiveTraversal keys.
+    return TransitiveTraversalValue.key(label);
+  }
+
+  public void testFunctionLoadsTargetAndNotUnspecifiedTargets() throws Exception {
+    // Given a package "//foo" with independent target rules ":foo" and ":foo2",
+    createFooAndFoo2(/*dependent=*/ false);
+
+    // Given a target pattern sequence consisting of a single-target pattern for "//foo",
+    ImmutableList<String> patternSequence = ImmutableList.of("//foo");
+
+    // When PrepareDepsOfPatternsFunction successfully completes evaluation,
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(patternSequence, /*successExpected=*/ true);
+
+    // Then the graph contains a value for the target "//foo:foo",
+    assertValidValue(walkableGraph, getKeyForLabel(Label.create("foo", "foo")));
+
+    // And the graph does not contain a value for the target "//foo:foo2".
+    assertFalse(walkableGraph.exists(getKeyForLabel(Label.create("foo", "foo2"))));
+  }
+
+  public void testFunctionLoadsTargetDependencies() throws Exception {
+    // Given a package "//foo" with target rules ":foo" and ":foo2",
+    // And given ":foo" depends on ":foo2",
+    createFooAndFoo2(/*dependent=*/ true);
+
+    // Given a target pattern sequence consisting of a single-target pattern for "//foo",
+    ImmutableList<String> patternSequence = ImmutableList.of("//foo");
+
+    // When PrepareDepsOfPatternsFunction successfully completes evaluation,
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(patternSequence, /*successExpected=*/ true);
+
+    // Then the graph contains an entry for ":foo"'s dependency, ":foo2".
+    assertValidValue(walkableGraph, getKeyForLabel(Label.create("foo", "foo2")));
+  }
+
+  public void testFunctionExpandsTargetPatterns() throws Exception {
+    // Given a package "//foo" with independent target rules ":foo" and ":foo2",
+    createFooAndFoo2(/*dependent=*/ false);
+
+    // Given a target pattern sequence consisting of a pattern for "//foo:*",
+    ImmutableList<String> patternSequence = ImmutableList.of("//foo:*");
+
+    // When PrepareDepsOfPatternsFunction successfully completes evaluation,
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(patternSequence, /*successExpected=*/ true);
+
+    // Then the graph contains an entry for ":foo" and ":foo2".
+    assertValidValue(walkableGraph, getKeyForLabel(Label.create("foo", "foo")));
+    assertValidValue(walkableGraph, getKeyForLabel(Label.create("foo", "foo2")));
+  }
+
+  public void testTargetParsingException() throws Exception {
+    // Given no packages, and a target pattern sequence referring to a non-existent target,
+    String nonexistentTarget = "//foo:foo";
+    ImmutableList<String> patternSequence = ImmutableList.of(nonexistentTarget);
+
+    // When PrepareDepsOfPatternsFunction completes evaluation,
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(patternSequence, /*successExpected=*/ false);
+
+    // Then the graph does not contain an entry for ":foo",
+    assertFalse(walkableGraph.exists(getKeyForLabel(Label.create("foo", "foo"))));
+  }
+
+  public void testDependencyTraversalNoSuchPackageException() throws Exception {
+    // Given a package "//foo" with a target ":foo" that has a dependency on a non-existent target
+    // "//bar:bar" in a non-existent package "//bar",
+    createFooWithDependencyOnMissingBarPackage();
+
+    // Given a target pattern sequence consisting of a single-target pattern for "//foo",
+    ImmutableList<String> patternSequence = ImmutableList.of("//foo");
+
+    // When PrepareDepsOfPatternsFunction completes evaluation,
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(patternSequence, /*successExpected=*/ false);
+
+    // Then the graph contains an entry for ":foo",
+    assertValidValue(
+        walkableGraph,
+        getKeyForLabel(Label.create("foo", "foo")),
+        /*expectTransitiveException=*/ true);
+
+    // And an entry with a NoSuchPackageException for "//bar:bar",
+    Exception e = assertException(walkableGraph, getKeyForLabel(Label.create("bar", "bar")));
+    assertThat(e).isInstanceOf(NoSuchPackageException.class);
+  }
+
+  public void testDependencyTraversalNoSuchTargetException() throws Exception {
+    // Given a package "//foo" with a target ":foo" that has a dependency on a non-existent target
+    // "//bar:bar" in an existing package "//bar",
+    createFooWithDependencyOnBarPackageWithMissingTarget();
+
+    // Given a target pattern sequence consisting of a single-target pattern for "//foo",
+    ImmutableList<String> patternSequence = ImmutableList.of("//foo");
+
+    // When PrepareDepsOfPatternsFunction completes evaluation,
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(patternSequence, /*successExpected=*/ false);
+
+    // Then the graph contains an entry for ":foo" which has both a value and an exception,
+    assertValidValue(
+        walkableGraph,
+        getKeyForLabel(Label.create("foo", "foo")),
+        /*expectTransitiveException=*/ true);
+
+    // And an entry with a NoSuchTargetException for "//bar:bar",
+    Exception e = assertException(walkableGraph, getKeyForLabel(Label.create("bar", "bar")));
+    assertThat(e).isInstanceOf(NoSuchTargetException.class);
+  }
+
+  public void testParsingProblemsKeepGoing() throws Exception {
+    parsingProblem(/*keepGoing=*/ true);
+  }
+
+  /**
+   * PrepareDepsOfPatternsFunction always keeps going despite any target pattern parsing errors,
+   * in keeping with the original behavior of {@link SkyframeExecutor#prepareAndGet}, which
+   * always used {@code keepGoing=true} during target pattern parsing because it was responsible
+   * for ensuring that queries had a complete graph to work on.
+   */
+  public void testParsingProblemsNoKeepGoing() throws Exception {
+    parsingProblem(/*keepGoing=*/ false);
+  }
+
+  private void parsingProblem(boolean keepGoing) throws Exception {
+    // Given a package "//foo" with target rule ":foo",
+    createFooAndFoo2(/*dependent=*/ false);
+
+    // Given a target pattern sequence consisting of a pattern with parsing problems followed by
+    // a legit target pattern,
+    String bogusPattern = "//foo/....";
+    ImmutableList<String> patternSequence = ImmutableList.of(bogusPattern, "//foo:foo");
+
+    // When PrepareDepsOfPatternsFunction runs in the selected keep-going mode,
+    WalkableGraph walkableGraph =
+        getGraphFromPatternsEvaluation(
+            patternSequence, /*successExpected=*/ true, /*keepGoing=*/ keepGoing);
+
+    // Then it skips evaluation of the malformed target pattern, but logs about it,
+    assertContainsEvent("Skipping '" + bogusPattern + "': ");
+
+    // And then the graph contains a value for the legit target pattern's target "//foo:foo".
+    assertTrue(walkableGraph.exists(getKeyForLabel(Label.create("foo", "foo"))));
+  }
+
+  // Helpers:
+
+  private WalkableGraph getGraphFromPatternsEvaluation(
+      ImmutableList<String> patternSequence, boolean successExpected) throws InterruptedException {
+    return getGraphFromPatternsEvaluation(patternSequence, successExpected, /*keepGoing=*/ true);
+  }
+
+  private WalkableGraph getGraphFromPatternsEvaluation(
+      ImmutableList<String> patternSequence, boolean successExpected, boolean keepGoing)
+      throws InterruptedException {
+    SkyKey independentTarget = PrepareDepsOfPatternsValue.key(patternSequence, "");
+    ImmutableList<SkyKey> singletonTargetPattern = ImmutableList.of(independentTarget);
+
+    // When PrepareDepsOfPatternsFunction completes evaluation,
+    EvaluationResult<SkyValue> evaluationResult =
+        getSkyframeExecutor()
+            .getDriverForTesting()
+            .evaluate(singletonTargetPattern, keepGoing, LOADING_PHASE_THREADS, eventCollector);
+
+    if (successExpected) {
+      // Then the evaluation completed successfully.
+      assertFalse(evaluationResult.hasError());
+    } else {
+      // Then the evaluation resulted in some errors.
+      assertTrue(evaluationResult.hasError());
+    }
+
+    return Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
+  }
+
+  private void createFooAndFoo2(boolean dependent) throws IOException {
+    String dependencyIfAny = dependent ? "srcs = [':foo2']," : "";
+    scratch.file(
+        "foo/BUILD",
+        "genrule(name = 'foo',",
+        dependencyIfAny,
+        "    outs = ['out.txt'],",
+        "    cmd = 'touch $@')",
+        "genrule(name = 'foo2',",
+        "    outs = ['out2.txt'],",
+        "    cmd = 'touch $@')");
+  }
+
+  private void createFooWithDependencyOnMissingBarPackage() throws IOException {
+    scratch.file(
+        "foo/BUILD",
+        "genrule(name = 'foo',",
+        "    srcs = ['//bar:bar'],",
+        "    outs = ['out.txt'],",
+        "    cmd = 'touch $@')");
+  }
+
+  private void createFooWithDependencyOnBarPackageWithMissingTarget() throws IOException {
+    scratch.file(
+        "foo/BUILD",
+        "genrule(name = 'foo',",
+        "    srcs = ['//bar:bar'],",
+        "    outs = ['out.txt'],",
+        "    cmd = 'touch $@')");
+    scratch.file("bar/BUILD");
+  }
+
+  private void assertValidValue(WalkableGraph graph, SkyKey key) {
+    assertValidValue(graph, key, /*expectTransitiveException=*/ false);
+  }
+
+  /**
+   * A node in the walkable graph may have both a value and an exception. This happens when one
+   * of a node's transitive dependencies throws an exception, but its parent recovers from it.
+   */
+  private void assertValidValue(
+      WalkableGraph graph, SkyKey key, boolean expectTransitiveException) {
+    assertTrue(graph.exists(key));
+    assertNotNull(graph.getValue(key));
+    if (expectTransitiveException) {
+      assertNotNull(graph.getException(key));
+    } else {
+      assertNull(graph.getException(key));
+    }
+  }
+
+  private Exception assertException(WalkableGraph graph, SkyKey key) {
+    assertTrue(graph.exists(key));
+    assertNull(graph.getValue(key));
+    Exception exception = graph.getException(key);
+    assertNotNull(exception);
+    return exception;
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
new file mode 100644
index 0000000000..fb46d738a7
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
@@ -0,0 +1,757 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode.CROSS;
+import static com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode.DONT_CROSS;
+import static com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode.REPORT_ERROR;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Supplier;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode;
+import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.ResolvedFile;
+import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.TraversalRequest;
+import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+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.skyframe.ErrorInfo;
+import com.google.devtools.build.skyframe.EvaluationProgressReceiver;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
+import com.google.devtools.build.skyframe.MemoizingEvaluator;
+import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import java.io.OutputStream;
+import java.nio.charset.StandardCharsets;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.regex.Pattern;
+
+/** Tests for {@link RecursiveFilesystemTraversalFunction}. */
+public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTestCase {
+
+  private TimestampGranularityMonitor tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
+  private RecordingEvaluationProgressReceiver progressReceiver;
+  private MemoizingEvaluator evaluator;
+  private SequentialBuildDriver driver;
+  private RecordingDifferencer differencer;
+  private AtomicReference<PathPackageLocator> pkgLocator;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+
+    pkgLocator = new AtomicReference<>(new PathPackageLocator(rootDirectory));
+    AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages =
+        new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+
+    Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
+
+    skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
+    skyFunctions.put(
+        SkyFunctions.DIRECTORY_LISTING_STATE,
+        new DirectoryListingStateFunction(externalFilesHelper));
+    skyFunctions.put(
+        SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL, new RecursiveFilesystemTraversalFunction());
+    skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));
+
+    progressReceiver = new RecordingEvaluationProgressReceiver();
+    differencer = new RecordingDifferencer();
+    evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer, progressReceiver);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+  }
+
+  private Artifact sourceArtifact(String path) {
+    return new Artifact(new PathFragment(path), Root.asSourceRoot(rootDirectory));
+  }
+
+  private Artifact sourceArtifactUnderPackagePath(String path, String packagePath) {
+    return new Artifact(
+        new PathFragment(path), Root.asSourceRoot(rootDirectory.getRelative(packagePath)));
+  }
+
+  private Artifact derivedArtifact(String path) {
+    PathFragment execPath = new PathFragment("out").getRelative(path);
+    Path fullPath = rootDirectory.getRelative(execPath);
+    Artifact output =
+        new Artifact(
+            fullPath,
+            Root.asDerivedRoot(rootDirectory, rootDirectory.getRelative("out")),
+            execPath);
+    return output;
+  }
+
+  private static RootedPath rootedPath(Artifact artifact) {
+    return RootedPath.toRootedPath(artifact.getRoot().getPath(), artifact.getRootRelativePath());
+  }
+
+  private RootedPath rootedPath(String path, String packagePath) {
+    return RootedPath.toRootedPath(rootDirectory.getRelative(packagePath), new PathFragment(path));
+  }
+
+  private static RootedPath childOf(Artifact artifact, String relative) {
+    return RootedPath.toRootedPath(
+        artifact.getRoot().getPath(), artifact.getRootRelativePath().getRelative(relative));
+  }
+
+  private static RootedPath childOf(RootedPath path, String relative) {
+    return RootedPath.toRootedPath(path.getRoot(), path.getRelativePath().getRelative(relative));
+  }
+
+  private static RootedPath parentOf(RootedPath path) {
+    PathFragment parent = Preconditions.checkNotNull(path.getRelativePath().getParentDirectory());
+    return RootedPath.toRootedPath(path.getRoot(), parent);
+  }
+
+  private static RootedPath siblingOf(RootedPath path, String relative) {
+    PathFragment parent = Preconditions.checkNotNull(path.getRelativePath().getParentDirectory());
+    return RootedPath.toRootedPath(path.getRoot(), parent.getRelative(relative));
+  }
+
+  private static RootedPath siblingOf(Artifact artifact, String relative) {
+    PathFragment parent =
+        Preconditions.checkNotNull(artifact.getRootRelativePath().getParentDirectory());
+    return RootedPath.toRootedPath(artifact.getRoot().getPath(), parent.getRelative(relative));
+  }
+
+  private void createFile(Path path, String... contents) throws Exception {
+    if (!path.getParentDirectory().exists()) {
+      scratch.dir(path.getParentDirectory().getPathString());
+    }
+    scratch.file(path.getPathString(), contents);
+  }
+
+  private void createFile(Artifact artifact, String... contents) throws Exception {
+    createFile(artifact.getPath(), contents);
+  }
+
+  private RootedPath createFile(RootedPath path, String... contents) throws Exception {
+    scratch.dir(parentOf(path).asPath().getPathString());
+    createFile(path.asPath(), contents);
+    return path;
+  }
+
+  private static TraversalRequest fileLikeRoot(Artifact file, PackageBoundaryMode pkgBoundaryMode) {
+    return new TraversalRequest(
+        rootedPath(file), !file.isSourceArtifact(), pkgBoundaryMode, false, null, null);
+  }
+
+  private static TraversalRequest pkgRoot(
+      RootedPath pkgDirectory, PackageBoundaryMode pkgBoundaryMode) {
+    return new TraversalRequest(pkgDirectory, false, pkgBoundaryMode, true, null, null);
+  }
+
+  private <T extends SkyValue> EvaluationResult<T> eval(SkyKey key) throws Exception {
+    return driver.evaluate(
+        ImmutableList.of(key),
+        false,
+        SkyframeExecutor.DEFAULT_THREAD_COUNT,
+        NullEventHandler.INSTANCE);
+  }
+
+  private RecursiveFilesystemTraversalValue evalTraversalRequest(TraversalRequest params)
+      throws Exception {
+    SkyKey key = rftvSkyKey(params);
+    EvaluationResult<RecursiveFilesystemTraversalValue> result = eval(key);
+    assertThat(result.hasError()).isFalse();
+    return result.get(key);
+  }
+
+  private static SkyKey rftvSkyKey(TraversalRequest params) {
+    return RecursiveFilesystemTraversalValue.key(params);
+  }
+
+  /**
+   * Asserts that the requested SkyValue can be built and results in the expected set of files.
+   *
+   * <p>The metadata of files is ignored in comparing the actual results with the expected ones.
+   * The returned object however contains the actual metadata.
+   */
+  @SafeVarargs
+  private final RecursiveFilesystemTraversalValue traverseAndAssertFiles(
+      TraversalRequest params, ResolvedFile... expectedFilesIgnoringMetadata) throws Exception {
+    Set<ResolvedFile> expectedMap = new HashSet<>();
+    for (ResolvedFile exp : expectedFilesIgnoringMetadata) {
+      // Strip metadata so only the type and path of the objects are compared.
+      expectedMap.add(exp.stripMetadataForTesting());
+    }
+    RecursiveFilesystemTraversalValue result = evalTraversalRequest(params);
+    Set<ResolvedFile> actualMap = new HashSet<>();
+    for (ResolvedFile act : result.getTransitiveFiles()) {
+      // Strip metadata so only the type and path of the objects are compared.
+      actualMap.add(act.stripMetadataForTesting());
+    }
+    // First just assert equality of the keys, so in case of a mismatch the error message is easier
+    // to read.
+    assertThat(expectedMap).isEqualTo(actualMap);
+
+    // The returned object still has the unstripped metadata.
+    return result;
+  }
+
+  private void appendToFile(RootedPath rootedPath, String content) throws Exception {
+    Path path = rootedPath.asPath();
+    if (path.exists()) {
+      try (OutputStream os = path.getOutputStream(/*append=*/ true)) {
+        os.write(content.getBytes(StandardCharsets.UTF_8));
+      }
+      differencer.invalidate(ImmutableList.of(FileStateValue.key(rootedPath)));
+    } else {
+      createFile(path, content);
+    }
+  }
+
+  private void appendToFile(Artifact file, String content) throws Exception {
+    appendToFile(rootedPath(file), content);
+  }
+
+  private void invalidateDirectory(RootedPath path) {
+    differencer.invalidate(ImmutableList.of(DirectoryListingStateValue.key(path)));
+  }
+
+  private void invalidateDirectory(Artifact directoryArtifact) {
+    invalidateDirectory(rootedPath(directoryArtifact));
+  }
+
+  private static final class RecordingEvaluationProgressReceiver
+      implements EvaluationProgressReceiver {
+    Set<SkyKey> invalidations;
+    Set<SkyValue> evaluations;
+
+    RecordingEvaluationProgressReceiver() {
+      clear();
+    }
+
+    void clear() {
+      invalidations = Sets.newConcurrentHashSet();
+      evaluations = Sets.newConcurrentHashSet();
+    }
+
+    @Override
+    public void invalidated(SkyKey skyKey, InvalidationState state) {
+      invalidations.add(skyKey);
+    }
+
+    @Override
+    public void enqueueing(SkyKey skyKey) {}
+
+    @Override
+    public void computed(SkyKey skyKey, long elapsedTimeNanos) {}
+
+    @Override
+    public void evaluated(
+        SkyKey skyKey, Supplier<SkyValue> skyValueSupplier, EvaluationState state) {
+      SkyValue value = skyValueSupplier.get();
+      if (value != null) {
+        evaluations.add(value);
+      }
+    }
+  }
+
+  private ResolvedFile resolvedFile(RootedPath path) throws Exception {
+    return ResolvedFile.regularFile(path, FileStateValue.create(path, tsgm));
+  }
+
+  private ResolvedFile resolvedDanglingSymlink(RootedPath linkNamePath, PathFragment linkTargetPath)
+      throws Exception {
+    return ResolvedFile.danglingSymlink(
+        linkNamePath, linkTargetPath, FileStateValue.create(linkNamePath, tsgm));
+  }
+
+  private ResolvedFile resolvedSymlinkToFile(
+      RootedPath targetPath, RootedPath linkNamePath, PathFragment linkTargetPath)
+      throws Exception {
+    return ResolvedFile.symlinkToFile(
+        targetPath, linkNamePath, linkTargetPath, FileStateValue.create(linkNamePath, tsgm));
+  }
+
+  private ResolvedFile resolvedSymlinkToDir(
+      RootedPath targetPath, RootedPath linkNamePath, PathFragment linkTargetPath)
+      throws Exception {
+    return ResolvedFile.symlinkToDirectory(
+        targetPath, linkNamePath, linkTargetPath, FileStateValue.create(linkNamePath, tsgm));
+  }
+
+  private void assertTraversalOfFile(Artifact rootArtifact) throws Exception {
+    TraversalRequest traversalRoot = fileLikeRoot(rootArtifact, DONT_CROSS);
+    RootedPath rootedPath = createFile(rootedPath(rootArtifact), "foo");
+
+    // Assert that the SkyValue is built and looks right.
+    ResolvedFile expected = resolvedFile(rootedPath);
+    RecursiveFilesystemTraversalValue v1 = traverseAndAssertFiles(traversalRoot, expected);
+    assertThat(progressReceiver.invalidations).isEmpty();
+    assertThat(progressReceiver.evaluations).contains(v1);
+    progressReceiver.clear();
+
+    // Edit the file and verify that the value is rebuilt.
+    appendToFile(rootArtifact, "bar");
+    RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(traversalRoot, expected);
+    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.evaluations).contains(v2);
+    assertThat(v2).isNotEqualTo(v1);
+    progressReceiver.clear();
+  }
+
+  public void testTraversalOfSourceFile() throws Exception {
+    assertTraversalOfFile(sourceArtifact("foo/bar.txt"));
+  }
+
+  public void testTraversalOfGeneratedFile() throws Exception {
+    assertTraversalOfFile(derivedArtifact("foo/bar.txt"));
+  }
+
+  public void testTraversalOfSymlinkToFile() throws Exception {
+    Artifact linkNameArtifact = sourceArtifact("foo/baz/qux.sym");
+    Artifact linkTargetArtifact = sourceArtifact("foo/bar/baz.txt");
+    PathFragment linkValue = new PathFragment("../bar/baz.txt");
+    TraversalRequest traversalRoot = fileLikeRoot(linkNameArtifact, DONT_CROSS);
+    createFile(linkTargetArtifact);
+    scratch.dir(linkNameArtifact.getExecPath().getParentDirectory().getPathString());
+    rootDirectory.getRelative(linkNameArtifact.getExecPath()).createSymbolicLink(linkValue);
+
+    // Assert that the SkyValue is built and looks right.
+    RootedPath symlinkNamePath = rootedPath(linkNameArtifact);
+    RootedPath symlinkTargetPath = rootedPath(linkTargetArtifact);
+    ResolvedFile expected = resolvedSymlinkToFile(symlinkTargetPath, symlinkNamePath, linkValue);
+    RecursiveFilesystemTraversalValue v1 = traverseAndAssertFiles(traversalRoot, expected);
+    assertThat(progressReceiver.invalidations).isEmpty();
+    assertThat(progressReceiver.evaluations).contains(v1);
+    progressReceiver.clear();
+
+    // Edit the target of the symlink and verify that the value is rebuilt.
+    appendToFile(linkTargetArtifact, "bar");
+    RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(traversalRoot, expected);
+    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.evaluations).contains(v2);
+    assertThat(v2).isNotEqualTo(v1);
+  }
+
+  public void testTraversalOfTransitiveSymlinkToFile() throws Exception {
+    Artifact directLinkArtifact = sourceArtifact("direct/file.sym");
+    Artifact transitiveLinkArtifact = sourceArtifact("transitive/sym.sym");
+    RootedPath fileA = createFile(rootedPath(sourceArtifact("a/file.a")));
+    RootedPath directLink = rootedPath(directLinkArtifact);
+    RootedPath transitiveLink = rootedPath(transitiveLinkArtifact);
+    PathFragment directLinkPath = new PathFragment("../a/file.a");
+    PathFragment transitiveLinkPath = new PathFragment("../direct/file.sym");
+
+    parentOf(directLink).asPath().createDirectory();
+    parentOf(transitiveLink).asPath().createDirectory();
+    directLink.asPath().createSymbolicLink(directLinkPath);
+    transitiveLink.asPath().createSymbolicLink(transitiveLinkPath);
+
+    traverseAndAssertFiles(
+        fileLikeRoot(directLinkArtifact, DONT_CROSS),
+        resolvedSymlinkToFile(fileA, directLink, directLinkPath));
+
+    traverseAndAssertFiles(
+        fileLikeRoot(transitiveLinkArtifact, DONT_CROSS),
+        resolvedSymlinkToFile(fileA, transitiveLink, transitiveLinkPath));
+  }
+
+  private void assertTraversalOfDirectory(Artifact directoryArtifact) throws Exception {
+    // Create files under the directory.
+    // Use the root + root-relative path of the rootArtifact to create these files, rather than
+    // using the rootDirectory + execpath of the rootArtifact. The resulting paths are the same
+    // but the RootedPaths are different:
+    // in the 1st case, it is: RootedPath(/root/execroot, relative), in the second it is
+    // in the 2nd case, it is: RootedPath(/root, execroot/relative).
+    // Creating the files will also create the parent directories.
+    RootedPath file1 = createFile(childOf(directoryArtifact, "bar.txt"));
+    RootedPath file2 = createFile(childOf(directoryArtifact, "baz/qux.txt"));
+
+    TraversalRequest traversalRoot = fileLikeRoot(directoryArtifact, DONT_CROSS);
+
+    // Assert that the SkyValue is built and looks right.
+    ResolvedFile expected1 = resolvedFile(file1);
+    ResolvedFile expected2 = resolvedFile(file2);
+    RecursiveFilesystemTraversalValue v1 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2);
+    assertThat(progressReceiver.invalidations).isEmpty();
+    assertThat(progressReceiver.evaluations).contains(v1);
+    progressReceiver.clear();
+
+    // Add a new file to the directory and see that the value is rebuilt.
+    RootedPath file3 = createFile(childOf(directoryArtifact, "foo.txt"));
+    invalidateDirectory(directoryArtifact);
+    ResolvedFile expected3 = resolvedFile(file3);
+    RecursiveFilesystemTraversalValue v2 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
+    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.evaluations).contains(v2);
+    assertThat(v2).isNotEqualTo(v1);
+    progressReceiver.clear();
+
+    // Edit a file in the directory and see that the value is rebuilt.
+    appendToFile(file1, "bar");
+    RecursiveFilesystemTraversalValue v3 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
+    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.evaluations).contains(v3);
+    assertThat(v3).isNotEqualTo(v2);
+    progressReceiver.clear();
+
+    // Add a new file *outside* of the directory and see that the value is *not* rebuilt.
+    Artifact someFile = sourceArtifact("somewhere/else/a.file");
+    createFile(someFile, "new file");
+    appendToFile(someFile, "not all changes are treated equal");
+    RecursiveFilesystemTraversalValue v4 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
+    assertThat(v4).isEqualTo(v3);
+    assertThat(progressReceiver.invalidations).doesNotContain(rftvSkyKey(traversalRoot));
+  }
+
+  public void testTraversalOfSourceDirectory() throws Exception {
+    assertTraversalOfDirectory(sourceArtifact("dir"));
+  }
+
+  public void testTraversalOfGeneratedDirectory() throws Exception {
+    assertTraversalOfDirectory(derivedArtifact("dir"));
+  }
+
+  public void testTraversalOfTransitiveSymlinkToDirectory() throws Exception {
+    Artifact directLinkArtifact = sourceArtifact("direct/dir.sym");
+    Artifact transitiveLinkArtifact = sourceArtifact("transitive/sym.sym");
+    RootedPath fileA = createFile(rootedPath(sourceArtifact("a/file.a")));
+    RootedPath directLink = rootedPath(directLinkArtifact);
+    RootedPath transitiveLink = rootedPath(transitiveLinkArtifact);
+    PathFragment directLinkPath = new PathFragment("../a");
+    PathFragment transitiveLinkPath = new PathFragment("../direct/dir.sym");
+
+    parentOf(directLink).asPath().createDirectory();
+    parentOf(transitiveLink).asPath().createDirectory();
+    directLink.asPath().createSymbolicLink(directLinkPath);
+    transitiveLink.asPath().createSymbolicLink(transitiveLinkPath);
+
+    // Expect the file as if was a child of the direct symlink, not of the actual directory.
+    traverseAndAssertFiles(
+        fileLikeRoot(directLinkArtifact, DONT_CROSS),
+        resolvedSymlinkToDir(parentOf(fileA), directLink, directLinkPath),
+        resolvedFile(childOf(directLinkArtifact, "file.a")));
+
+    // Expect the file as if was a child of the transitive symlink, not of the actual directory.
+    traverseAndAssertFiles(
+        fileLikeRoot(transitiveLinkArtifact, DONT_CROSS),
+        resolvedSymlinkToDir(parentOf(fileA), transitiveLink, transitiveLinkPath),
+        resolvedFile(childOf(transitiveLinkArtifact, "file.a")));
+  }
+
+  public void testTraversePackage() throws Exception {
+    Artifact buildFile = sourceArtifact("pkg/BUILD");
+    RootedPath buildFilePath = createFile(rootedPath(buildFile));
+    RootedPath file1 = createFile(siblingOf(buildFile, "subdir/file.a"));
+
+    traverseAndAssertFiles(
+        pkgRoot(parentOf(buildFilePath), DONT_CROSS),
+        resolvedFile(buildFilePath),
+        resolvedFile(file1));
+  }
+
+  public void testTraversalOfSymlinkToDirectory() throws Exception {
+    Artifact linkNameArtifact = sourceArtifact("link/foo.sym");
+    Artifact linkTargetArtifact = sourceArtifact("dir");
+    RootedPath linkName = rootedPath(linkNameArtifact);
+    PathFragment linkValue = new PathFragment("../dir");
+    RootedPath file1 = createFile(childOf(linkTargetArtifact, "file.1"));
+    createFile(childOf(linkTargetArtifact, "sub/file.2"));
+    scratch.dir(parentOf(linkName).asPath().getPathString());
+    linkName.asPath().createSymbolicLink(linkValue);
+
+    // Assert that the SkyValue is built and looks right.
+    TraversalRequest traversalRoot = fileLikeRoot(linkNameArtifact, DONT_CROSS);
+    ResolvedFile expected1 =
+        resolvedSymlinkToDir(rootedPath(linkTargetArtifact), linkName, linkValue);
+    ResolvedFile expected2 = resolvedFile(childOf(linkNameArtifact, "file.1"));
+    ResolvedFile expected3 = resolvedFile(childOf(linkNameArtifact, "sub/file.2"));
+    // We expect to see all the files from the symlink'd directory, under the symlink's path, not
+    // under the symlink target's path.
+    RecursiveFilesystemTraversalValue v1 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
+    assertThat(progressReceiver.invalidations).isEmpty();
+    assertThat(progressReceiver.evaluations).contains(v1);
+    progressReceiver.clear();
+
+    // Add a new file to the directory and see that the value is rebuilt.
+    createFile(childOf(linkTargetArtifact, "file.3"));
+    invalidateDirectory(linkTargetArtifact);
+    ResolvedFile expected4 = resolvedFile(childOf(linkNameArtifact, "file.3"));
+    RecursiveFilesystemTraversalValue v2 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
+    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.evaluations).contains(v2);
+    assertThat(v2).isNotEqualTo(v1);
+    progressReceiver.clear();
+
+    // Edit a file in the directory and see that the value is rebuilt.
+    appendToFile(file1, "bar");
+    RecursiveFilesystemTraversalValue v3 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
+    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.evaluations).contains(v3);
+    assertThat(v3).isNotEqualTo(v2);
+    progressReceiver.clear();
+
+    // Add a new file *outside* of the directory and see that the value is *not* rebuilt.
+    Artifact someFile = sourceArtifact("somewhere/else/a.file");
+    createFile(someFile, "new file");
+    appendToFile(someFile, "not all changes are treated equal");
+    RecursiveFilesystemTraversalValue v4 =
+        traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
+    assertThat(v4).isEqualTo(v3);
+    assertThat(progressReceiver.invalidations).doesNotContain(rftvSkyKey(traversalRoot));
+  }
+
+  public void testTraversalOfDanglingSymlink() throws Exception {
+    Artifact linkArtifact = sourceArtifact("a/dangling.sym");
+    RootedPath link = rootedPath(linkArtifact);
+    PathFragment linkTarget = new PathFragment("non_existent");
+    parentOf(link).asPath().createDirectory();
+    link.asPath().createSymbolicLink(linkTarget);
+    traverseAndAssertFiles(
+        fileLikeRoot(linkArtifact, DONT_CROSS), resolvedDanglingSymlink(link, linkTarget));
+  }
+
+  public void testTraversalOfDanglingSymlinkInADirectory() throws Exception {
+    Artifact dirArtifact = sourceArtifact("a");
+    RootedPath file = createFile(childOf(dirArtifact, "file.txt"));
+    RootedPath link = rootedPath(sourceArtifact("a/dangling.sym"));
+    PathFragment linkTarget = new PathFragment("non_existent");
+    parentOf(link).asPath().createDirectory();
+    link.asPath().createSymbolicLink(linkTarget);
+    traverseAndAssertFiles(
+        fileLikeRoot(dirArtifact, DONT_CROSS),
+        resolvedFile(file),
+        resolvedDanglingSymlink(link, linkTarget));
+  }
+
+  private void assertTraverseSubpackages(PackageBoundaryMode traverseSubpackages) throws Exception {
+    Artifact pkgDirArtifact = sourceArtifact("pkg1/foo");
+    Artifact subpkgDirArtifact = sourceArtifact("pkg1/foo/subdir/subpkg");
+    RootedPath pkgBuildFile = childOf(pkgDirArtifact, "BUILD");
+    RootedPath subpkgBuildFile = childOf(subpkgDirArtifact, "BUILD");
+    scratch.dir(rootedPath(pkgDirArtifact).asPath().getPathString());
+    scratch.dir(rootedPath(subpkgDirArtifact).asPath().getPathString());
+    createFile(pkgBuildFile);
+    createFile(subpkgBuildFile);
+
+    TraversalRequest traversalRoot = pkgRoot(parentOf(pkgBuildFile), traverseSubpackages);
+
+    ResolvedFile expected1 = resolvedFile(pkgBuildFile);
+    ResolvedFile expected2 = resolvedFile(subpkgBuildFile);
+    switch (traverseSubpackages) {
+      case CROSS:
+        traverseAndAssertFiles(traversalRoot, expected1, expected2);
+        break;
+      case DONT_CROSS:
+        traverseAndAssertFiles(traversalRoot, expected1);
+        break;
+      case REPORT_ERROR:
+        SkyKey key = rftvSkyKey(traversalRoot);
+        EvaluationResult<SkyValue> result = eval(key);
+        assertThat(result.hasError()).isTrue();
+        assertThat(result.getError().getException().getMessage())
+            .contains("crosses package boundary into package rooted at");
+        break;
+      default:
+        throw new IllegalStateException(traverseSubpackages.toString());
+    }
+  }
+
+  public void testTraverseSubpackages() throws Exception {
+    assertTraverseSubpackages(CROSS);
+  }
+
+  public void testDoNotTraverseSubpackages() throws Exception {
+    assertTraverseSubpackages(DONT_CROSS);
+  }
+
+  public void testReportErrorWhenTraversingSubpackages() throws Exception {
+    assertTraverseSubpackages(REPORT_ERROR);
+  }
+
+  public void testSwitchPackageRootsWhenUsingMultiplePackagePaths() throws Exception {
+    // Layout:
+    //   pp1://a/BUILD
+    //   pp1://a/file.a
+    //   pp1://a/b.sym -> b/   (only created later)
+    //   pp1://a/b/
+    //   pp1://a/b/file.fake
+    //   pp1://a/subdir/file.b
+    //
+    //   pp2://a/BUILD
+    //   pp2://a/b/
+    //   pp2://a/b/BUILD
+    //   pp2://a/b/file.a
+    //   pp2://a/subdir.fake/
+    //   pp2://a/subdir.fake/file.fake
+    //
+    // Notice that pp1://a/b will be overlaid by pp2://a/b as the latter has a BUILD file and that
+    // takes precedence. On the other hand the package definition pp2://a/BUILD will be ignored
+    // since package //a is already defined under pp1.
+    //
+    // Notice also that pp1://a/b.sym is a relative symlink pointing to b/. This should be resolved
+    // to the definition of //a/b/ under pp1, not under pp2.
+
+    // Set the package paths.
+    pkgLocator.set(
+        new PathPackageLocator(rootDirectory.getRelative("pp1"), rootDirectory.getRelative("pp2")));
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+
+    Artifact aBuildArtifact = sourceArtifactUnderPackagePath("a/BUILD", "pp1");
+    Artifact bBuildArtifact = sourceArtifactUnderPackagePath("a/b/BUILD", "pp2");
+
+    RootedPath pp1aBuild = createFile(rootedPath(aBuildArtifact));
+    RootedPath pp1aFileA = createFile(siblingOf(pp1aBuild, "file.a"));
+    RootedPath pp1bFileFake = createFile(siblingOf(pp1aBuild, "b/file.fake"));
+    RootedPath pp1aSubdirFileB = createFile(siblingOf(pp1aBuild, "subdir/file.b"));
+
+    RootedPath pp2aBuild = createFile(rootedPath("a/BUILD", "pp2"));
+    RootedPath pp2bBuild = createFile(rootedPath(bBuildArtifact));
+    RootedPath pp2bFileA = createFile(siblingOf(pp2bBuild, "file.a"));
+    createFile(siblingOf(pp2aBuild, "subdir.fake/file.fake"));
+
+    // Traverse //a including subpackages. The result should contain the pp1-definition of //a and
+    // the pp2-definition of //a/b.
+    traverseAndAssertFiles(
+        pkgRoot(parentOf(rootedPath(aBuildArtifact)), CROSS),
+        resolvedFile(pp1aBuild),
+        resolvedFile(pp1aFileA),
+        resolvedFile(pp1aSubdirFileB),
+        resolvedFile(pp2bBuild),
+        resolvedFile(pp2bFileA));
+
+    // Traverse //a excluding subpackages. The result should only contain files from //a and not
+    // from //a/b.
+    traverseAndAssertFiles(
+        pkgRoot(parentOf(rootedPath(aBuildArtifact)), DONT_CROSS),
+        resolvedFile(pp1aBuild),
+        resolvedFile(pp1aFileA),
+        resolvedFile(pp1aSubdirFileB));
+
+    // Create a relative symlink pp1://a/b.sym -> b/. It will be resolved to the subdirectory
+    // pp1://a/b, even though a package definition pp2://a/b exists.
+    RootedPath pp1aBsym = siblingOf(pp1aFileA, "b.sym");
+    pp1aBsym.asPath().createSymbolicLink(new PathFragment("b"));
+    invalidateDirectory(parentOf(pp1aBsym));
+
+    // Traverse //a excluding subpackages. The relative symlink //a/b.sym points to the subdirectory
+    // a/b, i.e. the pp1-definition, even though there is a pp2-defined package //a/b and we expect
+    // to see b.sym/b.fake (not b/b.fake).
+    traverseAndAssertFiles(
+        pkgRoot(parentOf(rootedPath(aBuildArtifact)), DONT_CROSS),
+        resolvedFile(pp1aBuild),
+        resolvedFile(pp1aFileA),
+        resolvedFile(childOf(pp1aBsym, "file.fake")),
+        resolvedSymlinkToDir(parentOf(pp1bFileFake), pp1aBsym, new PathFragment("b")),
+        resolvedFile(pp1aSubdirFileB));
+  }
+
+  public void testFileDigestChangeCausesRebuild() throws Exception {
+    Artifact artifact = sourceArtifact("foo/bar.txt");
+    RootedPath path = rootedPath(artifact);
+    createFile(path, "hello");
+
+    // Assert that the SkyValue is built and looks right.
+    TraversalRequest params = fileLikeRoot(artifact, DONT_CROSS);
+    ResolvedFile expected = resolvedFile(path);
+    RecursiveFilesystemTraversalValue v1 = traverseAndAssertFiles(params, expected);
+    assertThat(progressReceiver.evaluations).contains(v1);
+    progressReceiver.clear();
+
+    // Change the digest of the file. See that the value is rebuilt.
+    appendToFile(path, "world");
+    RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(params, expected);
+    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(params));
+    assertThat(v2).isNotEqualTo(v1);
+  }
+
+  public void testFileMtimeChangeDoesNotCauseRebuildIfDigestIsUnchanged() throws Exception {
+    Artifact artifact = sourceArtifact("foo/bar.txt");
+    RootedPath path = rootedPath(artifact);
+    createFile(path, "hello");
+
+    // Assert that the SkyValue is built and looks right.
+    TraversalRequest params = fileLikeRoot(artifact, DONT_CROSS);
+    ResolvedFile expected = resolvedFile(path);
+    RecursiveFilesystemTraversalValue v1 = traverseAndAssertFiles(params, expected);
+    assertThat(progressReceiver.evaluations).contains(v1);
+    progressReceiver.clear();
+
+    // Change the mtime of the file but not the digest. See that the value is *not* rebuilt.
+    long mtime = path.asPath().getLastModifiedTime();
+    mtime += 1000000L; // more than the timestamp granularity of any filesystem
+    path.asPath().setLastModifiedTime(mtime);
+    RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(params, expected);
+    assertThat(v2).isEqualTo(v1);
+  }
+
+  public void testRegexp() throws Exception {
+    Artifact wantedArtifact = sourceArtifact("foo/bar/baz.txt");
+    Artifact unwantedArtifact = sourceArtifact("foo/boo/baztxt.bak");
+    RootedPath wantedPath = rootedPath(wantedArtifact);
+    createFile(wantedPath, "hello");
+    createFile(unwantedArtifact, "nope");
+    Artifact pkgDirArtifact = sourceArtifact("foo");
+    RootedPath dir = rootedPath(pkgDirArtifact);
+    scratch.dir(dir.asPath().getPathString());
+
+    TraversalRequest traversalRoot =
+        new TraversalRequest(
+            dir, false, PackageBoundaryMode.REPORT_ERROR, true, null, Pattern.compile(".*\\.txt"));
+
+    ResolvedFile expected = resolvedFile(wantedPath);
+    traverseAndAssertFiles(traversalRoot, expected);
+  }
+
+  public void testGeneratedDirectoryConflictsWithPackage() throws Exception {
+    Artifact genDir = derivedArtifact("a/b");
+    createFile(rootedPath(sourceArtifact("a/b/c/file.real")));
+    createFile(rootedPath(derivedArtifact("a/b/c/file.fake")));
+    createFile(sourceArtifact("a/b/c/BUILD"));
+
+    SkyKey key = rftvSkyKey(fileLikeRoot(genDir, CROSS));
+    EvaluationResult<SkyValue> result = eval(key);
+    assertThat(result.hasError()).isTrue();
+    ErrorInfo error = result.getError(key);
+    assertThat(error.isTransient()).isFalse();
+    assertThat(error.getException().getMessage())
+        .contains("Generated directory a/b/c conflicts with package under the same path.");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java
new file mode 100644
index 0000000000..ce2b84d402
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java
@@ -0,0 +1,169 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+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.skyframe.BuildDriver;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.WalkableGraph;
+
+/**
+ * Tests for {@link RecursivePkgFunction}. Unfortunately, we can't directly test
+ * RecursivePkgFunction as it uses PackageValues, and PackageFunction uses legacy stuff that
+ * isn't easily mockable. So our testing strategy is to make hacky calls to
+ * SequencedSkyframeExecutor.
+ *
+ * <p>Target parsing tests already cover most of the behavior of RecursivePkgFunction, but there
+ * are a couple of corner cases we need to test directly.
+ */
+public class RecursivePkgFunctionTest extends BuildViewTestCase {
+
+  private SkyframeExecutor skyframeExecutor;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    skyframeExecutor = getSkyframeExecutor();
+  }
+
+  private SkyKey buildRecursivePkgKey(
+      Path root, PathFragment rootRelativePath, ImmutableSet<PathFragment> excludedPaths) {
+    RootedPath rootedPath = RootedPath.toRootedPath(root, rootRelativePath);
+    return RecursivePkgValue.key(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME, rootedPath, excludedPaths);
+  }
+
+  private RecursivePkgValue buildRecursivePkgValue(Path root, PathFragment rootRelativePath)
+      throws Exception {
+    return buildRecursivePkgValue(root, rootRelativePath, ImmutableSet.<PathFragment>of());
+  }
+
+  private RecursivePkgValue buildRecursivePkgValue(
+      Path root, PathFragment rootRelativePath, ImmutableSet<PathFragment> excludedPaths)
+      throws Exception {
+    SkyKey key = buildRecursivePkgKey(root, rootRelativePath, excludedPaths);
+    return getEvaluationResult(key).get(key);
+  }
+
+  private EvaluationResult<RecursivePkgValue> getEvaluationResult(SkyKey key)
+      throws InterruptedException {
+    BuildDriver driver = skyframeExecutor.getDriverForTesting();
+    EvaluationResult<RecursivePkgValue> evaluationResult =
+        driver.evaluate(
+            ImmutableList.of(key),
+            /*keepGoing=*/ false,
+            SequencedSkyframeExecutor.DEFAULT_THREAD_COUNT,
+            reporter);
+    Preconditions.checkState(!evaluationResult.hasError());
+    return evaluationResult;
+  }
+
+  public void testStartingAtBuildFile() throws Exception {
+    scratch.file("a/b/c/BUILD");
+    RecursivePkgValue value =
+        buildRecursivePkgValue(rootDirectory, new PathFragment("a/b/c/BUILD"));
+    assertTrue(value.getPackages().isEmpty());
+  }
+
+  public void testPackagesUnderMultipleRoots() throws Exception {
+    Path root1 = rootDirectory.getRelative("root1");
+    Path root2 = rootDirectory.getRelative("root2");
+    scratch.file(root1 + "/WORKSPACE");
+    scratch.file(root2 + "/WORKSPACE");
+    scratch.file(root1 + "/a/BUILD");
+    scratch.file(root2 + "/a/b/BUILD");
+    setPackageCacheOptions("--package_path=" + "root1" + ":" + "root2");
+
+    RecursivePkgValue valueForRoot1 = buildRecursivePkgValue(root1, new PathFragment("a"));
+    String root1Pkg = Iterables.getOnlyElement(valueForRoot1.getPackages());
+    assertEquals(root1Pkg, "a");
+
+    RecursivePkgValue valueForRoot2 = buildRecursivePkgValue(root2, new PathFragment("a"));
+    String root2Pkg = Iterables.getOnlyElement(valueForRoot2.getPackages());
+    assertEquals(root2Pkg, "a/b");
+  }
+
+  public void testSubdirectoryExclusion() throws Exception {
+    // Given a package "a" with two packages below it, "a/b" and "a/c",
+    scratch.file("a/BUILD");
+    scratch.file("a/b/BUILD");
+    scratch.file("a/c/BUILD");
+
+    // When the top package is evaluated for recursive package values, and "a/b" is excluded,
+    PathFragment excludedPathFragment = new PathFragment("a/b");
+    SkyKey key =
+        buildRecursivePkgKey(
+            rootDirectory, new PathFragment("a"), ImmutableSet.of(excludedPathFragment));
+    EvaluationResult<RecursivePkgValue> evaluationResult = getEvaluationResult(key);
+    RecursivePkgValue value = evaluationResult.get(key);
+
+    // Then the package corresponding to "a/b" is not present in the result,
+    assertThat(value.getPackages()).doesNotContain("a/b");
+
+    // And the "a" package and "a/c" package are.
+    assertThat(value.getPackages()).contains("a");
+    assertThat(value.getPackages()).contains("a/c");
+
+    // Also, the computation graph does not contain a cached value for "a/b".
+    WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
+    assertFalse(
+        graph.exists(
+            buildRecursivePkgKey(
+                rootDirectory, excludedPathFragment, ImmutableSet.<PathFragment>of())));
+
+    // And the computation graph does contain a cached value for "a/c" with the empty set excluded,
+    // because that key was evaluated.
+    assertTrue(
+        graph.exists(
+            buildRecursivePkgKey(
+                rootDirectory, new PathFragment("a/c"), ImmutableSet.<PathFragment>of())));
+  }
+
+  public void testExcludedSubdirectoryGettingPassedDown() throws Exception {
+    // Given a package "a" with two packages below a directory below it, "a/b/c" and "a/b/d",
+    scratch.file("a/BUILD");
+    scratch.file("a/b/c/BUILD");
+    scratch.file("a/b/d/BUILD");
+
+    // When the top package is evaluated for recursive package values, and "a/b/c" is excluded,
+    ImmutableSet<PathFragment> excludedPaths = ImmutableSet.of(new PathFragment("a/b/c"));
+    SkyKey key = buildRecursivePkgKey(rootDirectory, new PathFragment("a"), excludedPaths);
+    EvaluationResult<RecursivePkgValue> evaluationResult = getEvaluationResult(key);
+    RecursivePkgValue value = evaluationResult.get(key);
+
+    // Then the package corresponding to the excluded subdirectory is not present in the result,
+    assertThat(value.getPackages()).doesNotContain("a/b/c");
+
+    // And the top package and other subsubdirectory package are.
+    assertThat(value.getPackages()).contains("a");
+    assertThat(value.getPackages()).contains("a/b/d");
+
+    // Also, the computation graph contains a cached value for "a/b" with "a/b/c" excluded, because
+    // "a/b/c" does live underneath "a/b".
+    WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
+    assertTrue(
+        graph.exists(buildRecursivePkgKey(rootDirectory, new PathFragment("a/b"), excludedPaths)));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
new file mode 100644
index 0000000000..4c312db139
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
@@ -0,0 +1,81 @@
+// 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.collect.ImmutableSet;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
+import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyKey;
+
+/** Tests for {@link RecursivePkgKey}. */
+public class RecursivePkgKeyTest extends BuildViewTestCase {
+
+  private SkyKey buildRecursivePkgKey(
+      RepositoryName repository,
+      PathFragment rootRelativePath,
+      ImmutableSet<PathFragment> excludedPaths) {
+    RootedPath rootedPath = RootedPath.toRootedPath(rootDirectory, rootRelativePath);
+    return RecursivePkgValue.key(repository, rootedPath, excludedPaths);
+  }
+
+  private void invalidHelper(
+      PathFragment rootRelativePath, ImmutableSet<PathFragment> excludedPaths) {
+    try {
+      buildRecursivePkgKey(
+          PackageIdentifier.DEFAULT_REPOSITORY_NAME, rootRelativePath, excludedPaths);
+      fail();
+    } catch (IllegalArgumentException expected) {
+    }
+  }
+
+  public void testValidRecursivePkgKeys() throws Exception {
+    buildRecursivePkgKey(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME,
+        new PathFragment(""),
+        ImmutableSet.<PathFragment>of());
+    buildRecursivePkgKey(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME,
+        new PathFragment(""),
+        ImmutableSet.of(new PathFragment("a")));
+
+    buildRecursivePkgKey(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME,
+        new PathFragment("a"),
+        ImmutableSet.<PathFragment>of());
+    buildRecursivePkgKey(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME,
+        new PathFragment("a"),
+        ImmutableSet.of(new PathFragment("a/b")));
+
+    buildRecursivePkgKey(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME,
+        new PathFragment("a/b"),
+        ImmutableSet.<PathFragment>of());
+    buildRecursivePkgKey(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME,
+        new PathFragment("a/b"),
+        ImmutableSet.of(new PathFragment("a/b/c")));
+  }
+
+  public void testInvalidRecursivePkgKeys() throws Exception {
+    invalidHelper(new PathFragment(""), ImmutableSet.of(new PathFragment("")));
+    invalidHelper(new PathFragment("a"), ImmutableSet.of(new PathFragment("a")));
+    invalidHelper(new PathFragment("a"), ImmutableSet.of(new PathFragment("b")));
+    invalidHelper(new PathFragment("a/b"), ImmutableSet.of(new PathFragment("a")));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
new file mode 100644
index 0000000000..282bb51afb
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
@@ -0,0 +1,786 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Objects;
+import com.google.common.base.Supplier;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import com.google.common.util.concurrent.Callables;
+import com.google.devtools.build.lib.actions.AbstractAction;
+import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionExecutionContext;
+import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Executor;
+import com.google.devtools.build.lib.actions.ResourceSet;
+import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
+import com.google.devtools.build.lib.actions.util.DummyExecutor;
+import com.google.devtools.build.lib.util.Fingerprint;
+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.skyframe.EvaluationProgressReceiver;
+import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState;
+import com.google.devtools.build.skyframe.SkyFunction.Environment;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.nio.charset.StandardCharsets;
+import java.util.Set;
+import java.util.concurrent.Callable;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import javax.annotation.Nullable;
+
+/** Tests for {@link SkyframeAwareAction}. */
+public class SkyframeAwareActionTest extends TimestampBuilderTestCase {
+  private Builder builder;
+  private Executor executor;
+  private TrackingEvaluationProgressReceiver invalidationReceiver;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    invalidationReceiver = new TrackingEvaluationProgressReceiver();
+    builder = createBuilder(inMemoryCache, 1, /*keepGoing=*/ false, invalidationReceiver);
+    executor = new DummyExecutor(rootDirectory);
+  }
+
+  private static final class TrackingEvaluationProgressReceiver
+      implements EvaluationProgressReceiver {
+
+    public static final class InvalidatedKey {
+      public final SkyKey skyKey;
+      public final InvalidationState state;
+
+      InvalidatedKey(SkyKey skyKey, InvalidationState state) {
+        this.skyKey = skyKey;
+        this.state = state;
+      }
+
+      @Override
+      public boolean equals(Object obj) {
+        return obj instanceof InvalidatedKey
+            && this.skyKey.equals(((InvalidatedKey) obj).skyKey)
+            && this.state.equals(((InvalidatedKey) obj).state);
+      }
+
+      @Override
+      public int hashCode() {
+        return Objects.hashCode(skyKey, state);
+      }
+    }
+
+    public static final class EvaluatedEntry {
+      public final SkyKey skyKey;
+      public final SkyValue value;
+      public final EvaluationState state;
+
+      EvaluatedEntry(SkyKey skyKey, SkyValue value, EvaluationState state) {
+        this.skyKey = skyKey;
+        this.value = value;
+        this.state = state;
+      }
+
+      @Override
+      public boolean equals(Object obj) {
+        return obj instanceof EvaluatedEntry
+            && this.skyKey.equals(((EvaluatedEntry) obj).skyKey)
+            && this.value.equals(((EvaluatedEntry) obj).value)
+            && this.state.equals(((EvaluatedEntry) obj).state);
+      }
+
+      @Override
+      public int hashCode() {
+        return Objects.hashCode(skyKey, value, state);
+      }
+    }
+
+    public final Set<InvalidatedKey> invalidated = Sets.newConcurrentHashSet();
+    public final Set<SkyKey> enqueued = Sets.newConcurrentHashSet();
+    public final Set<EvaluatedEntry> evaluated = Sets.newConcurrentHashSet();
+
+    public void reset() {
+      invalidated.clear();
+      enqueued.clear();
+      evaluated.clear();
+    }
+
+    public boolean wasInvalidated(SkyKey skyKey) {
+      for (InvalidatedKey e : invalidated) {
+        if (e.skyKey.equals(skyKey)) {
+          return true;
+        }
+      }
+      return false;
+    }
+
+    public EvaluatedEntry getEvalutedEntry(SkyKey forKey) {
+      for (EvaluatedEntry e : evaluated) {
+        if (e.skyKey.equals(forKey)) {
+          return e;
+        }
+      }
+      return null;
+    }
+
+    @Override
+    public void invalidated(SkyKey skyKey, InvalidationState state) {
+      invalidated.add(new InvalidatedKey(skyKey, state));
+    }
+
+    @Override
+    public void enqueueing(SkyKey skyKey) {
+      enqueued.add(skyKey);
+    }
+
+    @Override
+    public void computed(SkyKey skyKey, long elapsedTimeNanos) {}
+
+    @Override
+    public void evaluated(
+        SkyKey skyKey, Supplier<SkyValue> skyValueSupplier, EvaluationState state) {
+      evaluated.add(new EvaluatedEntry(skyKey, skyValueSupplier.get(), state));
+    }
+  }
+
+  /** A mock action that counts how many times it was executed. */
+  private static class ExecutionCountingAction extends AbstractAction {
+    private final AtomicInteger executionCounter;
+
+    ExecutionCountingAction(Artifact input, Artifact output, AtomicInteger executionCounter) {
+      super(ActionsTestUtil.NULL_ACTION_OWNER, ImmutableList.of(input), ImmutableList.of(output));
+      this.executionCounter = executionCounter;
+    }
+
+    @Override
+    public void execute(ActionExecutionContext actionExecutionContext)
+        throws ActionExecutionException, InterruptedException {
+      executionCounter.incrementAndGet();
+
+      // This action first reads its input file (there can be only one). For the purpose of these
+      // tests we assume that the input file is short, maybe just 10 bytes long.
+      byte[] input = new byte[10];
+      int inputLen = 0;
+      try (InputStream in = Iterables.getOnlyElement(getInputs()).getPath().getInputStream()) {
+        inputLen = in.read(input);
+      } catch (IOException e) {
+        throw new ActionExecutionException(e, this, false);
+      }
+
+      // This action then writes the contents of the input to the (only) output file, and appends an
+      // extra "x" character too.
+      try (OutputStream out = getPrimaryOutput().getPath().getOutputStream()) {
+        out.write(input, 0, inputLen);
+        out.write('x');
+      } catch (IOException e) {
+        throw new ActionExecutionException(e, this, false);
+      }
+    }
+
+    @Override
+    public String describeStrategy(Executor executor) {
+      return null;
+    }
+
+    @Override
+    public String getMnemonic() {
+      return null;
+    }
+
+    @Override
+    protected String computeKey() {
+      return getPrimaryOutput().getExecPathString() + executionCounter.get();
+    }
+
+    @Override
+    public ResourceSet estimateResourceConsumption(Executor executor) {
+      return ResourceSet.ZERO;
+    }
+  }
+
+  private static class ExecutionCountingCacheBypassingAction extends ExecutionCountingAction {
+    ExecutionCountingCacheBypassingAction(
+        Artifact input, Artifact output, AtomicInteger executionCounter) {
+      super(input, output, executionCounter);
+    }
+
+    @Override
+    public boolean executeUnconditionally() {
+      return true;
+    }
+
+    @Override
+    public boolean isVolatile() {
+      return true;
+    }
+  }
+
+  /** A mock skyframe-aware action that counts how many times it was executed. */
+  private static class SkyframeAwareExecutionCountingAction
+      extends ExecutionCountingCacheBypassingAction implements SkyframeAwareAction {
+    private final SkyKey actionDepKey;
+
+    SkyframeAwareExecutionCountingAction(
+        Artifact input, Artifact output, AtomicInteger executionCounter, SkyKey actionDepKey) {
+      super(input, output, executionCounter);
+      this.actionDepKey = actionDepKey;
+    }
+
+    @Override
+    public void establishSkyframeDependencies(Environment env) throws ExceptionBase {
+      // Establish some Skyframe dependency. A real action would then use this to compute and
+      // cache data for the execute(...) method.
+      env.getValue(actionDepKey);
+    }
+  }
+
+  private interface ExecutionCountingActionFactory {
+    ExecutionCountingAction create(Artifact input, Artifact output, AtomicInteger executionCounter);
+  }
+
+  private enum ChangeArtifact {
+    DONT_CHANGE,
+    CHANGE_MTIME {
+      @Override
+      boolean changeMtime() {
+        return true;
+      }
+    },
+    CHANGE_MTIME_AND_CONTENT {
+      @Override
+      boolean changeMtime() {
+        return true;
+      }
+
+      @Override
+      boolean changeContent() {
+        return true;
+      }
+    };
+
+    boolean changeMtime() {
+      return false;
+    }
+
+    boolean changeContent() {
+      return false;
+    }
+  }
+
+  private enum ExpectActionIs {
+    NOT_DIRTIED {
+      @Override
+      boolean actuallyClean() {
+        return true;
+      }
+    },
+    DIRTIED_BUT_VERIFIED_CLEAN {
+      @Override
+      boolean dirtied() {
+        return true;
+      }
+
+      @Override
+      boolean actuallyClean() {
+        return true;
+      }
+    },
+
+    // REBUILT_BUT_ACTION_CACHE_HIT,
+    // This would be a bug, symptom of a skyframe-aware action that doesn't bypass the action cache
+    // and is incorrectly regarded as an action cache hit when its inputs stayed the same but its
+    // "skyframe dependencies" changed.
+
+    REEXECUTED {
+      @Override
+      boolean dirtied() {
+        return true;
+      }
+
+      @Override
+      boolean reexecuted() {
+        return true;
+      }
+    };
+
+    boolean dirtied() {
+      return false;
+    }
+
+    boolean actuallyClean() {
+      return false;
+    }
+
+    boolean reexecuted() {
+      return false;
+    }
+  }
+
+  private void maybeChangeFile(Artifact file, ChangeArtifact changeRequest) throws Exception {
+    if (changeRequest == ChangeArtifact.DONT_CHANGE) {
+      return;
+    }
+
+    if (changeRequest.changeMtime()) {
+      // 1000000 should be larger than the filesystem timestamp granularity.
+      file.getPath().setLastModifiedTime(file.getPath().getLastModifiedTime() + 1000000);
+      tsgm.waitForTimestampGranularity(reporter.getOutErr());
+    }
+
+    if (changeRequest.changeContent()) {
+      appendToFile(file.getPath());
+    }
+
+    // Invalidate the file state value to inform Skyframe that the file may have changed.
+    // This will also invalidate the action execution value.
+    differencer.invalidate(
+        ImmutableList.of(
+            FileStateValue.key(
+                RootedPath.toRootedPath(file.getRoot().getPath(), file.getRootRelativePath()))));
+  }
+
+  private void assertActionExecutions(
+      ExecutionCountingActionFactory actionFactory,
+      ChangeArtifact changeActionInput,
+      Callable<Void> betweenBuilds,
+      ExpectActionIs expectActionIs)
+      throws Exception {
+    // Set up the action's input, output, owner and most importantly the execution counter.
+    Artifact actionInput = createSourceArtifact("foo/action-input.txt");
+    Artifact actionOutput = createDerivedArtifact("foo/action-output.txt");
+    AtomicInteger executionCounter = new AtomicInteger(0);
+
+    scratch.file(actionInput.getPath().getPathString(), "foo");
+
+    // Generating actions of artifacts are found by looking them up in the graph. The lookup value
+    // must be present in the graph before execution.
+    Action action = actionFactory.create(actionInput, actionOutput, executionCounter);
+    registerAction(action);
+
+    // Build the output for the first time.
+    builder.buildArtifacts(
+        reporter,
+        ImmutableSet.of(actionOutput),
+        null,
+        null,
+        null,
+        null,
+        executor,
+        null,
+        false,
+        null);
+
+    // Sanity check that our invalidation receiver is working correctly. We'll rely on it again.
+    SkyKey actionKey = ActionExecutionValue.key(action);
+    TrackingEvaluationProgressReceiver.EvaluatedEntry evaluatedAction =
+        invalidationReceiver.getEvalutedEntry(actionKey);
+    assertThat(evaluatedAction).isNotNull();
+    SkyValue actionValue = evaluatedAction.value;
+
+    // Mutate the action input if requested.
+    maybeChangeFile(actionInput, changeActionInput);
+
+    // Execute user code before next build.
+    betweenBuilds.call();
+
+    // Rebuild the output.
+    invalidationReceiver.reset();
+    builder.buildArtifacts(
+        reporter,
+        ImmutableSet.of(actionOutput),
+        null,
+        null,
+        null,
+        null,
+        executor,
+        null,
+        false,
+        null);
+
+    if (expectActionIs.dirtied()) {
+      assertThat(invalidationReceiver.wasInvalidated(actionKey)).isTrue();
+
+      TrackingEvaluationProgressReceiver.EvaluatedEntry newEntry =
+          invalidationReceiver.getEvalutedEntry(actionKey);
+      assertThat(newEntry).isNotNull();
+      if (expectActionIs.actuallyClean()) {
+        // Action was dirtied but verified clean.
+        assertThat(newEntry.state).isEqualTo(EvaluationState.CLEAN);
+        assertThat(newEntry.value).isEqualTo(actionValue);
+      } else {
+        // Action was dirtied and rebuilt. It was either reexecuted or was an action cache hit,
+        // doesn't matter here.
+        assertThat(newEntry.state).isEqualTo(EvaluationState.BUILT);
+        assertThat(newEntry.value).isNotEqualTo(actionValue);
+      }
+    } else {
+      // Action was not dirtied.
+      assertThat(invalidationReceiver.wasInvalidated(actionKey)).isFalse();
+    }
+
+    // Assert that the action was executed the right number of times. Whether the action execution
+    // function was called again is up for the test method to verify.
+    assertThat(executionCounter.get()).isEqualTo(expectActionIs.reexecuted() ? 2 : 1);
+  }
+
+  private RootedPath createSkyframeDepOfAction() throws Exception {
+    scratch.file(rootDirectory.getRelative("action.dep").getPathString(), "blah");
+    return RootedPath.toRootedPath(rootDirectory, new PathFragment("action.dep"));
+  }
+
+  private void appendToFile(Path path) throws Exception {
+    try (OutputStream stm = path.getOutputStream(/*append=*/ true)) {
+      stm.write("blah".getBytes(StandardCharsets.UTF_8));
+    }
+  }
+
+  public void testCacheCheckingActionWithContentChangingInput() throws Exception {
+    assertActionWithContentChangingInput(/* unconditionalExecution */ false);
+  }
+
+  public void testCacheBypassingActionWithContentChangingInput() throws Exception {
+    assertActionWithContentChangingInput(/* unconditionalExecution */ true);
+  }
+
+  private void assertActionWithContentChangingInput(final boolean unconditionalExecution)
+      throws Exception {
+    // Assert that a simple, non-skyframe-aware action is executed twice
+    // if its input's content changes between builds.
+    assertActionExecutions(
+        new ExecutionCountingActionFactory() {
+          @Override
+          public ExecutionCountingAction create(
+              Artifact input, Artifact output, AtomicInteger executionCounter) {
+            return unconditionalExecution
+                ? new ExecutionCountingCacheBypassingAction(input, output, executionCounter)
+                : new ExecutionCountingAction(input, output, executionCounter);
+          }
+        },
+        ChangeArtifact.CHANGE_MTIME_AND_CONTENT,
+        Callables.<Void>returning(null),
+        ExpectActionIs.REEXECUTED);
+  }
+
+  public void testCacheCheckingActionWithMtimeChangingInput() throws Exception {
+    assertActionWithMtimeChangingInput(/* unconditionalExecution */ false);
+  }
+
+  public void testCacheBypassingActionWithMtimeChangingInput() throws Exception {
+    assertActionWithMtimeChangingInput(/* unconditionalExecution */ true);
+  }
+
+  private void assertActionWithMtimeChangingInput(final boolean unconditionalExecution)
+      throws Exception {
+    // Assert that a simple, non-skyframe-aware action is executed only once
+    // if its input's mtime changes but its contents stay the same between builds.
+    assertActionExecutions(
+        new ExecutionCountingActionFactory() {
+          @Override
+          public ExecutionCountingAction create(
+              Artifact input, Artifact output, AtomicInteger executionCounter) {
+            return unconditionalExecution
+                ? new ExecutionCountingCacheBypassingAction(input, output, executionCounter)
+                : new ExecutionCountingAction(input, output, executionCounter);
+          }
+        },
+        ChangeArtifact.CHANGE_MTIME,
+        Callables.<Void>returning(null),
+        ExpectActionIs.DIRTIED_BUT_VERIFIED_CLEAN);
+  }
+
+  public void testActionWithNonChangingInput(final boolean unconditionalExecution)
+      throws Exception {
+    // Assert that a simple, non-skyframe-aware action is executed only once
+    // if its input does not change at all between builds.
+    assertActionExecutions(
+        new ExecutionCountingActionFactory() {
+          @Override
+          public ExecutionCountingAction create(
+              Artifact input, Artifact output, AtomicInteger executionCounter) {
+            return unconditionalExecution
+                ? new ExecutionCountingCacheBypassingAction(input, output, executionCounter)
+                : new ExecutionCountingAction(input, output, executionCounter);
+          }
+        },
+        ChangeArtifact.DONT_CHANGE,
+        Callables.<Void>returning(null),
+        ExpectActionIs.NOT_DIRTIED);
+  }
+
+  private void assertActionWithMaybeChangingInputAndChangingSkyframeDeps(
+      ChangeArtifact changeInputFile) throws Exception {
+    final RootedPath depPath = createSkyframeDepOfAction();
+    final SkyKey skyframeDep = FileStateValue.key(depPath);
+
+    // Assert that an action-cache-check-bypassing action is executed twice if its skyframe deps
+    // change while its input does not. The skyframe dependency is established by making the action
+    // skyframe-aware and updating the value between builds.
+    assertActionExecutions(
+        new ExecutionCountingActionFactory() {
+          @Override
+          public ExecutionCountingAction create(
+              Artifact input, Artifact output, AtomicInteger executionCounter) {
+            return new SkyframeAwareExecutionCountingAction(
+                input, output, executionCounter, skyframeDep);
+          }
+        },
+        changeInputFile,
+        new Callable<Void>() {
+          @Override
+          public Void call() throws Exception {
+            // Invalidate the dependency and change what its value will be in the next build. This
+            // should enforce rebuilding of the action.
+            appendToFile(depPath.asPath());
+            differencer.invalidate(ImmutableList.of(skyframeDep));
+            return null;
+          }
+        },
+        ExpectActionIs.REEXECUTED);
+  }
+
+  public void testActionWithNonChangingInputButChangingSkyframeDeps() throws Exception {
+    assertActionWithMaybeChangingInputAndChangingSkyframeDeps(ChangeArtifact.DONT_CHANGE);
+  }
+
+  public void testActionWithChangingInputMtimeAndChangingSkyframeDeps() throws Exception {
+    assertActionWithMaybeChangingInputAndChangingSkyframeDeps(ChangeArtifact.CHANGE_MTIME);
+  }
+
+  public void testActionWithChangingInputAndChangingSkyframeDeps() throws Exception {
+    assertActionWithMaybeChangingInputAndChangingSkyframeDeps(
+        ChangeArtifact.CHANGE_MTIME_AND_CONTENT);
+  }
+
+  public void testActionWithNonChangingInputAndNonChangingSkyframeDeps() throws Exception {
+    final SkyKey skyframeDep = FileStateValue.key(createSkyframeDepOfAction());
+
+    // Assert that an action-cache-check-bypassing action is executed only once if neither its input
+    // nor its Skyframe dependency changes between builds.
+    assertActionExecutions(
+        new ExecutionCountingActionFactory() {
+          @Override
+          public ExecutionCountingAction create(
+              Artifact input, Artifact output, AtomicInteger executionCounter) {
+            return new SkyframeAwareExecutionCountingAction(
+                input, output, executionCounter, skyframeDep);
+          }
+        },
+        ChangeArtifact.DONT_CHANGE,
+        new Callable<Void>() {
+          @Override
+          public Void call() throws Exception {
+            // Invalidate the dependency but leave its value up-to-date, so the action should not
+            // be rebuilt.
+            differencer.invalidate(ImmutableList.of(skyframeDep));
+            return null;
+          }
+        },
+        ExpectActionIs.DIRTIED_BUT_VERIFIED_CLEAN);
+  }
+
+  private abstract static class SingleOutputAction extends AbstractAction {
+    SingleOutputAction(@Nullable Artifact input, Artifact output) {
+      super(
+          ActionsTestUtil.NULL_ACTION_OWNER,
+          input == null ? ImmutableList.<Artifact>of() : ImmutableList.of(input),
+          ImmutableList.of(output));
+    }
+
+    protected static final class Buffer {
+      final int size;
+      final byte[] data;
+
+      Buffer(byte[] data, int size) {
+        this.data = data;
+        this.size = size;
+      }
+    }
+
+    protected Buffer readInput() throws ActionExecutionException {
+      byte[] input = new byte[100];
+      int inputLen = 0;
+      try (InputStream in = getPrimaryInput().getPath().getInputStream()) {
+        inputLen = in.read(input, 0, input.length);
+      } catch (IOException e) {
+        throw new ActionExecutionException(e, this, false);
+      }
+      return new Buffer(input, inputLen);
+    }
+
+    protected void writeOutput(@Nullable Buffer buf, String data) throws ActionExecutionException {
+      try (OutputStream out = getPrimaryOutput().getPath().getOutputStream()) {
+        if (buf != null) {
+          out.write(buf.data, 0, buf.size);
+        }
+        out.write(data.getBytes(StandardCharsets.UTF_8), 0, data.length());
+      } catch (IOException e) {
+        throw new ActionExecutionException(e, this, false);
+      }
+    }
+
+    @Override
+    public String describeStrategy(Executor executor) {
+      return null;
+    }
+
+    @Override
+    public String getMnemonic() {
+      return "MockActionMnemonic";
+    }
+
+    @Override
+    protected String computeKey() {
+      return new Fingerprint().addInt(42).hexDigestAndReset();
+    }
+
+    @Override
+    public ResourceSet estimateResourceConsumption(Executor executor) {
+      return ResourceSet.ZERO;
+    }
+  }
+
+  private abstract static class SingleOutputSkyframeAwareAction extends SingleOutputAction
+      implements SkyframeAwareAction {
+    SingleOutputSkyframeAwareAction(@Nullable Artifact input, Artifact output) {
+      super(input, output);
+    }
+
+    @Override
+    public boolean executeUnconditionally() {
+      return true;
+    }
+
+    @Override
+    public boolean isVolatile() {
+      return true;
+    }
+  }
+
+  /**
+   * Regression test to avoid a potential race condition in {@link ActionExecutionFunction}.
+   *
+   * <p>The test ensures that when ActionExecutionFunction executes a Skyframe-aware action
+   * (implementor of {@link SkyframeAwareAction}), ActionExecutionFunction first requests the inputs
+   * of the action and ensures they are built before requesting any of its Skyframe dependencies.
+   *
+   * <p>This strict ordering is very important to avoid the race condition, which could arise if the
+   * compute method were too eager to request all dependencies: request input files but even if some
+   * are missing, request also the skyframe-dependencies. The race is described in this method's
+   * body.
+   */
+  public void testRaceConditionBetweenInputAcquisitionAndSkyframeDeps() throws Exception {
+    // Sequence of events on threads A and B, showing SkyFunctions and requested SkyKeys, leading
+    // to an InconsistentFilesystemException:
+    //
+    // _______________[Thread A]_________________|_______________[Thread B]_________________
+    // ActionExecutionFunction(gen2_action:      | idle
+    //   genfiles/gen1 -> genfiles/foo/bar/gen2) |
+    // ARTIFACT:genfiles/gen1                    |
+    // MOCK_VALUE:dummy_argument                 |
+    // env.valuesMissing():yes ==> return        |
+    //                                           |
+    // ArtifactFunction(genfiles/gen1)           | MockFunction()
+    // CONFIGURED_TARGET://foo:gen1              | FILE:genfiles/foo
+    // ACTION_EXECUTION:gen1_action              | env.valuesMissing():yes ==> return
+    // env.valuesMissing():yes ==> return        |
+    //                                           | FileFunction(genfiles/foo)
+    // ActionExecutionFunction(gen1_action)      | FILE:genfiles
+    // ARTIFACT:genfiles/gen0                    | env.valuesMissing():yes ==> return
+    // env.valuesMissing():yes ==> return        |
+    //                                           | FileFunction(genfiles)
+    // ArtifactFunction(genfiles/gen0)           | FILE_STATE:genfiles
+    // CONFIGURED_TARGET://foo:gen0              | env.valuesMissing():yes ==> return
+    // ACTION_EXECUTION:gen0_action              |
+    // env.valuesMissing():yes ==> return        | FileStateFunction(genfiles)
+    //                                           | stat genfiles
+    // ActionExecutionFunction(gen0_action)      | return FileStateValue:non-existent
+    // create output directory: genfiles         |
+    // working                                   | FileFunction(genfiles/foo)
+    //                                           | FILE:genfiles
+    //                                           | FILE_STATE:genfiles/foo
+    //                                           | env.valuesMissing():yes ==> return
+    //                                           |
+    //                                           | FileStateFunction(genfiles/foo)
+    //                                           | stat genfiles/foo
+    //                                           | return FileStateValue:non-existent
+    //                                           |
+    // done, created genfiles/gen0               | FileFunction(genfiles/foo)
+    // return ActionExecutionValue(gen0_action)  | FILE:genfiles
+    //                                           | FILE_STATE:genfiles/foo
+    // ArtifactFunction(genfiles/gen0)           | return FileValue(genfiles/foo:non-existent)
+    // CONFIGURED_TARGET://foo:gen0              |
+    // ACTION_EXECUTION:gen0_action              | MockFunction()
+    // return ArtifactValue(genfiles/gen0)       | FILE:genfiles/foo
+    //                                           | FILE:genfiles/foo/bar/gen1
+    // ActionExecutionFunction(gen1_action)      | env.valuesMissing():yes ==> return
+    // ARTIFACT:genfiles/gen0                    |
+    // create output directory: genfiles/foo/bar | FileFunction(genfiles/foo/bar/gen1)
+    // done, created genfiles/foo/bar/gen1       | FILE:genfiles/foo/bar
+    // return ActionExecutionValue(gen1_action)  | env.valuesMissing():yes ==> return
+    //                                           |
+    // idle                                      | FileFunction(genfiles/foo/bar)
+    //                                           | FILE:genfiles/foo
+    //                                           | FILE_STATE:genfiles/foo/bar
+    //                                           | env.valuesMissing():yes ==> return
+    //                                           |
+    //                                           | FileStateFunction(genfiles/foo/bar)
+    //                                           | stat genfiles/foo/bar
+    //                                           | return FileStateValue:directory
+    //                                           |
+    //                                           | FileFunction(genfiles/foo/bar)
+    //                                           | FILE:genfiles/foo
+    //                                           | FILE_STATE:genfiles/foo/bar
+    //                                           | throw InconsistentFilesystemException:
+    //                                           |     genfiles/foo doesn't exist but
+    //                                           |     genfiles/foo/bar does!
+
+    Artifact genFile1 = createDerivedArtifact("foo/bar/gen1.txt");
+    Artifact genFile2 = createDerivedArtifact("gen2.txt");
+
+    registerAction(
+        new SingleOutputAction(null, genFile1) {
+          @Override
+          public void execute(ActionExecutionContext actionExecutionContext)
+              throws ActionExecutionException, InterruptedException {
+            writeOutput(null, "gen1");
+          }
+        });
+
+    registerAction(
+        new SingleOutputSkyframeAwareAction(genFile1, genFile2) {
+          @Override
+          public void establishSkyframeDependencies(Environment env) throws ExceptionBase {
+            assertThat(env.valuesMissing()).isFalse();
+          }
+
+          @Override
+          public void execute(ActionExecutionContext actionExecutionContext)
+              throws ActionExecutionException, InterruptedException {
+            writeOutput(readInput(), "gen2");
+          }
+        });
+
+    builder.buildArtifacts(
+        reporter, ImmutableSet.of(genFile2), null, null, null, null, executor, null, false, null);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkFileContentHashTests.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkFileContentHashTests.java
new file mode 100644
index 0000000000..29470dda85
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkFileContentHashTests.java
@@ -0,0 +1,165 @@
+// 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.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.packages.ConstantRuleVisibility;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.SkyKey;
+
+import java.util.Collection;
+import java.util.UUID;
+
+/**
+ * Tests for the hash code calculated for Skylark RuleClasses based on the transitive closure
+ * of the imports of their respective definition SkylarkEnvironments.
+ */
+public class SkylarkFileContentHashTests extends BuildViewTestCase {
+
+  @Override
+  public void setUp() throws Exception {
+    super.setUp();
+    scratch.file("foo/BUILD");
+    scratch.file("bar/BUILD");
+    scratch.file("helper/BUILD");
+
+    scratch.file("helper/ext.bzl", "def rule_impl(ctx):", "  return None");
+
+    scratch.file(
+        "foo/ext.bzl",
+        "load('/helper/ext', 'rule_impl')",
+        "",
+        "foo1 = rule(implementation = rule_impl)",
+        "foo2 = rule(implementation = rule_impl)");
+
+    scratch.file(
+        "bar/ext.bzl",
+        "load('/helper/ext', 'rule_impl')",
+        "",
+        "bar1 = rule(implementation = rule_impl)");
+
+    scratch.file(
+        "pkg/BUILD",
+        "load('/foo/ext', 'foo1')",
+        "load('/foo/ext', 'foo2')",
+        "load('/bar/ext', 'bar1')",
+        "",
+        "foo1(name = 'foo1')",
+        "foo2(name = 'foo2')",
+        "bar1(name = 'bar1')");
+  }
+
+  public void testHashInvariance() throws Exception {
+    assertEquals(getHash("pkg", "foo1"), getHash("pkg", "foo1"));
+  }
+
+  public void testHashInvarianceAfterOverwritingFileWithSameContents() throws Exception {
+    String bar1 = getHash("pkg", "bar1");
+    scratch.overwriteFile(
+        "bar/ext.bzl",
+        "load('/helper/ext', 'rule_impl')",
+        "",
+        "bar1 = rule(implementation = rule_impl)");
+    invalidatePackages();
+    assertEquals(bar1, getHash("pkg", "bar1"));
+  }
+
+  public void testHashSameForRulesDefinedInSameFile() throws Exception {
+    assertEquals(getHash("pkg", "foo1"), getHash("pkg", "foo2"));
+  }
+
+  public void testHashNotSameForRulesDefinedInDifferentFiles() throws Exception {
+    assertNotEquals(getHash("pkg", "foo1"), getHash("pkg", "bar1"));
+  }
+
+  public void testImmediateFileChangeChangesHash() throws Exception {
+    String bar1 = getHash("pkg", "bar1");
+    scratch.overwriteFile(
+        "bar/ext.bzl",
+        "load('/helper/ext', 'rule_impl')",
+        "# Some comments to change file hash",
+        "",
+        "bar1 = rule(implementation = rule_impl)");
+    invalidatePackages();
+    assertNotEquals(bar1, getHash("pkg", "bar1"));
+  }
+
+  public void testTransitiveFileChangeChangesHash() throws Exception {
+    String bar1 = getHash("pkg", "bar1");
+    String foo1 = getHash("pkg", "foo1");
+    String foo2 = getHash("pkg", "foo2");
+    scratch.overwriteFile(
+        "helper/ext.bzl",
+        "# Some comments to change file hash",
+        "def rule_impl(ctx):",
+        "  return None");
+    invalidatePackages();
+    assertNotEquals(bar1, getHash("pkg", "bar1"));
+    assertNotEquals(foo1, getHash("pkg", "foo1"));
+    assertNotEquals(foo2, getHash("pkg", "foo2"));
+  }
+
+  public void testFileChangeDoesNotAffectRulesDefinedOutsideOfTransitiveClosure() throws Exception {
+    String foo1 = getHash("pkg", "foo1");
+    String foo2 = getHash("pkg", "foo2");
+    scratch.overwriteFile(
+        "bar/ext.bzl",
+        "load('/helper/ext', 'rule_impl')",
+        "# Some comments to change file hash",
+        "",
+        "bar1 = rule(implementation = rule_impl)");
+    invalidatePackages();
+    assertEquals(foo1, getHash("pkg", "foo1"));
+    assertEquals(foo2, getHash("pkg", "foo2"));
+  }
+
+  private void assertNotEquals(String hash, String hash2) {
+    assertFalse(hash.equals(hash2));
+  }
+
+  /**
+   * Returns the hash code of the rule target defined by the pkg and the target name parameters.
+   * Asserts that the targets and it's Skylark dependencies were loaded properly.
+   */
+  private String getHash(String pkg, String name) throws Exception {
+    getSkyframeExecutor()
+        .preparePackageLoading(
+            new PathPackageLocator(rootDirectory),
+            ConstantRuleVisibility.PUBLIC,
+            true,
+            7,
+            "",
+            UUID.randomUUID());
+    SkyKey pkgLookupKey = PackageValue.key(PackageIdentifier.parse(pkg));
+    EvaluationResult<PackageValue> result =
+        SkyframeExecutorTestUtils.evaluate(
+            getSkyframeExecutor(), pkgLookupKey, /*keepGoing=*/ false, reporter);
+    assertFalse(result.hasError());
+    Collection<Target> targets = result.get(pkgLookupKey).getPackage().getTargets();
+    for (Target target : targets) {
+      if (target.getName().equals(name)) {
+        return ((Rule) target)
+            .getRuleClassObject()
+            .getRuleDefinitionEnvironment()
+            .getTransitiveContentHashCode();
+      }
+    }
+    throw new IllegalStateException("target not found: " + name);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunctionTest.java
new file mode 100644
index 0000000000..abd94d9f27
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunctionTest.java
@@ -0,0 +1,141 @@
+// 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.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.packages.ConstantRuleVisibility;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.skyframe.ErrorInfo;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.SkyKey;
+
+import java.util.UUID;
+
+/**
+ * Tests for SkylarkImportLookupFunction.
+ */
+public class SkylarkImportLookupFunctionTest extends BuildViewTestCase {
+
+  @Override
+  public void setUp() throws Exception {
+    super.setUp();
+    Path alternativeRoot = scratch.dir("/root_2");
+    getSkyframeExecutor()
+        .preparePackageLoading(
+            new PathPackageLocator(rootDirectory, alternativeRoot),
+            ConstantRuleVisibility.PUBLIC,
+            true,
+            7,
+            "",
+            UUID.randomUUID());
+  }
+
+  public void testSkylarkImportLabels() throws Exception {
+    scratch.file("pkg1/BUILD");
+    scratch.file("pkg1/ext.bzl");
+    checkLabel("pkg1/ext.bzl", "//pkg1:ext.bzl");
+
+    scratch.file("pkg2/BUILD");
+    scratch.file("pkg2/dir/ext.bzl");
+    checkLabel("pkg2/dir/ext.bzl", "//pkg2:dir/ext.bzl");
+
+    scratch.file("dir/pkg3/BUILD");
+    scratch.file("dir/pkg3/dir/ext.bzl");
+    checkLabel("dir/pkg3/dir/ext.bzl", "//dir/pkg3:dir/ext.bzl");
+  }
+
+  public void testSkylarkImportLabelsAlternativeRoot() throws Exception {
+    scratch.file("/root_2/pkg4/BUILD");
+    scratch.file("/root_2/pkg4/ext.bzl");
+    checkLabel("pkg4/ext.bzl", "//pkg4:ext.bzl");
+  }
+
+  public void testSkylarkImportLabelsMultipleRoot_1() throws Exception {
+    scratch.file("pkg5/BUILD");
+    scratch.file("/root_2/pkg5/ext.bzl");
+    checkLabel("pkg5/ext.bzl", "//pkg5:ext.bzl");
+  }
+
+  public void testSkylarkImportLabelsMultipleRoot_2() throws Exception {
+    scratch.file("/root_2/pkg6/BUILD");
+    scratch.file("pkg6/ext.bzl");
+    checkLabel("pkg6/ext.bzl", "//pkg6:ext.bzl");
+  }
+
+  public void testSkylarkImportLabelsMultipleBuildFiles() throws Exception {
+    scratch.file("dir1/BUILD");
+    scratch.file("dir1/dir2/BUILD");
+    scratch.file("dir1/dir2/ext.bzl");
+    checkLabel("dir1/dir2/ext.bzl", "//dir1/dir2:ext.bzl");
+  }
+
+  public void testLoadRelativePath() throws Exception {
+    scratch.file("pkg/BUILD");
+    scratch.file("pkg/ext1.bzl", "a = 1");
+    scratch.file("pkg/ext2.bzl", "load('ext1', 'a')");
+    get(key("pkg/ext2.bzl"));
+  }
+
+  public void testLoadAbsolutePath() throws Exception {
+    scratch.file("pkg2/BUILD");
+    scratch.file("pkg3/BUILD");
+    scratch.file("pkg2/ext.bzl", "b = 1");
+    scratch.file("pkg3/ext.bzl", "load('/pkg2/ext', 'b')");
+    get(key("pkg3/ext.bzl"));
+  }
+
+  private EvaluationResult<SkylarkImportLookupValue> get(SkyKey skylarkImportLookupKey)
+      throws Exception {
+    EvaluationResult<SkylarkImportLookupValue> result =
+        SkyframeExecutorTestUtils.evaluate(
+            getSkyframeExecutor(), skylarkImportLookupKey, /*keepGoing=*/ false, reporter);
+    if (result.hasError()) {
+      fail(result.getError(skylarkImportLookupKey).getException().getMessage());
+    }
+    return result;
+  }
+
+  private SkyKey key(String file) throws Exception {
+    return SkylarkImportLookupValue.key(
+        PackageIdentifier.createInDefaultRepo(new PathFragment(file)));
+  }
+
+  private void checkLabel(String file, String label) throws Exception {
+    SkyKey skylarkImportLookupKey = key(file);
+    EvaluationResult<SkylarkImportLookupValue> result = get(skylarkImportLookupKey);
+    assertEquals(label, result.get(skylarkImportLookupKey).getDependency().getLabel().toString());
+  }
+
+  public void testSkylarkImportLookupNoBuildFile() throws Exception {
+    scratch.file("pkg/ext.bzl", "");
+    SkyKey skylarkImportLookupKey =
+        SkylarkImportLookupValue.key(
+            PackageIdentifier.createInDefaultRepo(new PathFragment("pkg/ext.bzl")));
+    EvaluationResult<SkylarkImportLookupValue> result =
+        SkyframeExecutorTestUtils.evaluate(
+            getSkyframeExecutor(), skylarkImportLookupKey, /*keepGoing=*/ false, reporter);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skylarkImportLookupKey);
+    String errorMessage = errorInfo.getException().getMessage();
+    assertEquals(
+        "Every .bzl file must have a corresponding package, but 'pkg/ext.bzl' "
+            + "does not have one. Please create a BUILD file in the same or any parent directory. "
+            + "Note that this BUILD file does not need to do anything except exist.",
+        errorMessage);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TargetMarkerFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TargetMarkerFunctionTest.java
new file mode 100644
index 0000000000..8ac667f2cb
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TargetMarkerFunctionTest.java
@@ -0,0 +1,154 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Maps;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
+import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.vfs.FileStatus;
+import com.google.devtools.build.lib.vfs.FileSystem;
+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.lib.vfs.inmemoryfs.InMemoryFileSystem;
+import com.google.devtools.build.skyframe.ErrorInfo;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.SkyKey;
+
+import java.io.IOException;
+import java.util.Map;
+
+/**
+ * Tests for {@link TargetMarkerFunction}. Unfortunately, we can't directly test
+ * TargetMarkerFunction as it uses PackageValues, and PackageFunction uses legacy stuff
+ * that isn't easily mockable. So our testing strategy is to make hacky calls to SkyframeExecutor.
+ */
+public class TargetMarkerFunctionTest extends BuildViewTestCase {
+
+  private SkyframeExecutor skyframeExecutor;
+  private CustomInMemoryFs fs = new CustomInMemoryFs();
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    skyframeExecutor = getSkyframeExecutor();
+  }
+
+  @Override
+  protected FileSystem createFileSystem() {
+    return fs;
+  }
+
+  private SkyKey skyKey(String labelName) throws Exception {
+    return TargetMarkerValue.key(Label.parseAbsolute(labelName));
+  }
+
+  private Throwable getErrorFromTargetValue(String labelName) throws Exception {
+    reporter.removeHandler(failFastHandler);
+    SkyKey targetKey = TargetMarkerValue.key(Label.parseAbsolute(labelName));
+    EvaluationResult<TargetMarkerValue> evaluationResult =
+        SkyframeExecutorTestUtils.evaluate(
+            skyframeExecutor, targetKey, /*keepGoing=*/ false, reporter);
+    Preconditions.checkState(evaluationResult.hasError());
+    reporter.addHandler(failFastHandler);
+    ErrorInfo errorInfo = evaluationResult.getError(skyKey(labelName));
+    // Ensures that TargetFunction rethrows all transitive exceptions.
+    assertEquals(targetKey, Iterables.getOnlyElement(errorInfo.getRootCauses()));
+    return errorInfo.getException();
+  }
+
+  /** Regression test for b/12545745 */
+  public void testLabelCrossingSubpackageBoundary() throws Exception {
+    scratch.file("a/b/c/foo.sh", "echo 'FOO'");
+    scratch.file("a/BUILD", "sh_library(name = 'foo', srcs = ['b/c/foo.sh'])");
+    String labelName = "//a:b/c/foo.sh";
+
+    scratch.file("a/b/BUILD");
+    ModifiedFileSet subpackageBuildFile =
+        ModifiedFileSet.builder().modify(new PathFragment("a/b/BUILD")).build();
+    skyframeExecutor.invalidateFilesUnderPathForTesting(
+        reporter, subpackageBuildFile, rootDirectory);
+
+    NoSuchTargetException exn = (NoSuchTargetException) getErrorFromTargetValue(labelName);
+    // In the presence of b/12545745, the error message is different and comes from the
+    // PackageFunction.
+    assertThat(exn.getMessage())
+        .contains("Label '//a:b/c/foo.sh' crosses boundary of subpackage 'a/b'");
+  }
+
+  public void testNoBuildFileForTargetWithSlash() throws Exception {
+    String labelName = "//no/such/package:target/withslash";
+    BuildFileNotFoundException exn =
+        (BuildFileNotFoundException) getErrorFromTargetValue(labelName);
+    assertEquals(PackageIdentifier.createInDefaultRepo("no/such/package"), exn.getPackageId());
+    String expectedMessage =
+        "no such package 'no/such/package': BUILD file not found on "
+            + "package path for 'no/such/package'";
+    assertThat(exn).hasMessage(expectedMessage);
+  }
+
+  public void testRuleWithError() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    scratch.file(
+        "a/BUILD",
+        "genrule(name = 'conflict1', cmd = '', srcs = [], outs = ['conflict'])",
+        "genrule(name = 'conflict2', cmd = '', srcs = [], outs = ['conflict'])");
+    String labelName = "//a:conflict1";
+    NoSuchTargetException exn = (NoSuchTargetException) getErrorFromTargetValue(labelName);
+    assertThat(exn.getMessage())
+        .contains("Target '//a:conflict1' contains an error and its package is in error");
+    assertEquals(labelName, exn.getLabel().toString());
+    assertTrue(exn.hasTarget());
+  }
+
+  public void testTargetFunctionRethrowsExceptions() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    scratch.file("a/BUILD", "sh_library(name = 'b/c')");
+    Path subpackageBuildFile = scratch.file("a/b/BUILD", "sh_library(name = 'c')");
+    fs.stubStatIOException(subpackageBuildFile, new IOException("nope"));
+    BuildFileNotFoundException exn =
+        (BuildFileNotFoundException) getErrorFromTargetValue("//a:b/c");
+    assertThat(exn.getMessage()).contains("nope");
+  }
+
+  private static class CustomInMemoryFs extends InMemoryFileSystem {
+
+    private Map<Path, IOException> stubbedStatExceptions = Maps.newHashMap();
+
+    public CustomInMemoryFs() {
+      super(BlazeClock.instance());
+    }
+
+    public void stubStatIOException(Path path, IOException stubbedResult) {
+      stubbedStatExceptions.put(path, stubbedResult);
+    }
+
+    @Override
+    public FileStatus stat(Path path, boolean followSymlinks) throws IOException {
+      if (stubbedStatExceptions.containsKey(path)) {
+        throw stubbedStatExceptions.get(path);
+      }
+      return super.stat(path, followSymlinks);
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderMediumTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderMediumTest.java
new file mode 100644
index 0000000000..7ecc956d9a
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderMediumTest.java
@@ -0,0 +1,472 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.cache.CompactPersistentActionCache;
+import com.google.devtools.build.lib.testutil.BlazeTestUtils;
+import com.google.devtools.build.lib.testutil.Suite;
+import com.google.devtools.build.lib.testutil.TestSpec;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.UnixGlob;
+
+import java.io.IOException;
+
+/**
+ * These tests belong to {@link TimestampBuilderTest}, but they're in a
+ * separate class for now because they are a little slower.
+ */
+@TestSpec(size = Suite.MEDIUM_TESTS)
+public class TimestampBuilderMediumTest extends TimestampBuilderTestCase {
+  private Path cacheRoot;
+  private CompactPersistentActionCache cache;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    // BlazeRuntime.setupLogging(Level.FINEST);  // Uncomment this for debugging.
+
+    cacheRoot = scratch.dir("cacheRoot");
+    cache = createCache();
+  }
+
+  private CompactPersistentActionCache createCache() throws IOException {
+    return new CompactPersistentActionCache(cacheRoot, clock);
+  }
+
+  /**
+   * Creates and returns a new caching builder based on a given {@code cache}.
+   */
+  private Builder persistentBuilder(CompactPersistentActionCache cache) {
+    return createBuilder(cache);
+  }
+
+  // TODO(blaze-team): (2009) :
+  // - test timestamp monotonicity is not required (i.e. set mtime backwards)
+  // - test change of key causes rebuild
+
+  public void testUnneededInputs() throws Exception {
+    Artifact hello = createSourceArtifact("hello");
+    BlazeTestUtils.makeEmptyFile(hello.getPath());
+    Artifact optional = createSourceArtifact("hello.optional");
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button = createActionButton(Sets.newHashSet(hello, optional), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Creating a new persistent cache does not cause a rebuild
+    cache.save();
+    cache = createCache();
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    BlazeTestUtils.makeEmptyFile(optional.getPath());
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    optional.getPath().delete();
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    // Creating a new persistent cache does not cause a rebuild
+    cache.save();
+    cache = createCache();
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testPersistentCache_ModifyingInputCausesActionReexecution() throws Exception {
+    // /hello -> [action] -> /goodbye
+    Artifact hello = createSourceArtifact("hello");
+    BlazeTestUtils.makeEmptyFile(hello.getPath());
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button = createActionButton(Sets.newHashSet(hello), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    FileSystemUtils.touchFile(hello.getPath());
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Creating a new persistent cache does not cause a rebuild
+    cache.save();
+    buildArtifacts(persistentBuilder(createCache()), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testModifyingInputCausesActionReexecution() throws Exception {
+    // /hello -> [action] -> /goodbye
+    Artifact hello = createSourceArtifact("hello");
+    FileSystemUtils.createDirectoryAndParents(hello.getPath().getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content1");
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button = createActionButton(Sets.newHashSet(hello), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // still not rebuilt
+
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content2");
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Creating a new persistent cache does not cause a rebuild
+    cache.save();
+    buildArtifacts(persistentBuilder(createCache()), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testArtifactOrderingDoesNotMatter() throws Exception {
+    // (/hello,/there) -> [action] -> /goodbye
+
+    Artifact hello = createSourceArtifact("hello");
+    Artifact there = createSourceArtifact("there");
+    FileSystemUtils.createDirectoryAndParents(hello.getPath().getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "hello");
+    FileSystemUtils.writeContentAsLatin1(there.getPath(), "there");
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button =
+        createActionButton(
+            Sets.newLinkedHashSet(ImmutableList.of(hello, there)), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Now create duplicate graph, with swapped order.
+    clearActions();
+    Artifact goodbye2 = createDerivedArtifact("goodbye");
+    Button button2 =
+        createActionButton(
+            Sets.newLinkedHashSet(ImmutableList.of(there, hello)), Sets.newHashSet(goodbye2));
+
+    button2.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button2.pressed); // still not rebuilt
+  }
+
+  public void testOldCacheKeysAreCleanedUp() throws Exception {
+    // [action1] -> (/goodbye), cache key will be /goodbye
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    FileSystemUtils.createDirectoryAndParents(goodbye.getPath().getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(goodbye.getPath(), "test");
+    Button button = createActionButton(emptySet, Sets.newLinkedHashSet(ImmutableList.of(goodbye)));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    // action1 is cached using the cache key /goodbye.
+    assertThat(cache.get(goodbye.getExecPathString())).isNotNull();
+
+    // [action2] -> (/hello,/goodbye), cache key will be /hello
+    clearActions();
+    Artifact hello = createDerivedArtifact("hello");
+    Artifact goodbye2 = createDerivedArtifact("goodbye");
+    Button button2 =
+        createActionButton(emptySet, Sets.newLinkedHashSet(ImmutableList.of(hello, goodbye2)));
+
+    button2.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello, goodbye2);
+    assertTrue(button2.pressed); // rebuilt
+
+    // action2 is cached using the cache key /hello.
+    assertThat(cache.get(hello.getExecPathString())).isNotNull();
+
+    // Now, action1 should no longer be in the cache.
+    assertThat(cache.get(goodbye.getExecPathString())).isNull();
+  }
+
+  public void testArtifactNamesMatter() throws Exception {
+    // /hello -> [action] -> /goodbye
+
+    Artifact hello = createSourceArtifact("hello");
+    FileSystemUtils.createDirectoryAndParents(hello.getPath().getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "hello");
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button = createActionButton(Sets.newHashSet(hello), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Now create duplicate graph, replacing "hello" with "hi".
+    clearActions();
+    Artifact hi = createSourceArtifact("hi");
+    FileSystemUtils.createDirectoryAndParents(hi.getPath().getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(hi.getPath(), "hello");
+    Artifact goodbye2 = createDerivedArtifact("goodbye");
+    Button button2 = createActionButton(Sets.newHashSet(hi), Sets.newHashSet(goodbye2));
+
+    button2.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye2);
+    assertTrue(button2.pressed); // name changed. must rebuild.
+  }
+
+  public void testDuplicateInputs() throws Exception {
+    // (/hello,/hello) -> [action] -> /goodbye
+
+    Artifact hello = createSourceArtifact("hello");
+    FileSystemUtils.createDirectoryAndParents(hello.getPath().getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "hello");
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button =
+        createActionButton(Lists.<Artifact>newArrayList(hello, hello), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "hello2");
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Creating a new persistent cache does not cause a rebuild
+    cache.save();
+    buildArtifacts(persistentBuilder(createCache()), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  /**
+   * Tests that changing timestamp of the input file without changing it content
+   * does not cause action reexecution when metadata cache uses file digests in
+   * addition to the timestamp.
+   */
+  public void testModifyingTimestampOnlyDoesNotCauseActionReexecution() throws Exception {
+    // /hello -> [action] -> /goodbye
+    Artifact hello = createSourceArtifact("hello");
+    FileSystemUtils.createDirectoryAndParents(hello.getPath().getParentDirectory());
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content1");
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button = createActionButton(Sets.newHashSet(hello), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Creating a new persistent caches, including metadata cache does not cause
+    // a rebuild
+    cache.save();
+    Builder builder = persistentBuilder(createCache());
+    buildArtifacts(builder, goodbye);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testPersistentCache_ModifyingOutputCausesActionReexecution() throws Exception {
+    // [action] -> /hello
+    Artifact hello = createDerivedArtifact("hello");
+    Button button = createActionButton(emptySet, Sets.newHashSet(hello));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    BlazeTestUtils.changeModtime(hello.getPath());
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Creating a new persistent cache does not cause a rebuild
+    cache.save();
+    buildArtifacts(persistentBuilder(createCache()), hello);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testPersistentCache_missingFilenameIndexCausesActionReexecution() throws Exception {
+    // [action] -> /hello
+    Artifact hello = createDerivedArtifact("hello");
+    Button button = createActionButton(emptySet, Sets.newHashSet(hello));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    BlazeTestUtils.changeModtime(hello.getPath());
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Creating a new persistent cache does not cause a rebuild
+    cache.save();
+
+    // Remove filename index file.
+    assertTrue(
+        Iterables.getOnlyElement(
+                UnixGlob.forPath(cacheRoot).addPattern("filename_index*").globInterruptible())
+            .delete());
+
+    // Now first cache creation attempt should cause IOException while renaming corrupted files.
+    // Second attempt will initialize empty cache, causing rebuild.
+    try {
+      createCache();
+      fail("Expected IOException");
+    } catch (IOException e) {
+      assertThat(e).hasMessage("Failed action cache referential integrity check: empty index");
+    }
+
+    buildArtifacts(persistentBuilder(createCache()), hello);
+    assertTrue(button.pressed); // rebuilt due to the missing filename index
+  }
+
+  public void testPersistentCache_failedIntegrityCheckCausesActionReexecution() throws Exception {
+    // [action] -> /hello
+    Artifact hello = createDerivedArtifact("hello");
+    Button button = createActionButton(emptySet, Sets.newHashSet(hello));
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    BlazeTestUtils.changeModtime(hello.getPath());
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(persistentBuilder(cache), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    cache.save();
+
+    // Get filename index path and store a copy of it.
+    Path indexPath =
+        Iterables.getOnlyElement(
+            UnixGlob.forPath(cacheRoot).addPattern("filename_index*").globInterruptible());
+    Path indexCopy = scratch.resolve("index_copy");
+    FileSystemUtils.copyFile(indexPath, indexCopy);
+
+    // Add extra records to the action cache and indexer.
+    Artifact helloExtra = createDerivedArtifact("hello_extra");
+    Button buttonExtra = createActionButton(emptySet, Sets.newHashSet(helloExtra));
+    buildArtifacts(persistentBuilder(cache), helloExtra);
+    assertTrue(buttonExtra.pressed); // built
+
+    cache.save();
+    assertTrue(indexPath.getFileSize() > indexCopy.getFileSize());
+
+    // Validate current cache.
+    buildArtifacts(persistentBuilder(createCache()), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Restore outdated file index.
+    FileSystemUtils.copyFile(indexCopy, indexPath);
+
+    // Now first cache creation attempt should cause IOException while renaming corrupted files.
+    // Second attempt will initialize empty cache, causing rebuild.
+    try {
+      createCache();
+      fail("Expected IOException");
+    } catch (IOException e) {
+      assertThat(e.getMessage()).contains("Failed action cache referential integrity check");
+    }
+
+    // Validate cache with incorrect (out-of-date) filename index.
+    buildArtifacts(persistentBuilder(createCache()), hello);
+    assertTrue(button.pressed); // rebuilt due to the out-of-date index
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
new file mode 100644
index 0000000000..abd081c440
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -0,0 +1,385 @@
+// 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 static com.google.devtools.build.lib.actions.util.ActionCacheTestHelper.AMNESIAC_CACHE;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Range;
+import com.google.common.collect.Sets;
+import com.google.common.eventbus.EventBus;
+import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionCacheChecker;
+import com.google.devtools.build.lib.actions.ActionExecutionStatusReporter;
+import com.google.devtools.build.lib.actions.ActionLogBufferPathGenerator;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.BuildFailedException;
+import com.google.devtools.build.lib.actions.Executor;
+import com.google.devtools.build.lib.actions.ResourceManager;
+import com.google.devtools.build.lib.actions.ResourceSet;
+import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.actions.TestExecException;
+import com.google.devtools.build.lib.actions.cache.ActionCache;
+import com.google.devtools.build.lib.actions.util.DummyExecutor;
+import com.google.devtools.build.lib.actions.util.TestAction;
+import com.google.devtools.build.lib.analysis.ConfiguredTarget;
+import com.google.devtools.build.lib.buildtool.SkyframeBuilder;
+import com.google.devtools.build.lib.events.Reporter;
+import com.google.devtools.build.lib.events.StoredEventHandler;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.ActionExecutionFunction;
+import com.google.devtools.build.lib.skyframe.ActionLookupValue;
+import com.google.devtools.build.lib.skyframe.ArtifactFunction;
+import com.google.devtools.build.lib.skyframe.ArtifactValue;
+import com.google.devtools.build.lib.skyframe.AspectValue;
+import com.google.devtools.build.lib.skyframe.Builder;
+import com.google.devtools.build.lib.skyframe.ExternalFilesHelper;
+import com.google.devtools.build.lib.skyframe.FileFunction;
+import com.google.devtools.build.lib.skyframe.FileStateFunction;
+import com.google.devtools.build.lib.skyframe.PrecomputedValue;
+import com.google.devtools.build.lib.skyframe.SkyFunctions;
+import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor;
+import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.testutil.TestUtils;
+import com.google.devtools.build.lib.util.AbruptExitException;
+import com.google.devtools.build.lib.util.BlazeClock;
+import com.google.devtools.build.lib.util.Clock;
+import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileSystem;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.skyframe.CycleInfo;
+import com.google.devtools.build.skyframe.ErrorInfo;
+import com.google.devtools.build.skyframe.EvaluationProgressReceiver;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
+import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicReference;
+
+import javax.annotation.Nullable;
+
+/**
+ * The common code that's shared between various builder tests.
+ */
+public abstract class TimestampBuilderTestCase extends FoundationTestCase {
+
+  private static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
+  protected static final ActionLookupValue.ActionLookupKey ALL_OWNER =
+      new SingletonActionLookupKey();
+  protected static final Predicate<Action> ALWAYS_EXECUTE_FILTER = Predicates.alwaysTrue();
+  protected static final String CYCLE_MSG = "Yarrrr, there be a cycle up in here";
+
+  protected Clock clock = BlazeClock.instance();
+  protected TimestampGranularityMonitor tsgm;
+  protected RecordingDifferencer differencer = new RecordingDifferencer();
+  private Set<Action> actions;
+
+  protected AtomicReference<EventBus> eventBusRef = new AtomicReference<>();
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    inMemoryCache = new InMemoryActionCache();
+    tsgm = new TimestampGranularityMonitor(clock);
+    ResourceManager.instance().setAvailableResources(ResourceSet.createWithRamCpuIo(100, 1, 1));
+    actions = new HashSet<>();
+  }
+
+  protected void clearActions() {
+    actions.clear();
+  }
+
+  protected <T extends Action> T registerAction(T action) {
+    actions.add(action);
+    return action;
+  }
+
+  protected Builder createBuilder(ActionCache actionCache) {
+    return createBuilder(actionCache, 1, /*keepGoing=*/ false);
+  }
+
+  /**
+   * Create a ParallelBuilder with a DatabaseDependencyChecker using the
+   * specified ActionCache.
+   */
+  protected Builder createBuilder(
+      final ActionCache actionCache, final int threadCount, final boolean keepGoing) {
+    return createBuilder(actionCache, threadCount, keepGoing, null);
+  }
+
+  protected Builder createBuilder(
+      final ActionCache actionCache,
+      final int threadCount,
+      final boolean keepGoing,
+      @Nullable EvaluationProgressReceiver evaluationProgressReceiver) {
+    AtomicReference<PathPackageLocator> pkgLocator =
+        new AtomicReference<>(new PathPackageLocator());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    differencer = new RecordingDifferencer();
+
+    ActionExecutionStatusReporter statusReporter =
+        ActionExecutionStatusReporter.create(new StoredEventHandler());
+    final SkyframeActionExecutor skyframeActionExecutor =
+        new SkyframeActionExecutor(
+            ResourceManager.instance(), eventBusRef, new AtomicReference<>(statusReporter));
+
+    skyframeActionExecutor.setActionLogBufferPathGenerator(
+        new ActionLogBufferPathGenerator(actionOutputBase));
+
+    final InMemoryMemoizingEvaluator evaluator =
+        new InMemoryMemoizingEvaluator(
+            ImmutableMap.of(
+                SkyFunctions.FILE_STATE,
+                new FileStateFunction(tsgm, externalFilesHelper),
+                SkyFunctions.FILE,
+                new FileFunction(pkgLocator, tsgm, externalFilesHelper),
+                SkyFunctions.ARTIFACT,
+                new ArtifactFunction(Predicates.<PathFragment>alwaysFalse()),
+                SkyFunctions.ACTION_EXECUTION,
+                new ActionExecutionFunction(skyframeActionExecutor, tsgm)),
+            differencer,
+            evaluationProgressReceiver);
+    final SequentialBuildDriver driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+
+    return new Builder() {
+      private void setGeneratingActions() {
+        if (evaluator.getExistingValueForTesting(OWNER_KEY) == null) {
+          differencer.inject(ImmutableMap.of(OWNER_KEY, new ActionLookupValue(actions)));
+        }
+      }
+
+      @Override
+      public void buildArtifacts(
+          Reporter reporter,
+          Set<Artifact> artifacts,
+          Set<ConfiguredTarget> parallelTests,
+          Set<ConfiguredTarget> exclusiveTests,
+          Collection<ConfiguredTarget> targetsToBuild,
+          Collection<AspectValue> aspects,
+          Executor executor,
+          Set<ConfiguredTarget> builtTargets,
+          boolean explain,
+          Range<Long> lastExecutionTimeRange)
+          throws BuildFailedException, AbruptExitException, InterruptedException,
+              TestExecException {
+        skyframeActionExecutor.prepareForExecution(
+            reporter,
+            executor,
+            keepGoing, /*explain=*/
+            false,
+            new ActionCacheChecker(actionCache, null, ALWAYS_EXECUTE_FILTER, false));
+
+        List<SkyKey> keys = new ArrayList<>();
+        for (Artifact artifact : artifacts) {
+          keys.add(ArtifactValue.key(artifact, true));
+        }
+
+        setGeneratingActions();
+        EvaluationResult<SkyValue> result = driver.evaluate(keys, keepGoing, threadCount, reporter);
+
+        if (result.hasError()) {
+          boolean hasCycles = false;
+          for (Map.Entry<SkyKey, ErrorInfo> entry : result.errorMap().entrySet()) {
+            Iterable<CycleInfo> cycles = entry.getValue().getCycleInfo();
+            hasCycles |= !Iterables.isEmpty(cycles);
+          }
+          if (hasCycles) {
+            throw new BuildFailedException(CYCLE_MSG);
+          } else if (result.errorMap().isEmpty() || keepGoing) {
+            throw new BuildFailedException();
+          } else {
+            SkyframeBuilder.rethrow(Preconditions.checkNotNull(result.getError().getException()));
+          }
+        }
+      }
+    };
+  }
+
+  /** A non-persistent cache. */
+  protected InMemoryActionCache inMemoryCache;
+
+  /** A class that records an event. */
+  protected static class Button implements Runnable {
+    protected boolean pressed = false;
+
+    @Override
+    public void run() {
+      pressed = true;
+    }
+  }
+
+  /** A class that counts occurrences of an event. */
+  static class Counter implements Runnable {
+    int count = 0;
+
+    @Override
+    public void run() {
+      count++;
+    }
+  }
+
+  Artifact createSourceArtifact(String name) {
+    return createSourceArtifact(scratch.getFileSystem(), name);
+  }
+
+  Artifact createSourceArtifact(FileSystem fs, String name) {
+    Path root = fs.getPath(TestUtils.tmpDir());
+    return new Artifact(new PathFragment(name), Root.asSourceRoot(root));
+  }
+
+  protected Artifact createDerivedArtifact(String name) {
+    return createDerivedArtifact(scratch.getFileSystem(), name);
+  }
+
+  Artifact createDerivedArtifact(FileSystem fs, String name) {
+    Path execRoot = fs.getPath(TestUtils.tmpDir());
+    PathFragment execPath = new PathFragment("out").getRelative(name);
+    Path path = execRoot.getRelative(execPath);
+    return new Artifact(
+        path, Root.asDerivedRoot(execRoot, execRoot.getRelative("out")), execPath, ALL_OWNER);
+  }
+
+  /**
+   * Creates and returns a new "amnesiac" builder based on the amnesiac cache.
+   */
+  protected Builder amnesiacBuilder() {
+    return createBuilder(AMNESIAC_CACHE);
+  }
+
+  /**
+   * Creates and returns a new caching builder based on the inMemoryCache.
+   */
+  protected Builder cachingBuilder() {
+    return createBuilder(inMemoryCache);
+  }
+
+  /**
+   * Creates a TestAction from 'inputs' to 'outputs', and a new button, such
+   * that executing the action causes the button to be pressed.  The button is
+   * returned.
+   */
+  protected Button createActionButton(Collection<Artifact> inputs, Collection<Artifact> outputs) {
+    Button button = new Button();
+    registerAction(new TestAction(button, inputs, outputs));
+    return button;
+  }
+
+  /**
+   * Creates a TestAction from 'inputs' to 'outputs', and a new counter, such
+   * that executing the action causes the counter to be incremented.  The
+   * counter is returned.
+   */
+  protected Counter createActionCounter(Collection<Artifact> inputs, Collection<Artifact> outputs) {
+    Counter counter = new Counter();
+    registerAction(new TestAction(counter, inputs, outputs));
+    return counter;
+  }
+
+  protected static Set<Artifact> emptySet = Collections.emptySet();
+
+  protected void buildArtifacts(Builder builder, Artifact... artifacts)
+      throws BuildFailedException, AbruptExitException, InterruptedException, TestExecException {
+
+    tsgm.setCommandStartTime();
+    Set<Artifact> artifactsToBuild = Sets.newHashSet(artifacts);
+    Set<ConfiguredTarget> builtArtifacts = new HashSet<>();
+    try {
+      builder.buildArtifacts(
+          reporter,
+          artifactsToBuild,
+          null,
+          null,
+          null,
+          null,
+          new DummyExecutor(rootDirectory),
+          builtArtifacts, /*explain=*/
+          false,
+          null);
+    } finally {
+      tsgm.waitForTimestampGranularity(reporter.getOutErr());
+    }
+  }
+
+  protected static class InMemoryActionCache implements ActionCache {
+
+    private final Map<String, Entry> actionCache = new HashMap<>();
+
+    @Override
+    public synchronized void put(String key, ActionCache.Entry entry) {
+      actionCache.put(key, entry);
+    }
+
+    @Override
+    public synchronized Entry get(String key) {
+      return actionCache.get(key);
+    }
+
+    @Override
+    public synchronized void remove(String key) {
+      actionCache.remove(key);
+    }
+
+    @Override
+    public Entry createEntry(String key) {
+      return new ActionCache.Entry(key);
+    }
+
+    public synchronized void reset() {
+      actionCache.clear();
+    }
+
+    @Override
+    public long save() {
+      // safe to ignore
+      return 0;
+    }
+
+    @Override
+    public void dump(PrintStream out) {
+      out.println("In-memory action cache has " + actionCache.size() + " records");
+    }
+  }
+
+  private static class SingletonActionLookupKey extends ActionLookupValue.ActionLookupKey {
+    @Override
+    SkyKey getSkyKey() {
+      return OWNER_KEY;
+    }
+
+    @Override
+    SkyFunctionName getType() {
+      throw new UnsupportedOperationException();
+    }
+  }
+}