diff --git a/src/test/java/com/google/devtools/build/lib/BUILD b/src/test/java/com/google/devtools/build/lib/BUILD
index f3d0b6a..888f231 100644
--- a/src/test/java/com/google/devtools/build/lib/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/BUILD
@@ -59,10 +59,12 @@
         "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/skyframe",
         "//src/test/java/com/google/devtools/build/lib:packages_testutil",
+        "//src/test/java/com/google/devtools/build/skyframe:testutil",
         "//third_party:guava",
         "//third_party:guava-testlib",
         "//third_party:jsr305",
         "//third_party:junit4",
+        "//third_party:mockito",
         "//third_party:truth",
     ],
 )
@@ -99,6 +101,7 @@
         "//third_party:guava-testlib",
         "//third_party:jsr305",
         "//third_party:junit4",
+        "//third_party:mockito",
         "//third_party:truth",
     ],
 )
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
new file mode 100644
index 0000000..8fe6c9d
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
@@ -0,0 +1,557 @@
+// 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.Predicates;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+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.ConstantRuleVisibility;
+import com.google.devtools.build.lib.packages.Preprocessor;
+import com.google.devtools.build.lib.packages.util.SubincludePreprocessor;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
+import com.google.devtools.build.lib.testutil.ManualClock;
+import com.google.devtools.build.lib.vfs.Dirent;
+import com.google.devtools.build.lib.vfs.FileStatus;
+import com.google.devtools.build.lib.vfs.FileSystem;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+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.RootedPath;
+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.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+import java.io.IOException;
+import java.util.Collection;
+import java.util.Map;
+import java.util.Set;
+import java.util.UUID;
+
+import javax.annotation.Nullable;
+
+/**
+ * Unit tests of specific functionality of PackageFunction. Note that it's already tested
+ * indirectly in several other places.
+ */
+public class PackageFunctionTest extends BuildViewTestCase {
+
+  private CustomInMemoryFs fs = new CustomInMemoryFs(new ManualClock());
+
+  @Override
+  protected Preprocessor.Factory.Supplier getPreprocessorFactorySupplier() {
+    return new SubincludePreprocessor.FactorySupplier(scratch.getFileSystem());
+  }
+
+  @Override
+  protected FileSystem createFileSystem() {
+    return fs;
+  }
+
+  private PackageValue validPackage(SkyKey skyKey) throws InterruptedException {
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    if (result.hasError()) {
+      fail(result.getError(skyKey).getException().getMessage());
+    }
+    PackageValue value = result.get(skyKey);
+    assertFalse(value.getPackage().containsErrors());
+    return value;
+  }
+
+  public void testInconsistentNewPackage() throws Exception {
+    scratch.file("pkg/BUILD", "subinclude('//foo:sub')");
+    scratch.file("foo/sub");
+
+    getSkyframeExecutor().preparePackageLoading(
+        new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
+        ConstantRuleVisibility.PUBLIC, true,
+        7, "", UUID.randomUUID());
+
+    SkyKey pkgLookupKey = PackageLookupValue.key(new PathFragment("foo"));
+    EvaluationResult<PackageLookupValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), pkgLookupKey, /*keepGoing=*/false, reporter);
+    assertFalse(result.hasError());
+    assertFalse(result.get(pkgLookupKey).packageExists());
+
+    scratch.file("foo/BUILD");
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("pkg"));
+    result = SkyframeExecutorTestUtils.evaluate(getSkyframeExecutor(),
+        skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    Throwable exception = result.getError(skyKey).getException();
+    assertThat(exception.getMessage()).contains("Inconsistent filesystem operations");
+    assertThat(exception.getMessage()).contains("Unexpected package");
+  }
+
+  public void testInconsistentMissingPackage() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    Path root1 = fs.getPath("/root1");
+    scratch.file("/root1/WORKSPACE");
+    scratch.file("/root1/foo/sub");
+    scratch.file("/root1/pkg/BUILD", "subinclude('//foo:sub')");
+
+    Path root2 = fs.getPath("/root2");
+    scratch.file("/root2/foo/BUILD");
+    scratch.file("/root2/foo/sub");
+
+    getSkyframeExecutor().preparePackageLoading(
+        new PathPackageLocator(outputBase, ImmutableList.of(root1, root2)),
+        ConstantRuleVisibility.PUBLIC, true,
+        7, "", UUID.randomUUID());
+
+    SkyKey pkgLookupKey = PackageLookupValue.key(PackageIdentifier.parse("foo"));
+    EvaluationResult<PackageLookupValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), pkgLookupKey, /*keepGoing=*/false, reporter);
+    assertFalse(result.hasError());
+    assertEquals(root2, result.get(pkgLookupKey).getRoot());
+
+    scratch.file("/root1/foo/BUILD");
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("pkg"));
+    result = SkyframeExecutorTestUtils.evaluate(getSkyframeExecutor(),
+        skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    Throwable exception = result.getError(skyKey).getException();
+    System.out.println("exception: " + exception.getMessage());
+    assertThat(exception.getMessage()).contains("Inconsistent filesystem operations");
+    assertThat(exception.getMessage()).contains("Inconsistent package location");
+  }
+
+  public void testPropagatesFilesystemInconsistencies() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    RecordingDifferencer differencer = getSkyframeExecutor().getDifferencerForTesting();
+    Path pkgRoot = getSkyframeExecutor().getPathEntries().get(0);
+    Path fooBuildFile = scratch.file("foo/BUILD");
+    Path fooDir = fooBuildFile.getParentDirectory();
+
+    // Our custom filesystem says "foo/BUILD" exists but its parent "foo" is a file.
+    FileStatus inconsistentParentFileStatus = new FileStatus() {
+      @Override
+      public boolean isFile() {
+        return true;
+      }
+
+      @Override
+      public boolean isDirectory() {
+        return false;
+      }
+
+      @Override
+      public boolean isSymbolicLink() {
+        return false;
+      }
+
+      @Override
+      public boolean isSpecialFile() {
+        return false;
+      }
+
+      @Override
+      public long getSize() throws IOException {
+        return 0;
+      }
+
+      @Override
+      public long getLastModifiedTime() throws IOException {
+        return 0;
+      }
+
+      @Override
+      public long getLastChangeTime() throws IOException {
+        return 0;
+      }
+
+      @Override
+      public long getNodeId() throws IOException {
+        return 0;
+      }
+    };
+    fs.stubStat(fooDir, inconsistentParentFileStatus);
+    RootedPath pkgRootedPath = RootedPath.toRootedPath(pkgRoot, fooDir);
+    SkyValue fooDirValue = FileStateValue.create(pkgRootedPath,
+        getSkyframeExecutor().getTimestampGranularityMonitorForTesting());
+    differencer.inject(ImmutableMap.of(FileStateValue.key(pkgRootedPath), fooDirValue));
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("foo"));
+    String expectedMessage = "/workspace/foo/BUILD exists but its parent path /workspace/foo isn't "
+        + "an existing directory";
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    String errorMessage = errorInfo.getException().getMessage();
+    assertThat(errorMessage).contains("Inconsistent filesystem operations");
+    assertThat(errorMessage).contains(expectedMessage);
+  }
+
+  public void testPropagatesFilesystemInconsistencies_Globbing() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    RecordingDifferencer differencer = getSkyframeExecutor().getDifferencerForTesting();
+    Path pkgRoot = getSkyframeExecutor().getPathEntries().get(0);
+    scratch.file("foo/BUILD",
+        "subinclude('//a:a')",
+        "sh_library(name = 'foo', srcs = glob(['bar/**/baz.sh']))");
+    scratch.file("a/BUILD");
+    scratch.file("a/a");
+    Path bazFile = scratch.file("foo/bar/baz/baz.sh");
+    Path bazDir = bazFile.getParentDirectory();
+    Path barDir = bazDir.getParentDirectory();
+
+    long bazFileNodeId = bazFile.stat().getNodeId();
+    // Our custom filesystem says "foo/bar/baz" does not exist but it also says that "foo/bar"
+    // has a child directory "baz".
+    fs.stubStat(bazDir, null);
+    RootedPath barDirRootedPath = RootedPath.toRootedPath(pkgRoot, barDir);
+    FileStateValue barDirFileStateValue = FileStateValue.create(barDirRootedPath,
+        getSkyframeExecutor().getTimestampGranularityMonitorForTesting());
+    FileValue barDirFileValue = FileValue.value(barDirRootedPath, barDirFileStateValue,
+        barDirRootedPath, barDirFileStateValue);
+    DirectoryListingValue barDirListing = DirectoryListingValue.value(barDirRootedPath,
+        barDirFileValue, DirectoryListingStateValue.create(ImmutableList.of(
+            new Dirent("baz", Dirent.Type.DIRECTORY))));
+    differencer.inject(ImmutableMap.of(DirectoryListingValue.key(barDirRootedPath), barDirListing));
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("foo"));
+    String expectedMessage = "Some filesystem operations implied /workspace/foo/bar/baz/baz.sh was "
+        + "a regular file with size of 0 and mtime of 0 and nodeId of " + bazFileNodeId + " and "
+        + "mtime of 0 but others made us think it was a nonexistent path";
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    String errorMessage = errorInfo.getException().getMessage();
+    assertThat(errorMessage).contains("Inconsistent filesystem operations");
+    assertThat(errorMessage).contains(expectedMessage);
+  }
+
+  /** Regression test for unexpected exception type from PackageValue. */
+  public void testDiscrepancyBetweenLegacyAndSkyframePackageLoadingErrors() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    Path fooBuildFile = scratch.file("foo/BUILD",
+        "sh_library(name = 'foo', srcs = glob(['bar/*.sh']))");
+    Path fooDir = fooBuildFile.getParentDirectory();
+    Path barDir = fooDir.getRelative("bar");
+    scratch.file("foo/bar/baz.sh");
+    fs.scheduleMakeUnreadableAfterReaddir(barDir);
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("foo"));
+    String expectedMessage = "Encountered error 'Directory is not readable'";
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    String errorMessage = errorInfo.getException().getMessage();
+    assertThat(errorMessage).contains("Inconsistent filesystem operations");
+    assertThat(errorMessage).contains(expectedMessage);
+  }
+
+  public void testMultipleSubincludesFromSamePackage() throws Exception {
+    scratch.file("foo/BUILD",
+        "subinclude('//bar:a')",
+        "subinclude('//bar:b')");
+    scratch.file("bar/BUILD",
+        "exports_files(['a', 'b'])");
+    scratch.file("bar/a");
+    scratch.file("bar/b");
+
+    getSkyframeExecutor().preparePackageLoading(
+        new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
+        ConstantRuleVisibility.PUBLIC, true,
+        7, "", UUID.randomUUID());
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("foo"));
+    validPackage(skyKey);
+  }
+
+  public void testTransitiveSubincludesStoredInPackage() throws Exception {
+    scratch.file("foo/BUILD",
+        "subinclude('//bar:a')");
+    scratch.file("bar/BUILD",
+        "exports_files(['a'])");
+    scratch.file("bar/a",
+        "subinclude('//baz:b')");
+    scratch.file("baz/BUILD",
+        "exports_files(['b', 'c'])");
+    scratch.file("baz/b");
+    scratch.file("baz/c");
+
+    getSkyframeExecutor().preparePackageLoading(
+        new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
+        ConstantRuleVisibility.PUBLIC, true,
+        7, "", UUID.randomUUID());
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("foo"));
+    PackageValue value = validPackage(skyKey);
+    assertThat(value.getPackage().getSubincludeLabels()).containsExactly(
+        Label.parseAbsolute("//bar:a"), Label.parseAbsolute("//baz:b"));
+
+    scratch.overwriteFile("bar/a",
+        "subinclude('//baz:c')");
+    getSkyframeExecutor().invalidateFilesUnderPathForTesting(reporter,
+        ModifiedFileSet.builder().modify(new PathFragment("bar/a")).build(), rootDirectory);
+
+    value = validPackage(skyKey);
+    assertThat(value.getPackage().getSubincludeLabels()).containsExactly(
+        Label.parseAbsolute("//bar:a"), Label.parseAbsolute("//baz:c"));
+  }
+
+  public void testTransitiveSkylarkDepsStoredInPackage() throws Exception {
+    scratch.file("foo/BUILD",
+        "load('/bar/ext', 'a')");
+    scratch.file("bar/BUILD");
+    scratch.file("bar/ext.bzl",
+        "load('/baz/ext', 'b')",
+        "a = b");
+    scratch.file("baz/BUILD");
+    scratch.file("baz/ext.bzl",
+        "b = 1");
+    scratch.file("qux/BUILD");
+    scratch.file("qux/ext.bzl",
+        "c = 1");
+
+    getSkyframeExecutor().preparePackageLoading(
+        new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
+        ConstantRuleVisibility.PUBLIC, true,
+        7, "", UUID.randomUUID());
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("foo"));
+    PackageValue value = validPackage(skyKey);
+    assertThat(value.getPackage().getSkylarkFileDependencies()).containsExactly(
+        Label.parseAbsolute("//bar:ext.bzl"), Label.parseAbsolute("//baz:ext.bzl"));
+
+    scratch.overwriteFile("bar/ext.bzl",
+        "load('/qux/ext', 'c')",
+        "a = c");
+    getSkyframeExecutor().invalidateFilesUnderPathForTesting(reporter,
+        ModifiedFileSet.builder().modify(new PathFragment("bar/ext.bzl")).build(), rootDirectory);
+
+    value = validPackage(skyKey);
+    assertThat(value.getPackage().getSkylarkFileDependencies()).containsExactly(
+        Label.parseAbsolute("//bar:ext.bzl"), Label.parseAbsolute("//qux:ext.bzl"));
+  }
+
+  public void testNonExistingSkylarkExtension() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    scratch.file("test/skylark/BUILD",
+        "load('/test/skylark/bad_extension', 'some_symbol')",
+        "genrule(name = gr,",
+        "    outs = ['out.txt'],",
+        "    cmd = 'echo hello >@')");
+    invalidatePackages();
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("test/skylark"));
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    assertThat(errorInfo.getException())
+        .hasMessage("error loading package 'test/skylark': Extension file not found. "
+            + "Unable to load file '//test/skylark:bad_extension.bzl': "
+            + "file doesn't exist or isn't a file");
+  }
+
+  public void testNonExistingSkylarkExtensionWithPythonPreprocessing() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    scratch.file("foo/BUILD",
+        "exports_files(['a'])");
+    scratch.file("foo/a",
+        "load('/test/skylark/bad_extension', 'some_symbol')");
+    scratch.file("test/skylark/BUILD",
+        "subinclude('//foo:a')");
+    invalidatePackages();
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("test/skylark"));
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    assertContainsEvent("Extension file not found. "
+        + "Unable to load file '//test/skylark:bad_extension.bzl': "
+        + "file doesn't exist or isn't a file");
+  }
+
+  public void testNonExistingSkylarkExtensionFromExtension() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    scratch.file("test/skylark/extension.bzl",
+        "load('/test/skylark/bad_extension', 'some_symbol')",
+        "a = 'a'");
+    scratch.file("test/skylark/BUILD",
+        "load('/test/skylark/extension', 'a')",
+        "genrule(name = gr,",
+        "    outs = ['out.txt'],",
+        "    cmd = 'echo hello >@')");
+    invalidatePackages();
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("test/skylark"));
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    assertThat(errorInfo.getException())
+        .hasMessage("error loading package 'test/skylark': Extension file not found. "
+            + "Unable to load file '//test/skylark:bad_extension.bzl': "
+            + "file doesn't exist or isn't a file");
+  }
+
+  public void testSymlinkCycleWithSkylarkExtension() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    Path extensionFilePath = scratch.resolve("/workspace/test/skylark/extension.bzl");
+    FileSystemUtils.ensureSymbolicLink(extensionFilePath, new PathFragment("extension.bzl"));
+    scratch.file("test/skylark/BUILD",
+        "load('/test/skylark/extension', 'a')",
+        "genrule(name = gr,",
+        "    outs = ['out.txt'],",
+        "    cmd = 'echo hello >@')");
+    invalidatePackages();
+
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("test/skylark"));
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    ErrorInfo errorInfo = result.getError(skyKey);
+    assertEquals(skyKey, errorInfo.getRootCauseOfException());
+    assertThat(errorInfo.getException())
+        .hasMessage(
+            "error loading package 'test/skylark': Encountered error while reading extension "
+            + "file 'test/skylark/extension.bzl': Symlink cycle");
+  }
+
+  public void testIOErrorLookingForSubpackageForLabelIsHandled() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    scratch.file("foo/BUILD",
+        "sh_library(name = 'foo', srcs = ['bar/baz.sh'])");
+    Path barBuildFile = scratch.file("foo/bar/BUILD");
+    fs.stubStatError(barBuildFile, new IOException("nope"));
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.parse("foo"));
+    EvaluationResult<PackageValue> result = SkyframeExecutorTestUtils.evaluate(
+        getSkyframeExecutor(), skyKey, /*keepGoing=*/false, reporter);
+    assertTrue(result.hasError());
+    assertContainsEvent("nope");
+  }
+
+  public void testLoadRelativePath() throws Exception {
+    scratch.file("pkg/BUILD", "load('ext', 'a')");
+    scratch.file("pkg/ext.bzl", "a = 1");
+    validPackage(PackageValue.key(PackageIdentifier.parse("pkg")));
+  }
+
+  public void testLoadAbsolutePath() throws Exception {
+    scratch.file("pkg1/BUILD");
+    scratch.file("pkg2/BUILD",
+        "load('/pkg1/ext', 'a')");
+    scratch.file("pkg1/ext.bzl", "a = 1");
+    validPackage(PackageValue.key(PackageIdentifier.parse("pkg2")));
+  }
+
+  public void testBadWorkspaceFile() throws Exception {
+    Path workspacePath = scratch.overwriteFile("WORKSPACE", "junk");
+    SkyKey skyKey = PackageValue.key(PackageIdentifier.createInDefaultRepo("external"));
+    getSkyframeExecutor()
+        .invalidate(
+            Predicates.equalTo(
+                FileStateValue.key(
+                    RootedPath.toRootedPath(
+                        workspacePath.getParentDirectory(),
+                        new PathFragment(workspacePath.getBaseName())))));
+
+    reporter.removeHandler(failFastHandler);
+    EvaluationResult<PackageValue> result =
+        SkyframeExecutorTestUtils.evaluate(
+            getSkyframeExecutor(), skyKey, /*keepGoing=*/ false, reporter);
+    assertFalse(result.hasError());
+    assertTrue(result.get(skyKey).getPackage().containsErrors());
+  }
+
+  private static class CustomInMemoryFs extends InMemoryFileSystem {
+    private abstract static class FileStatusOrException {
+      abstract FileStatus get() throws IOException;
+
+      private static class ExceptionImpl extends FileStatusOrException {
+        private final IOException exn;
+
+        private ExceptionImpl(IOException exn) {
+          this.exn = exn;
+        }
+
+        @Override
+        FileStatus get() throws IOException {
+          throw exn;
+        }
+      }
+
+      private static class FileStatusImpl extends FileStatusOrException {
+
+        @Nullable
+        private final FileStatus fileStatus;
+
+        private  FileStatusImpl(@Nullable FileStatus fileStatus) {
+          this.fileStatus = fileStatus;
+        }
+
+        @Override
+        @Nullable
+        FileStatus get() {
+          return fileStatus;
+        }
+      }
+    }
+
+    private Map<Path, FileStatusOrException> stubbedStats = Maps.newHashMap();
+    private Set<Path> makeUnreadableAfterReaddir = Sets.newHashSet();
+
+    public CustomInMemoryFs(ManualClock manualClock) {
+      super(manualClock);
+    }
+
+    public void stubStat(Path path, @Nullable FileStatus stubbedResult) {
+      stubbedStats.put(path, new FileStatusOrException.FileStatusImpl(stubbedResult));
+    }
+
+    public void stubStatError(Path path, IOException stubbedResult) {
+      stubbedStats.put(path, new FileStatusOrException.ExceptionImpl(stubbedResult));
+    }
+
+    @Override
+    public FileStatus stat(Path path, boolean followSymlinks) throws IOException {
+      if (stubbedStats.containsKey(path)) {
+        return stubbedStats.get(path).get();
+      }
+      return super.stat(path, followSymlinks);
+    }
+
+    public void scheduleMakeUnreadableAfterReaddir(Path path) {
+      makeUnreadableAfterReaddir.add(path);
+    }
+
+    @Override
+    public Collection<Dirent> readdir(Path path, boolean followSymlinks) throws IOException {
+      Collection<Dirent> result = super.readdir(path, followSymlinks);
+      if (makeUnreadableAfterReaddir.contains(path)) {
+        path.setReadable(false);
+      }
+      return result;
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
new file mode 100644
index 0000000..dfc1c44
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
@@ -0,0 +1,231 @@
+// 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.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.bazel.rules.BazelRulesModule;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.packages.PackageFactory;
+import com.google.devtools.build.lib.packages.RuleClassProvider;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.PackageLookupValue.ErrorReason;
+import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
+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.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 PackageLookupFunction}.
+ */
+public class PackageLookupFunctionTest extends FoundationTestCase {
+  private AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages;
+  private MemoizingEvaluator evaluator;
+  private SequentialBuildDriver driver;
+  private RecordingDifferencer differencer;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+
+    Path emptyPackagePath = rootDirectory.getRelative("somewhere/else");
+    scratch.file("parentpackage/BUILD");
+
+    AtomicReference<PathPackageLocator> pkgLocator = new AtomicReference<>(
+        new PathPackageLocator(outputBase, ImmutableList.of(emptyPackagePath, rootDirectory)));
+    deletedPackages = new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    TimestampGranularityMonitor tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
+    BlazeDirectories directories = new BlazeDirectories(rootDirectory, outputBase, rootDirectory);
+
+    Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
+    skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP,
+        new PackageLookupFunction(deletedPackages));
+    skyFunctions.put(
+        SkyFunctions.PACKAGE,
+        new PackageFunction(null, null, null, null, null, null, null));
+    skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES,
+        new BlacklistedPackagePrefixesFunction());
+    RuleClassProvider ruleClassProvider = TestRuleClassProvider.getRuleClassProvider();
+    skyFunctions.put(
+        SkyFunctions.WORKSPACE_FILE,
+        new WorkspaceFileFunction(
+            ruleClassProvider,
+            new PackageFactory(
+                ruleClassProvider, new BazelRulesModule().getPackageEnvironmentExtension()),
+            directories));
+    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());
+    PrecomputedValue.BLACKLISTED_PACKAGE_PREFIXES_FILE.set(
+        differencer, PathFragment.EMPTY_FRAGMENT);
+  }
+
+  private PackageLookupValue lookupPackage(String packageName) throws InterruptedException {
+    return lookupPackage(PackageIdentifier.createInDefaultRepo(packageName));
+  }
+
+  private PackageLookupValue lookupPackage(PackageIdentifier packageId)
+      throws InterruptedException {
+    SkyKey key = PackageLookupValue.key(packageId);
+    return driver.<PackageLookupValue>evaluate(
+        ImmutableList.of(key), false, SkyframeExecutor.DEFAULT_THREAD_COUNT,
+        NullEventHandler.INSTANCE).get(key);
+  }
+
+  public void testNoBuildFile() throws Exception {
+    scratch.file("parentpackage/nobuildfile/foo.txt");
+    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/nobuildfile");
+    assertFalse(packageLookupValue.packageExists());
+    assertEquals(ErrorReason.NO_BUILD_FILE, packageLookupValue.getErrorReason());
+    assertNotNull(packageLookupValue.getErrorMsg());
+  }
+
+  public void testNoBuildFileAndNoParentPackage() throws Exception {
+    scratch.file("noparentpackage/foo.txt");
+    PackageLookupValue packageLookupValue = lookupPackage("noparentpackage");
+    assertFalse(packageLookupValue.packageExists());
+    assertEquals(ErrorReason.NO_BUILD_FILE, packageLookupValue.getErrorReason());
+    assertNotNull(packageLookupValue.getErrorMsg());
+  }
+
+  public void testDeletedPackage() throws Exception {
+    scratch.file("parentpackage/deletedpackage/BUILD");
+    deletedPackages.set(ImmutableSet.of(
+        PackageIdentifier.createInDefaultRepo("parentpackage/deletedpackage")));
+    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/deletedpackage");
+    assertFalse(packageLookupValue.packageExists());
+    assertEquals(ErrorReason.DELETED_PACKAGE, packageLookupValue.getErrorReason());
+    assertNotNull(packageLookupValue.getErrorMsg());
+  }
+
+
+  public void testBlacklistedPackage() throws Exception {
+    scratch.file("blacklisted/subdir/BUILD");
+    scratch.file("blacklisted/BUILD");
+    PrecomputedValue.BLACKLISTED_PACKAGE_PREFIXES_FILE.set(differencer,
+        new PathFragment("config/blacklisted.txt"));
+    Path blacklist = scratch.file("config/blacklisted.txt", "blacklisted");
+
+    ImmutableSet<String> pkgs = ImmutableSet.of("blacklisted/subdir", "blacklisted");
+    for (String pkg : pkgs) {
+      PackageLookupValue packageLookupValue = lookupPackage(pkg);
+      assertFalse(packageLookupValue.packageExists());
+      assertEquals(ErrorReason.DELETED_PACKAGE, packageLookupValue.getErrorReason());
+      assertNotNull(packageLookupValue.getErrorMsg());
+    }
+
+    scratch.overwriteFile("config/blacklisted.txt", "not_blacklisted");
+    RootedPath rootedBlacklist = RootedPath.toRootedPath(
+        blacklist.getParentDirectory().getParentDirectory(),
+        new PathFragment("config/blacklisted.txt"));
+    differencer.invalidate(ImmutableSet.of(FileStateValue.key(rootedBlacklist)));
+    for (String pkg : pkgs) {
+      PackageLookupValue packageLookupValue = lookupPackage(pkg);
+      assertTrue(packageLookupValue.packageExists());
+    }
+  }
+
+  public void testInvalidPackageName() throws Exception {
+    scratch.file("parentpackage/invalidpackagename%42/BUILD");
+    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/invalidpackagename%42");
+    assertFalse(packageLookupValue.packageExists());
+    assertEquals(ErrorReason.INVALID_PACKAGE_NAME,
+        packageLookupValue.getErrorReason());
+    assertNotNull(packageLookupValue.getErrorMsg());
+  }
+
+  public void testDirectoryNamedBuild() throws Exception {
+    scratch.dir("parentpackage/isdirectory/BUILD");
+    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/isdirectory");
+    assertFalse(packageLookupValue.packageExists());
+    assertEquals(ErrorReason.NO_BUILD_FILE,
+        packageLookupValue.getErrorReason());
+    assertNotNull(packageLookupValue.getErrorMsg());
+  }
+
+  public void testEverythingIsGood() throws Exception {
+    scratch.file("parentpackage/everythinggood/BUILD");
+    PackageLookupValue packageLookupValue = lookupPackage("parentpackage/everythinggood");
+    assertTrue(packageLookupValue.packageExists());
+    assertEquals(rootDirectory, packageLookupValue.getRoot());
+  }
+
+  public void testEmptyPackageName() throws Exception {
+    scratch.file("BUILD");
+    PackageLookupValue packageLookupValue = lookupPackage("");
+    assertTrue(packageLookupValue.packageExists());
+    assertEquals(rootDirectory, packageLookupValue.getRoot());
+  }
+
+  public void testWorkspaceLookup() throws Exception {
+    scratch.overwriteFile("WORKSPACE");
+    PackageLookupValue packageLookupValue = lookupPackage("external");
+    assertTrue(packageLookupValue.packageExists());
+    assertEquals(rootDirectory, packageLookupValue.getRoot());
+  }
+
+  // TODO(kchodorow): Clean this up (see TODOs in PackageLookupValue).
+  public void testExternalPackageLookupSemantics() {
+    PackageLookupValue existing = PackageLookupValue.workspace(rootDirectory);
+    assertTrue(existing.isExternalPackage());
+    assertTrue(existing.packageExists());
+    PackageLookupValue nonExistent = PackageLookupValue.workspace(rootDirectory.getRelative("x/y"));
+    assertTrue(nonExistent.isExternalPackage());
+    assertFalse(nonExistent.packageExists());
+  }
+
+  public void testPackageLookupValueHashCodeAndEqualsContract() throws Exception {
+    Path root1 = rootDirectory.getRelative("root1");
+    Path root2 = rootDirectory.getRelative("root2");
+    // Our (seeming) duplication of parameters here is intentional. Some of the subclasses of
+    // PackageLookupValue are supposed to have reference equality semantics, and some are supposed
+    // to have logical equality semantics.
+    new EqualsTester()
+        .addEqualityGroup(PackageLookupValue.success(root1), PackageLookupValue.success(root1))
+        .addEqualityGroup(PackageLookupValue.success(root2), PackageLookupValue.success(root2))
+        .addEqualityGroup(
+            PackageLookupValue.NO_BUILD_FILE_VALUE, PackageLookupValue.NO_BUILD_FILE_VALUE)
+        .addEqualityGroup(
+            PackageLookupValue.DELETED_PACKAGE_VALUE, PackageLookupValue.DELETED_PACKAGE_VALUE)
+        .addEqualityGroup(PackageLookupValue.invalidPackageName("nope1"),
+            PackageLookupValue.invalidPackageName("nope1"))
+        .addEqualityGroup(PackageLookupValue.invalidPackageName("nope2"),
+             PackageLookupValue.invalidPackageName("nope2"))
+        .testEquals();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ParallelBuilderMediumTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ParallelBuilderMediumTest.java
new file mode 100644
index 0000000..1d923d7
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ParallelBuilderMediumTest.java
@@ -0,0 +1,44 @@
+// 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.testutil.Suite;
+import com.google.devtools.build.lib.testutil.TestSpec;
+
+/**
+ * Stress tests for the parallel builder.
+ */
+@TestSpec(size = Suite.MEDIUM_TESTS)
+public class ParallelBuilderMediumTest extends ParallelBuilderTest {
+
+  /**
+   * A larger set of tests using randomly-generated complex dependency graphs.
+   */
+  public void testRandomStressTest1() throws Exception {
+    final int numTrials = 2;
+    final int numArtifacts = 100;
+    final int randomSeed = 43;
+    StressTest test = new StressTest(numArtifacts, numTrials, randomSeed);
+    test.runStressTest();
+  }
+
+  public void testRandomStressTest2() throws Exception {
+    final int numTrials = 10;
+    final int numArtifacts = 10;
+    final int randomSeed = 44;
+    StressTest test = new StressTest(numArtifacts, numTrials, randomSeed);
+    test.runStressTest();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ParallelBuilderTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ParallelBuilderTest.java
new file mode 100644
index 0000000..b1637b2
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ParallelBuilderTest.java
@@ -0,0 +1,863 @@
+// 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.ImmutableSet;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+import com.google.common.eventbus.EventBus;
+import com.google.common.eventbus.Subscribe;
+import com.google.common.util.concurrent.Runnables;
+import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionExecutedEvent;
+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.BuildFailedException;
+import com.google.devtools.build.lib.actions.Executor;
+import com.google.devtools.build.lib.actions.LocalHostCapacity;
+import com.google.devtools.build.lib.actions.ResourceManager;
+import com.google.devtools.build.lib.actions.ResourceSet;
+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.TestAction;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.events.EventKind;
+import com.google.devtools.build.lib.events.PrintingEventHandler;
+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.testutil.TestUtils;
+import com.google.devtools.build.lib.util.AbruptExitException;
+import com.google.devtools.build.lib.vfs.FileStatus;
+import com.google.devtools.build.lib.vfs.FileSystem;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
+
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import java.util.concurrent.Callable;
+import java.util.concurrent.Semaphore;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.logging.Logger;
+
+/**
+ * Test suite for ParallelBuilder.
+ *
+ */
+@TestSpec(size = Suite.MEDIUM_TESTS)
+public class ParallelBuilderTest extends TimestampBuilderTestCase {
+
+  private static final Logger LOG =
+    Logger.getLogger(ParallelBuilderTest.class.getName());
+
+  protected ActionCache cache;
+
+  protected static final int DEFAULT_NUM_JOBS = 100;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    this.cache = new InMemoryActionCache();
+    ResourceManager.instance().setAvailableResources(LocalHostCapacity.getLocalHostCapacity());
+    ResourceManager.instance().setRamUtilizationPercentage(
+        ResourceManager.DEFAULT_RAM_UTILIZATION_PERCENTAGE);
+    ResourceManager.instance().resetResourceUsage();
+  }
+
+  @SafeVarargs
+  protected static <T> Set<T> asSet(T... elements) {
+    return Sets.newHashSet(elements);
+  }
+
+  protected void buildArtifacts(Artifact... artifacts)
+      throws BuildFailedException, AbruptExitException,
+      InterruptedException, TestExecException {
+    buildArtifacts(createBuilder(DEFAULT_NUM_JOBS, false), artifacts);
+  }
+
+  private Builder createBuilder(int jobs, boolean keepGoing) {
+    return createBuilder(cache, jobs, keepGoing);
+  }
+
+  private volatile boolean runningFooAction;
+  private volatile boolean runningBarAction;
+
+  /**
+   * Test that independent actions are run in parallel threads
+   * that are scheduled concurrently.
+   */
+  public void runsInParallelWithBuilder(Builder builder) throws Exception {
+    // We create two actions, each of which waits (spinning) until the
+    // other action has started.  If the two actions are not run
+    // in parallel, the test will deadlock and time out.
+
+    // This specifies how many iterations to run before timing out.
+    // This should be large enough to ensure that that there is at
+    // least one context switch, otherwise the test may spuriously fail.
+    final long maxIterations = 100000000;
+
+    // This specifies how often to print out progress messages.
+    // Uncomment this for debugging.
+    //final long PRINT_FREQUENCY = maxIterations / 10;
+
+    runningFooAction = false;
+    runningBarAction = false;
+
+    // [action] -> foo
+    Artifact foo = createDerivedArtifact("foo");
+    Runnable makeFoo = new Runnable() {
+          @Override
+          public void run() {
+            runningFooAction = true;
+            for (long i = 0; i < maxIterations; i++) {
+              Thread.yield();
+              if (runningBarAction) {
+                return;
+              }
+              // Uncomment this for debugging.
+              //if (i % PRINT_FREQUENCY == 0) {
+              //  String msg = "ParallelBuilderTest: foo: waiting for bar";
+              //  System.out.println(bar);
+              //}
+            }
+            fail("ParallelBuilderTest: foo: waiting for bar: timed out");
+          }
+        };
+    registerAction(new TestAction(makeFoo, Artifact.NO_ARTIFACTS, ImmutableList.of(foo)));
+
+    // [action] -> bar
+    Artifact bar = createDerivedArtifact("bar");
+    Runnable makeBar = new Runnable() {
+          @Override
+          public void run() {
+            runningBarAction = true;
+            for (long i = 0; i < maxIterations; i++) {
+              Thread.yield();
+              if (runningFooAction) {
+                return;
+              }
+              // Uncomment this for debugging.
+              //if (i % PRINT_FREQUENCY == 0) {
+              //  String msg = "ParallelBuilderTest: bar: waiting for foo";
+              //  System.out.println(msg);
+              //}
+            }
+            fail("ParallelBuilderTest: bar: waiting for foo: timed out");
+          }
+        };
+    registerAction(new TestAction(makeBar, Artifact.NO_ARTIFACTS, ImmutableList.of(bar)));
+
+    buildArtifacts(builder, foo, bar);
+  }
+
+  /**
+   * Intercepts actionExecuted events, ordinarily written to the master log, for
+   * use locally within this test suite.
+   */
+  public static class ActionEventRecorder {
+    private final List<ActionExecutedEvent> actionExecutedEvents = new ArrayList<>();
+
+    @Subscribe
+    public void actionExecuted(ActionExecutedEvent event) {
+      actionExecutedEvents.add(event);
+    }
+  }
+
+  public void testReportsActionExecutedEvent() throws Exception {
+    Artifact pear = createDerivedArtifact("pear");
+    ActionEventRecorder recorder = new ActionEventRecorder();
+    EventBus eventBus = new EventBus();
+    eventBusRef.set(eventBus);
+    eventBus.register(recorder);
+
+    Action action = registerAction(new TestAction(Runnables.doNothing(), emptySet, asSet(pear)));
+
+    buildArtifacts(createBuilder(DEFAULT_NUM_JOBS, true), pear);
+    assertThat(recorder.actionExecutedEvents).hasSize(1);
+    assertEquals(action, recorder.actionExecutedEvents.get(0).getAction());
+  }
+
+  public void testRunsInParallel() throws Exception {
+    runsInParallelWithBuilder(createBuilder(DEFAULT_NUM_JOBS, false));
+  }
+
+  /**
+   * Test that we can recover properly after a failed build.
+   */
+  public void testFailureRecovery() throws Exception {
+
+    // [action] -> foo
+    Artifact foo = createDerivedArtifact("foo");
+    Callable<Void> makeFoo = new Callable<Void>() {
+          @Override
+          public Void call() throws IOException {
+            throw new IOException("building 'foo' is supposed to fail");
+          }
+        };
+    registerAction(new TestAction(makeFoo, Artifact.NO_ARTIFACTS, ImmutableList.of(foo)));
+
+    // [action] -> bar
+    Artifact bar = createDerivedArtifact("bar");
+    registerAction(new TestAction(TestAction.NO_EFFECT, emptySet, ImmutableList.of(bar)));
+
+    // Don't fail fast when we encounter the error
+    reporter.removeHandler(failFastHandler);
+
+    // test that building 'foo' fails
+    try {
+      buildArtifacts(foo);
+      fail("building 'foo' was supposed to fail!");
+    } catch (BuildFailedException e) {
+      if (!e.getMessage().contains("building 'foo' is supposed to fail")) {
+        throw e;
+      }
+      // Make sure the reporter reported the error message.
+      assertContainsEvent("building 'foo' is supposed to fail");
+    }
+    // test that a subsequent build of 'bar' succeeds
+    buildArtifacts(bar);
+  }
+
+  public void testUpdateCacheError() throws Exception {
+    FileSystem fs = new InMemoryFileSystem() {
+      @Override
+      public FileStatus stat(Path path, boolean followSymlinks) throws IOException {
+        final FileStatus stat = super.stat(path, followSymlinks);
+        if (path.toString().endsWith("/out/foo")) {
+          return new FileStatus() {
+            private final FileStatus original = stat;
+
+            @Override
+            public boolean isSymbolicLink() {
+              return original.isSymbolicLink();
+            }
+
+            @Override
+            public boolean isFile() {
+              return original.isFile();
+            }
+
+            @Override
+            public boolean isDirectory() {
+              return original.isDirectory();
+            }
+
+            @Override
+            public boolean isSpecialFile() {
+              return original.isSpecialFile();
+            }
+
+            @Override
+            public long getSize() throws IOException {
+              return original.getSize();
+            }
+
+            @Override
+            public long getNodeId() throws IOException {
+              return original.getNodeId();
+            }
+
+            @Override
+            public long getLastModifiedTime() throws IOException {
+              throw new IOException();
+            }
+
+            @Override
+            public long getLastChangeTime() throws IOException {
+              return original.getLastChangeTime();
+            }
+          };
+        }
+        return stat;
+      }
+    };
+    Artifact foo = createDerivedArtifact(fs, "foo");
+    registerAction(new TestAction(TestAction.NO_EFFECT, emptySet, ImmutableList.of(foo)));
+    reporter.removeHandler(failFastHandler);
+    try {
+      buildArtifacts(foo);
+      fail("Expected to fail");
+    } catch (BuildFailedException e) {
+      assertContainsEvent("not all outputs were created");
+    }
+  }
+
+  public void testNullBuild() throws Exception {
+    // BuildTool.setupLogging(Level.FINEST);
+    LOG.fine("Testing null build...");
+    buildArtifacts();
+  }
+
+  /**
+   * Test a randomly-generated complex dependency graph.
+   */
+  public void testSmallRandomStressTest() throws Exception {
+    final int numTrials = 1;
+    final int numArtifacts = 30;
+    final int randomSeed = 42;
+    StressTest test = new StressTest(numArtifacts, numTrials, randomSeed);
+    test.runStressTest();
+  }
+
+  private static enum BuildKind { Clean, Incremental, Nop }
+
+  /**
+   * Sets up and manages stress tests of arbitrary size.
+   */
+  protected class StressTest {
+
+    final int numArtifacts;
+    final int numTrials;
+
+    Random random;
+    Artifact artifacts[];
+
+    public StressTest(int numArtifacts, int numTrials, int randomSeed) {
+      this.numTrials = numTrials;
+      this.numArtifacts = numArtifacts;
+      this.random = new Random(randomSeed);
+    }
+
+    public void runStressTest() throws Exception {
+      for (int trial = 0; trial < numTrials; trial++) {
+        List<Counter> counters = buildRandomActionGraph(trial);
+
+        // do a clean build
+        LOG.fine("Testing clean build... (trial " + trial + ")");
+        Artifact[] buildTargets = chooseRandomBuild();
+        buildArtifacts(buildTargets);
+        doSanityChecks(buildTargets, counters, BuildKind.Clean);
+        resetCounters(counters);
+
+        // Do an incremental build.
+        //
+        // BuildTool creates new instances of the Builder for each build request. It may rely on
+        // that fact (that its state will be discarded after each build request) - thus
+        // test should use same approach and ensure that a new instance is used each time.
+        LOG.fine("Testing incremental build...");
+        buildTargets = chooseRandomBuild();
+        buildArtifacts(buildTargets);
+        doSanityChecks(buildTargets, counters, BuildKind.Incremental);
+        resetCounters(counters);
+
+        // do a do-nothing build
+        LOG.fine("Testing do-nothing rebuild...");
+        buildArtifacts(buildTargets);
+        doSanityChecks(buildTargets, counters, BuildKind.Nop);
+        //resetCounters(counters);
+      }
+    }
+
+    /**
+     * Construct a random action graph, and initialize the file system
+     * so that all of the input files exist and none of the output files
+     * exist.
+     */
+    public List<Counter> buildRandomActionGraph(int actionGraphNumber) throws IOException {
+      List<Counter> counters = new ArrayList<>(numArtifacts);
+
+      artifacts = new Artifact[numArtifacts];
+      for (int i = 0; i < numArtifacts; i++) {
+        artifacts[i] = createDerivedArtifact("file" + actionGraphNumber + "-" + i);
+      }
+
+      int numOutputs;
+      for (int i = 0; i < artifacts.length; i += numOutputs) {
+        int numInputs = random.nextInt(3);
+        numOutputs = 1 + random.nextInt(2);
+        if (i + numOutputs >= artifacts.length) {
+          numOutputs = artifacts.length - i;
+        }
+
+        Collection<Artifact> inputs = new ArrayList<>(numInputs);
+        for (int j = 0; j < numInputs; j++) {
+          if (i != 0) {
+            int inputNum = random.nextInt(i);
+            inputs.add(artifacts[inputNum]);
+          }
+        }
+        Collection<Artifact> outputs = new ArrayList<>(numOutputs);
+        for (int j = 0; j < numOutputs; j++) {
+          outputs.add(artifacts[i + j]);
+        }
+        counters.add(createActionCounter(inputs, outputs));
+        if (inputs.isEmpty()) {
+          // source files -- create them
+          for (Artifact output : outputs) {
+            BlazeTestUtils.makeEmptyFile(output.getPath());
+          }
+        } else {
+          // generated files -- delete them
+          for (Artifact output : outputs) {
+            try {
+              output.getPath().delete();
+            } catch (FileNotFoundException e) {
+              // ok
+            }
+          }
+        }
+      }
+      return counters;
+    }
+
+    /**
+     * Choose a random set of targets to build.
+     */
+    public Artifact[] chooseRandomBuild() {
+      Artifact[] buildTargets;
+      switch (random.nextInt(4)) {
+        case 0:
+          // build the final output target
+          LOG.fine("Building final output target.");
+          buildTargets = new Artifact[] { artifacts[numArtifacts - 1] };
+          break;
+
+        case 1: {
+          // build all the targets (in random order);
+          LOG.fine("Building all the targets.");
+          List<Artifact> targets = Lists.newArrayList(artifacts);
+          Collections.shuffle(targets, random);
+          buildTargets = targets.toArray(new Artifact[numArtifacts]);
+          break;
+        }
+
+        case 2:
+          // build a random target
+          LOG.fine("Building a random target.");
+          buildTargets = new Artifact[] {
+                artifacts[random.nextInt(numArtifacts)]
+              };
+          break;
+
+        case 3: {
+          // build a random subset of targets
+          LOG.fine("Building a random subset of targets.");
+          List<Artifact> targets = Lists.newArrayList(artifacts);
+          Collections.shuffle(targets, random);
+          List<Artifact> targetSubset = new ArrayList<>();
+          int numTargetsToTest = random.nextInt(numArtifacts);
+          LOG.fine("numTargetsToTest = " + numTargetsToTest);
+          Iterator<Artifact> iterator = targets.iterator();
+          for (int i = 0; i < numTargetsToTest; i++) {
+            targetSubset.add(iterator.next());
+          }
+          buildTargets = targetSubset.toArray(new Artifact[numTargetsToTest]);
+          break;
+        }
+
+        default:
+          throw new IllegalStateException();
+      }
+      return buildTargets;
+    }
+
+    public void doSanityChecks(Artifact[] targets, List<Counter> counters,
+        BuildKind kind) {
+      // Check that we really did build all the targets.
+      for (Artifact file : targets) {
+        assertTrue(file.getPath().exists());
+      }
+      // Check that each action was executed the right number of times
+      for (Counter counter : counters) {
+        switch (kind) {
+          case Clean:
+            //assert counter.count == 1;
+            //break;
+          case Incremental:
+            assert counter.count == 0 || counter.count == 1;
+            break;
+          case Nop:
+            assert counter.count == 0;
+            break;
+        }
+      }
+    }
+
+    private void resetCounters(List<Counter> counters) {
+      for (Counter counter : counters) {
+        counter.count = 0;
+      }
+    }
+
+  }
+
+  // Regression test for bug fixed in CL 3548332: builder was not waiting for
+  // all its subprocesses to terminate.
+  public void testWaitsForSubprocesses() throws Exception {
+    final Semaphore semaphore = new Semaphore(1);
+    final boolean[] finished = { false };
+
+    semaphore.acquireUninterruptibly(); // t=0: semaphore acquired
+
+    // This arrangement ensures that the "bar" action tries to run for about
+    // 100ms after the "foo" action has completed (failed).
+
+    // [action] -> foo
+    Artifact foo = createDerivedArtifact("foo");
+    Callable<Void> makeFoo = new Callable<Void>() {
+          @Override
+          public Void call() throws IOException {
+            semaphore.acquireUninterruptibly(); // t=2: semaphore re-acquired
+            throw new IOException("foo action failed");
+          }
+        };
+    registerAction(new TestAction(makeFoo, Artifact.NO_ARTIFACTS, ImmutableList.of(foo)));
+
+    // [action] -> bar
+    Artifact bar = createDerivedArtifact("bar");
+    Runnable makeBar = new Runnable() {
+          @Override
+          public void run() {
+            semaphore.release(); // t=1: semaphore released
+            try {
+              Thread.sleep(100); // 100ms
+            } catch (InterruptedException e) {
+              // This might happen (though not necessarily).  The
+              // ParallelBuilder interrupts all its workers at the first sign
+              // of trouble.
+            }
+            finished[0] = true;
+          }
+        };
+    registerAction(new TestAction(makeBar, emptySet, asSet(bar)));
+
+    // Don't fail fast when we encounter the error
+    reporter.removeHandler(failFastHandler);
+
+    try {
+      buildArtifacts(foo, bar);
+      fail();
+    } catch (BuildFailedException e) {
+      assertThat(e.getMessage()).contains("TestAction failed due to exception: foo action failed");
+      assertContainsEvent("TestAction failed due to exception: foo action failed");
+    }
+
+    assertTrue("bar action not finished, yet buildArtifacts has completed.",
+               finished[0]);
+  }
+
+  public void testSchedulingOfMemoryResources() throws Exception {
+    // The action graph consists of 100 independent actions, but execution is
+    // memory limited: only 6 TestActions can run concurrently:
+    ResourceManager.instance().setRamUtilizationPercentage(50);
+    ResourceManager.instance().setAvailableResources(
+        ResourceSet.createWithRamCpuIo(/*memoryMb=*/12.8, /*cpu=*/Integer.MAX_VALUE, /*io=*/0.0));
+    ResourceManager.instance().resetResourceUsage();
+
+    class Counter {
+      int currentlyRunning = 0;
+      int maxConcurrent = 0;
+      synchronized void increment() {
+        ++currentlyRunning;
+        if (currentlyRunning > maxConcurrent) {
+          maxConcurrent = currentlyRunning;
+        }
+      }
+      synchronized void decrement() {
+        currentlyRunning--;
+      }
+    }
+    final Counter counter = new Counter();
+
+    Artifact[] outputs = new Artifact[100];
+    for (int ii = 0; ii < outputs.length; ++ii) {
+      Artifact artifact = createDerivedArtifact("file" + ii);
+      Callable<Void> callable = new Callable<Void>() {
+          @Override
+          public Void call() throws Exception{
+            counter.increment();
+            Thread.sleep(100); // 100ms
+            counter.decrement();
+            return null;
+          }
+        };
+      registerAction(new TestAction(callable, Artifact.NO_ARTIFACTS, ImmutableList.of(artifact)));
+      outputs[ii] = artifact;
+    }
+
+    buildArtifacts(outputs);
+
+    assertEquals(0, counter.currentlyRunning);
+    assertEquals(6, counter.maxConcurrent);
+  }
+
+  public void testEstimateExceedsAvailableRam() throws Exception {
+    // Pretend that the machine has only 1MB of RAM available,
+    // then test running an action that we estimate requires 2MB of RAM.
+
+    ResourceManager.instance().setAvailableResources(
+        ResourceSet.createWithRamCpuIo(/*memoryMb=*/1.0, /*cpuUsage=*/4, /*ioUsage=*/0));
+    ResourceManager.instance().resetResourceUsage();
+
+    final boolean[] finished = { false };
+    Artifact foo = createDerivedArtifact("foo");
+    Runnable makeFoo = new Runnable() {
+        @Override
+        public void run() {
+          finished[0] = true;
+        }
+      };
+    registerAction(new TestAction(makeFoo, emptySet, asSet(foo)) {
+        @Override
+        public ResourceSet estimateResourceConsumption(Executor executor) {
+          return ResourceSet.createWithRamCpuIo(/*memoryMb=*/2.0, /*cpuUsage=*/1, /*ioUsage=*/0);
+        }
+      });
+    buildArtifacts(foo);
+    assertTrue(finished[0]);
+  }
+
+  public void testCyclicActionGraph() throws Exception {
+    // foo -> [action] -> bar
+    // bar -> [action] -> baz
+    // baz -> [action] -> foo
+    Artifact foo = createDerivedArtifact("foo");
+    Artifact bar = createDerivedArtifact("bar");
+    Artifact baz = createDerivedArtifact("baz");
+    try {
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(foo), asSet(bar)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(bar), asSet(baz)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(baz), asSet(foo)));
+      buildArtifacts(foo);
+      fail("Builder failed to detect cyclic action graph");
+    } catch (BuildFailedException e) {
+      assertEquals(e.getMessage(), CYCLE_MSG);
+    }
+  }
+
+  public void testSelfCyclicActionGraph() throws Exception {
+    // foo -> [action] -> foo
+    Artifact foo = createDerivedArtifact("foo");
+    try {
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(foo), asSet(foo)));
+      buildArtifacts(foo);
+      fail("Builder failed to detect cyclic action graph");
+    } catch (BuildFailedException e) {
+      assertEquals(e.getMessage(), CYCLE_MSG);
+    }
+  }
+
+  public void testCycleInActionGraphBelowTwoActions() throws Exception {
+    // bar -> [action] -> foo1
+    // bar -> [action] -> foo2
+    // baz -> [action] -> bar
+    // bar -> [action] -> baz
+    Artifact foo1 = createDerivedArtifact("foo1");
+    Artifact foo2 = createDerivedArtifact("foo2");
+    Artifact bar = createDerivedArtifact("bar");
+    Artifact baz = createDerivedArtifact("baz");
+    try {
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(bar), asSet(foo1)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(bar), asSet(foo2)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(baz), asSet(bar)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(bar), asSet(baz)));
+      buildArtifacts(foo1, foo2);
+      fail("Builder failed to detect cyclic action graph");
+    } catch (BuildFailedException e) {
+      assertEquals(e.getMessage(), CYCLE_MSG);
+    }
+  }
+
+
+  public void testCyclicActionGraphWithTail() throws Exception {
+    // bar -> [action] -> foo
+    // baz -> [action] -> bar
+    // bat, foo -> [action] -> baz
+    Artifact foo = createDerivedArtifact("foo");
+    Artifact bar = createDerivedArtifact("bar");
+    Artifact baz = createDerivedArtifact("baz");
+    Artifact bat = createDerivedArtifact("bat");
+    try {
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(bar), asSet(foo)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(baz), asSet(bar)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, asSet(bat, foo), asSet(baz)));
+      registerAction(new TestAction(TestAction.NO_EFFECT, ImmutableSet.<Artifact>of(), asSet(bat)));
+      buildArtifacts(foo);
+      fail("Builder failed to detect cyclic action graph");
+    } catch (BuildFailedException e) {
+      assertEquals(e.getMessage(), CYCLE_MSG);
+    }
+  }
+
+  public void testDuplicatedInput() throws Exception {
+    // <null> -> [action] -> foo
+    // (foo, foo) -> [action] -> bar
+    Artifact foo = createDerivedArtifact("foo");
+    Artifact bar = createDerivedArtifact("bar");
+    registerAction(
+        new TestAction(TestAction.NO_EFFECT, ParallelBuilderTest.<Artifact>asSet(), asSet(foo)));
+    registerAction(
+        new TestAction(TestAction.NO_EFFECT, Lists.<Artifact>newArrayList(foo, foo), asSet(bar)));
+    buildArtifacts(bar);
+  }
+
+
+  // Regression test for bug #735765, "ParallelBuilder still issues new jobs
+  // after one has failed, without --keep-going."  The incorrect behaviour is
+  // that, when the first job fails, while no new jobs are added to the queue
+  // of runnable jobs, the queue may have lots of work in it, and the
+  // ParallelBuilder always completes these jobs before it returns.  The
+  // correct behaviour is to discard all the jobs in the queue after the first
+  // one fails.
+  public void assertNoNewJobsAreRunAfterFirstFailure(final boolean catastrophe, boolean keepGoing)
+      throws Exception {
+    // Strategy: Limit parallelism to 3.  Enqueue 10 runnable tasks that run
+    // for an appreciable period (say 100ms).  Ensure that at most 3 of those
+    // tasks completed.  This proves that all runnable tasks were dropped from
+    // the queue after the first batch (which included errors) was finished.
+    // It should be pretty robust even in the face of timing variations.
+
+    final AtomicInteger completedTasks = new AtomicInteger(0);
+
+    int numJobs = 50;
+    Artifact[] artifacts = new Artifact[numJobs];
+
+    for (int ii = 0; ii < numJobs; ++ii) {
+      Artifact out = createDerivedArtifact(ii + ".out");
+      List<Artifact> inputs = (catastrophe && ii > 10)
+          ? ImmutableList.of(artifacts[0])
+          : Artifact.NO_ARTIFACTS;
+      final int iCopy = ii;
+      registerAction(new TestAction(new Callable<Void>() {
+          @Override
+          public Void call() throws Exception {
+            Thread.sleep(100); // 100ms
+            completedTasks.getAndIncrement();
+            throw new IOException("task failed");
+          }
+        },
+          inputs, ImmutableList.of(out)) {
+        @Override
+        public void execute(ActionExecutionContext actionExecutionContext)
+        throws ActionExecutionException {
+          if (catastrophe && iCopy == 0) {
+            try {
+              Thread.sleep(300); // 300ms
+            } catch (InterruptedException e) {
+              throw new RuntimeException(e);
+            }
+            completedTasks.getAndIncrement();
+            throw new ActionExecutionException("This is a catastrophe", this, true);
+          }
+          super.execute(actionExecutionContext);
+        }
+      });
+      artifacts[ii] = out;
+    }
+
+    // Don't fail fast when we encounter the error
+    reporter.removeHandler(failFastHandler);
+
+    try {
+      buildArtifacts(createBuilder(3, keepGoing), artifacts);
+      fail();
+    } catch (BuildFailedException e) {
+      assertContainsEvent("task failed");
+    }
+    if (completedTasks.get() >= numJobs) {
+      fail("Expected early termination due to failed task, but all tasks ran to completion.");
+    }
+  }
+
+   public void testNoNewJobsAreRunAfterFirstFailure() throws Exception {
+     assertNoNewJobsAreRunAfterFirstFailure(false, false);
+   }
+
+   public void testNoNewJobsAreRunAfterCatastrophe() throws Exception {
+     assertNoNewJobsAreRunAfterFirstFailure(true, true);
+   }
+
+  private Artifact createInputFile(String name) throws IOException {
+    Artifact artifact = createSourceArtifact(name);
+    Path path = artifact.getPath();
+    FileSystemUtils.createDirectoryAndParents(path.getParentDirectory());
+    FileSystemUtils.createEmptyFile(path);
+    return artifact;
+  }
+
+  public void testProgressReporting() throws Exception {
+    // Build three artifacts in 3 separate actions (baz depends on bar and bar
+    // depends on foo.  Make sure progress is reported at the beginning of all
+    // three actions.
+    List<Artifact> sourceFiles = new ArrayList<>();
+    for (int i = 0; i < 10; i++) {
+      sourceFiles.add(createInputFile("file" + i));
+    }
+    Artifact foo = createDerivedArtifact("foo");
+    Artifact bar = createDerivedArtifact("bar");
+    Artifact baz = createDerivedArtifact("baz");
+    bar.getPath().delete();
+    baz.getPath().delete();
+
+    final List<String> messages = new ArrayList<>();
+    EventHandler handler = new EventHandler() {
+
+      @Override
+      public void handle(Event event) {
+        EventKind k = event.getKind();
+        if (k == EventKind.START || k == EventKind.FINISH) {
+          // Remove the tmpDir as this is user specific and the assert would
+          // fail below.
+          messages.add(
+              event.getMessage().replaceFirst(TestUtils.tmpDir(), "") + " " + event.getKind());
+        }
+      }
+    };
+    reporter.addHandler(handler);
+    reporter.addHandler(new PrintingEventHandler(EventKind.ALL_EVENTS));
+
+    registerAction(new TestAction(TestAction.NO_EFFECT, sourceFiles, asSet(foo)));
+    registerAction(new TestAction(TestAction.NO_EFFECT, asSet(foo), asSet(bar)));
+    registerAction(new TestAction(TestAction.NO_EFFECT, asSet(bar), asSet(baz)));
+    buildArtifacts(baz);
+    // Check that the percentages increase non-linearly, because foo has 10 input files
+    List<String> expectedMessages = Lists.newArrayList(
+        "Test foo START",
+        "Test foo FINISH",
+        "Test bar START",
+        "Test bar FINISH",
+        "Test baz START",
+        "Test baz FINISH");
+    assertThat(messages).containsAllIn(expectedMessages);
+
+    // Now do an incremental rebuild of bar and baz,
+    // and check the incremental progress percentages.
+    messages.clear();
+    bar.getPath().delete();
+    baz.getPath().delete();
+    // This uses a new builder instance so that we refetch timestamps from
+    // (in-memory) file system, rather than using cached entries.
+    buildArtifacts(baz);
+    expectedMessages = Lists.newArrayList(
+        "Test bar START",
+        "Test bar FINISH",
+        "Test baz START",
+        "Test baz FINISH");
+    assertThat(messages).containsAllIn(expectedMessages);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java
new file mode 100644
index 0000000..7574951
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java
@@ -0,0 +1,217 @@
+// 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.Label;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
+import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
+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;
+
+import java.io.IOException;
+
+/**
+ * Tests for {@link PrepareDepsOfTargetsUnderDirectoryFunction}. Insert excuses here.
+ */
+public class PrepareDepsOfTargetsUnderDirectoryFunctionTest extends BuildViewTestCase {
+
+  private SkyframeExecutor skyframeExecutor;
+
+  @Override
+  protected void setUp() throws Exception {
+    super.setUp();
+    skyframeExecutor = getSkyframeExecutor();
+  }
+
+  private SkyKey createPrepDepsKey(Path root, PathFragment rootRelativePath) {
+    return createPrepDepsKey(root, rootRelativePath, ImmutableSet.<PathFragment>of());
+  }
+
+  private SkyKey createPrepDepsKey(Path root, PathFragment rootRelativePath,
+      ImmutableSet<PathFragment> excludedPaths) {
+    RootedPath rootedPath = RootedPath.toRootedPath(root, rootRelativePath);
+    return PrepareDepsOfTargetsUnderDirectoryValue.key(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME, rootedPath, excludedPaths);
+  }
+
+  private SkyKey createPrepDepsKey(Path root, PathFragment rootRelativePath,
+      ImmutableSet<PathFragment> excludedPaths, FilteringPolicy filteringPolicy) {
+    RootedPath rootedPath = RootedPath.toRootedPath(root, rootRelativePath);
+    return PrepareDepsOfTargetsUnderDirectoryValue.key(
+        PackageIdentifier.DEFAULT_REPOSITORY_NAME, rootedPath, excludedPaths, filteringPolicy);
+  }
+
+  private EvaluationResult<PrepareDepsOfTargetsUnderDirectoryValue> getEvaluationResult(SkyKey key)
+      throws InterruptedException {
+    BuildDriver driver = skyframeExecutor.getDriverForTesting();
+    EvaluationResult<PrepareDepsOfTargetsUnderDirectoryValue> evaluationResult =
+        driver.evaluate(ImmutableList.of(key), /*keepGoing=*/false,
+            SequencedSkyframeExecutor.DEFAULT_THREAD_COUNT, reporter);
+    Preconditions.checkState(!evaluationResult.hasError());
+    return evaluationResult;
+  }
+
+  public void testTransitiveLoading() throws Exception {
+    // Given a package "a" with a genrule "a" that depends on a target in package "b",
+    createPackages();
+
+    // When package "a" is evaluated,
+    SkyKey key = createPrepDepsKey(rootDirectory, new PathFragment("a"));
+    EvaluationResult<PrepareDepsOfTargetsUnderDirectoryValue> evaluationResult =
+        getEvaluationResult(key);
+    WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
+
+    // Then the TransitiveTraversalValue for "a:a" is evaluated,
+    SkyKey aaKey = TransitiveTraversalValue.key(Label.create("a", "a"));
+    assertThat(graph.exists(aaKey)).isTrue();
+
+    // And that TransitiveTraversalValue depends on "b:b.txt".
+    Iterable<SkyKey> depsOfAa =
+        Iterables.getOnlyElement(graph.getDirectDeps(ImmutableList.of(aaKey)).values());
+    SkyKey bTxtKey = TransitiveTraversalValue.key(Label.create("b", "b.txt"));
+    assertThat(depsOfAa).contains(bTxtKey);
+
+    // And the TransitiveTraversalValue for "b:b.txt" is evaluated.
+    assertThat(graph.exists(bTxtKey)).isTrue();
+  }
+
+  public void testTargetFilterSensitivity() throws Exception {
+    // Given a package "a" with a genrule "a" that depends on a target in package "b", and a test
+    // rule "aTest",
+    createPackages();
+
+    // When package "a" is evaluated under a test-only filtering policy,
+    SkyKey key = createPrepDepsKey(rootDirectory, new PathFragment("a"),
+        ImmutableSet.<PathFragment>of(), FilteringPolicies.FILTER_TESTS);
+    EvaluationResult<PrepareDepsOfTargetsUnderDirectoryValue> evaluationResult =
+        getEvaluationResult(key);
+    WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
+
+    // Then the TransitiveTraversalValue for "a:a" is not evaluated,
+    SkyKey aaKey = TransitiveTraversalValue.key(Label.create("a", "a"));
+    assertThat(graph.exists(aaKey)).isFalse();
+
+    // But the TransitiveTraversalValue for "a:aTest" is.
+    SkyKey aaTestKey = TransitiveTraversalValue.key(Label.create("a", "aTest"));
+    assertThat(graph.exists(aaTestKey)).isTrue();
+  }
+
+  /**
+   * Creates a package "a" with a genrule "a" that depends on a target in a created package "b",
+   * and a test rule "aTest".
+   */
+  private void createPackages() throws IOException {
+    scratch.file("a/BUILD",
+        "genrule(name='a', cmd='', srcs=['//b:b.txt'], outs=['a.out'])",
+        "sh_test(name='aTest', size='small', srcs=['aTest.sh'])");
+    scratch.file("b/BUILD",
+        "exports_files(['b.txt'])");
+  }
+
+  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 via PrepareDepsOfTargetsUnderDirectoryValue with "a/b"
+    // excluded,
+    PathFragment excludedPathFragment = new PathFragment("a/b");
+    SkyKey key = createPrepDepsKey(rootDirectory, new PathFragment("a"),
+        ImmutableSet.of(excludedPathFragment));
+    EvaluationResult<PrepareDepsOfTargetsUnderDirectoryValue> evaluationResult =
+        getEvaluationResult(key);
+    PrepareDepsOfTargetsUnderDirectoryValue value = evaluationResult.get(key);
+
+    // Then the value reports that "a" is a package,
+    assertThat(value.isDirectoryPackage()).isTrue();
+
+    // And only the subdirectory corresponding to "a/c" is present in the result,
+    RootedPath onlySubdir =
+        Iterables.getOnlyElement(value.getSubdirectoryTransitivelyContainsPackages().keySet());
+    assertThat(onlySubdir.getRelativePath()).isEqualTo(new PathFragment("a/c"));
+
+    // And the "a/c" subdirectory reports a package under it.
+    assertThat(value.getSubdirectoryTransitivelyContainsPackages().get(onlySubdir)).isTrue();
+
+    // Also, the computation graph does not contain a cached value for "a/b".
+    WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
+    assertFalse(graph.exists(createPrepDepsKey(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(createPrepDepsKey(rootDirectory, new PathFragment("a/c"),
+        ImmutableSet.<PathFragment>of())));
+  }
+
+  public void testExcludedSubdirectoryGettingPassedDown() throws Exception {
+    // Given a package "a", and a package below it in "a/b/c", and a non-BUILD file below it in
+    // "a/b/d",
+    scratch.file("a/BUILD");
+    scratch.file("a/b/c/BUILD");
+    scratch.file("a/b/d/helloworld");
+
+    // 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 = createPrepDepsKey(rootDirectory, new PathFragment("a"), excludedPaths);
+    EvaluationResult<PrepareDepsOfTargetsUnderDirectoryValue> evaluationResult =
+        getEvaluationResult(key);
+    PrepareDepsOfTargetsUnderDirectoryValue value = evaluationResult.get(key);
+
+    // Then the value reports that "a" is a package,
+    assertThat(value.isDirectoryPackage()).isTrue();
+
+    // And the subdirectory corresponding to "a/b" is present in the result,
+    RootedPath onlySubdir =
+        Iterables.getOnlyElement(value.getSubdirectoryTransitivelyContainsPackages().keySet());
+    assertThat(onlySubdir.getRelativePath()).isEqualTo(new PathFragment("a/b"));
+
+    // And the "a/b" subdirectory does not report a package under it (because it got excluded).
+    assertThat(value.getSubdirectoryTransitivelyContainsPackages().get(onlySubdir)).isFalse();
+
+    // 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());
+    SkyKey abKey = createPrepDepsKey(rootDirectory, new PathFragment("a/b"), excludedPaths);
+    assertThat(graph.exists(abKey)).isTrue();
+    PrepareDepsOfTargetsUnderDirectoryValue abValue =
+        (PrepareDepsOfTargetsUnderDirectoryValue) Preconditions.checkNotNull(graph.getValue(abKey));
+
+    // And that value says that "a/b" is not a package,
+    assertThat(abValue.isDirectoryPackage()).isFalse();
+
+    // And only the subdirectory "a/b/d" is present in that value,
+    RootedPath abd =
+        Iterables.getOnlyElement(abValue.getSubdirectoryTransitivelyContainsPackages().keySet());
+    assertThat(abd.getRelativePath()).isEqualTo(new PathFragment("a/b/d"));
+
+    // And no package is under "a/b/d".
+    assertThat(abValue.getSubdirectoryTransitivelyContainsPackages().get(abd)).isFalse();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTest.java
new file mode 100644
index 0000000..5359fe9
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTest.java
@@ -0,0 +1,317 @@
+// 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 org.junit.Assert.fail;
+
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.BuildFailedException;
+import com.google.devtools.build.lib.actions.util.TestAction;
+import com.google.devtools.build.lib.testutil.BlazeTestUtils;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+
+import java.util.Collection;
+import java.util.Collections;
+
+/**
+ * Test suite for TimestampBuilder.
+ *
+ */
+public class TimestampBuilderTest extends TimestampBuilderTestCase {
+
+  public void testAmnesiacBuilderAlwaysRebuilds() throws Exception {
+    // [action] -> hello
+    Artifact hello = createDerivedArtifact("hello");
+    Button button = createActionButton(emptySet, Sets.newHashSet(hello));
+
+    button.pressed = false;
+    buildArtifacts(amnesiacBuilder(), hello);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(amnesiacBuilder(), hello);
+    assertTrue(button.pressed); // rebuilt
+  }
+
+  // If we re-use the same builder (even an "amnesiac" builder), it remembers
+  // which Actions it has already visited, and doesn't revisit them, even if
+  // they would otherwise be rebuilt.
+  //
+  // That is, Builders conflate traversal and dependency analysis, and don't
+  // revisit a node (traversal) even if it needs to be rebuilt (dependency
+  // analysis).  We might want to separate these aspects.
+  public void testBuilderDoesntRevisitActions() throws Exception {
+    // [action] -> hello
+    Artifact hello = createDerivedArtifact("hello");
+    Counter counter = createActionCounter(emptySet, Sets.newHashSet(hello));
+
+    Builder amnesiacBuilder = amnesiacBuilder();
+
+    counter.count = 0;
+    buildArtifacts(amnesiacBuilder, hello, hello);
+    assertEquals(counter.count, 1); // built only once
+  }
+
+  public void testBuildingExistingSourcefileSuceeds() throws Exception {
+    Artifact hello = createSourceArtifact("hello");
+    BlazeTestUtils.makeEmptyFile(hello.getPath());
+    buildArtifacts(cachingBuilder(), hello);
+  }
+
+  public void testBuildingNonexistentSourcefileFails() throws Exception {
+    reporter.removeHandler(failFastHandler);
+    Artifact hello = createSourceArtifact("hello");
+    try {
+      buildArtifacts(cachingBuilder(), hello);
+      fail("Expected input file to be missing");
+    } catch (BuildFailedException e) {
+      assertThat(e).hasMessage("missing input file '" + hello.getPath() + "'");
+    }
+  }
+
+  public void testCachingBuilderCachesUntilReset() throws Exception {
+    // [action] -> hello
+    Artifact hello = createDerivedArtifact("hello");
+    Button button = createActionButton(emptySet, Sets.newHashSet(hello));
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), hello);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    inMemoryCache.reset();
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), hello);
+    assertTrue(button.pressed); // rebuilt
+  }
+
+  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(cachingBuilder(), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    BlazeTestUtils.makeEmptyFile(optional.getPath());
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    optional.getPath().delete();
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testModifyingInputCausesActionReexecution() 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(cachingBuilder(), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    // inMemoryMetadataCache.useFileDigest is false, so new timestamp is enough to force a rebuild.
+    FileSystemUtils.touchFile(hello.getPath());
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testOnlyModifyingInputContentCausesReexecution() throws Exception {
+    // hello -> [action] -> goodbye
+    Artifact hello = createSourceArtifact("hello");
+    // touch file to create the directory structure
+    BlazeTestUtils.makeEmptyFile(hello.getPath());
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content1");
+
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button = createActionButton(Sets.newHashSet(hello), Sets.newHashSet(goodbye));
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+
+    FileSystemUtils.touchFile(hello.getPath());
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // still not rebuilt
+
+    FileSystemUtils.writeContentAsLatin1(hello.getPath(), "content2");
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testModifyingOutputCausesActionReexecution() throws Exception {
+    // [action] -> hello
+    Artifact hello = createDerivedArtifact("hello");
+    Button button = createActionButton(emptySet, Sets.newHashSet(hello));
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), hello);
+    assertTrue(button.pressed); // built
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), hello);
+    assertFalse(button.pressed); // not rebuilt
+
+    // Touching the *output* file 'hello' causes 'action' to re-execute, to
+    // make things consistent again; this is not what Make would do, but it is
+    // correct according to this Builder.
+    BlazeTestUtils.changeModtime(hello.getPath());
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), hello);
+    assertTrue(button.pressed); // rebuilt
+
+    button.pressed = false;
+    buildArtifacts(cachingBuilder(), hello);
+    assertFalse(button.pressed); // not rebuilt
+  }
+
+  public void testBuildingTransitivePrerequisites() throws Exception {
+    // hello -> [action1] -> wazuup -> [action2] -> goodbye
+    Artifact hello = createSourceArtifact("hello");
+    BlazeTestUtils.makeEmptyFile(hello.getPath());
+    Artifact wazuup = createDerivedArtifact("wazuup");
+    Button button1 = createActionButton(Sets.newHashSet(hello), Sets.newHashSet(wazuup));
+    Artifact goodbye = createDerivedArtifact("goodbye");
+    Button button2 = createActionButton(Sets.newHashSet(wazuup), Sets.newHashSet(goodbye));
+
+    button1.pressed = button2.pressed = false;
+    buildArtifacts(cachingBuilder(), wazuup);
+    assertTrue(button1.pressed); // built wazuup
+    assertFalse(button2.pressed); // goodbye not built
+
+    button1.pressed = button2.pressed = false;
+    buildArtifacts(cachingBuilder(), wazuup);
+    assertFalse(button1.pressed); // wazuup not rebuilt
+    assertFalse(button2.pressed); // goodbye not built
+
+    button1.pressed = button2.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button1.pressed); // wazuup not rebuilt
+    assertTrue(button2.pressed); // built goodbye
+
+    button1.pressed = button2.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertFalse(button1.pressed); // wazuup not rebuilt
+    assertFalse(button2.pressed); // goodbye not rebuilt
+
+    FileSystemUtils.touchFile(hello.getPath());
+
+    button1.pressed = button2.pressed = false;
+    buildArtifacts(cachingBuilder(), goodbye);
+    assertTrue(button1.pressed); // hello rebuilt
+    assertTrue(button2.pressed); // goodbye rebuilt
+  }
+
+  public void testWillNotRebuildActionsWithEmptyListOfInputsSpuriously()
+      throws Exception {
+
+    Artifact anOutputFile = createDerivedArtifact("anOutputFile");
+    Artifact anotherOutputFile = createDerivedArtifact("anotherOutputFile");
+    Collection<Artifact> noInputs = Collections.emptySet();
+
+    Button aButton = createActionButton(noInputs, Sets.newHashSet(anOutputFile));
+    Button anotherButton = createActionButton(noInputs,
+                                              Sets.newHashSet(anotherOutputFile));
+
+    buildArtifacts(cachingBuilder(), anOutputFile, anotherOutputFile);
+
+    assertTrue(aButton.pressed);
+    assertTrue(anotherButton.pressed);
+
+    aButton.pressed = anotherButton.pressed = false;
+
+    buildArtifacts(cachingBuilder(), anOutputFile, anotherOutputFile);
+
+    assertFalse(aButton.pressed);
+    assertFalse(anotherButton.pressed);
+  }
+
+  public void testMissingSourceFileIsAnError() throws Exception {
+    // A missing input to an action must be treated as an error because there's
+    // a risk that the action that consumes it will succeed, but with a
+    // different behavior (imagine that it globs over the directory, for
+    // example).  It's not ok to simply try the action and let the action
+    // report "input file not found".
+    //
+    // (However, there are exceptions to this principle: C++ compilation
+    // actions may depend on non-existent headers from stale .d files.  We need
+    // to allow the action to proceed to execution in this case.)
+
+    reporter.removeHandler(failFastHandler);
+    Artifact in = createSourceArtifact("in"); // doesn't exist
+    Artifact out = createDerivedArtifact("out");
+
+    registerAction(new TestAction(TestAction.NO_EFFECT, Collections.singleton(in),
+        Collections.singleton(out)));
+
+    try {
+      buildArtifacts(amnesiacBuilder(), out); // fails with ActionExecutionException
+      fail();
+    } catch (BuildFailedException e) {
+      assertThat(e.getMessage()).contains("1 input file(s) do not exist");
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunctionTest.java
new file mode 100644
index 0000000..da7eadc
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunctionTest.java
@@ -0,0 +1,195 @@
+// 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.ConfiguredRuleClassProvider;
+import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
+import com.google.devtools.build.lib.bazel.rules.BazelRulesModule;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageFactory;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.testutil.MoreAsserts;
+import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
+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.SkyFunction;
+import com.google.devtools.build.skyframe.SkyKey;
+
+import org.mockito.Matchers;
+import org.mockito.Mockito;
+
+import java.io.IOException;
+
+/**
+ * Test for {@link WorkspaceFileFunction}.
+ */
+public class WorkspaceFileFunctionTest extends BuildViewTestCase {
+
+  private WorkspaceFileFunction skyFunc;
+  private FakeFileValue fakeWorkspaceFileValue;
+
+  private static class FakeFileValue extends FileValue {
+    private boolean exists;
+    private long size;
+
+    FakeFileValue() {
+      super();
+      exists = true;
+      size = 0L;
+    }
+
+    @Override
+    public RootedPath realRootedPath() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public FileStateValue realFileStateValue() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public boolean exists() {
+      return exists;
+    }
+
+    private void setExists(boolean exists) {
+      this.exists = exists;
+    }
+
+    @Override
+    public long getSize() {
+      return size;
+    }
+
+    private void setSize(long size) {
+      this.size = size;
+    }
+  }
+
+  @Override
+  public void setUp() throws Exception {
+    super.setUp();
+    ConfiguredRuleClassProvider ruleClassProvider = TestRuleClassProvider.getRuleClassProvider();
+    skyFunc =
+        new WorkspaceFileFunction(
+            ruleClassProvider,
+            new PackageFactory(
+                TestRuleClassProvider.getRuleClassProvider(),
+                new BazelRulesModule().getPackageEnvironmentExtension()),
+            directories);
+    fakeWorkspaceFileValue = new FakeFileValue();
+  }
+
+  private Label getLabelMapping(Package pkg, String name) throws NoSuchTargetException {
+    return (Label) ((Rule) pkg.getTarget(name)).getAttributeContainer().getAttr("actual");
+  }
+
+  private RootedPath createWorkspaceFile(String... contents) throws IOException {
+    Path workspacePath = scratch.overwriteFile("WORKSPACE", contents);
+    fakeWorkspaceFileValue.setSize(workspacePath.getFileSize());
+    return RootedPath.toRootedPath(
+        workspacePath.getParentDirectory(), new PathFragment(workspacePath.getBaseName()));
+  }
+
+  private SkyFunction.Environment getEnv() {
+    SkyFunction.Environment env = Mockito.mock(SkyFunction.Environment.class);
+    Mockito.when(env.getValue(Matchers.<SkyKey>any())).thenReturn(fakeWorkspaceFileValue);
+    return env;
+  }
+
+  public void testInvalidRepo() throws Exception {
+    RootedPath workspacePath = createWorkspaceFile("workspace(name = 'foo$')");
+    PackageValue value =
+        (PackageValue) skyFunc.compute(PackageValue.workspaceKey(workspacePath), getEnv());
+    Package pkg = value.getPackage();
+    assertTrue(pkg.containsErrors());
+    MoreAsserts.assertContainsEvent(pkg.getEvents(), "target names may not contain '$'");
+  }
+
+  public void testBindFunction() throws Exception {
+    String lines[] = {"bind(name = 'foo/bar',", "actual = '//foo:bar')"};
+    RootedPath workspacePath = createWorkspaceFile(lines);
+
+    SkyKey key = PackageValue.workspaceKey(workspacePath);
+    PackageValue value = (PackageValue) skyFunc.compute(key, getEnv());
+    Package pkg = value.getPackage();
+    assertEquals(Label.parseAbsolute("//foo:bar"), getLabelMapping(pkg, "foo/bar"));
+    MoreAsserts.assertNoEvents(pkg.getEvents());
+  }
+
+  public void testBindArgsReversed() throws Exception {
+    String lines[] = {"bind(actual = '//foo:bar', name = 'foo/bar')"};
+    RootedPath workspacePath = createWorkspaceFile(lines);
+
+    SkyKey key = PackageValue.workspaceKey(workspacePath);
+    PackageValue value = (PackageValue) skyFunc.compute(key, getEnv());
+    Package pkg = value.getPackage();
+    assertEquals(Label.parseAbsolute("//foo:bar"), getLabelMapping(pkg, "foo/bar"));
+    MoreAsserts.assertNoEvents(pkg.getEvents());
+  }
+
+  public void testNonExternalBinding() throws Exception {
+    // name must be a valid label name.
+    String lines[] = {"bind(name = 'foo:bar', actual = '//bar/baz')"};
+    RootedPath workspacePath = createWorkspaceFile(lines);
+
+    PackageValue value =
+        (PackageValue) skyFunc.compute(PackageValue.workspaceKey(workspacePath), getEnv());
+    Package pkg = value.getPackage();
+    assertTrue(pkg.containsErrors());
+    MoreAsserts.assertContainsEvent(pkg.getEvents(), "target names may not contain ':'");
+  }
+
+  public void testWorkspaceFileParsingError() throws Exception {
+    // //external:bar:baz is not a legal package.
+    String lines[] = {"bind(name = 'foo/bar', actual = '//external:bar:baz')"};
+    RootedPath workspacePath = createWorkspaceFile(lines);
+
+    PackageValue value =
+        (PackageValue) skyFunc.compute(PackageValue.workspaceKey(workspacePath), getEnv());
+    Package pkg = value.getPackage();
+    assertTrue(pkg.containsErrors());
+    MoreAsserts.assertContainsEvent(pkg.getEvents(), "target names may not contain ':'");
+  }
+
+  public void testNoWorkspaceFile() throws Exception {
+    // Even though the WORKSPACE exists, Skyframe thinks it doesn't, so it doesn't.
+    String lines[] = {"bind(name = 'foo/bar', actual = '//foo:bar')"};
+    RootedPath workspacePath = createWorkspaceFile(lines);
+    fakeWorkspaceFileValue.setExists(false);
+
+    PackageValue value =
+        (PackageValue) skyFunc.compute(PackageValue.workspaceKey(workspacePath), getEnv());
+    Package pkg = value.getPackage();
+    assertFalse(pkg.containsErrors());
+    MoreAsserts.assertNoEvents(pkg.getEvents());
+  }
+
+  public void testListBindFunction() throws Exception {
+    String lines[] = {
+        "L = ['foo', 'bar']", "bind(name = '%s/%s' % (L[0], L[1]),", "actual = '//foo:bar')"};
+    RootedPath workspacePath = createWorkspaceFile(lines);
+
+    SkyKey key = PackageValue.workspaceKey(workspacePath);
+    PackageValue value = (PackageValue) skyFunc.compute(key, getEnv());
+    Package pkg = value.getPackage();
+    assertEquals(Label.parseAbsolute("//foo:bar"), getLabelMapping(pkg, "foo/bar"));
+    MoreAsserts.assertNoEvents(pkg.getEvents());
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/skyframe/BUILD b/src/test/java/com/google/devtools/build/skyframe/BUILD
new file mode 100644
index 0000000..7313ed0
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/skyframe/BUILD
@@ -0,0 +1,53 @@
+TESTUTIL_FILES = [
+    "DeterministicInMemoryGraph.java",
+    "NotifyingInMemoryGraph.java",
+    "TrackingAwaiter.java",
+    "GraphTester.java",
+    "GenericFunctionException.java",
+    "SomeErrorException.java",
+    "TrackingInvalidationReceiver.java",
+    "WalkableGraphUtils.java",
+]
+
+java_library(
+    name = "testutil",
+    srcs = TESTUTIL_FILES,
+    visibility = [
+        "//src/test/java/com/google/devtools/build/lib:__pkg__",
+    ],
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib:collect",
+        "//src/main/java/com/google/devtools/build/lib:concurrent",
+        "//src/main/java/com/google/devtools/build/lib:events",
+        "//src/main/java/com/google/devtools/build/lib:util",
+        "//src/main/java/com/google/devtools/build/skyframe",
+        "//src/test/java/com/google/devtools/build/lib:testutil",
+        "//third_party:guava",
+        "//third_party:guava-testlib",
+        "//third_party:jsr305",
+        "//third_party:truth",
+    ],
+)
+
+java_test(
+    name = "skyframe_base_test",
+    srcs = glob(
+        ["*.java"],
+        exclude = TESTUTIL_FILES,
+    ),
+    args = ["com.google.devtools.build.skyframe.AllTests"],
+    deps = [
+        ":testutil",
+        "//src/main/java/com/google/devtools/build/lib:collect",
+        "//src/main/java/com/google/devtools/build/lib:concurrent",
+        "//src/main/java/com/google/devtools/build/lib:events",
+        "//src/main/java/com/google/devtools/build/lib:util",
+        "//src/main/java/com/google/devtools/build/skyframe",
+        "//src/test/java/com/google/devtools/build/lib:testutil",
+        "//third_party:guava",
+        "//third_party:guava-testlib",
+        "//third_party:jsr305",
+        "//third_party:junit4",
+        "//third_party:truth",
+    ],
+)