Don't treat external files as immutable

Fixes #352.

RELNOTES: Files in external repositories are now treated as mutable, which will make the correctness guarantees of using external repositories stronger (existent), but may cause performance penalties.

--
MOS_MIGRATED_REVID=109676408
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/BazelRepositoryModule.java b/src/main/java/com/google/devtools/build/lib/bazel/BazelRepositoryModule.java
index 4a3e356..d9e324b 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/BazelRepositoryModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/BazelRepositoryModule.java
@@ -16,7 +16,6 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.BlazeVersionInfo;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
@@ -60,13 +59,11 @@
 import com.google.devtools.build.lib.runtime.CommandEnvironment;
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.util.Clock;
-import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.common.options.OptionsProvider;
 
 import java.util.Map.Entry;
-import java.util.Set;
 import java.util.UUID;
 import java.util.concurrent.atomic.AtomicBoolean;
 
@@ -75,7 +72,6 @@
  */
 public class BazelRepositoryModule extends BlazeModule {
 
-  private BlazeDirectories directories;
   // A map of repository handlers that can be looked up by rule class name.
   private final ImmutableMap<String, RepositoryFunction> repositoryHandlers;
   private final AtomicBoolean isFetch = new AtomicBoolean(false);
@@ -109,18 +105,12 @@
   public void blazeStartup(OptionsProvider startupOptions,
       BlazeVersionInfo versionInfo, UUID instanceId, BlazeDirectories directories,
       Clock clock) {
-    this.directories = directories;
     for (RepositoryFunction handler : repositoryHandlers.values()) {
       handler.setDirectories(directories);
     }
   }
 
   @Override
-  public Set<Path> getImmutableDirectories() {
-    return ImmutableSet.of(RepositoryFunction.getExternalRepositoryDirectory(directories));
-  }
-
-  @Override
   public void initializeRuleClasses(ConfiguredRuleClassProvider.Builder builder) {
     for (Entry<String, RepositoryFunction> handler : repositoryHandlers.entrySet()) {
       // TODO(bazel-team): Migrate away from Class<?>
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
index e6bff64..f14b954 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.pkgcache;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Objects;
 import com.google.common.base.Verify;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -33,6 +32,7 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
+import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicReference;
 
@@ -93,23 +93,23 @@
 
   /**
    * Like #getPackageBuildFile(), but returns null instead of throwing.
-   *
-   * @param packageName the name of the package.
+   *  @param packageIdentifier the name of the package.
    * @param cache a filesystem-level cache of stat() calls.
    */
-  public Path getPackageBuildFileNullable(PackageIdentifier packageName,
+  public Path getPackageBuildFileNullable(PackageIdentifier packageIdentifier,
       AtomicReference<? extends UnixGlob.FilesystemCalls> cache)  {
-    if (packageName.getRepository().isDefault()) {
-      return getFilePath(packageName.getPackageFragment().getRelative("BUILD"), cache);
-    } else if (!packageName.getRepository().isDefault()) {
+    if (packageIdentifier.getRepository().isDefault()) {
+      return getFilePath(packageIdentifier.getPackageFragment().getRelative("BUILD"), cache);
+    } else if (!packageIdentifier.getRepository().isDefault()) {
       Verify.verify(outputBase != null, String.format(
           "External package '%s' needs to be loaded but this PathPackageLocator instance does not "
-          + "support external packages",   packageName));
+              + "support external packages", packageIdentifier));
       // This works only to some degree, because it relies on the presence of the repository under
       // $OUTPUT_BASE/external, which is created by the appropriate RepositoryValue. This is true
       // for the invocation in GlobCache, but not for the locator.getBuildFileForPackage()
       // invocation in Parser#include().
-      Path buildFile = outputBase.getRelative(packageName.getPathFragment()).getRelative("BUILD");
+      Path buildFile = outputBase.getRelative(
+          packageIdentifier.getPathFragment()).getRelative("BUILD");
       FileStatus stat = cache.get().statNullable(buildFile, Symlinks.FOLLOW);
       if (stat != null && stat.isFile()) {
         return buildFile;
@@ -182,6 +182,7 @@
         resolvedPaths.add(rootPath);
       }
     }
+
     return new PathPackageLocator(outputBase, resolvedPaths);
   }
 
@@ -235,7 +236,7 @@
 
   @Override
   public int hashCode() {
-    return Objects.hashCode(pathEntries, outputBase);
+    return Objects.hash(pathEntries, outputBase);
   }
 
   @Override
@@ -246,7 +247,12 @@
     if (!(other instanceof PathPackageLocator)) {
       return false;
     }
-    return this.getPathEntries().equals(((PathPackageLocator) other).getPathEntries())
-        && Objects.equal(this.outputBase, ((PathPackageLocator) other).outputBase);
+    PathPackageLocator pathPackageLocator = (PathPackageLocator) other;
+    return Objects.equals(getPathEntries(), pathPackageLocator.getPathEntries())
+        && Objects.equals(outputBase, pathPackageLocator.outputBase);
+  }
+
+  public Path getOutputBase() {
+    return outputBase;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java
index 9f661be..2c23469 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeModule.java
@@ -17,7 +17,6 @@
 import com.google.common.base.Supplier;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.ActionContextConsumer;
 import com.google.devtools.build.lib.actions.ActionContextProvider;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
@@ -51,7 +50,6 @@
 
 import java.io.IOException;
 import java.util.Map;
-import java.util.Set;
 import java.util.UUID;
 
 import javax.annotation.Nullable;
@@ -105,13 +103,6 @@
   }
 
   /**
-   * Returns the set of directories under which blaze may assume all files are immutable.
-   */
-  public Set<Path> getImmutableDirectories() {
-    return ImmutableSet.<Path>of();
-  }
-
-  /**
    * May yield a supplier that provides factories for the Preprocessor to apply. Only one of the
    * configured modules may return non-null.
    *
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
index a0ab1bc..d804e11 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
@@ -24,7 +24,6 @@
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Range;
@@ -1341,16 +1340,7 @@
         }
       }
 
-      Set<Path> immutableDirectories = null;
-      {
-        ImmutableSet.Builder<Path> builder = new ImmutableSet.Builder<>();
-        for (BlazeModule module : blazeModules) {
-          builder.addAll(module.getImmutableDirectories());
-        }
-        immutableDirectories = builder.build();
-      }
-
-      Iterable<DiffAwareness.Factory> diffAwarenessFactories = null;
+      Iterable<DiffAwareness.Factory> diffAwarenessFactories;
       {
         ImmutableList.Builder<DiffAwareness.Factory> builder = new ImmutableList.Builder<>();
         boolean watchFS = startupOptionsProvider != null
@@ -1419,7 +1409,6 @@
               binTools,
               workspaceStatusActionFactory,
               ruleClassProvider.getBuildInfoFactories(),
-              immutableDirectories,
               diffAwarenessFactories,
               allowedMissingInputs,
               preprocessorFactorySupplier,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java b/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java
index eddbd9e..fc53e8d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/DirtinessCheckerUtils.java
@@ -16,8 +16,10 @@
 import static com.google.devtools.build.lib.skyframe.SkyFunctions.DIRECTORY_LISTING_STATE;
 import static com.google.devtools.build.lib.skyframe.SkyFunctions.FILE_STATE;
 
+import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -30,7 +32,7 @@
 import javax.annotation.Nullable;
 
 /** Utilities for checking dirtiness of keys (mainly filesystem keys) in the graph. */
-class DirtinessCheckerUtils {
+public class DirtinessCheckerUtils {
   private DirtinessCheckerUtils() {}
 
   static class FileDirtinessChecker extends SkyValueDirtinessChecker {
@@ -91,16 +93,53 @@
   }
 
   static final class MissingDiffDirtinessChecker extends BasicFilesystemDirtinessChecker {
-    private final Set<Path> missingDiffPaths;
+    private final Set<Path> missingDiffPackageRoots;
 
-    MissingDiffDirtinessChecker(final Set<Path> missingDiffPaths) {
-      this.missingDiffPaths = missingDiffPaths;
+    MissingDiffDirtinessChecker(final Set<Path> missingDiffPackageRoots) {
+      this.missingDiffPackageRoots = missingDiffPackageRoots;
     }
 
     @Override
     public boolean applies(SkyKey key) {
       return super.applies(key)
-          && missingDiffPaths.contains(((RootedPath) key.argument()).getRoot());
+          && missingDiffPackageRoots.contains(((RootedPath) key.argument()).getRoot());
+    }
+  }
+
+  /** Checks files outside of the package roots for changes. */
+  static final class ExternalDirtinessChecker extends BasicFilesystemDirtinessChecker {
+    private final PathPackageLocator packageLocator;
+
+    ExternalDirtinessChecker(PathPackageLocator packageLocator) {
+      this.packageLocator = packageLocator;
+    }
+
+    @Override
+    public boolean applies(SkyKey key) {
+      return super.applies(key)
+          && !ExternalFilesHelper.isInternal((RootedPath) key.argument(), packageLocator);
+    }
+
+    /**
+     * Files under output_base/external have a dependency on the WORKSPACE file, so we don't add a
+     * new SkyValue to the graph yet because it might change once the WORKSPACE file has been
+     * parsed.
+     *
+     * <p>This dirtiness checker is a bit conservative: files that are outside the package roots
+     * but aren't under output_base/external/ could just be stat-ed here (but they aren't).</p>
+     */
+    @Nullable
+    @Override
+    public SkyValue createNewValue(SkyKey key, @Nullable TimestampGranularityMonitor tsgm) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public SkyValueDirtinessChecker.DirtyResult check(
+        SkyKey skyKey, SkyValue oldValue, @Nullable TimestampGranularityMonitor tsgm) {
+      return Objects.equal(super.createNewValue(skyKey, tsgm), oldValue)
+          ? SkyValueDirtinessChecker.DirtyResult.notDirty(oldValue)
+          : SkyValueDirtinessChecker.DirtyResult.dirty(oldValue);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java
index 17d29ed..100858a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java
@@ -13,129 +13,91 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
-import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunction;
 
-import java.util.Set;
 import java.util.concurrent.atomic.AtomicReference;
 
 /** Common utilities for dealing with files outside the package roots. */
 public class ExternalFilesHelper {
 
   private final AtomicReference<PathPackageLocator> pkgLocator;
-  private final Set<Path> immutableDirs;
-  private final boolean errorOnExternalFiles;
-
-  public ExternalFilesHelper(AtomicReference<PathPackageLocator> pkgLocator) {
-    this(pkgLocator, ImmutableSet.<Path>of(), /*errorOnExternalFiles=*/false);
-  }
-
-  @VisibleForTesting
-  ExternalFilesHelper(AtomicReference<PathPackageLocator> pkgLocator,
-      boolean errorOnExternalFiles) {
-    this(pkgLocator, ImmutableSet.<Path>of(), errorOnExternalFiles);
-  }
+  private final ExternalFileAction externalFileAction;
 
   /**
    * @param pkgLocator an {@link AtomicReference} to a {@link PathPackageLocator} used to
-   *    determine what files are internal
-   * @param immutableDirs directories whose contents may be considered unchangeable
-   * @param errorOnExternalFiles whether or not to allow references to files outside of
-   *    the directories provided by pkgLocator or immutableDirs. See
-   *    {@link #maybeHandleExternalFile(RootedPath, SkyFunction.Environment)} for more details.
+   *    determine what files are internal.
+   * @param errorOnExternalFiles If files outside of package paths should be allowed.
    */
-  ExternalFilesHelper(AtomicReference<PathPackageLocator> pkgLocator, Set<Path> immutableDirs,
-      boolean errorOnExternalFiles) {
+  public ExternalFilesHelper(
+      AtomicReference<PathPackageLocator> pkgLocator, boolean errorOnExternalFiles) {
     this.pkgLocator = pkgLocator;
-    this.immutableDirs = immutableDirs;
-    this.errorOnExternalFiles = errorOnExternalFiles;
+    if (errorOnExternalFiles) {
+      this.externalFileAction = ExternalFileAction.ERROR_OUT;
+    } else {
+      this.externalFileAction = ExternalFileAction.DEPEND_ON_EXTERNAL_PKG;
+    }
+  }
+
+  private enum ExternalFileAction {
+    // Re-check the files when the WORKSPACE file changes.
+    DEPEND_ON_EXTERNAL_PKG,
+
+    // Throw an exception if there is an external file.
+    ERROR_OUT,
   }
 
   private enum FileType {
-    // A file inside the package roots.
+    // A file inside the package roots or in an external repository.
     INTERNAL_FILE,
 
-    // A file outside the package roots that users of ExternalFilesHelper may pretend is immutable.
-    EXTERNAL_IMMUTABLE_FILE,
-
     // A file outside the package roots about which we may make no other assumptions.
     EXTERNAL_MUTABLE_FILE,
   }
 
-  private FileType getFileType(RootedPath rootedPath) {
+  public static boolean isInternal(RootedPath rootedPath, PathPackageLocator packageLocator) {
     // TODO(bazel-team): This is inefficient when there are a lot of package roots or there are a
-    // lot of immutable directories. Consider either explicitly preventing this case or using a more
-    // efficient approach here (e.g. use a trie for determing if a file is under an immutable
+    // lot of external directories. Consider either explicitly preventing this case or using a more
+    // efficient approach here (e.g. use a trie for determining if a file is under an external
     // directory).
-    if (!pkgLocator.get().getPathEntries().contains(rootedPath.getRoot())) {
-      Path path = rootedPath.asPath();
-      for (Path immutableDir : immutableDirs) {
-        if (path.startsWith(immutableDir)) {
-          return FileType.EXTERNAL_IMMUTABLE_FILE;
-        }
-      }
-      return FileType.EXTERNAL_MUTABLE_FILE;
-    }
-    return FileType.INTERNAL_FILE;
-  }
-
-  public boolean shouldAssumeImmutable(RootedPath rootedPath) {
-    return getFileType(rootedPath) == FileType.EXTERNAL_IMMUTABLE_FILE;
+    return packageLocator.getPathEntries().contains(rootedPath.getRoot());
   }
 
   /**
-   * Potentially adds a dependency on build_id to env if this instance is configured
-   * with errorOnExternalFiles=false and rootedPath is an external mutable file.
-   * If errorOnExternalFiles=true and rootedPath is an external mutable file then
-   * a FileOutsidePackageRootsException is thrown. If the file is an external file that is
-   * referenced by the WORKSPACE, it gets a dependency on the //external package (and, thus,
-   * WORKSPACE file changes). This method is a no-op for any rootedPaths that fall within the known
-   * package roots.
-   *
-   * @param rootedPath
-   * @param env
-   * @throws FileOutsidePackageRootsException
+   * If this instance is configured with DEPEND_ON_EXTERNAL_PKG and rootedPath is a file that isn't
+   * under a package root then this adds a dependency on the //external package. If the action is
+   * ERROR_OUT, it will throw an error instead.
    */
   public void maybeHandleExternalFile(RootedPath rootedPath, SkyFunction.Environment env)
       throws FileOutsidePackageRootsException {
-    if (getFileType(rootedPath) == FileType.EXTERNAL_MUTABLE_FILE) {
-      if (!errorOnExternalFiles) {
-        // For files outside the package roots that are not assumed to be immutable, add a
-        // dependency on the build_id. This is sufficient for correctness; all other files
-        // will be handled by diff awareness of their respective package path, but these
-        // files need to be addressed separately.
-        //
-        // Using the build_id here seems to introduce a performance concern because the upward
-        // transitive closure of these external files will get eagerly invalidated on each
-        // incremental build (e.g. if every file had a transitive dependency on the filesystem root,
-        // then we'd have a big performance problem). But this a non-issue by design:
-        // - We don't add a dependency on the parent directory at the package root boundary, so the
-        // only transitive dependencies from files inside the package roots to external files are
-        // through symlinks. So the upwards transitive closure of external files is small.
-        // - The only way external source files get into the skyframe graph in the first place is
-        // through symlinks outside the package roots, which we neither want to encourage nor
-        // optimize for since it is not common. So the set of external files is small.
-        //
-        // The above reasoning doesn't hold for bazel, because external repositories
-        // (e.g. new_local_repository) cause lots of external symlinks to be present in the build.
-        // So bazel pretends that these external repositories are immutable to avoid the performance
-        // penalty described above.
-        PrecomputedValue.dependOnBuildId(env);
-      } else {
-        throw new FileOutsidePackageRootsException(rootedPath);
+    if (isInternal(rootedPath, pkgLocator.get())) {
+      return;
+    }
+
+    if (externalFileAction == ExternalFileAction.DEPEND_ON_EXTERNAL_PKG) {
+      // For files outside the package roots, add a dependency on the //external package so that if
+      // the WORKSPACE file changes, the File/DirectoryStateValue will be re-evaluated.
+      //
+      // Note that:
+      // - We don't add a dependency on the parent directory at the package root boundary, so
+      // the only transitive dependencies from files inside the package roots to external files
+      // are through symlinks. So the upwards transitive closure of external files is small.
+      // - The only way other than external repositories for external source files to get into the
+      // skyframe graph in the first place is through symlinks outside the package roots, which we
+      // neither want to encourage nor optimize for since it is not common. So the set of external
+      // files is small.
+      // TODO(kchodorow): check that the path is under output_base/external before adding the dep.
+      PackageValue pkgValue = (PackageValue) env.getValue(PackageValue.key(
+              PackageIdentifier.createInDefaultRepo(PackageIdentifier.EXTERNAL_PREFIX)));
+      if (pkgValue == null) {
+        return;
       }
-    } else if (getFileType(rootedPath) == FileType.EXTERNAL_IMMUTABLE_FILE) {
-      PackageValue pkgValue =
-          (PackageValue)
-              Preconditions.checkNotNull(
-                  env.getValue(PackageValue.key(Package.EXTERNAL_PACKAGE_IDENTIFIER)));
       Preconditions.checkState(!pkgValue.getPackage().containsErrors());
+    } else {
+      throw new FileOutsidePackageRootsException(rootedPath);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
index 6adf32f..e270f41 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
@@ -20,7 +20,6 @@
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.util.Pair;
-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;
@@ -30,7 +29,6 @@
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
-import java.io.IOException;
 import java.util.ArrayList;
 import java.util.TreeSet;
 import java.util.concurrent.atomic.AtomicReference;
@@ -46,15 +44,9 @@
  */
 public class FileFunction implements SkyFunction {
   private final AtomicReference<PathPackageLocator> pkgLocator;
-  private final TimestampGranularityMonitor tsgm;
-  private final ExternalFilesHelper externalFilesHelper;
 
-  public FileFunction(AtomicReference<PathPackageLocator> pkgLocator,
-      TimestampGranularityMonitor tsgm,
-      ExternalFilesHelper externalFilesHelper) {
+  public FileFunction(AtomicReference<PathPackageLocator> pkgLocator) {
     this.pkgLocator = pkgLocator;
-    this.tsgm = tsgm;
-    this.externalFilesHelper = externalFilesHelper;
   }
 
   @Override
@@ -101,33 +93,13 @@
     while (realFileStateValue.getType().equals(FileStateValue.Type.SYMLINK)) {
       symlinkChain.add(realRootedPath);
       orderedSeenPaths.add(realRootedPath.asPath());
-      if (externalFilesHelper.shouldAssumeImmutable(realRootedPath)) {
-        // If the file is assumed to be immutable, we want to resolve the symlink chain without
-        // adding dependencies since we don't care about incremental correctness.
-        try {
-          Path realPath = rootedPath.asPath().resolveSymbolicLinks();
-          realRootedPath = RootedPath.toRootedPathMaybeUnderRoot(realPath,
-              pkgLocator.get().getPathEntries());
-          realFileStateValue = FileStateValue.create(realRootedPath, tsgm);
-        } catch (IOException e) {
-          RootedPath root = RootedPath.toRootedPath(
-              rootedPath.asPath().getFileSystem().getRootDirectory(),
-              rootedPath.asPath().getFileSystem().getRootDirectory());
-          return FileValue.value(
-              rootedPath, fileStateValue,
-              root, FileStateValue.NONEXISTENT_FILE_STATE_NODE);
-        } catch (InconsistentFilesystemException e) {
-          throw new FileFunctionException(e, Transience.TRANSIENT);
-        }
-      } else {
-        Pair<RootedPath, FileStateValue> resolvedState = getSymlinkTargetRootedPath(realRootedPath,
-            realFileStateValue.getSymlinkTarget(), orderedSeenPaths, symlinkChain, env);
-        if (resolvedState == null) {
-          return null;
-        }
-        realRootedPath = resolvedState.getFirst();
-        realFileStateValue = resolvedState.getSecond();
+      Pair<RootedPath, FileStateValue> resolvedState = getSymlinkTargetRootedPath(realRootedPath,
+          realFileStateValue.getSymlinkTarget(), orderedSeenPaths, symlinkChain, env);
+      if (resolvedState == null) {
+        return null;
       }
+      realRootedPath = resolvedState.getFirst();
+      realFileStateValue = resolvedState.getSecond();
     }
     return FileValue.value(rootedPath, fileStateValue, realRootedPath, realFileStateValue);
   }
@@ -142,10 +114,7 @@
     PathFragment relativePath = rootedPath.getRelativePath();
     RootedPath realRootedPath = rootedPath;
     FileValue parentFileValue = null;
-    // We only resolve ancestors if the file is not assumed to be immutable (handling ancestors
-    // would be too aggressive).
-    if (!externalFilesHelper.shouldAssumeImmutable(rootedPath)
-        && !relativePath.equals(PathFragment.EMPTY_FRAGMENT)) {
+    if (!relativePath.equals(PathFragment.EMPTY_FRAGMENT)) {
       RootedPath parentRootedPath = RootedPath.toRootedPath(rootedPath.getRoot(),
           relativePath.getParentDirectory());
       parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
index 804171d..5abc3c3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
@@ -126,7 +126,7 @@
    * Only intended to be used by {@link FileFunction}. Should not be used for symlink cycles.
    */
   static FileValue value(RootedPath rootedPath, FileStateValue fileStateValue,
-      RootedPath realRootedPath, FileStateValue realFileStateValue) {
+                         RootedPath realRootedPath, FileStateValue realFileStateValue) {
     if (rootedPath.equals(realRootedPath)) {
       Preconditions.checkState(fileStateValue.getType() != FileStateValue.Type.SYMLINK,
           "rootedPath: %s, fileStateValue: %s, realRootedPath: %s, realFileStateValue: %s",
@@ -137,7 +137,8 @@
         return new SymlinkFileValue(realRootedPath, realFileStateValue,
             fileStateValue.getSymlinkTarget());
       } else {
-        return new DifferentRealPathFileValue(realRootedPath, realFileStateValue);
+        return new DifferentRealPathFileValue(
+            realRootedPath, realFileStateValue);
       }
     }
   }
@@ -201,7 +202,7 @@
     protected final FileStateValue realFileStateValue;
 
     public DifferentRealPathFileValue(RootedPath realRootedPath,
-        FileStateValue realFileStateValue) {
+                                      FileStateValue realFileStateValue) {
       this.realRootedPath = Preconditions.checkNotNull(realRootedPath);
       this.realFileStateValue = Preconditions.checkNotNull(realFileStateValue);
     }
@@ -245,7 +246,7 @@
     private final PathFragment linkValue;
 
     public SymlinkFileValue(RootedPath realRootedPath, FileStateValue realFileState,
-        PathFragment linkTarget) {
+                            PathFragment linkTarget) {
       super(realRootedPath, realFileState);
       this.linkValue = linkTarget;
     }
@@ -276,7 +277,8 @@
 
     @Override
     public int hashCode() {
-      return Objects.hash(realRootedPath, realFileStateValue, linkValue, Boolean.TRUE);
+      return Objects.hash(
+          realRootedPath, realFileStateValue, linkValue, Boolean.TRUE);
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index c4b11d2..b7f3757 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -42,6 +42,7 @@
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.skyframe.DirtinessCheckerUtils.BasicFilesystemDirtinessChecker;
+import com.google.devtools.build.lib.skyframe.DirtinessCheckerUtils.ExternalDirtinessChecker;
 import com.google.devtools.build.lib.skyframe.DirtinessCheckerUtils.MissingDiffDirtinessChecker;
 import com.google.devtools.build.lib.skyframe.DirtinessCheckerUtils.UnionDirtinessChecker;
 import com.google.devtools.build.lib.util.AbruptExitException;
@@ -104,7 +105,6 @@
       BinTools binTools,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
-      Set<Path> immutableDirectories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
       Predicate<PathFragment> allowedMissingInputs,
       Preprocessor.Factory.Supplier preprocessorFactorySupplier,
@@ -119,11 +119,10 @@
         binTools,
         workspaceStatusActionFactory,
         buildInfoFactories,
-        immutableDirectories,
         allowedMissingInputs,
         preprocessorFactorySupplier,
         extraSkyFunctions,
-        extraPrecomputedValues, /*errorOnExternalFiles=*/
+        extraPrecomputedValues,
         false);
     this.diffAwarenessManager = new DiffAwarenessManager(diffAwarenessFactories);
     this.customDirtinessCheckers = customDirtinessCheckers;
@@ -136,7 +135,6 @@
       BinTools binTools,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
-      Set<Path> immutableDirectories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
       Predicate<PathFragment> allowedMissingInputs,
       Preprocessor.Factory.Supplier preprocessorFactorySupplier,
@@ -152,7 +150,6 @@
             binTools,
             workspaceStatusActionFactory,
             buildInfoFactories,
-            immutableDirectories,
             diffAwarenessFactories,
             allowedMissingInputs,
             preprocessorFactorySupplier,
@@ -168,7 +165,6 @@
       TimestampGranularityMonitor tsgm, BlazeDirectories directories, BinTools binTools,
       WorkspaceStatusAction.Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
-      Set<Path> immutableDirectories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories) {
     return create(
         pkgFactory,
@@ -177,7 +173,6 @@
         binTools,
         workspaceStatusActionFactory,
         buildInfoFactories,
-        immutableDirectories,
         diffAwarenessFactories,
         Predicates.<PathFragment>alwaysFalse(),
         Preprocessor.Factory.Supplier.NullSupplier.INSTANCE,
@@ -331,10 +326,6 @@
   private void handleDiffsWithMissingDiffInformation(EventHandler eventHandler,
       Set<Pair<Path, DiffAwarenessManager.ProcessableModifiedFileSet>>
           pathEntriesWithoutDiffInformation) throws InterruptedException {
-    if (pathEntriesWithoutDiffInformation.isEmpty() && Iterables.isEmpty(customDirtinessCheckers)) {
-      return;
-    }
-
     // Before running the FilesystemValueChecker, ensure that all values marked for invalidation
     // have actually been invalidated (recall that invalidation happens at the beginning of the
     // next evaluate() call), because checking those is a waste of time.
@@ -346,11 +337,12 @@
     // system values under package roots for which we don't have diff information. If at least
     // one path entry doesn't have diff information, then we're going to have to iterate over
     // the skyframe values at least once no matter what.
-    Set<Path> pathEntries = new HashSet<>();
+    Set<Path> diffPackageRootsUnderWhichToCheck = new HashSet<>();
     for (Pair<Path, DiffAwarenessManager.ProcessableModifiedFileSet> pair :
         pathEntriesWithoutDiffInformation) {
-      pathEntries.add(pair.getFirst());
+      diffPackageRootsUnderWhichToCheck.add(pair.getFirst());
     }
+
     Differencer.Diff diff =
         fsvc.getDirtyKeys(
             memoizingEvaluator.getValues(),
@@ -358,8 +350,9 @@
                 Iterables.concat(
                     customDirtinessCheckers,
                     ImmutableList.<SkyValueDirtinessChecker>of(
-                        new MissingDiffDirtinessChecker(pathEntries)))));
-    handleChangedFiles(pathEntries, diff);
+                        new ExternalDirtinessChecker(pkgLocator.get()),
+                        new MissingDiffDirtinessChecker(diffPackageRootsUnderWhichToCheck)))));
+    handleChangedFiles(diffPackageRootsUnderWhichToCheck, diff);
 
     for (Pair<Path, DiffAwarenessManager.ProcessableModifiedFileSet> pair :
         pathEntriesWithoutDiffInformation) {
@@ -367,11 +360,13 @@
     }
   }
 
-  private void handleChangedFiles(Collection<Path> pathEntries, Differencer.Diff diff) {
+  private void handleChangedFiles(
+      Collection<Path> diffPackageRootsUnderWhichToCheck, Differencer.Diff diff) {
     Collection<SkyKey> changedKeysWithoutNewValues = diff.changedKeysWithoutNewValues();
     Map<SkyKey, SkyValue> changedKeysWithNewValues = diff.changedKeysWithNewValues();
 
-    logDiffInfo(pathEntries, changedKeysWithoutNewValues, changedKeysWithNewValues);
+    logDiffInfo(diffPackageRootsUnderWhichToCheck, changedKeysWithoutNewValues,
+        changedKeysWithNewValues);
 
     recordingDiffer.invalidate(changedKeysWithoutNewValues);
     recordingDiffer.inject(changedKeysWithNewValues);
@@ -382,8 +377,8 @@
   }
 
   private static void logDiffInfo(Iterable<Path> pathEntries,
-      Collection<SkyKey> changedWithoutNewValue,
-      Map<SkyKey, ? extends SkyValue> changedWithNewValue) {
+                                  Collection<SkyKey> changedWithoutNewValue,
+                                  Map<SkyKey, ? extends SkyValue> changedWithNewValue) {
     int numModified = changedWithNewValue.size() + changedWithoutNewValue.size();
     StringBuilder result = new StringBuilder("DiffAwareness found ")
         .append(numModified)
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java
index 45881c8..5b6484d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutorFactory.java
@@ -23,13 +23,10 @@
 import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.packages.Preprocessor;
 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.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 
-import java.util.Set;
-
 /**
  * A factory of SkyframeExecutors that returns SequencedSkyframeExecutor.
  */
@@ -43,7 +40,6 @@
       BinTools binTools,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
-      Set<Path> immutableDirectories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
       Predicate<PathFragment> allowedMissingInputs,
       Preprocessor.Factory.Supplier preprocessorFactorySupplier,
@@ -57,7 +53,6 @@
         binTools,
         workspaceStatusActionFactory,
         buildInfoFactories,
-        immutableDirectories,
         diffAwarenessFactories,
         allowedMissingInputs,
         preprocessorFactorySupplier,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 9a316f4..4b96a2d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -173,6 +173,7 @@
   private final PackageFactory pkgFactory;
   private final WorkspaceStatusAction.Factory workspaceStatusActionFactory;
   private final BlazeDirectories directories;
+  protected final ExternalFilesHelper externalFilesHelper;
   @Nullable
   private OutputService outputService;
 
@@ -244,8 +245,6 @@
   protected SkyframeProgressReceiver progressReceiver;
   private final AtomicReference<CyclesReporter> cyclesReporter = new AtomicReference<>();
 
-  private final Set<Path> immutableDirectories;
-
   private final BinTools binTools;
   private boolean needToInjectEmbeddedArtifacts = true;
   private boolean needToInjectPrecomputedValuesForAnalysis = true;
@@ -275,7 +274,6 @@
       BinTools binTools,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
-      Set<Path> immutableDirectories,
       Predicate<PathFragment> allowedMissingInputs,
       Preprocessor.Factory.Supplier preprocessorFactorySupplier,
       ImmutableMap<SkyFunctionName, SkyFunction> extraSkyFunctions,
@@ -296,7 +294,6 @@
         resourceManager, eventBus, statusReporterRef);
     this.directories = Preconditions.checkNotNull(directories);
     this.buildInfoFactories = buildInfoFactories;
-    this.immutableDirectories = immutableDirectories;
     this.allowedMissingInputs = allowedMissingInputs;
     this.preprocessorFactorySupplier = preprocessorFactorySupplier;
     this.extraSkyFunctions = extraSkyFunctions;
@@ -310,14 +307,13 @@
         binTools,
         (ConfiguredRuleClassProvider) pkgFactory.getRuleClassProvider());
     this.artifactFactory.set(skyframeBuildView.getArtifactFactory());
+    this.externalFilesHelper = new ExternalFilesHelper(pkgLocator, this.errorOnExternalFiles);
   }
 
   private ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions(
       Root buildDataDirectory,
       PackageFactory pkgFactory,
       Predicate<PathFragment> allowedMissingInputs) {
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator,
-        immutableDirectories, errorOnExternalFiles);
     RuleClassProvider ruleClassProvider = pkgFactory.getRuleClassProvider();
     // We use an immutable map builder for the nice side effect that it throws if a duplicate key
     // is inserted.
@@ -330,7 +326,7 @@
         new FileSymlinkCycleUniquenessFunction());
     map.put(SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS,
         new FileSymlinkInfiniteExpansionUniquenessFunction());
-    map.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    map.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
     map.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
     map.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));
     map.put(SkyFunctions.CONTAINING_PACKAGE_LOOKUP, new ContainingPackageLookupFunction());
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java
index 7cd34988..ddfdd23 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutorFactory.java
@@ -24,13 +24,10 @@
 import com.google.devtools.build.lib.packages.Preprocessor;
 import com.google.devtools.build.lib.util.AbruptExitException;
 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.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 
-import java.util.Set;
-
 /**
 * A factory that creates instances of SkyframeExecutor.
 */
@@ -61,7 +58,6 @@
       BinTools binTools,
       Factory workspaceStatusActionFactory,
       ImmutableList<BuildInfoFactory> buildInfoFactories,
-      Set<Path> immutableDirectories,
       Iterable<? extends DiffAwareness.Factory> diffAwarenessFactories,
       Predicate<PathFragment> allowedMissingInputs,
       Preprocessor.Factory.Supplier preprocessorFactorySupplier,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
index 345800d..a1bb468 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
@@ -66,12 +66,12 @@
     Path repoWorkspace = workspaceRoot.getRoot().getRelative(workspaceRoot.getRelativePath());
     LegacyBuilder builder =
         com.google.devtools.build.lib.packages.Package.newExternalPackageBuilder(
-            repoWorkspace, packageFactory.getRuleClassProvider().getRunfilesPrefix());
+            repoWorkspace, ruleClassProvider.getRunfilesPrefix());
     try (Mutability mutability = Mutability.create("workspace %s", repoWorkspace)) {
       WorkspaceFactory parser =
           new WorkspaceFactory(
               builder,
-              packageFactory.getRuleClassProvider(),
+              ruleClassProvider,
               packageFactory.getEnvironmentExtensions(),
               mutability,
               directories.getEmbeddedBinariesRoot(),
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
index 405bc21..e175ab5 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
@@ -16,7 +16,6 @@
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
 import com.google.common.eventbus.EventBus;
@@ -62,7 +61,6 @@
 import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.ModifiedFileSet;
-import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.common.options.Options;
@@ -161,7 +159,6 @@
             binTools,
             workspaceStatusActionFactory,
             ruleClassProvider.getBuildInfoFactories(),
-            ImmutableSet.<Path>of(),
             ImmutableList.<DiffAwareness.Factory>of(),
             Predicates.<PathFragment>alwaysFalse(),
             Preprocessor.Factory.Supplier.NullSupplier.INSTANCE,
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index 21d5a66..a71ddda 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -209,7 +209,6 @@
             binTools,
             workspaceStatusActionFactory,
             ruleClassProvider.getBuildInfoFactories(),
-            ImmutableSet.<Path>of(),
             ImmutableList.<DiffAwareness.Factory>of(),
             Predicates.<PathFragment>alwaysFalse(),
             getPreprocessorFactorySupplier(),
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
index b4a5a37..0eda907 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/ConfigurationTestCase.java
@@ -17,7 +17,6 @@
 
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Root;
@@ -106,7 +105,6 @@
             BinTools.forUnitTesting(directories, TestConstants.EMBEDDED_TOOLS),
             workspaceStatusActionFactory,
             ruleClassProvider.getBuildInfoFactories(),
-            ImmutableSet.<Path>of(),
             ImmutableList.<DiffAwareness.Factory>of(),
             Predicates.<PathFragment>alwaysFalse(),
             Preprocessor.Factory.Supplier.NullSupplier.INSTANCE,
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java b/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
index 17138fa..24d0c5d 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/PackageLoadingTestCase.java
@@ -45,7 +45,6 @@
 import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.ModifiedFileSet;
-import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -91,7 +90,6 @@
             null, /* BinTools */
             null, /* workspaceStatusActionFactory */
             ruleClassProvider.getBuildInfoFactories(),
-            ImmutableSet.<Path>of(),
             ImmutableList.<DiffAwareness.Factory>of(),
             Predicates.<PathFragment>alwaysFalse(),
             preprocessorFactorySupplier,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
index e054642..f7cb450 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -33,9 +33,12 @@
 import com.google.devtools.build.lib.actions.MissingInputFileException;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.actions.util.TestAction.DummyAction;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
+import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.util.Pair;
@@ -91,24 +94,36 @@
   public final void setUp() throws Exception  {
     setupRoot(new CustomInMemoryFs());
     AtomicReference<PathPackageLocator> pkgLocator =
-        new AtomicReference<>(PathPackageLocator.EMPTY);
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+        new AtomicReference<>(new PathPackageLocator(root));
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
     differencer = new RecordingDifferencer();
     evaluator =
         new InMemoryMemoizingEvaluator(
-            ImmutableMap.of(
-                SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper),
-                SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper),
-                SkyFunctions.ARTIFACT, new ArtifactFunction(Predicates.<PathFragment>alwaysFalse()),
-                SkyFunctions.ACTION_EXECUTION, new SimpleActionExecutionFunction()),
+            ImmutableMap.<SkyFunctionName, SkyFunction>builder()
+                .put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper))
+                .put(SkyFunctions.FILE, new FileFunction(pkgLocator))
+                .put(SkyFunctions.ARTIFACT,
+                    new ArtifactFunction(Predicates.<PathFragment>alwaysFalse()))
+                .put(SkyFunctions.ACTION_EXECUTION, new SimpleActionExecutionFunction())
+                .put(SkyFunctions.PACKAGE,
+                    new PackageFunction(null, null, null, null, null, null, null))
+                .put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(null))
+                .put(SkyFunctions.WORKSPACE_FILE,
+                    new WorkspaceFileFunction(TestRuleClassProvider.getRuleClassProvider(),
+                        new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
+                        new BlazeDirectories(root, root, root)))
+                .build(),
             differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
     actions = new HashSet<>();
   }
 
-  private void setupRoot(CustomInMemoryFs fs) {
+  private void setupRoot(CustomInMemoryFs fs) throws IOException {
     root = fs.getPath(TestUtils.tmpDir());
+    FileSystemUtils.createDirectoryAndParents(root);
+    FileSystemUtils.createEmptyFile(root.getRelative("WORKSPACE"));
   }
 
   private void assertFileArtifactValueMatches(boolean expectDigest) throws Throwable {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
index 83c8775..3d7f77e 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
@@ -60,7 +60,7 @@
     AtomicReference<PathPackageLocator> pkgLocator =
         new AtomicReference<>(new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)));
     deletedPackages = new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
     TimestampGranularityMonitor tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
 
     Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
@@ -69,7 +69,7 @@
     skyFunctions.put(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES,
         new BlacklistedPackagePrefixesFunction());
     skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
-    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
     RecordingDifferencer differencer = new RecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
index ae5de27..96dc02a 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
@@ -19,7 +19,6 @@
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotSame;
 import static org.junit.Assert.assertNull;
-import static org.junit.Assert.assertSame;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
@@ -34,10 +33,14 @@
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.common.testing.EqualsTester;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.events.NullEventHandler;
 import com.google.devtools.build.lib.events.StoredEventHandler;
+import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.testutil.ManualClock;
+import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.util.Pair;
@@ -56,6 +59,7 @@
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
@@ -121,15 +125,26 @@
     differencer = new RecordingDifferencer();
     MemoizingEvaluator evaluator =
         new InMemoryMemoizingEvaluator(
-            ImmutableMap.of(
-                SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper),
-                SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS,
-                    new FileSymlinkCycleUniquenessFunction(),
-                SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS,
-                    new FileSymlinkInfiniteExpansionUniquenessFunction(),
-                SkyFunctions.FILE, new FileFunction(pkgLocatorRef, tsgm, externalFilesHelper)),
+            ImmutableMap.<SkyFunctionName, SkyFunction>builder()
+                .put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper))
+                .put(SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS,
+                    new FileSymlinkCycleUniquenessFunction())
+                .put(SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS,
+                    new FileSymlinkInfiniteExpansionUniquenessFunction())
+                .put(SkyFunctions.FILE, new FileFunction(pkgLocatorRef))
+                .put(SkyFunctions.PACKAGE,
+                    new PackageFunction(null, null, null, null, null, null, null))
+                .put(SkyFunctions.PACKAGE_LOOKUP,
+                    new PackageLookupFunction(new AtomicReference<>(
+                        ImmutableSet.<PackageIdentifier>of())))
+                .put(SkyFunctions.WORKSPACE_FILE,
+                    new WorkspaceFileFunction(TestRuleClassProvider.getRuleClassProvider(),
+                        new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
+                        new BlazeDirectories(pkgRoot, outputBase, pkgRoot)))
+                .build(),
             differencer);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator);
     return new SequentialBuildDriver(evaluator);
   }
 
@@ -265,6 +280,7 @@
         getFilesSeenAndAssertValueChangesIfContentsOfFileChanges("../outside", true, "a"));
     assertThat(seenFiles)
         .containsExactly(
+            rootedPath("WORKSPACE"),
             rootedPath("a"),
             rootedPath(""),
             RootedPath.toRootedPath(fs.getRootDirectory(), PathFragment.EMPTY_FRAGMENT),
@@ -282,6 +298,7 @@
         getFilesSeenAndAssertValueChangesIfContentsOfFileChanges("/absolute", true, "a"));
     assertThat(seenFiles)
         .containsExactly(
+            rootedPath("WORKSPACE"),
             rootedPath("a"),
             rootedPath(""),
             RootedPath.toRootedPath(fs.getRootDirectory(), PathFragment.EMPTY_FRAGMENT),
@@ -537,7 +554,7 @@
   }
 
   @Test
-  public void testFilesOutsideRootHasDepOnBuildID() throws Exception {
+  public void testFilesOutsideRootIsReEvaluated() throws Exception {
     Path file = file("/outsideroot");
     SequentialBuildDriver driver = makeDriver();
     SkyKey key = skyKey("/outsideroot");
@@ -552,6 +569,7 @@
     assertTrue(oldValue.exists());
 
     file.delete();
+    differencer.invalidate(ImmutableList.of(fileStateSkyKey("/outsideroot")));
     result =
         driver.evaluate(
             ImmutableList.of(key), false, DEFAULT_THREAD_COUNT, NullEventHandler.INSTANCE);
@@ -559,16 +577,6 @@
       fail(String.format("Evaluation error for %s: %s", key, result.getError()));
     }
     FileValue newValue = (FileValue) result.get(key);
-    assertSame(oldValue, newValue);
-
-    PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
-    result =
-        driver.evaluate(
-            ImmutableList.of(key), false, DEFAULT_THREAD_COUNT, NullEventHandler.INSTANCE);
-    if (result.hasError()) {
-      fail(String.format("Evaluation error for %s: %s", key, result.getError()));
-    }
-    newValue = (FileValue) result.get(key);
     assertNotSame(oldValue, newValue);
     assertFalse(newValue.exists());
   }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
index 17eb2a1..302bb2b 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
@@ -85,12 +85,12 @@
         new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)));
     AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages =
         new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
 
     Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
 
     skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
-    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
     skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
     skyFunctions.put(
         SkyFunctions.DIRECTORY_LISTING_STATE,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
index 69a267b..933d5ad 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -28,9 +28,13 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.actions.util.TestAction;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
+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.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.skyframe.DirtinessCheckerUtils.BasicFilesystemDirtinessChecker;
+import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.BatchStat;
@@ -91,22 +95,34 @@
 
     fs = new MockFileSystem();
     pkgRoot = fs.getPath("/testroot");
+    FileSystemUtils.createDirectoryAndParents(pkgRoot);
+    FileSystemUtils.createEmptyFile(pkgRoot.getRelative("WORKSPACE"));
 
     tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
     AtomicReference<PathPackageLocator> pkgLocator =
-        new AtomicReference<>(PathPackageLocator.EMPTY);
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+        new AtomicReference<>(new PathPackageLocator(pkgRoot));
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
     skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
-    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
     skyFunctions.put(
         SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, new FileSymlinkCycleUniquenessFunction());
     skyFunctions.put(
         SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS,
         new FileSymlinkInfiniteExpansionUniquenessFunction());
+    skyFunctions.put(SkyFunctions.PACKAGE,
+        new PackageFunction(null, null, null, null, null, null, null));
+    skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP,
+        new PackageLookupFunction(new AtomicReference<>(ImmutableSet.<PackageIdentifier>of())));
+    skyFunctions.put(SkyFunctions.WORKSPACE_FILE,
+        new WorkspaceFileFunction(TestRuleClassProvider.getRuleClassProvider(),
+            new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
+            new BlazeDirectories(pkgRoot, pkgRoot, pkgRoot)));
+
     differencer = new RecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions.build(), differencer);
     driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
   }
 
   @Test
@@ -123,8 +139,8 @@
     FileSystemUtils.createEmptyFile(path);
     assertEmptyDiff(getDirtyFilesystemKeys(evaluator, checker));
 
-    SkyKey skyKey =
-        FileStateValue.key(RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("foo")));
+    SkyKey skyKey = FileStateValue.key(
+        RootedPath.toRootedPath(fs.getRootDirectory(), new PathFragment("foo")));
     EvaluationResult<SkyValue> result =
         driver.evaluate(
             ImmutableList.of(skyKey),
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
index a5c9614..cb55822 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
@@ -125,7 +125,7 @@
   private Map<SkyFunctionName, SkyFunction> createFunctionMap() {
     AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages =
         new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
 
     Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
     skyFunctions.put(SkyFunctions.GLOB, new GlobFunction(alwaysUseDirListing()));
@@ -140,7 +140,7 @@
         SkyFunctions.FILE_STATE,
         new FileStateFunction(
             new TimestampGranularityMonitor(BlazeClock.instance()), externalFilesHelper));
-    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
     return skyFunctions;
   }
 
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
index 6b540e5..a27cb61 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
@@ -73,7 +73,7 @@
     AtomicReference<PathPackageLocator> pkgLocator = new AtomicReference<>(
         new PathPackageLocator(outputBase, ImmutableList.of(emptyPackagePath, rootDirectory)));
     deletedPackages = new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
     TimestampGranularityMonitor tsgm = new TimestampGranularityMonitor(BlazeClock.instance());
     BlazeDirectories directories = new BlazeDirectories(rootDirectory, outputBase, rootDirectory);
 
@@ -84,7 +84,7 @@
         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.FILE, new FileFunction(pkgLocator));
     skyFunctions.put(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES,
         new BlacklistedPackagePrefixesFunction());
     RuleClassProvider ruleClassProvider = TestRuleClassProvider.getRuleClassProvider();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
index 5b4f17d..6efb91e 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
@@ -30,12 +30,15 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode;
 import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
 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.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.ResolvedFile;
 import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.TraversalRequest;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.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;
@@ -86,12 +89,12 @@
         new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)));
     AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages =
         new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
 
     Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
 
     skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper));
-    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
     skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
     skyFunctions.put(
         SkyFunctions.DIRECTORY_LISTING_STATE,
@@ -101,6 +104,14 @@
     skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));
     skyFunctions.put(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES,
         new BlacklistedPackagePrefixesFunction());
+    skyFunctions.put(SkyFunctions.PACKAGE,
+        new PackageFunction(null, null, null, null, null, null, null));
+    skyFunctions.put(SkyFunctions.PACKAGE_LOOKUP,
+        new PackageLookupFunction(deletedPackages));
+    skyFunctions.put(SkyFunctions.WORKSPACE_FILE,
+        new WorkspaceFileFunction(TestRuleClassProvider.getRuleClassProvider(),
+            new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
+            new BlazeDirectories(rootDirectory, outputBase, rootDirectory)));
 
     progressReceiver = new RecordingEvaluationProgressReceiver();
     differencer = new RecordingDifferencer();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index a9697d8..18227f8 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -38,12 +38,15 @@
 import com.google.devtools.build.lib.actions.cache.ActionCache;
 import com.google.devtools.build.lib.actions.util.DummyExecutor;
 import com.google.devtools.build.lib.actions.util.TestAction;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.buildtool.SkyframeBuilder;
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.events.StoredEventHandler;
+import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.util.AbruptExitException;
 import com.google.devtools.build.lib.util.BlazeClock;
@@ -59,6 +62,7 @@
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
@@ -133,8 +137,8 @@
       final boolean keepGoing,
       @Nullable EvaluationProgressReceiver evaluationProgressReceiver) {
     AtomicReference<PathPackageLocator> pkgLocator =
-        new AtomicReference<>(new PathPackageLocator(outputBase, ImmutableList.<Path>of()));
-    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator);
+        new AtomicReference<>(new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)));
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(pkgLocator, false);
     differencer = new RecordingDifferencer();
 
     ActionExecutionStatusReporter statusReporter =
@@ -148,19 +152,26 @@
 
     final InMemoryMemoizingEvaluator evaluator =
         new InMemoryMemoizingEvaluator(
-            ImmutableMap.of(
-                SkyFunctions.FILE_STATE,
-                new FileStateFunction(tsgm, externalFilesHelper),
-                SkyFunctions.FILE,
-                new FileFunction(pkgLocator, tsgm, externalFilesHelper),
-                SkyFunctions.ARTIFACT,
-                new ArtifactFunction(Predicates.<PathFragment>alwaysFalse()),
-                SkyFunctions.ACTION_EXECUTION,
-                new ActionExecutionFunction(skyframeActionExecutor, tsgm)),
+            ImmutableMap.<SkyFunctionName, SkyFunction>builder()
+                .put(SkyFunctions.FILE_STATE, new FileStateFunction(tsgm, externalFilesHelper))
+                .put(SkyFunctions.FILE, new FileFunction(pkgLocator))
+                .put(SkyFunctions.ARTIFACT,
+                    new ArtifactFunction(Predicates.<PathFragment>alwaysFalse()))
+                .put(SkyFunctions.ACTION_EXECUTION,
+                    new ActionExecutionFunction(skyframeActionExecutor, tsgm))
+                .put(SkyFunctions.PACKAGE,
+                    new PackageFunction(null, null, null, null, null, null, null))
+                .put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(null))
+                .put(SkyFunctions.WORKSPACE_FILE,
+                    new WorkspaceFileFunction(TestRuleClassProvider.getRuleClassProvider(),
+                        new PackageFactory(TestRuleClassProvider.getRuleClassProvider()),
+                        new BlazeDirectories(rootDirectory, outputBase, rootDirectory)))
+                .build(),
             differencer,
             evaluationProgressReceiver);
     final SequentialBuildDriver driver = new SequentialBuildDriver(evaluator);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
 
     return new Builder() {
       private void setGeneratingActions() {
diff --git a/src/test/shell/bazel/BUILD b/src/test/shell/bazel/BUILD
index c9c29c0..6570a33 100644
--- a/src/test/shell/bazel/BUILD
+++ b/src/test/shell/bazel/BUILD
@@ -147,6 +147,12 @@
 )
 
 sh_test(
+    name = "external_correctness_test",
+    srcs = ["external_correctness_test.sh"],
+    data = [":test-deps"],
+)
+
+sh_test(
     name = "external_integration_test",
     size = "large",
     srcs = ["external_integration_test.sh"],
diff --git a/src/test/shell/bazel/external_correctness_test.sh b/src/test/shell/bazel/external_correctness_test.sh
new file mode 100755
index 0000000..5e9cdde
--- /dev/null
+++ b/src/test/shell/bazel/external_correctness_test.sh
@@ -0,0 +1,132 @@
+#!/bin/bash
+#
+# 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.
+
+source $(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)/test-setup.sh \
+  || { echo "test-setup.sh not found!" >&2; exit 1; }
+
+function set_up() {
+  LOCAL=$(pwd)
+  REMOTE=$TEST_TMPDIR/remote
+
+  # Set up empty remote repo.
+  mkdir -p $REMOTE
+  touch $REMOTE/WORKSPACE
+  cat > $REMOTE/BUILD <<EOF
+genrule(
+    name = "get-input",
+    outs = ["an-input"],
+    srcs = ["input"],
+    cmd = "cat \$< > \$@",
+    visibility = ["//visibility:public"],
+)
+EOF
+
+  # Set up local repo that uses $REMOTE as an external repo.
+  cat > $LOCAL/WORKSPACE <<EOF
+local_repository(
+    name = "a",
+    path = "$REMOTE",
+)
+EOF
+  cat > $LOCAL/BUILD <<EOF
+genrule(
+    name = "b",
+    srcs = ["@a//:get-input"],
+    outs = ["b.out"],
+    cmd = "cat \$< > \$@",
+)
+EOF
+}
+
+function test_build_file_changes_are_noticed() {
+  cat > $REMOTE/BUILD <<EOF
+SYNTAX ERROR
+EOF
+  bazel build //:b &> $TEST_log && fail "Build succeeded"
+  expect_log "syntax error at 'ERROR'"
+
+  cat > $REMOTE/BUILD <<EOF
+genrule(
+    name = "get-input",
+    outs = ["a.out"],
+    cmd = "echo 'I come from @a' > \$@",
+    visibility = ["//visibility:public"],
+)
+EOF
+
+  bazel build //:b &> $TEST_log || fail "Build failed"
+  assert_contains "I come from @a" bazel-genfiles/b.out
+}
+
+function test_external_file_changes_are_noticed() {
+  version="1.0"
+  cat > $REMOTE/input <<EOF
+$version
+EOF
+  bazel build //:b &> $TEST_log || fail "Build failed"
+  assert_contains $version bazel-genfiles/b.out
+
+  version="2.0"
+  cat > $REMOTE/input <<EOF
+$version
+EOF
+  bazel build //:b &> $TEST_log || fail "Build failed"
+  assert_contains $version bazel-genfiles/b.out
+}
+
+function test_symlink_changes_are_noticed() {
+  cat > $REMOTE/version1 <<EOF
+1.0
+EOF
+  cat > $REMOTE/version2 <<EOF
+2.0
+EOF
+  rm $REMOTE/input
+  ln -s $REMOTE/version1 $REMOTE/input
+  bazel build //:b &> $TEST_log || fail "Build failed"
+  assert_contains 1.0 bazel-genfiles/b.out
+
+  rm $REMOTE/input
+  ln -s $REMOTE/version2 $REMOTE/input
+  bazel build //:b &> $TEST_log || fail "Build failed"
+  assert_contains 2.0 bazel-genfiles/b.out
+}
+
+function test_parent_symlink_change() {
+  REMOTE1=$TEST_TMPDIR/remote1
+  REMOTE2=$TEST_TMPDIR/remote2
+  mkdir -p $REMOTE1 $REMOTE2
+  cp -R $REMOTE/* $REMOTE1
+  cp -R $REMOTE/* $REMOTE2
+  cat > $REMOTE1/input <<EOF
+1.0
+EOF
+  cat > $REMOTE2/input <<EOF
+2.0
+EOF
+  rm -rf $REMOTE
+  ln -s $REMOTE1 $REMOTE
+
+  bazel build //:b &> $TEST_log || fail "Build failed"
+  assert_contains 1.0 bazel-genfiles/b.out
+
+  rm $REMOTE
+  ln -s $REMOTE2 $REMOTE
+  bazel build //:b &> $TEST_log || fail "Build failed"
+  assert_contains 2.0 bazel-genfiles/b.out
+}
+
+run_suite "//external correctness tests"
diff --git a/src/test/shell/bazel/external_integration_test.sh b/src/test/shell/bazel/external_integration_test.sh
index 565e960..e50d7cf 100755
--- a/src/test/shell/bazel/external_integration_test.sh
+++ b/src/test/shell/bazel/external_integration_test.sh
@@ -332,7 +332,6 @@
 }
 EOF
 
-  bazel fetch //zoo:ball-pit || fail "Fetch failed"
   bazel run //zoo:ball-pit >& $TEST_log || echo "Expected run to succeed"
   kill_nc
   expect_log "Tra-la!"
@@ -407,7 +406,6 @@
 EOF
 
   chmod +x test/test.sh
-  bazel fetch //test || fail "Fetch failed"
   bazel run //test >& $TEST_log || echo "Expected run to succeed"
   kill_nc
   expect_log "Tra-la!"
@@ -592,13 +590,13 @@
 )
 EOF
 
-  bazel build @x//:catter || fail "Build failed"
+  bazel build @x//:catter &> $TEST_log || fail "Build 1 failed"
   assert_contains "abc" bazel-genfiles/external/x/catter.out
   mv x.BUILD x.BUILD.new || fail "Moving x.BUILD failed"
   sed 's/x.BUILD/x.BUILD.new/g' WORKSPACE > WORKSPACE.tmp || \
     fail "Editing WORKSPACE failed"
   mv WORKSPACE.tmp WORKSPACE
-  bazel build @x//:catter || fail "Build failed"
+  bazel build @x//:catter &> $TEST_log || fail "Build 2 failed"
   assert_contains "abc" bazel-genfiles/external/x/catter.out
 }
 
@@ -635,12 +633,12 @@
 )
 EOF
 
-  bazel build @x//:catter || fail "Build failed"
+  bazel build @x//:catter || fail "Build 1 failed"
   assert_contains "abc" bazel-genfiles/external/x/catter.out
   sed 's/x.BUILD/x.BUILD.new/g' WORKSPACE > WORKSPACE.tmp || \
     fail "Editing WORKSPACE failed"
   mv WORKSPACE.tmp WORKSPACE
-  bazel build @x//:catter || fail "Build failed"
+  bazel build @x//:catter &> $TEST_log || fail "Build 2 failed"
   assert_contains "def" bazel-genfiles/external/x/catter.out
 }
 
diff --git a/src/test/shell/bazel/local_repository_test.sh b/src/test/shell/bazel/local_repository_test.sh
index e2e4a6e..127fff7 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -44,7 +44,7 @@
 filegroup(name="mfg", srcs=["//external:e"])
 EOF
 
-  bazel build //:mfg
+  bazel build //:mfg &> $TEST_log || fail "Building //:mfg failed"
 }
 
 # Uses a glob from a different repository for a runfile.
@@ -259,14 +259,11 @@
 }
 EOF
 
-  # Check that rebuilding this doesn't rebuild libmongoose.jar, even though it
-  # has changed. Bazel assumes that files in external repositories are
-  # immutable.
+  # Check that external repo changes are noticed and libmongoose.jar is rebuilt.
   bazel fetch //zoo:ball-pit || fail "Fetch failed"
   bazel run //zoo:ball-pit >& $TEST_log || fail "Failed to build/run zoo"
-  expect_log "Tra-la!"
-  expect_not_log "Building endangered/libmongoose.jar"
-  expect_not_log "Growl!"
+  expect_not_log "Tra-la!"
+  expect_log "Growl!"
 }
 
 function test_default_ws() {
@@ -329,7 +326,7 @@
 # Creates an indirect dependency on X from A and make sure the error message
 # refers to the correct label.
 function test_indirect_dep_message() {
-  local external_dir=$TEST_TMPDIR
+  local external_dir=$TEST_TMPDIR/ext-dir
   mkdir -p a b $external_dir/x
   cat > a/A.java <<EOF
 package a;
@@ -395,7 +392,6 @@
 )
 EOF
 
-  bazel fetch //a:a || fail "Fetch failed"
   bazel build //a:a >& $TEST_log && fail "Building //a:a should error out"
   expect_log "** Please add the following dependencies:"
   expect_log "@x-repo//x  to //a:a"