Change execution root for external repositories to be ../repo

Some of the important aspect of this change:

* Remote repos in the execution root are under output_base/execroot/repo_name, so the prefix is ../repo_name (to escape the local workspace name).
* Package roots for external repos were previously "output_base/", they are now output_base/external/repo_name (which means source artifacts always have a relative path from their repository).
* Outputs are under bazel-bin/external/repo_name/ (or similarly under genfiles). Note that this is a bit of a change from how this was implemented in the previous cl.

Fixes #1262.

RELNOTES[INC]: Previously, an external repository would be symlinked into the
execution root at execroot/local_repo/external/remote_repo. This changes it to
be at execroot/remote_repo. This may break genrules/Skylark actions that
hardcode execution root paths. If this causes breakages for you, ensure that
genrules are using $(location :target) to access files and Skylark rules are
using http://bazel.io/docs/skylark/lib/File.html's path, dirname, etc.
functions.

Roll forward of bdfd58a.

--
MOS_MIGRATED_REVID=133606309

52 files changed, 571 insertions, 422 deletions

diff --git a/.gitignore b/.gitignore
index c60c36e148..50ca03469b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -8,6 +8,7 @@
 /WORKSPACE.user.bzl
 /bazel-bazel
 /bazel-bin
+/bazel-external
 /bazel-genfiles
 /bazel-io_bazel
 /bazel-out
diff --git a/src/java_tools/buildjar/java/com/google/devtools/build/java/bazel/BUILD b/src/java_tools/buildjar/java/com/google/devtools/build/java/bazel/BUILD
index 3ede677953..8818072e3a 100644
--- a/src/java_tools/buildjar/java/com/google/devtools/build/java/bazel/BUILD
+++ b/src/java_tools/buildjar/java/com/google/devtools/build/java/bazel/BUILD
@@ -12,7 +12,7 @@ genrule(
     name = "javac-bootclasspath-locations",
     srcs = ["@bazel_tools//tools/jdk:bootclasspath"],
     outs = ["JavacBootclasspathLocations.java"],
-    cmd = "$(location javac-bootclasspath-locations.sh) $@ $(GENDIR) '' $(SRCS)",
+    cmd = "$(location javac-bootclasspath-locations.sh) $@ $(GENDIR) 'bazel_tools/' $(SRCS)",
     tools = ["javac-bootclasspath-locations.sh"],
 )
 
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index 374f8872ba..d1ae560ab1 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -40,17 +40,19 @@ import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.List;
+import java.util.Objects;
 import javax.annotation.Nullable;
 
 /**
  * An Artifact represents a file used by the build system, whether it's a source
  * file or a derived (output) file. Not all Artifacts have a corresponding
- * FileTarget object in the <code>build.packages</code> API: for example,
+ * FileTarget object in the <code>build.lib.packages</code> API: for example,
  * low-level intermediaries internal to a given rule, such as a Java class files
  * or C++ object files. However all FileTargets have a corresponding Artifact.
  *
- * <p>In any given call to Builder#buildArtifacts(), no two Artifacts in the
- * action graph may refer to the same path.
+ * <p>In any given call to
+ * {@link com.google.devtools.build.lib.skyframe.SkyframeExecutor#buildArtifacts}, no two Artifacts
+ * in the action graph may refer to the same path.
  *
  * <p>Artifacts generally fall into two classifications, source and derived, but
  * there exist a few other cases that are fuzzy and difficult to classify. The
@@ -128,7 +130,6 @@ public class Artifact
     return EvalUtils.compareByClass(this, o);
   }
 
-
   /** An object that can expand middleman artifacts. */
   public interface ArtifactExpander {
 
@@ -182,10 +183,10 @@ public class Artifact
    * </pre>
    *
    * <p>In a derived Artifact, the execPath will overlap with part of the root, which in turn will
-   * be below of the execRoot.
+   * be below the execRoot.
    * <pre>
    *  [path] == [/root][pathTail] == [/execRoot][execPath] == [/execRoot][rootPrefix][pathTail]
-   * <pre>
+   * </pre>
    */
   @VisibleForTesting
   public Artifact(Path path, Root root, PathFragment execPath, ArtifactOwner owner) {
@@ -200,7 +201,6 @@ public class Artifact
     this.hashCode = path.hashCode();
     this.path = path;
     this.root = root;
-    this.execPath = execPath;
     // These two lines establish the invariant that
     // execPath == rootRelativePath <=> execPath.equals(rootRelativePath)
     // This is important for isSourceArtifact.
@@ -210,6 +210,7 @@ public class Artifact
           + rootRel + " at " + path + " with root " + root);
     }
     this.rootRelativePath = rootRel.equals(execPath) ? execPath : rootRel;
+    this.execPath = externalfy(execPath);
     this.owner = Preconditions.checkNotNull(owner, path);
   }
 
@@ -350,7 +351,12 @@ public class Artifact
   @SkylarkCallable(name = "is_source", structField =  true,
       doc = "Returns true if this is a source file, i.e. it is not generated")
   public final boolean isSourceArtifact() {
-    return execPath == rootRelativePath;
+    // All source roots should, you know, point to sources. However, for embedded binaries, they
+    // are actually created as derived artifacts, so we have to special-case isSourceArtifact to
+    // treat derived roots in the main repo where execPath==rootRelPath as source roots.
+    // Source artifacts have reference-identical execPaths and rootRelativePaths, so use
+    // of == instead of .equals() is intentional here.
+    return execPath == rootRelativePath || root.isSourceRoot();
   }
 
   /**
@@ -515,15 +521,9 @@ public class Artifact
    * For targets in external repositories, this returns the path the artifact live at in the
    * runfiles tree. For local targets, it returns the rootRelativePath.
    */
+  // TODO(kchodorow): remove.
   public final PathFragment getRunfilesPath() {
-    PathFragment relativePath = rootRelativePath;
-    if (relativePath.segmentCount() > 1
-        && relativePath.getSegment(0).equals(Label.EXTERNAL_PATH_PREFIX)) {
-      // Turn external/repo/foo into ../repo/foo.
-      relativePath = relativePath.relativeTo(Label.EXTERNAL_PATH_PREFIX);
-      relativePath = new PathFragment("..").getRelative(relativePath);
-    }
-    return relativePath;
+    return externalfy(rootRelativePath);
   }
 
   @SkylarkCallable(
@@ -557,7 +557,31 @@ public class Artifact
             + "runfiles of a binary."
   )
   public final String getExecPathString() {
-    return getExecPath().getPathString();
+    return getExecPath().toString();
+  }
+
+  private PathFragment externalfy(PathFragment relativePath) {
+    if (root.isMainRepo()) {
+      return relativePath;
+    }
+
+    PathFragment prefix;
+    if (root.isSourceRoot()) {
+      prefix = new PathFragment(Label.EXTERNAL_PATH_PREFIX)
+          .getRelative(root.getPath().getBaseName());
+    } else {
+      prefix = new PathFragment(Label.EXTERNAL_PATH_PREFIX)
+          .getRelative(root.getExecRoot().getBaseName());
+    }
+    return prefix.getRelative(relativePath);
+  }
+
+  /**
+   * Returns if this artifact is in the main repository or not.
+   */
+  // TODO(kchodorow): remove once execroot path is correct.
+  public boolean isInMainRepo() {
+    return root.isMainRepo();
   }
 
   /*
@@ -585,7 +609,7 @@ public class Artifact
     // We don't bother to check root in the equivalence relation, because we
     // assume that no root is an ancestor of another one.
     Artifact that = (Artifact) other;
-    return this.path.equals(that.path);
+    return Objects.equals(this.path, that.path);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
index bba49288b0..19eddd680f 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
@@ -287,8 +287,9 @@ public class ArtifactFactory implements ArtifactResolver, ArtifactSerializer, Ar
    * not null). That Artifact will have root determined by the package roots of this factory if it
    * lives in a subpackage distinct from that of baseExecPath, and {@code baseRoot} otherwise.
    */
-  public synchronized Artifact resolveSourceArtifactWithAncestor(
-      PathFragment relativePath, PathFragment baseExecPath, Root baseRoot) {
+  private synchronized Artifact resolveSourceArtifactWithAncestor(
+      PathFragment relativePath, PathFragment baseExecPath, Root baseRoot,
+      RepositoryName repositoryName) {
     Preconditions.checkState(
         (baseExecPath == null) == (baseRoot == null),
         "%s %s %s",
@@ -313,7 +314,15 @@ public class ArtifactFactory implements ArtifactResolver, ArtifactSerializer, Ar
       return null;
     }
 
-    return createArtifactIfNotValid(findSourceRoot(execPath, baseExecPath, baseRoot), execPath);
+    return createArtifactIfNotValid(
+        findSourceRoot(execPath, baseExecPath, baseRoot, repositoryName), execPath);
+  }
+
+  // TODO(kchodorow): make remote repositories work with include scanning.
+  public synchronized Artifact resolveSourceArtifactWithAncestor(
+      PathFragment relativePath, PathFragment baseExecPath, Root baseRoot) {
+    return resolveSourceArtifactWithAncestor(
+        relativePath, baseExecPath, baseRoot, RepositoryName.MAIN);
   }
 
   /**
@@ -322,21 +331,20 @@ public class ArtifactFactory implements ArtifactResolver, ArtifactSerializer, Ar
    */
   @Nullable
   private Root findSourceRoot(
-      PathFragment execPath, @Nullable PathFragment baseExecPath, @Nullable Root baseRoot) {
+      PathFragment execPath, @Nullable PathFragment baseExecPath, @Nullable Root baseRoot,
+      RepositoryName repoName) {
     PathFragment dir = execPath.getParentDirectory();
     if (dir == null) {
       return null;
     }
 
-    RepositoryName repoName = RepositoryName.MAIN;
-
     Pair<RepositoryName, PathFragment> repo = RepositoryName.fromPathFragment(dir);
     if (repo != null) {
       repoName = repo.getFirst();
       dir = repo.getSecond();
     }
 
-    while (dir != null && !dir.equals(baseExecPath)) {
+    while (packageRoots != null && dir != null && !dir.equals(baseExecPath)) {
       Root sourceRoot = packageRoots.get(PackageIdentifier.create(repoName, dir));
       if (sourceRoot != null) {
         return sourceRoot;
@@ -348,9 +356,8 @@ public class ArtifactFactory implements ArtifactResolver, ArtifactSerializer, Ar
   }
 
   @Override
-  public Artifact resolveSourceArtifact(PathFragment execPath,
-      @SuppressWarnings("unused") RepositoryName repositoryName) {
-    return resolveSourceArtifactWithAncestor(execPath, null, null);
+  public Artifact resolveSourceArtifact(PathFragment execPath, RepositoryName repositoryName) {
+    return resolveSourceArtifactWithAncestor(execPath, null, null, repositoryName);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Root.java b/src/main/java/com/google/devtools/build/lib/actions/Root.java
index f39bceda29..f870787320 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Root.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Root.java
@@ -170,7 +170,7 @@ public final class Root implements Comparable<Root>, Serializable {
     return isMiddlemanRoot;
   }
 
-  public boolean isMainRepo() {
+  boolean isMainRepo() {
     return isMainRepo;
   }
 
@@ -181,7 +181,7 @@ public final class Root implements Comparable<Root>, Serializable {
 
   @Override
   public int hashCode() {
-    return Objects.hash(execRoot, path.hashCode());
+    return Objects.hash(execRoot, path.hashCode(), isMainRepo);
   }
 
   @Override
@@ -193,7 +193,9 @@ public final class Root implements Comparable<Root>, Serializable {
       return false;
     }
     Root r = (Root) o;
-    return path.equals(r.path) && Objects.equals(execRoot, r.execRoot);
+    return path.equals(r.path)
+        && Objects.equals(execRoot, r.execRoot)
+        && Objects.equals(isMainRepo, r.isMainRepo);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
index 495d5ebdd4..6da8281b40 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
@@ -123,7 +123,7 @@ public final class AnalysisUtils {
    * <p>For example "//pkg:target" -> "pkg/&lt;fragment&gt;/target.
    */
   public static PathFragment getUniqueDirectory(Label label, PathFragment fragment) {
-    return label.getPackageIdentifier().getSourceRoot().getRelative(fragment)
+    return label.getPackageIdentifier().getPackageFragment().getRelative(fragment)
         .getRelative(label.getName());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CompilationHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/CompilationHelper.java
index 8a1fddc6ff..a3769e3e07 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CompilationHelper.java
@@ -54,8 +54,8 @@ public final class CompilationHelper {
     }
     MiddlemanFactory factory = env.getMiddlemanFactory();
     return ImmutableList.of(factory.createMiddlemanAllowMultiple(
-        env, actionOwner, ruleContext.getPackageDirectory(), purpose, filesToBuild,
-        ruleContext.getConfiguration().getMiddlemanDirectory(
+        env, actionOwner, ruleContext.getRule().getLabel().getPackageIdentifier().getSourceRoot(),
+        purpose, filesToBuild, ruleContext.getConfiguration().getMiddlemanDirectory(
             ruleContext.getRule().getRepository())));
   }
 
@@ -87,7 +87,8 @@ public final class CompilationHelper {
     MiddlemanFactory factory = env.getMiddlemanFactory();
     Iterable<Artifact> artifacts = dep.getProvider(FileProvider.class).getFilesToBuild();
     return ImmutableList.of(
-        factory.createMiddlemanAllowMultiple(env, actionOwner, ruleContext.getPackageDirectory(),
+        factory.createMiddlemanAllowMultiple(env, actionOwner,
+            ruleContext.getRule().getLabel().getPackageIdentifier().getSourceRoot(),
             purpose, artifacts, ruleContext.getConfiguration().getMiddlemanDirectory(
                 ruleContext.getRule().getRepository())));
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index fdd38db6de..17ab4416fd 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -143,9 +143,7 @@ public final class ConfiguredTargetFactory {
         : configuration.getGenfilesDirectory(rule.getRepository());
     ArtifactOwner owner =
         new ConfiguredTargetKey(rule.getLabel(), configuration.getArtifactOwnerConfiguration());
-    PathFragment rootRelativePath =
-        outputFile.getLabel().getPackageIdentifier().getSourceRoot().getRelative(
-            outputFile.getLabel().getName());
+    PathFragment rootRelativePath = outputFile.getLabel().toPathFragment();
     Artifact result = isFileset
         ? artifactFactory.getFilesetArtifact(rootRelativePath, root, owner)
         : artifactFactory.getDerivedArtifact(rootRelativePath, root, owner);
@@ -196,7 +194,7 @@ public final class ConfiguredTargetFactory {
     } else if (target instanceof InputFile) {
       InputFile inputFile = (InputFile) target;
       Artifact artifact = artifactFactory.getSourceArtifact(
-          inputFile.getExecPath(),
+          inputFile.getLabel().toPathFragment(),
           Root.asSourceRoot(inputFile.getPackage().getSourceRoot(),
               inputFile.getPackage().getPackageIdentifier().getRepository().isMain()),
           new ConfiguredTargetKey(target.getLabel(), config));
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index f160424223..563abe5387 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -609,7 +609,7 @@ public final class RuleContext extends TargetContext
    * {@link #getUniqueDirectoryArtifact(String, PathFragment, Root)}) ensures that this is the case.
    */
   public PathFragment getPackageDirectory() {
-    return getLabel().getPackageIdentifier().getSourceRoot();
+    return getLabel().getPackageIdentifier().getPackageFragment();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java b/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
index 0de1b2d513..e0bb6ce79e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Runfiles.java
@@ -417,6 +417,19 @@ public final class Runfiles {
     return newManifest;
   }
 
+  private static PathFragment getRootRelativePath(Artifact artifact) {
+    Preconditions.checkArgument(artifact != null);
+    if (artifact.isInMainRepo()) {
+      return artifact.getRootRelativePath();
+    }
+
+    return new PathFragment(Label.EXTERNAL_PATH_PREFIX)
+        .getRelative(artifact.isSourceArtifact()
+            ? artifact.getRoot().getPath().getBaseName()
+            : artifact.getRoot().getExecRoot().getBaseName())
+        .getRelative(artifact.getRootRelativePath());
+  }
+
   /**
    * Returns the symlinks as a map from PathFragment to Artifact.
    *
@@ -433,7 +446,7 @@ public final class Runfiles {
     Map<PathFragment, Artifact> manifest = getSymlinksAsMap(checker);
     // Add unconditional artifacts (committed to inclusion on construction of runfiles).
     for (Artifact artifact : getUnconditionalArtifactsWithoutMiddlemen()) {
-      checker.put(manifest, artifact.getRootRelativePath(), artifact);
+      checker.put(manifest, Runfiles.getRootRelativePath(artifact), artifact);
     }
 
     // Add conditional artifacts (only included if they appear in a pruning manifest).
@@ -490,7 +503,7 @@ public final class Runfiles {
     // workspace.
     private boolean sawWorkspaceName;
 
-    public ManifestBuilder(
+    ManifestBuilder(
         PathFragment workspaceName, boolean legacyExternalRunfiles) {
       this.manifest = new HashMap<>();
       this.workspaceName = workspaceName;
@@ -501,19 +514,27 @@ public final class Runfiles {
     /**
      * Adds a map under the workspaceName.
      */
-    public void addUnderWorkspace(
+    void addUnderWorkspace(
         Map<PathFragment, Artifact> inputManifest, ConflictChecker checker) {
       for (Map.Entry<PathFragment, Artifact> entry : inputManifest.entrySet()) {
         PathFragment path = entry.getKey();
-        if (isUnderWorkspace(path)) {
+        if (isUnderWorkspace(entry.getValue())) {
+          // For empty files (e.g., ../repo/__init__.py), we don't have an artifact so
+          // isUnderWorkspace returns true.
+          checker.put(manifest, workspaceName.getRelative(path).normalize(), entry.getValue());
           sawWorkspaceName = true;
-          checker.put(manifest, workspaceName.getRelative(path), entry.getValue());
         } else {
+          PathFragment root = entry.getValue().getRoot().getPath().asFragment();
           if (legacyExternalRunfiles) {
-            checker.put(manifest, workspaceName.getRelative(path), entry.getValue());
+            // external/repo
+            PathFragment repoDir = root.subFragment(root.segmentCount() - 2, root.segmentCount());
+            // Turn ../repo/foo info wsname/external/repo/foo.
+            checker.put(
+                manifest, workspaceName.getRelative(repoDir).getRelative(path).normalize(),
+                entry.getValue());
           }
-          // Always add the non-legacy .runfiles/repo/whatever path.
-          checker.put(manifest, getExternalPath(path), entry.getValue());
+          checker.put(
+              manifest, workspaceName.getRelative(entry.getKey()).normalize(), entry.getValue());
         }
       }
     }
@@ -541,17 +562,20 @@ public final class Runfiles {
       return manifest;
     }
 
-    private PathFragment getExternalPath(PathFragment path) {
-      return checkForWorkspace(path.relativeTo(Label.EXTERNAL_PACKAGE_NAME));
-    }
-
     private PathFragment checkForWorkspace(PathFragment path) {
-      sawWorkspaceName = sawWorkspaceName || path.getSegment(0).equals(workspaceName);
+      sawWorkspaceName = sawWorkspaceName
+          || path.getSegment(0).equals(workspaceName.getPathString());
       return path;
     }
 
-    private static boolean isUnderWorkspace(PathFragment path) {
-      return !path.startsWith(Label.EXTERNAL_PACKAGE_NAME);
+    private static boolean isUnderWorkspace(@Nullable Artifact artifact) {
+      if (artifact == null) {
+        return true;
+      }
+      PathFragment root = artifact.getRoot().getPath().asFragment();
+      return root.segmentCount() < 2
+          || !root.getSegment(root.segmentCount() - 2).equals(
+              Label.EXTERNAL_PACKAGE_NAME.getPathString());
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
index 3330b3f094..640cb13887 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.lib.analysis.config;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Joiner;
 import com.google.common.base.Verify;
 import com.google.common.collect.ArrayListMultimap;
@@ -24,6 +23,8 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.Interner;
+import com.google.common.collect.Interners;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
@@ -83,7 +84,6 @@ import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
-import java.util.Objects;
 import java.util.Queue;
 import java.util.Set;
 import java.util.TreeMap;
@@ -956,62 +956,6 @@ public final class BuildConfiguration {
     }
   }
 
-  /**
-   * All the output directories pertinent to a configuration.
-   */
-  private static final class OutputRoots implements Serializable {
-    private final Root outputDirectory; // the configuration-specific output directory.
-    private final Root binDirectory;
-    private final Root genfilesDirectory;
-    private final Root coverageMetadataDirectory; // for coverage-related metadata, artifacts, etc.
-    private final Root testLogsDirectory;
-    private final Root includeDirectory;
-    private final Root middlemanDirectory;
-
-    private OutputRoots(BlazeDirectories directories, String outputDirName) {
-      Path execRoot = directories.getExecRoot();
-      // configuration-specific output tree
-      Path outputDir = directories.getOutputPath().getRelative(outputDirName);
-      this.outputDirectory = Root.asDerivedRoot(execRoot, outputDir, true);
-
-      // specific subdirs under outputDirectory
-      this.binDirectory = Root
-          .asDerivedRoot(execRoot, outputDir.getRelative("bin"), true);
-      this.genfilesDirectory = Root.asDerivedRoot(
-          execRoot, outputDir.getRelative("genfiles"), true);
-      this.coverageMetadataDirectory = Root.asDerivedRoot(execRoot,
-          outputDir.getRelative("coverage-metadata"), true);
-      this.testLogsDirectory = Root.asDerivedRoot(
-          execRoot, outputDir.getRelative("testlogs"), true);
-      this.includeDirectory = Root.asDerivedRoot(
-          execRoot, outputDir.getRelative(BlazeDirectories.RELATIVE_INCLUDE_DIR), true);
-      this.middlemanDirectory = Root.middlemanRoot(execRoot, outputDir, true);
-    }
-
-    @Override
-    public boolean equals(Object o) {
-      if (o == this) {
-        return true;
-      }
-      if (!(o instanceof OutputRoots)) {
-        return false;
-      }
-      OutputRoots other = (OutputRoots) o;
-      return outputDirectory.equals(other.outputDirectory)
-          && binDirectory.equals(other.binDirectory)
-          && genfilesDirectory.equals(other.genfilesDirectory)
-          && coverageMetadataDirectory.equals(other.coverageMetadataDirectory)
-          && testLogsDirectory.equals(other.testLogsDirectory)
-          && includeDirectory.equals(other.includeDirectory);
-    }
-
-    @Override
-    public int hashCode() {
-      return Objects.hash(outputDirectory, binDirectory, genfilesDirectory,
-          coverageMetadataDirectory, testLogsDirectory, includeDirectory);
-    }
-  }
-
   private final String checksum;
 
   private Transitions transitions;
@@ -1023,7 +967,7 @@ public final class BuildConfiguration {
   /**
    * Directories in the output tree.
    *
-   * <p>The computation of the output directory should be a non-injective mapping from
+   * <p>The computation of the output directories should be a non-injective mapping from
    * BuildConfiguration instances to strings. The result should identify the aspects of the
    * configuration that should be reflected in the output file names.  Furthermore the
    * returned string must not contain shell metacharacters.
@@ -1060,7 +1004,54 @@ public final class BuildConfiguration {
    * this so that the build works even if the two configurations are too close (which is common)
    * and so that the path of artifacts in the host configuration is a bit more readable.
    */
-  private final OutputRoots outputRoots;
+  private enum OutputDirectory {
+    BIN("bin"),
+    GENFILES("genfiles"),
+    MIDDLEMAN(true),
+    TESTLOGS("testlogs"),
+    COVERAGE("coverage-metadata"),
+    INCLUDE(BlazeDirectories.RELATIVE_INCLUDE_DIR),
+    OUTPUT(false);
+
+    private final String name;
+    private final boolean middleman;
+
+    /**
+     * This constructor is for roots without suffixes, e.g.,
+     * [[execroot/repo]/bazel-out/local-fastbuild].
+     * @param isMiddleman whether the root should be a middleman root or a "normal" derived root.
+     */
+    OutputDirectory(boolean isMiddleman) {
+      this.name = "";
+      this.middleman = isMiddleman;
+    }
+
+    OutputDirectory(String name) {
+      this.name = name;
+      this.middleman = false;
+    }
+
+    Root getRoot(
+        RepositoryName repositoryName, String outputDirName, BlazeDirectories directories) {
+      // e.g., execroot/repo1/../repo2 -> execroot/repo2
+      Path execRoot = directories.getExecRoot().getRelative(repositoryName.getPathUnderExecRoot());
+      // e.g., execroot/repo2/bazel-out/config
+      Path outputDir = execRoot.getRelative(directories.getRelativeOutputPath())
+          .getRelative(outputDirName);
+      if (middleman) {
+        return INTERNER.intern(Root.middlemanRoot(execRoot, outputDir, repositoryName.isMain()));
+      }
+      // e.g., execroot/repo2/bazel-out/config/bin
+      return INTERNER.intern(
+          Root.asDerivedRoot(execRoot, outputDir.getRelative(name), repositoryName.isMain()));
+    }
+  }
+
+  // "Cache" of roots, so we don't keep around thousands of copies of the same root.
+  private static Interner<Root> INTERNER = Interners.newWeakInterner();
+
+  private final BlazeDirectories directories;
+  private final String outputDirName;
 
   /** If false, AnalysisEnviroment doesn't register any actions created by the ConfiguredTarget. */
   private final boolean actionsEnabled;
@@ -1238,23 +1229,12 @@ public final class BuildConfiguration {
   /**
    * Constructs a new BuildConfiguration instance.
    */
-  public BuildConfiguration(BlazeDirectories directories,
-      Map<Class<? extends Fragment>, Fragment> fragmentsMap,
-      BuildOptions buildOptions,
-      boolean actionsDisabled) {
-    this(null, directories, fragmentsMap, buildOptions, actionsDisabled);
-  }
-
-  /**
-   * Constructor variation that uses the passed in output roots if non-null, else computes them
-   * from the directories.
-   */
-  public BuildConfiguration(@Nullable OutputRoots outputRoots,
-      @Nullable BlazeDirectories directories,
+  public BuildConfiguration(
+      BlazeDirectories directories,
       Map<Class<? extends Fragment>, Fragment> fragmentsMap,
       BuildOptions buildOptions,
       boolean actionsDisabled) {
-    Preconditions.checkState(outputRoots == null ^ directories == null);
+    this.directories = directories;
     this.actionsEnabled = !actionsDisabled;
     this.fragments = ImmutableSortedMap.copyOf(fragmentsMap, lexicalFragmentSorter);
 
@@ -1282,16 +1262,12 @@ public final class BuildConfiguration {
     commandLineBuildVariables = ImmutableMap.copyOf(commandLineDefinesBuilder);
 
     this.mnemonic = buildMnemonic();
-    String outputDirName = (options.outputDirectoryName != null)
+    this.outputDirName = (options.outputDirectoryName != null)
         ? options.outputDirectoryName : mnemonic;
     this.platformName = buildPlatformName();
 
     this.shExecutable = collectExecutables().get("sh");
 
-    this.outputRoots = outputRoots != null
-        ? outputRoots
-        : new OutputRoots(directories, outputDirName);
-
     Pair<ImmutableMap<String, String>, ImmutableSet<String>> shellEnvironment =
         setupShellEnvironment();
     this.localShellEnvironment = shellEnvironment.getFirst();
@@ -1335,7 +1311,7 @@ public final class BuildConfiguration {
     BuildOptions options = buildOptions.trim(
         getOptionsClasses(fragmentsMap.keySet(), ruleClassProvider));
     BuildConfiguration newConfig =
-        new BuildConfiguration(outputRoots, null, fragmentsMap, options, !actionsEnabled);
+        new BuildConfiguration(directories, fragmentsMap, options, !actionsEnabled);
     newConfig.setConfigurationTransitions(this.transitions);
     return newConfig;
   }
@@ -1851,23 +1827,6 @@ public final class BuildConfiguration {
   }
 
   /**
-   * For an given environment, returns a subset containing all
-   * variables in the given list if they are defined in the given
-   * environment.
-   */
-  @VisibleForTesting
-  static Map<String, String> getMapping(List<String> variables,
-      Map<String, String> environment) {
-    Map<String, String> result = new HashMap<>();
-    for (String var : variables) {
-      if (environment.containsKey(var)) {
-        result.put(var, environment.get(var));
-      }
-    }
-    return result;
-  }
-
-  /**
    * Returns the {@link Option} class the defines the given option, null if the
    * option isn't recognized.
    *
@@ -1916,7 +1875,7 @@ public final class BuildConfiguration {
    * Returns the output directory for this build configuration.
    */
   public Root getOutputDirectory(RepositoryName repositoryName) {
-    return outputRoots.outputDirectory;
+    return OutputDirectory.OUTPUT.getRoot(repositoryName, outputDirName, directories);
   }
 
   /**
@@ -1925,7 +1884,7 @@ public final class BuildConfiguration {
   @SkylarkCallable(name = "bin_dir", structField = true, documented = false)
   @Deprecated
   public Root getBinDirectory() {
-    return outputRoots.binDirectory;
+    return getBinDirectory(RepositoryName.MAIN);
   }
 
   /**
@@ -1933,11 +1892,9 @@ public final class BuildConfiguration {
    * repositories without changes to how ArtifactFactory resolves derived roots. This is not an
    * issue right now because it only effects Blaze's include scanning (internal) and Bazel's
    * repositories (external) but will need to be fixed.
-   * TODO(kchodorow): Use the repository name to derive the bin directory.
    */
-  @SuppressWarnings("unused")
   public Root getBinDirectory(RepositoryName repositoryName) {
-    return getBinDirectory();
+    return OutputDirectory.BIN.getRoot(repositoryName, outputDirName, directories);
   }
 
   /**
@@ -1949,11 +1906,9 @@ public final class BuildConfiguration {
 
   /**
    * Returns the include directory for this build configuration.
-   * TODO(kchodorow): Use the repository name to derive the include directory.
    */
-  @SuppressWarnings("unused")
   public Root getIncludeDirectory(RepositoryName repositoryName) {
-    return outputRoots.includeDirectory;
+    return OutputDirectory.INCLUDE.getRoot(repositoryName, outputDirName, directories);
   }
 
   /**
@@ -1962,33 +1917,27 @@ public final class BuildConfiguration {
   @SkylarkCallable(name = "genfiles_dir", structField = true, documented = false)
   @Deprecated
   public Root getGenfilesDirectory() {
-    return outputRoots.genfilesDirectory;
+    return getGenfilesDirectory(RepositoryName.MAIN);
   }
 
-  // TODO(kchodorow): Use the repository name to derive the genfiles directory.
-  @SuppressWarnings("unused")
   public Root getGenfilesDirectory(RepositoryName repositoryName) {
-    return getGenfilesDirectory();
+    return OutputDirectory.GENFILES.getRoot(repositoryName, outputDirName, directories);
   }
 
   /**
    * Returns the directory where coverage-related artifacts and metadata files
    * should be stored. This includes for example uninstrumented class files
    * needed for Jacoco's coverage reporting tools.
-   * TODO(kchodorow): Use the repository name to derive the coverage directory.
    */
-  @SuppressWarnings("unused")
   public Root getCoverageMetadataDirectory(RepositoryName repositoryName) {
-    return outputRoots.coverageMetadataDirectory;
+    return OutputDirectory.COVERAGE.getRoot(repositoryName, outputDirName, directories);
   }
 
   /**
    * Returns the testlogs directory for this build configuration.
-   * TODO(kchodorow): Use the repository name to derive the test directory.
    */
-  @SuppressWarnings("unused")
   public Root getTestLogsDirectory(RepositoryName repositoryName) {
-    return outputRoots.testLogsDirectory;
+    return OutputDirectory.TESTLOGS.getRoot(repositoryName, outputDirName, directories);
   }
 
   /**
@@ -2013,11 +1962,9 @@ public final class BuildConfiguration {
 
   /**
    * Returns the internal directory (used for middlemen) for this build configuration.
-   * TODO(kchodorow): Use the repository name to derive the middleman directory.
    */
-  @SuppressWarnings("unused")
   public Root getMiddlemanDirectory(RepositoryName repositoryName) {
-    return outputRoots.middlemanDirectory;
+    return OutputDirectory.MIDDLEMAN.getRoot(repositoryName, outputDirName, directories);
   }
 
   public boolean getAllowRuntimeDepsOnNeverLink() {
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
index 8954aa01ed..40e9290651 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
@@ -36,6 +36,7 @@ import com.google.devtools.build.lib.analysis.Runfiles;
 import com.google.devtools.build.lib.analysis.RunfilesProvider;
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -206,9 +207,9 @@ public class GenRule implements RuleConfiguredTargetFactory {
                 } else {
                   dir = ruleContext.getConfiguration().getGenfilesFragment();
                 }
-                PathFragment relPath =
-                    ruleContext.getRule().getLabel().getPackageIdentifier().getSourceRoot();
-                return dir.getRelative(relPath).getPathString();
+                PackageIdentifier pkgId = ruleContext.getRule().getLabel().getPackageIdentifier();
+                return pkgId.getRepository().getPathUnderExecRoot().getRelative(dir)
+                    .getRelative(pkgId.getPackageFragment()).getPathString();
               }
             } else {
               return super.lookupMakeVariable(name);
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
index 3d86e63e58..80f9a58b4b 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
@@ -83,7 +83,8 @@ public class BazelPythonSemantics implements PythonSemantics {
   @Override
   public List<PathFragment> getImports(RuleContext ruleContext) {
     List<PathFragment> result = new ArrayList<>();
-    PathFragment packageFragment = ruleContext.getLabel().getPackageIdentifier().getRunfilesPath();
+    PathFragment packageFragment = ruleContext.getLabel().getPackageIdentifier()
+        .getPathUnderExecRoot();
     // Python scripts start with x.runfiles/ as the module space, so everything must be manually
     // adjusted to be relative to the workspace name.
     packageFragment = new PathFragment(ruleContext.getWorkspaceName())
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
index 5ee730e022..2efdc21693 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
@@ -508,8 +508,14 @@ public class ExecutionTool {
 
     // Plant the symlink forest.
     try {
-      new SymlinkForest(
-          packageRoots, getExecRoot(), runtime.getProductName(), workspaceName)
+      SymlinkForest.builder()
+          .setLegacyExternalRunfiles(
+              request.getOptions(BuildConfiguration.Options.class).legacyExternalRunfiles)
+          .setPackageRoots(packageRoots)
+          .setWorkspace(getExecRoot())
+          .setProductName(runtime.getProductName())
+          .setWorkspaceName(workspaceName)
+          .build()
           .plantSymlinkForest();
     } catch (IOException e) {
       throw new ExecutorInitException("Source forest creation failed", e);
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/SymlinkForest.java b/src/main/java/com/google/devtools/build/lib/buildtool/SymlinkForest.java
index 44cf5f196e..56c40bba20 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/SymlinkForest.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/SymlinkForest.java
@@ -15,54 +15,70 @@
 package com.google.devtools.build.lib.buildtool;
 
 import com.google.common.annotations.VisibleForTesting;
+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.Maps;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
+import com.google.devtools.build.lib.vfs.Symlinks;
 import java.io.IOException;
 import java.util.Map;
 import java.util.Set;
 import java.util.logging.Level;
 import java.util.logging.Logger;
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.Immutable;
 
 /**
  * Creates a symlink forest based on a package path map.
  */
-class SymlinkForest {
+@Immutable
+final class SymlinkForest {
 
-  private static final Logger LOG = Logger.getLogger(SymlinkForest.class.getName());
-  private static final boolean LOG_FINER = LOG.isLoggable(Level.FINER);
+  private static final Logger log = Logger.getLogger(SymlinkForest.class.getName());
+  private static final boolean LOG_FINER = log.isLoggable(Level.FINER);
 
   private final ImmutableMap<PackageIdentifier, Path> packageRoots;
   private final Path workspace;
   private final String workspaceName;
   private final String productName;
   private final String[] prefixes;
+  private final ImmutableSet<RepositoryName> repositories;
+  private final boolean legacyExternalRunfiles;
 
-  SymlinkForest(
-      ImmutableMap<PackageIdentifier, Path> packageRoots, Path workspace, String productName,
+  private SymlinkForest(
+      boolean legacyExternalRunfiles,
+      ImmutableMap<PackageIdentifier, Path> packageRoots,
+      Path workspace,
+      String productName,
+      String[] prefixes,
       String workspaceName) {
+    this.legacyExternalRunfiles = legacyExternalRunfiles;
     this.packageRoots = packageRoots;
     this.workspace = workspace;
     this.workspaceName = workspaceName;
     this.productName = productName;
-    this.prefixes = new String[] { ".", "_", productName + "-"};
+    this.prefixes = prefixes;
+    ImmutableSet.Builder<RepositoryName> repositoryNameBuilder = ImmutableSet.builder();
+    for (PackageIdentifier pkgId : packageRoots.keySet()) {
+      repositoryNameBuilder.add(pkgId.getRepository());
+    }
+    this.repositories = repositoryNameBuilder.build();
   }
 
   /**
    * Returns the longest prefix from a given set of 'prefixes' that are
    * contained in 'path'. I.e the closest ancestor directory containing path.
    * Returns null if none found.
-   * @param path
-   * @param prefixes
    */
   @VisibleForTesting
   static PackageIdentifier longestPathPrefix(
@@ -77,26 +93,43 @@ class SymlinkForest {
   }
 
   /**
-   * Delete all dir trees under a given 'dir' that don't start with one of a set
-   * of given 'prefixes'. Does not follow any symbolic links.
+   * Delete all dir trees under each repository root. For the main repository, don't delete trees
+   * that start with one of a set of given 'prefixes'. Does not follow any symbolic links.
    */
   @VisibleForTesting
   @ThreadSafety.ThreadSafe
-  static void deleteTreesBelowNotPrefixed(Path dir, String[] prefixes) throws IOException {
-    dirloop:
-    for (Path p : dir.getDirectoryEntries()) {
-      String name = p.getBaseName();
-      for (String prefix : prefixes) {
-        if (name.startsWith(prefix)) {
-          continue dirloop;
+  void deleteTreesBelowNotPrefixed() throws IOException {
+    for (RepositoryName repositoryName : Iterables.concat(
+        ImmutableList.of(RepositoryName.MAIN), repositories)) {
+      Path repositoryExecRoot = workspace.getRelative(repositoryName.getPathUnderExecRoot());
+      FileSystemUtils.createDirectoryAndParents(repositoryExecRoot);
+      dirloop:
+      for (Path p : repositoryExecRoot.getDirectoryEntries()) {
+        String name = p.getBaseName();
+        for (String prefix : prefixes) {
+          if (name.startsWith(prefix)) {
+            continue dirloop;
+          }
         }
+        FileSystemUtils.deleteTree(p);
       }
-      FileSystemUtils.deleteTree(p);
     }
   }
 
+  private boolean isPackage(PackageIdentifier pkgId) {
+    return packageRoots.containsKey(pkgId);
+  }
+
+  /**
+   * Finds the nearest ancestor package.
+   */
+  @Nullable
+  private PackageIdentifier findParentPackage(PackageIdentifier pkgId) {
+    return longestPathPrefix(pkgId, packageRoots.keySet());
+  }
+
   void plantSymlinkForest() throws IOException {
-    deleteTreesBelowNotPrefixed(workspace, prefixes);
+    deleteTreesBelowNotPrefixed();
 
     // Create a sorted map of all dirs (packages and their ancestors) to sets of their roots.
     // Packages come from exactly one root, but their shared ancestors may come from more.
@@ -122,23 +155,24 @@ class SymlinkForest {
     // Now add in roots for all non-pkg dirs that are in between two packages, and missed above.
     for (Map.Entry<PackageIdentifier, Set<Path>> entry : dirRootsMap.entrySet()) {
       PackageIdentifier dir = entry.getKey();
-      if (!packageRoots.containsKey(dir)) {
-        PackageIdentifier pkgId = longestPathPrefix(dir, packageRoots.keySet());
-        if (pkgId != null) {
-          entry.getValue().add(packageRoots.get(pkgId));
+      if (!isPackage(dir)) {
+        PackageIdentifier parentPackage = findParentPackage(dir);
+        if (parentPackage != null) {
+          entry.getValue().add(packageRoots.get(parentPackage));
         }
       }
     }
     // Create output dirs for all dirs that have more than one root and need to be split.
     for (Map.Entry<PackageIdentifier, Set<Path>> entry : dirRootsMap.entrySet()) {
       PackageIdentifier dir = entry.getKey();
+      // Handle creating top level directories for external repositories here, too.
       if (!dir.getRepository().isMain()) {
         FileSystemUtils.createDirectoryAndParents(
             workspace.getRelative(dir.getRepository().getPathUnderExecRoot()));
       }
       if (entry.getValue().size() > 1) {
         if (LOG_FINER) {
-          LOG.finer("mkdir " + workspace.getRelative(dir.getPathUnderExecRoot()));
+          log.finer("mkdir " + workspace.getRelative(dir.getPathUnderExecRoot()));
         }
         FileSystemUtils.createDirectoryAndParents(
             workspace.getRelative(dir.getPathUnderExecRoot()));
@@ -158,43 +192,20 @@ class SymlinkForest {
         // This is the top-most dir that can be linked to a single root. Make it so.
         Path root = roots.iterator().next();  // lone root in set
         if (LOG_FINER) {
-          LOG.finer("ln -s " + root.getRelative(dir.getSourceRoot()) + " "
+          log.finer("ln -s " + root.getRelative(dir.getPackageFragment()) + " "
               + workspace.getRelative(dir.getPathUnderExecRoot()));
         }
         workspace.getRelative(dir.getPathUnderExecRoot())
-            .createSymbolicLink(root.getRelative(dir.getSourceRoot()));
+            .createSymbolicLink(root.getRelative(dir.getPackageFragment()));
       }
     }
     // Make links for dirs within packages, skip parent-only dirs.
     for (Map.Entry<PackageIdentifier, Set<Path>> entry : dirRootsMap.entrySet()) {
-      PackageIdentifier dir = entry.getKey();
+      PackageIdentifier child = entry.getKey();
       if (entry.getValue().size() > 1) {
         // If this dir is at or below a package dir, link in its contents.
-        PackageIdentifier pkgId = longestPathPrefix(dir, packageRoots.keySet());
-        if (pkgId != null) {
-          Path root = packageRoots.get(pkgId);
-          try {
-            Path absdir = root.getRelative(dir.getSourceRoot());
-            if (absdir.isDirectory()) {
-              if (LOG_FINER) {
-                LOG.finer("ln -s " + absdir + "/* "
-                    + workspace.getRelative(dir.getSourceRoot()) + "/");
-              }
-              for (Path target : absdir.getDirectoryEntries()) {
-                PathFragment p = target.relativeTo(root);
-                if (!dirRootsMap.containsKey(createInRepo(pkgId, p))) {
-                  //LOG.finest("ln -s " + target + " " + linkRoot.getRelative(p));
-                  workspace.getRelative(p).createSymbolicLink(target);
-                }
-              }
-            } else {
-              LOG.fine("Symlink planting skipping dir '" + absdir + "'");
-            }
-          } catch (IOException e) {
-            e.printStackTrace();
-          }
-          // Otherwise its just an otherwise empty common parent dir.
-        }
+        PackageIdentifier parent = longestPathPrefix(child, packageRoots.keySet());
+        linkDirectoryEntries(parent, child, dirRootsMap);
       }
     }
 
@@ -210,20 +221,56 @@ class SymlinkForest {
       }
       // For the top-level directory, generate symlinks to everything in the directory instead of
       // the directory itself.
-      Path sourceDirectory = entry.getValue().getRelative(pkgId.getSourceRoot());
-      for (Path target : sourceDirectory.getDirectoryEntries()) {
+      for (Path target : entry.getValue().getDirectoryEntries()) {
         String baseName = target.getBaseName();
         Path execPath = execrootDirectory.getRelative(baseName);
         // Create any links that don't exist yet and don't start with bazel-.
-        if (!baseName.startsWith(productName + "-") && !execPath.exists()) {
+        if (!baseName.startsWith(productName + "-") && !execPath.exists(Symlinks.NOFOLLOW)) {
           execPath.createSymbolicLink(target);
         }
       }
     }
 
+    // Create the external/workspace directory.
+    if (legacyExternalRunfiles) {
+      workspace.getRelative(Label.EXTERNAL_PACKAGE_NAME).createSymbolicLink(
+          workspace.getRelative(Label.EXTERNAL_PATH_PREFIX));
+    }
     symlinkCorrectWorkspaceName();
   }
 
+  private void linkDirectoryEntries(
+      PackageIdentifier parent, PackageIdentifier child,
+      Map<PackageIdentifier, Set<Path>> dirRootsMap) {
+    if (parent == null) {
+      // No parent package in packageRoots.
+      return;
+    }
+    Path root = packageRoots.get(parent);
+    try {
+      Path absdir = root.getRelative(child.getPackageFragment());
+      if (absdir.isDirectory()) {
+        if (LOG_FINER) {
+          log.finer("ln -s " + absdir + "/* "
+              + workspace.getRelative(child.getPathUnderExecRoot()) + "/");
+        }
+        for (Path target : absdir.getDirectoryEntries()) {
+          PathFragment p = child.getPackageFragment().getRelative(target.getBaseName());
+          if (!dirRootsMap.containsKey(createInRepo(parent, p))) {
+            PathFragment execFragment = child.getPathUnderExecRoot()
+                .getRelative(target.getBaseName());
+            workspace.getRelative(execFragment).createSymbolicLink(target);
+          }
+        }
+      } else {
+        log.fine("Symlink planting skipping dir '" + absdir + "'");
+      }
+    } catch (IOException e) {
+      e.printStackTrace();
+    }
+    // Otherwise its just an otherwise empty common parent dir.
+  }
+
   /**
    * Right now, the execution root is under the basename of the source directory, not the name
    * defined in the WORKSPACE file. Thus, this adds a symlink with the WORKSPACE's workspace name
@@ -250,4 +297,55 @@ class SymlinkForest {
       PackageIdentifier repo, PathFragment packageFragment) {
     return PackageIdentifier.create(repo.getRepository(), packageFragment);
   }
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  public static class Builder {
+    private boolean legacyExternalRunfiles = false;
+    private ImmutableMap<PackageIdentifier, Path> packageRoots = ImmutableMap.of();
+    private Path workspace;
+    private String productName;
+    private String[] prefixes;
+    private String workspaceName;
+
+    Builder setLegacyExternalRunfiles(boolean legacyExternalRunfiles) {
+      this.legacyExternalRunfiles = legacyExternalRunfiles;
+      return this;
+    }
+
+    Builder setPackageRoots(ImmutableMap<PackageIdentifier, Path> packageRoots) {
+      this.packageRoots = packageRoots;
+      return this;
+    }
+
+    Builder setWorkspace(Path workspace) {
+      this.workspace = workspace;
+      return this;
+    }
+
+    Builder setProductName(String productName) {
+      this.productName = productName;
+      this.prefixes = new String[] { ".", "_", productName + "-"};
+      return this;
+    }
+
+    Builder setPrefixes(String[] prefixes) {
+      this.prefixes = prefixes;
+      return this;
+    }
+
+    Builder setWorkspaceName(String workspaceName) {
+      this.workspaceName = workspaceName;
+      return this;
+    }
+
+    public SymlinkForest build() {
+      Preconditions.checkState(workspace != null);
+      Preconditions.checkState(productName != null);
+      return new SymlinkForest(
+          legacyExternalRunfiles, packageRoots, workspace, productName, prefixes, workspaceName);
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
index b5a699023e..fb4c47f0c8 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
@@ -72,7 +72,7 @@ public final class Label implements Comparable<Label>, Serializable, SkylarkPrin
   public static final PackageIdentifier EXTERNAL_PACKAGE_IDENTIFIER =
       PackageIdentifier.createInMainRepo(EXTERNAL_PACKAGE_NAME);
 
-  public static final String EXTERNAL_PATH_PREFIX = "external";
+  public static final String EXTERNAL_PATH_PREFIX = "..";
 
   private static final Interner<Label> LABEL_INTERNER = Interners.newWeakInterner();
 
@@ -334,7 +334,7 @@ public final class Label implements Comparable<Label>, Serializable, SkylarkPrin
       doc = "Returns the execution root for the workspace of this label, relative to the execroot. "
       + "For instance:<br>"
       + "<pre class=language-python>Label(\"@repo//pkg/foo:abc\").workspace_root =="
-      + " \"external/repo\"</pre>")
+      + " \"../repo\"</pre>")
   public String getWorkspaceRoot() {
     return packageIdentifier.getRepository().getSourceRoot().toString();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java b/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java
index 905866f077..727433a244 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java
@@ -124,15 +124,7 @@ public final class PackageIdentifier implements Comparable<PackageIdentifier>, S
   }
 
   public PathFragment getPathUnderExecRoot() {
-    return getSourceRoot();
-  }
-
-  /**
-   * Returns the runfiles/execRoot path for this repository (relative to the x.runfiles/main-repo/
-   * directory).
-   */
-  public PathFragment getRunfilesPath() {
-    return repository.getRunfilesPath().getRelative(pkgName);
+    return repository.getPathUnderExecRoot().getRelative(pkgName);
   }
 
   public PackageIdentifier makeAbsolute() {
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java b/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java
index ba0f6b407b..cfad122e69 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java
@@ -214,8 +214,8 @@ public final class RepositoryName implements Serializable {
   }
 
   /**
-   * Returns the runfiles/execRoot path for this repository. If we don't know the name of this repo
-   * (i.e., it is in the main repository), return an empty path fragment.
+   * Returns the runfiles/execRoot path for this repository: ../reponame. If we don't know the name
+   * of this repo (i.e., it is in the main repository), return an empty path fragment.
    */
   public PathFragment getPathUnderExecRoot() {
     return isDefault() || isMain()
@@ -224,15 +224,6 @@ public final class RepositoryName implements Serializable {
   }
 
   /**
-   * Returns the runfiles path relative to the x.runfiles/main-repo directory.
-   */
-  // TODO(kchodorow): remove once execroot is reorg-ed.
-  public PathFragment getRunfilesPath() {
-    return isDefault() || isMain()
-        ? PathFragment.EMPTY_FRAGMENT : new PathFragment("..").getRelative(strippedName());
-  }
-
-  /**
    * Returns the repository name, with leading "{@literal @}" (or "" for the default repository).
    */
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeHelper.java b/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeHelper.java
index c5a70c61e8..758b9dd34c 100644
--- a/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/exec/SymlinkTreeHelper.java
@@ -152,8 +152,8 @@ public final class SymlinkTreeHelper {
       args.add("--use_metadata");
     }
 
-    args.add(inputManifest.relativeTo(execRoot).getPathString());
-    args.add(symlinkTreeRoot.relativeTo(execRoot).getPathString());
+    args.add(inputManifest.getPathString());
+    args.add(symlinkTreeRoot.getPathString());
 
     return args;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index f1d9b51878..5fd2759382 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -292,9 +292,10 @@ public class Package {
     this.filename = builder.getFilename();
     this.packageDirectory = filename.getParentDirectory();
 
-    this.sourceRoot = getSourceRoot(filename, packageIdentifier.getSourceRoot());
+    this.sourceRoot = getSourceRoot(filename, packageIdentifier.getPackageFragment());
     if ((sourceRoot == null
-        || !sourceRoot.getRelative(packageIdentifier.getSourceRoot()).equals(packageDirectory))
+        || !sourceRoot.getRelative(packageIdentifier.getPackageFragment())
+            .equals(packageDirectory))
         && !filename.getBaseName().equals("WORKSPACE")) {
       throw new IllegalArgumentException(
           "Invalid BUILD file name for package '" + packageIdentifier + "': " + filename);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/LocalResourceContainer.java b/src/main/java/com/google/devtools/build/lib/rules/android/LocalResourceContainer.java
index 05d60a8eb4..20281610e0 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/LocalResourceContainer.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/LocalResourceContainer.java
@@ -163,8 +163,7 @@ public final class LocalResourceContainer {
         PathFragment assetsDir, Iterable<? extends TransitiveInfoCollection> targets) {
       for (TransitiveInfoCollection target : targets) {
         for (Artifact file : target.getProvider(FileProvider.class).getFilesToBuild()) {
-          PathFragment packageFragment = file.getArtifactOwner().getLabel()
-              .getPackageIdentifier().getSourceRoot();
+          PathFragment packageFragment = file.getArtifactOwner().getLabel().getPackageFragment();
           PathFragment packageRelativePath =
               file.getRootRelativePath().relativeTo(packageFragment);
           if (packageRelativePath.startsWith(assetsDir)) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
index c7f11d8f29..35d5a99504 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
@@ -396,9 +396,13 @@ public final class CcCommon {
         continue;
       }
       PathFragment includesPath = packageFragment.getRelative(includesAttr).normalize();
-      if (!includesPath.isNormalized()) {
+      // It's okay for the includes path to start with ../workspace-name for external repos.
+      if ((packageIdentifier.getRepository().isMain() && !includesPath.isNormalized())
+          || (!packageIdentifier.getRepository().isMain()
+              && !includesPath.startsWith(
+                  packageIdentifier.getRepository().getPathUnderExecRoot()))) {
         ruleContext.attributeError("includes",
-            "Path references a path above the execution root.");
+            includesAttr + " references a path above the execution root (" + includesPath + ").");
       }
       if (includesPath.segmentCount() == 0) {
         ruleContext.attributeError(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java
index de7373a8ba..2e64a02e03 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibraryHelper.java
@@ -1106,7 +1106,7 @@ public final class CcLibraryHelper {
         ruleContext.getLabel().getPackageIdentifier().getRepository().getPathUnderExecRoot();
     contextBuilder.addQuoteIncludeDir(repositoryPath);
     contextBuilder.addQuoteIncludeDir(
-        ruleContext.getConfiguration().getGenfilesFragment().getRelative(repositoryPath));
+        repositoryPath.getRelative(ruleContext.getConfiguration().getGenfilesFragment()));
 
     for (PathFragment systemIncludeDir : systemIncludeDirs) {
       contextBuilder.addSystemIncludeDir(systemIncludeDir);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 21d0d307c5..d878e90f63 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -43,6 +43,7 @@ import com.google.devtools.build.lib.analysis.actions.ExecutionInfoSpecifier;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.PerLabelOptions;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -328,10 +329,15 @@ public class CppCompileAction extends AbstractAction
         continue;
       }
 
-      if (include.isAbsolute()
-          || !PathFragment.EMPTY_FRAGMENT.getRelative(include).normalize().isNormalized()) {
-        ruleContext.ruleError(
-            "The include path '" + include + "' references a path outside of the execution root.");
+      // One starting ../ is okay for getting to a sibling repository.
+      PathFragment originalInclude = include;
+      if (include.startsWith(new PathFragment(Label.EXTERNAL_PATH_PREFIX))) {
+        include = include.relativeTo(Label.EXTERNAL_PATH_PREFIX);
+      }
+
+      if (include.isAbsolute() || !include.normalize().isNormalized()) {
+        ruleContext.ruleError("The include path '" + originalInclude
+            + "' references a path outside of the execution root.");
       }
     }
   }
@@ -971,6 +977,7 @@ public class CppCompileAction extends AbstractAction
         if (execPath.getBaseName().endsWith(".pcm")) {
           continue;
         }
+        RepositoryName repositoryName = RepositoryName.MAIN;
         PathFragment execPathFragment = execPath.asFragment();
         if (execPathFragment.isAbsolute()) {
           // Absolute includes from system paths are ignored.
@@ -983,14 +990,25 @@ public class CppCompileAction extends AbstractAction
           // the build with an error.
           if (execPath.startsWith(execRoot)) {
             execPathFragment = execPath.relativeTo(execRoot); // funky but tolerable path
+          } else if (execPath.startsWith(execRoot.getParentDirectory())) {
+            // External repository.
+            execPathFragment = execPath.relativeTo(execRoot.getParentDirectory());
+            String workspace = execPathFragment.getSegment(0);
+            execPathFragment = execPathFragment.relativeTo(workspace);
+            try {
+              repositoryName = RepositoryName.create("@" + workspace);
+            } catch (LabelSyntaxException e) {
+              throw new IllegalStateException(workspace + " is not a valid repository name");
+            }
           } else {
             problems.add(execPathFragment.getPathString());
             continue;
           }
         }
-        Artifact artifact = allowedDerivedInputsMap.get(execPathFragment);
+        Artifact artifact = allowedDerivedInputsMap.get(
+            repositoryName.getPathUnderExecRoot().getRelative(execPathFragment));
         if (artifact == null) {
-          artifact = artifactResolver.resolveSourceArtifact(execPathFragment, RepositoryName.MAIN);
+          artifact = artifactResolver.resolveSourceArtifact(execPathFragment, repositoryName);
         }
         if (artifact != null) {
           inputs.add(artifact);
@@ -1003,7 +1021,7 @@ public class CppCompileAction extends AbstractAction
           problems.add(execPathFragment.getPathString());
         }
       }
-      //TODO(b/22551695): Remove in favor of seperate implementations.
+      //TODO(b/22551695): Remove in favor of separate implementations.
       if (semantics == null || semantics.needsIncludeValidation()) {
         problems.assertProblemFree(this, getSourceFile());
       }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
index f5e0ab5f39..7e7e83ae21 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
@@ -485,7 +485,7 @@ public class CppHelper {
         Preconditions.checkState(Link.SHARED_LIBRARY_FILETYPES.matches(artifact.getFilename()));
         symlinkedArtifacts.add(isCppRuntime
             ? SolibSymlinkAction.getCppRuntimeSymlink(
-                ruleContext, artifact, solibDirOverride, configuration)
+            ruleContext, artifact, solibDirOverride, configuration)
             : SolibSymlinkAction.getDynamicLibrarySymlink(
                 ruleContext, artifact, false, true, configuration));
       }
@@ -494,7 +494,8 @@ public class CppHelper {
     }
     return ImmutableList.of(
         factory.createMiddlemanAllowMultiple(ruleContext.getAnalysisEnvironment(), actionOwner,
-            ruleContext.getPackageDirectory(), purpose, artifacts,
+            ruleContext.getLabel().getPackageIdentifier().getPathUnderExecRoot(), purpose,
+            artifacts,
             configuration.getMiddlemanDirectory(ruleContext.getRule().getRepository())));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java
index 512281ad93..e77d02a71d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java
@@ -20,6 +20,7 @@ import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactResolver;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
@@ -93,7 +94,7 @@ public class HeaderDiscovery {
       return inputs.build();
     }
     List<Path> systemIncludePrefixes = permittedSystemIncludePrefixes;
-
+    RepositoryName repositoryName = RepositoryName.MAIN;
     // Check inclusions.
     IncludeProblems problems = new IncludeProblems();
     for (Path execPath : depSet.getDependencies()) {
@@ -111,16 +112,24 @@ public class HeaderDiscovery {
         // non-system include paths here should never be absolute. If they
         // are, it's probably due to a non-hermetic #include, & we should stop
         // the build with an error.
+        // funky but tolerable path
         if (execPath.startsWith(execRoot)) {
-          execPathFragment = execPath.relativeTo(execRoot); // funky but tolerable path
-        } else {
-          problems.add(execPathFragment.getPathString());
-          continue;
+          execPathFragment = execPath.relativeTo(execRoot);
+        } else if (execPath.startsWith(execRoot.getParentDirectory())) {
+          // External repository.
+          execPathFragment = execPath.relativeTo(execRoot.getParentDirectory());
+          String workspace = execPathFragment.getSegment(0);
+          execPathFragment = execPathFragment.relativeTo(workspace);
+          try {
+            repositoryName = RepositoryName.create("@" + workspace);
+          } catch (LabelSyntaxException e) {
+            throw new IllegalStateException(workspace + " is not a valid repository name");
+          }
         }
       }
       Artifact artifact = allowedDerivedInputsMap.get(execPathFragment);
       if (artifact == null) {
-        artifact = artifactResolver.resolveSourceArtifact(execPathFragment, RepositoryName.MAIN);
+        artifact = artifactResolver.resolveSourceArtifact(execPathFragment, repositoryName);
       }
       if (artifact != null) {
         inputs.add(artifact);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
index 647fc45490..10a3ce704a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
@@ -471,7 +471,7 @@ public class JavaCommon {
     if (launcher != null) {
       javaExecutable = launcher.getRootRelativePath();
     } else {
-      javaExecutable = ruleContext.getFragment(Jvm.class).getRunfilesJavaExecutable();
+      javaExecutable = ruleContext.getFragment(Jvm.class).getJavaExecutable();
     }
 
     if (!javaExecutable.isAbsolute()) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java b/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java
index 37271b8b48..fb7941f101 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java
@@ -89,7 +89,12 @@ public final class Jvm extends BuildConfiguration.Fragment {
   @SkylarkCallable(name = "java_executable", structField = true,
       doc = "The java executable, i.e. bin/java relative to the Java home.")
   public PathFragment getJavaExecutable() {
-    return java;
+    if (jvmLabel == null || jvmLabel.getPackageIdentifier().getRepository().isMain()) {
+      return java;
+    } else {
+      return jvmLabel.getPackageIdentifier().getRepository().getPathUnderExecRoot()
+          .getRelative(BIN_JAVA);
+    }
   }
 
   /**
@@ -103,17 +108,6 @@ public final class Jvm extends BuildConfiguration.Fragment {
     return jvmLabel;
   }
 
-  /**
-   * If possible, resolves java relative to the jvmLabel's repository. Otherwise, returns the
-   * same thing as getJavaExecutable().
-   */
-  public PathFragment getRunfilesJavaExecutable() {
-    if (jvmLabel == null || jvmLabel.getPackageIdentifier().getRepository().isMain()) {
-      return getJavaExecutable();
-    }
-    return jvmLabel.getPackageIdentifier().getRepository().getRunfilesPath().getRelative(BIN_JAVA);
-  }
-
   @Override
   public void addGlobalMakeVariables(Builder<String, String> globalMakeEnvBuilder) {
     globalMakeEnvBuilder.put("JAVABASE", getJavaHome().getPathString());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java b/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java
index fe97c33620..1a5f3b64d7 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java
@@ -126,7 +126,7 @@ public final class JvmConfigurationLoader implements ConfigurationFragmentFactor
             if (jvmTarget.getLabel().getPackageIdentifier().getRepository().isDefault()) {
               javaHomePath = jvmLabel.getPackageFragment();
             } else {
-              javaHomePath = jvmTarget.getLabel().getPackageIdentifier().getSourceRoot();
+              javaHomePath = jvmTarget.getLabel().getPackageIdentifier().getPathUnderExecRoot();
             }
 
             if ((jvmTarget instanceof Rule) &&
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java
index f84b5b9e2b..7634e33af2 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/DarwinSandboxedStrategy.java
@@ -176,8 +176,6 @@ public class DarwinSandboxedStrategy extends SandboxStrategy {
     ImmutableMap<String, String> spawnEnvironment =
         StandaloneSpawnStrategy.locallyDeterminedEnv(execRoot, productName, spawn.getEnvironment());
 
-    Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment());
-
     Path runUnderPath = getRunUnderPath(spawn);
 
     try {
@@ -185,6 +183,7 @@ public class DarwinSandboxedStrategy extends SandboxStrategy {
           new HardlinkedExecRoot(execRoot, sandboxPath, sandboxExecRoot, errWriter);
 
       ImmutableSet<PathFragment> outputs = SandboxHelpers.getOutputFiles(spawn);
+      Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment(), outputs);
       hardlinkedExecRoot.createFileSystem(
           getMounts(spawn, actionExecutionContext), outputs, writableDirs);
 
@@ -197,7 +196,7 @@ public class DarwinSandboxedStrategy extends SandboxStrategy {
           new DarwinSandboxRunner(
               sandboxPath,
               sandboxExecRoot,
-              getWritableDirs(sandboxExecRoot, spawnEnvironment),
+              getWritableDirs(sandboxExecRoot, spawnEnvironment, outputs),
               getInaccessiblePaths(),
               runUnderPath,
               verboseFailures);
@@ -221,11 +220,12 @@ public class DarwinSandboxedStrategy extends SandboxStrategy {
   }
 
   @Override
-  protected ImmutableSet<Path> getWritableDirs(Path sandboxExecRoot, Map<String, String> env) {
+  protected ImmutableSet<Path> getWritableDirs(Path sandboxExecRoot, Map<String, String> env,
+      ImmutableSet<PathFragment> outputs) {
     FileSystem fs = sandboxExecRoot.getFileSystem();
     ImmutableSet.Builder<Path> writableDirs = ImmutableSet.builder();
 
-    writableDirs.addAll(super.getWritableDirs(sandboxExecRoot, env));
+    writableDirs.addAll(super.getWritableDirs(sandboxExecRoot, env, outputs));
     writableDirs.add(fs.getPath("/dev"));
 
     String sysTmpDir = System.getenv("TMPDIR");
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
index 48892132cb..be49446a82 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/LinuxSandboxedStrategy.java
@@ -102,12 +102,12 @@ public class LinuxSandboxedStrategy extends SandboxStrategy {
     Path sandboxPath = SandboxHelpers.getSandboxRoot(blazeDirs, productName, uuid, execCounter);
     Path sandboxExecRoot = sandboxPath.getRelative("execroot").getRelative(execRoot.getBaseName());
 
-    Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment());
 
     try {
       // Build the execRoot for the sandbox.
       SymlinkedExecRoot symlinkedExecRoot = new SymlinkedExecRoot(sandboxExecRoot);
       ImmutableSet<PathFragment> outputs = SandboxHelpers.getOutputFiles(spawn);
+      Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment(), outputs);
       symlinkedExecRoot.createFileSystem(
           getMounts(spawn, actionExecutionContext), outputs, writableDirs);
 
@@ -118,7 +118,7 @@ public class LinuxSandboxedStrategy extends SandboxStrategy {
                 execRoot,
                 sandboxPath,
                 sandboxExecRoot,
-                getWritableDirs(sandboxExecRoot, spawn.getEnvironment()),
+                getWritableDirs(sandboxExecRoot, spawn.getEnvironment(), outputs),
                 getInaccessiblePaths(),
                 verboseFailures,
                 sandboxOptions.sandboxDebug);
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java
index 7a12e9b600..2b63527013 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SandboxStrategy.java
@@ -44,12 +44,16 @@ abstract class SandboxStrategy implements SpawnActionContext {
   }
 
   /** Gets the list of directories that the spawn will assume to be writable. */
-  protected ImmutableSet<Path> getWritableDirs(Path sandboxExecRoot, Map<String, String> env) {
+  protected ImmutableSet<Path> getWritableDirs(Path sandboxExecRoot, Map<String, String> env,
+      ImmutableSet<PathFragment> outputs) {
     Builder<Path> writableDirs = ImmutableSet.builder();
     // We have to make the TEST_TMPDIR directory writable if it is specified.
     if (env.containsKey("TEST_TMPDIR")) {
       writableDirs.add(sandboxExecRoot.getRelative(env.get("TEST_TMPDIR")));
     }
+    for (PathFragment output : outputs) {
+      writableDirs.add(sandboxExecRoot.getRelative(output).getParentDirectory());
+    }
     return writableDirs.build();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SymlinkedExecRoot.java b/src/main/java/com/google/devtools/build/lib/sandbox/SymlinkedExecRoot.java
index 9efe7fcb45..17fe4217b0 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SymlinkedExecRoot.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SymlinkedExecRoot.java
@@ -66,7 +66,7 @@ final class SymlinkedExecRoot implements SandboxExecRoot {
       throws IOException {
     for (PathFragment inputPath : inputs) {
       Path dir = sandboxExecRoot.getRelative(inputPath).getParentDirectory();
-      Preconditions.checkArgument(dir.startsWith(sandboxExecRoot));
+      Preconditions.checkArgument(dir.startsWith(sandboxExecRoot.getParentDirectory()));
       FileSystemUtils.createDirectoryAndParentsWithCache(createdDirs, dir);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java
index ceda17193d..57f19cfc4c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java
@@ -75,7 +75,7 @@ class SkyframePackageLoaderWithValueEnvironment implements PackageProviderForCon
   public void addDependency(Package pkg, String fileName)
       throws LabelSyntaxException, IOException, InterruptedException {
     RootedPath fileRootedPath = RootedPath.toRootedPath(pkg.getSourceRoot(),
-        pkg.getPackageIdentifier().getSourceRoot().getRelative(fileName));
+        pkg.getPackageIdentifier().getPackageFragment().getRelative(fileName));
     FileValue result = (FileValue) env.getValue(FileValue.key(fileRootedPath));
     if (result != null && !result.exists()) {
       throw new IOException();
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
index 1f83f28005..734f7d4f09 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesTest.java
@@ -21,18 +21,15 @@ import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Root;
-import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
 import java.util.HashMap;
 import java.util.LinkedHashMap;
 import java.util.Map;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
 
 /**
  * Test for {@link Runfiles}.
@@ -321,37 +318,36 @@ public class RunfilesTest extends FoundationTestCase {
 
   @Test
   public void testLegacyRunfilesStructure() {
-    Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
+    Root root = Root.asSourceRoot(scratch.resolve("/workspace/external/repo"));
     PathFragment workspaceName = new PathFragment("wsname");
-    PathFragment pathB = new PathFragment("external/repo/b");
+    PathFragment pathB = new PathFragment("b");
     Artifact artifactB = new Artifact(pathB, root);
 
     Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(workspaceName, true);
 
     Map<PathFragment, Artifact> inputManifest = Maps.newHashMap();
-    inputManifest.put(pathB, artifactB);
+    inputManifest.put(new PathFragment("../repo").getRelative(pathB), artifactB);
     Runfiles.ConflictChecker checker = new Runfiles.ConflictChecker(
         Runfiles.ConflictPolicy.WARN, reporter, null);
     builder.addUnderWorkspace(inputManifest, checker);
 
     assertThat(builder.build().entrySet()).containsExactly(
-        Maps.immutableEntry(workspaceName.getRelative(pathB), artifactB),
+        Maps.immutableEntry(workspaceName.getRelative("external/repo/b"), artifactB),
         Maps.immutableEntry(new PathFragment("repo/b"), artifactB));
     assertNoEvents();
   }
 
   @Test
   public void testRunfileAdded() {
-    Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
+    Root root = Root.asSourceRoot(scratch.resolve("/workspace/external/repo"));
     PathFragment workspaceName = new PathFragment("wsname");
-    PathFragment pathB = new PathFragment("external/repo/b");
+    PathFragment pathB = new PathFragment("b");
     Artifact artifactB = new Artifact(pathB, root);
 
     Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(workspaceName, false);
 
-    Map<PathFragment, Artifact> inputManifest = ImmutableMap.<PathFragment, Artifact>builder()
-        .put(pathB, artifactB)
-        .build();
+    Map<PathFragment, Artifact> inputManifest = ImmutableMap.of(
+        new PathFragment("../repo").getRelative(pathB), artifactB);
     Runfiles.ConflictChecker checker = new Runfiles.ConflictChecker(
         Runfiles.ConflictPolicy.WARN, reporter, null);
     builder.addUnderWorkspace(inputManifest, checker);
@@ -361,29 +357,4 @@ public class RunfilesTest extends FoundationTestCase {
         Maps.immutableEntry(new PathFragment("repo/b"), artifactB));
     assertNoEvents();
   }
-
-  // TODO(kchodorow): remove this once the default workspace name is always set.
-  @Test
-  public void testConflictWithExternal() {
-    Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
-    PathFragment pathB = new PathFragment("repo/b");
-    PathFragment externalPathB = Label.EXTERNAL_PACKAGE_NAME.getRelative(pathB);
-    Artifact artifactB = new Artifact(pathB, root);
-    Artifact artifactExternalB = new Artifact(externalPathB, root);
-
-    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
-        PathFragment.EMPTY_FRAGMENT, false);
-
-    Map<PathFragment, Artifact> inputManifest = ImmutableMap.<PathFragment, Artifact>builder()
-        .put(pathB, artifactB)
-        .put(externalPathB, artifactExternalB)
-        .build();
-    Runfiles.ConflictChecker checker = new Runfiles.ConflictChecker(
-        Runfiles.ConflictPolicy.WARN, reporter, null);
-    builder.addUnderWorkspace(inputManifest, checker);
-
-    assertThat(builder.build().entrySet()).containsExactly(
-        Maps.immutableEntry(new PathFragment("repo/b"), artifactExternalB));
-    checkConflictWarning();
-  }
 }
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 2ea8887392..f9daedb462 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
@@ -38,6 +38,7 @@ import com.google.devtools.build.lib.analysis.config.ConfigurationFactory;
 import com.google.devtools.build.lib.buildtool.BuildRequest.BuildRequestOptions;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.exec.ExecutionOptions;
 import com.google.devtools.build.lib.flags.InvocationPolicyEnforcer;
 import com.google.devtools.build.lib.packages.PackageFactory;
@@ -189,6 +190,8 @@ public abstract class AnalysisTestCase extends FoundationTestCase {
     loadingPhaseRunner = skyframeExecutor.getLoadingPhaseRunner(
         pkgFactory.getRuleClassNames(), defaultFlags().contains(Flag.SKYFRAME_LOADING_PHASE));
     buildView = new BuildView(directories, ruleClassProvider, skyframeExecutor, null);
+    buildView.setArtifactRoots(
+        ImmutableMap.of(PackageIdentifier.createInMainRepo(""), rootDirectory));
     useConfiguration();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java b/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java
index d86d2be261..5e0cda6d61 100644
--- a/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java
+++ b/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java
@@ -27,7 +27,6 @@ import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.testutil.ManualClock;
-import com.google.devtools.build.lib.testutil.TestConstants;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
@@ -125,7 +124,12 @@ public class SymlinkForestTest {
   @Test
   public void testDeleteTreesBelowNotPrefixed() throws IOException {
     createTestDirectoryTree();
-    SymlinkForest.deleteTreesBelowNotPrefixed(topDir, new String[]{"file-"});
+    SymlinkForest forest = SymlinkForest.builder()
+        .setWorkspace(topDir)
+        .setProductName("mock-name")
+        .setPrefixes(new String[]{"file-"})
+        .build();
+    forest.deleteTreesBelowNotPrefixed();
     assertTrue(file1.exists());
     assertTrue(file2.exists());
     assertFalse(aDir.exists());
@@ -187,7 +191,13 @@ public class SymlinkForestTest {
 
     Path linkRoot = fileSystem.getPath("/linkRoot");
     createDirectoryAndParents(linkRoot);
-    new SymlinkForest(packageRootMap, linkRoot, TestConstants.PRODUCT_NAME, "wsname")
+    SymlinkForest.builder()
+        .setLegacyExternalRunfiles(false)
+        .setPackageRoots(packageRootMap)
+        .setWorkspace(linkRoot)
+        .setProductName("mock-name")
+        .setWorkspaceName("wsname")
+        .build()
         .plantSymlinkForest();
 
     assertLinksTo(linkRoot, rootA, "pkgA");
@@ -215,7 +225,13 @@ public class SymlinkForestTest {
             .put(createPkg(rootX, rootY, "foo"), rootX)
             .build();
 
-    new SymlinkForest(packageRootMap, linkRoot, TestConstants.PRODUCT_NAME, "wsname")
+    SymlinkForest.builder()
+        .setLegacyExternalRunfiles(false)
+        .setPackageRoots(packageRootMap)
+        .setWorkspace(linkRoot)
+        .setProductName("mock-name")
+        .setWorkspaceName("wsname")
+        .build()
         .plantSymlinkForest();
     assertLinksTo(linkRoot, rootX, "file");
   }
@@ -223,24 +239,32 @@ public class SymlinkForestTest {
   @Test
   public void testRemotePackage() throws Exception {
     Path outputBase = fileSystem.getPath("/ob");
-    Path rootY = outputBase.getRelative(Label.EXTERNAL_PATH_PREFIX).getRelative("y");
-    Path rootZ = outputBase.getRelative(Label.EXTERNAL_PATH_PREFIX).getRelative("z");
-    Path rootW = outputBase.getRelative(Label.EXTERNAL_PATH_PREFIX).getRelative("w");
+    Path rootY = outputBase.getRelative(Label.EXTERNAL_PACKAGE_NAME).getRelative("y");
+    Path rootZ = outputBase.getRelative(Label.EXTERNAL_PACKAGE_NAME).getRelative("z");
+    Path rootW = outputBase.getRelative(Label.EXTERNAL_PACKAGE_NAME).getRelative("w");
     createDirectoryAndParents(rootY);
+    createDirectoryAndParents(rootZ);
+    createDirectoryAndParents(rootW);
     FileSystemUtils.createEmptyFile(rootY.getRelative("file"));
 
     ImmutableMap<PackageIdentifier, Path> packageRootMap =
         ImmutableMap.<PackageIdentifier, Path>builder()
             // Remote repo without top-level package.
-            .put(createPkg(outputBase, "y", "w"), outputBase)
+            .put(createPkg(outputBase, "y", "w"), rootY)
             // Remote repo with and without top-level package.
-            .put(createPkg(outputBase, "z", ""), outputBase)
-            .put(createPkg(outputBase, "z", "a/b/c"), outputBase)
+            .put(createPkg(outputBase, "z", ""), rootZ)
+            .put(createPkg(outputBase, "z", "a/b/c"), rootZ)
             // Only top-level pkg.
-            .put(createPkg(outputBase, "w", ""), outputBase)
+            .put(createPkg(outputBase, "w", ""), rootW)
             .build();
 
-    new SymlinkForest(packageRootMap, linkRoot, TestConstants.PRODUCT_NAME, "wsname")
+    SymlinkForest.builder()
+        .setLegacyExternalRunfiles(false)
+        .setPackageRoots(packageRootMap)
+        .setWorkspace(linkRoot)
+        .setProductName("mock-name")
+        .setWorkspaceName("wsname")
+        .build()
         .plantSymlinkForest();
     assertFalse(linkRoot.getRelative(Label.EXTERNAL_PATH_PREFIX + "/y/file").exists());
     assertLinksTo(
@@ -263,9 +287,15 @@ public class SymlinkForestTest {
             .put(Label.EXTERNAL_PACKAGE_IDENTIFIER, root)
             .build();
 
-    new SymlinkForest(packageRootMap, linkRoot, TestConstants.PRODUCT_NAME, "wsname")
+    SymlinkForest.builder()
+        .setLegacyExternalRunfiles(false)
+        .setPackageRoots(packageRootMap)
+        .setWorkspace(linkRoot)
+        .setProductName("mock-name")
+        .setWorkspaceName("wsname")
+        .build()
         .plantSymlinkForest();
-    assertThat(linkRoot.getRelative(Label.EXTERNAL_PATH_PREFIX).exists()).isFalse();
+    assertThat(linkRoot.getRelative(Label.EXTERNAL_PACKAGE_NAME).exists()).isFalse();
   }
 
   @Test
@@ -277,7 +307,13 @@ public class SymlinkForestTest {
             .put(createPkg(root, "y", "w"), root)
             .build();
 
-    new SymlinkForest(packageRootMap, linkRoot, TestConstants.PRODUCT_NAME, "wsname")
+    SymlinkForest.builder()
+        .setLegacyExternalRunfiles(true)
+        .setPackageRoots(packageRootMap)
+        .setWorkspace(linkRoot)
+        .setProductName("mock-name")
+        .setWorkspaceName("wsname")
+        .build()
         .plantSymlinkForest();
     assertThat(linkRoot.getRelative("../wsname").exists()).isTrue();
   }
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java
index 3f5a0e0820..42642b8851 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java
@@ -19,15 +19,13 @@ import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertSame;
 
 import com.google.devtools.build.lib.vfs.PathFragment;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
 import java.io.ByteArrayInputStream;
 import java.io.ByteArrayOutputStream;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
 
 /**
  * Unit tests for {@link PackageIdentifier}.
@@ -39,8 +37,7 @@ public class PackageIdentifierTest {
     PackageIdentifier fooA = PackageIdentifier.parse("@foo//a");
     assertThat(fooA.getRepository().strippedName()).isEqualTo("foo");
     assertThat(fooA.getPackageFragment().getPathString()).isEqualTo("a");
-    assertThat(fooA.getRepository().getSourceRoot()).isEqualTo(
-        new PathFragment("external/foo"));
+    assertThat(fooA.getRepository().getSourceRoot()).isEqualTo(new PathFragment("external/foo"));
 
     PackageIdentifier absoluteA = PackageIdentifier.parse("//a");
     assertThat(absoluteA.getRepository().strippedName()).isEqualTo("");
@@ -101,10 +98,12 @@ public class PackageIdentifierTest {
   }
 
   @Test
-  public void testRunfilesDir() throws Exception {
-    assertThat(PackageIdentifier.create("@foo", new PathFragment("bar/baz")).getRunfilesPath())
+  public void testPathUnderExecRoot() throws Exception {
+    assertThat(
+        PackageIdentifier.create("@foo", new PathFragment("bar/baz")).getPathUnderExecRoot())
         .isEqualTo(new PathFragment("../foo/bar/baz"));
-    assertThat(PackageIdentifier.create("@", new PathFragment("bar/baz")).getRunfilesPath())
+    assertThat(
+        PackageIdentifier.create("@", new PathFragment("bar/baz")).getPathUnderExecRoot())
         .isEqualTo(new PathFragment("bar/baz"));
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/RepositoryNameTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/RepositoryNameTest.java
index 9a39bbfda1..24a19172c7 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/RepositoryNameTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/RepositoryNameTest.java
@@ -58,12 +58,12 @@ public class RepositoryNameTest {
   }
 
   @Test
-  public void testRunfilesDir() throws Exception {
-    assertThat(RepositoryName.create("@foo").getRunfilesPath())
+  public void testPathUnderExecRoot() throws Exception {
+    assertThat(RepositoryName.create("@foo").getPathUnderExecRoot())
         .isEqualTo(new PathFragment("../foo"));
-    assertThat(RepositoryName.create("@").getRunfilesPath())
+    assertThat(RepositoryName.create("@").getPathUnderExecRoot())
         .isEqualTo(PathFragment.EMPTY_FRAGMENT);
-    assertThat(RepositoryName.create("").getRunfilesPath())
+    assertThat(RepositoryName.create("").getPathUnderExecRoot())
         .isEqualTo(PathFragment.EMPTY_FRAGMENT);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonTest.java
index 1fab14fa9b..5b3d20ca95 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonTest.java
@@ -696,7 +696,7 @@ public class CcCommonTest extends BuildViewTestCase {
     checkError(
         "test",
         "bad_relative_include",
-        "Path references a path above the execution root.",
+        "../.. references a path above the execution root (..).",
         "cc_library(name='bad_relative_include', srcs=[], includes=['../..'])");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java
index 2099df68a1..e476138dbe 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcLibraryConfiguredTargetTest.java
@@ -1121,8 +1121,8 @@ public class CcLibraryConfiguredTargetTest extends BuildViewTestCase {
   @Test
   public void testSystemIncludePathsOutsideExecutionRoot() throws Exception {
     checkError("root", "a",
-        "The include path '../system' references a path outside of the execution root.",
-        "cc_library(name='a', srcs=['a.cc'], copts=['-isystem../system'])");
+        "The include path '../../system' references a path outside of the execution root.",
+        "cc_library(name='a', srcs=['a.cc'], copts=['-isystem../../system'])");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
index 00b27d247e..af79883d2a 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
@@ -340,7 +340,7 @@ public class SkylarkRuleContextTest extends SkylarkTestCase {
     reporter.removeHandler(failFastHandler);
     getConfiguredTarget("@r//:cclib");
     assertContainsEvent(
-        "/external/r/BUILD:2:10: Label '@r//:sub/my_sub_lib.h' crosses boundary of "
+        "/r/BUILD:2:10: Label '@r//:sub/my_sub_lib.h' crosses boundary of "
             + "subpackage '@r//sub' (perhaps you meant to put the colon here: "
             + "'@r//sub:my_sub_lib.h'?)");
   }
diff --git a/src/test/java/com/google/devtools/build/lib/testutil/TestConstants.java b/src/test/java/com/google/devtools/build/lib/testutil/TestConstants.java
index 8db1105771..ba50706f2e 100644
--- a/src/test/java/com/google/devtools/build/lib/testutil/TestConstants.java
+++ b/src/test/java/com/google/devtools/build/lib/testutil/TestConstants.java
@@ -65,7 +65,7 @@ public class TestConstants {
         "com.google.devtools.build.lib.bazel.rules.BazelRulesModule";
   public static final ImmutableList<String> IGNORED_MESSAGE_PREFIXES = ImmutableList.<String>of();
 
-  public static final String GCC_INCLUDE_PATH = "external/bazel_tools/tools/cpp/gcc3";
+  public static final String GCC_INCLUDE_PATH = "../bazel_tools/tools/cpp/gcc3";
 
   public static final String TOOLS_REPOSITORY = "@bazel_tools";
 
diff --git a/src/test/shell/bazel/bazel_rules_test.sh b/src/test/shell/bazel/bazel_rules_test.sh
index b34a26bb77..ae452cf620 100755
--- a/src/test/shell/bazel/bazel_rules_test.sh
+++ b/src/test/shell/bazel/bazel_rules_test.sh
@@ -302,8 +302,8 @@ genrule(
 EOF
 
   bazel build @r//package:hi >$TEST_log 2>&1 || fail "Should build"
-  expect_log bazel-genfiles/external/r/package/a/b
-  expect_log bazel-genfiles/external/r/package/c/d
+  expect_log execroot/r/.*/genfiles/package/a/b
+  expect_log execroot/r/.*/genfiles/package/c/d
 }
 
 function test_python_with_workspace_name() {
diff --git a/src/test/shell/bazel/bazel_sandboxing_test.sh b/src/test/shell/bazel/bazel_sandboxing_test.sh
index 0f911f3f7d..03a146748c 100755
--- a/src/test/shell/bazel/bazel_sandboxing_test.sh
+++ b/src/test/shell/bazel/bazel_sandboxing_test.sh
@@ -80,8 +80,8 @@ genrule(
    name = "tooldir",
    srcs = [],
    outs = ["tooldir.txt"],
-   cmd = "ls -l external/bazel_tools/tools/genrule | tee $@ >&2; " +
-       "cat external/bazel_tools/tools/genrule/genrule-setup.sh >&2",
+   cmd = "ls -l ../bazel_tools/tools/genrule | tee $@ >&2; " +
+       "cat ../bazel_tools/tools/genrule/genrule-setup.sh >&2",
 )
 
 genrule(
diff --git a/src/test/shell/bazel/external_correctness_test.sh b/src/test/shell/bazel/external_correctness_test.sh
index 6d79320fe6..002dec0fc2 100755
--- a/src/test/shell/bazel/external_correctness_test.sh
+++ b/src/test/shell/bazel/external_correctness_test.sh
@@ -140,8 +140,8 @@ genrule(
 )
 EOF
   bazel build @a//b/c:echo-d &> $TEST_log || fail "Build failed"
-  assert_contains "bazel-out/local.*-fastbuild/genfiles/external/a/b/c" \
-    "bazel-genfiles/external/a/b/c/d"
+  assert_contains "a/bazel-out/local-fastbuild/genfiles/b/c" \
+    "$(bazel info execution_root)/../a/bazel-out/local-fastbuild/genfiles/b/c/d"
 }
 
 function test_package_group_in_external_repos() {
@@ -200,7 +200,8 @@ local_repository(
 EOF
 
   bazel build @remote2//:x &> $TEST_log || fail "Build failed"
-  assert_contains 1.0 bazel-genfiles/external/remote2/x.out
+  local execroot="$(bazel info execution_root)"
+  assert_contains 1.0 "$execroot/../remote2/bazel-out/local-fastbuild/genfiles/x.out"
 }
 
 function test_visibility_attributes_in_external_repos() {
@@ -275,16 +276,16 @@ config_setting(name = "four", values = { "define": "ARG=four" })
 EOF
 
   bazel build @r//a:gr || fail "build failed"
-  assert_contains "default" bazel-genfiles/external/r/a/gro
+  local execroot="$(bazel info execution_root)"
+  assert_contains "default" "$execroot/../r/bazel-out/local-fastbuild/genfiles/a/gro"
   bazel build @r//a:gr --define=ARG=one|| fail "build failed"
-  assert_contains "one" bazel-genfiles/external/r/a/gro
+  assert_contains "one" "$execroot/../r/bazel-out/local-fastbuild/genfiles/a/gro"
   bazel build @r//a:gr --define=ARG=two || fail "build failed"
-  assert_contains "two" bazel-genfiles/external/r/a/gro
+  assert_contains "two" "$execroot/../r/bazel-out/local-fastbuild/genfiles/a/gro"
   bazel build @r//a:gr --define=ARG=three || fail "build failed"
-  assert_contains "three" bazel-genfiles/external/r/a/gro
+  assert_contains "three" "$execroot/../r/bazel-out/local-fastbuild/genfiles/a/gro"
   bazel build @r//a:gr --define=ARG=four || fail "build failed"
-  assert_contains "four" bazel-genfiles/external/r/a/gro
-
+  assert_contains "four" "$execroot/../r/bazel-out/local-fastbuild/genfiles/a/gro"
 }
 
 function top_level_dir_changes_helper() {
@@ -306,16 +307,17 @@ genrule(
 )
 EOF
   cd m
+  local execroot="$(bazel info execution_root)"
   bazel "$batch_flag" build @r//:fg &> $TEST_log || \
     fail "Expected build to succeed"
   touch ../r/three
   bazel "$batch_flag" build @r//:fg &> $TEST_log || \
     fail "Expected build to succeed"
-  assert_contains "external/r/three" bazel-genfiles/external/r/fg.out
+  assert_contains "../r/three" "$execroot/../r/bazel-out/local-fastbuild/genfiles/fg.out"
   touch ../r/subdir/four
   bazel "$batch_flag" build @r//:fg &> $TEST_log || \
     fail "Expected build to succeed"
-  assert_contains "external/r/subdir/four" bazel-genfiles/external/r/fg.out
+  assert_contains "../r/subdir/four" "$execroot/../r/bazel-out/local-fastbuild/genfiles/fg.out"
 }
 
 function test_top_level_dir_changes_batch() {
diff --git a/src/test/shell/bazel/external_integration_test.sh b/src/test/shell/bazel/external_integration_test.sh
index 4873710775..0daf021928 100755
--- a/src/test/shell/bazel/external_integration_test.sh
+++ b/src/test/shell/bazel/external_integration_test.sh
@@ -145,7 +145,7 @@ fi
   kill_nc
   expect_log $what_does_the_fox_say
 
-  base_external_path=bazel-out/../external/endangered/fox
+  base_external_path="$(bazel info output_base)/external/endangered/fox"
   assert_files_same ${base_external_path}/male ${base_external_path}/male_relative
   assert_files_same ${base_external_path}/male ${base_external_path}/male_absolute
 }
@@ -630,7 +630,8 @@ genrule(
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  local execroot="$(bazel info execution_root)"
+  assert_contains "abc" "$execroot/../x/bazel-out/local-fastbuild/genfiles/catter.out"
 }
 
 function test_prefix_stripping_zip() {
@@ -659,7 +660,8 @@ genrule(
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  local execroot="$(bazel info execution_root)"
+  assert_contains "abc" "$execroot/../x/bazel-out/local-fastbuild/genfiles/catter.out"
 }
 
 function test_prefix_stripping_existing_repo() {
@@ -688,7 +690,8 @@ http_archive(
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  local execroot="$(bazel info execution_root)"
+  assert_contains "abc" "$execroot/../x/bazel-out/local-fastbuild/genfiles/catter.out"
 }
 
 function test_moving_build_file() {
@@ -715,14 +718,16 @@ genrule(
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build 1 failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  local execroot="$(bazel info execution_root)"
+  assert_contains "abc" "$execroot/../x/bazel-out/local-fastbuild/genfiles/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
   serve_file x.tar.gz
   bazel build @x//:catter &> $TEST_log || fail "Build 2 failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  local execroot="$(bazel info execution_root)"
+  assert_contains "abc" "$execroot/../x/bazel-out/local-fastbuild/genfiles/catter.out"
 }
 
 function test_changing_build_file() {
@@ -759,13 +764,14 @@ genrule(
 EOF
 
   bazel build @x//:catter || fail "Build 1 failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  execroot="$(bazel info execution_root)"
+  assert_contains "abc" "$execroot/../x/bazel-out/local-fastbuild/genfiles/catter.out"
   sed 's/x.BUILD/x.BUILD.new/g' WORKSPACE > WORKSPACE.tmp || \
     fail "Editing WORKSPACE failed"
   mv WORKSPACE.tmp WORKSPACE
   serve_file x.tar.gz
   bazel build @x//:catter &> $TEST_log || fail "Build 2 failed"
-  assert_contains "def" bazel-genfiles/external/x/catter.out
+  assert_contains "def" "$execroot/../x/bazel-out/local-fastbuild/genfiles/catter.out"
 }
 
 function test_truncated() {
diff --git a/src/test/shell/bazel/git_repository_test.sh b/src/test/shell/bazel/git_repository_test.sh
index 2c862b7f7e..b4a2919a0f 100755
--- a/src/test/shell/bazel/git_repository_test.sh
+++ b/src/test/shell/bazel/git_repository_test.sh
@@ -26,6 +26,8 @@ source $(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)/test-setup.sh \
 # Unpacks the test Git repositories in the test temporary directory.
 function set_up() {
   bazel clean --expunge
+  execroot=$(bazel info execution_root)
+  genfiles=$execroot/../g/bazel-out/local-fastbuild/genfiles
   local repos_dir=$TEST_TMPDIR/repos
   if [ -e "$repos_dir" ]; then
     rm -rf $repos_dir
@@ -267,17 +269,17 @@ EOF
 
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" "$genfiles/go"
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_not_log "Cloning"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" "$genfiles/go"
   cat > WORKSPACE <<EOF
 git_repository(name='g', remote='$repo_dir', commit='62777acc')
 EOF
 
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" "$genfiles/go"
 
   cat > WORKSPACE <<EOF
 # This comment line is to change the line numbers, which should not cause Bazel
@@ -287,7 +289,7 @@ EOF
 
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_not_log "Cloning"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" "$genfiles/go"
 
 }
 
@@ -300,9 +302,10 @@ function test_git_repository_refetched_when_commit_changes() {
 git_repository(name='g', remote='$repo_dir', commit='f0b79ff0')
 EOF
 
+  execroot=$(bazel info execution_root)
   bazel build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" "$genfiles/go"
 
   cat > WORKSPACE <<EOF
 git_repository(name='g', remote='$repo_dir', commit='62777acc')
@@ -311,7 +314,7 @@ EOF
 
   bazel build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" "$genfiles/go"
 }
 
 function test_git_repository_and_nofetch() {
@@ -322,10 +325,11 @@ function test_git_repository_and_nofetch() {
 git_repository(name='g', remote='$repo_dir', commit='f0b79ff0')
 EOF
 
+  execroot=$(bazel info execution_root)
   bazel build --nofetch @g//:g >& $TEST_log && fail "Build succeeded"
   expect_log "fetching repositories is disabled"
   bazel build @g//:g >& $TEST_log || fail "Build failed"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" "$genfiles/go"
 
   cat > WORKSPACE <<EOF
 git_repository(name='g', remote='$repo_dir', commit='62777acc')
@@ -334,9 +338,9 @@ EOF
 
   bazel build --nofetch @g//:g >& $TEST_log || fail "Build failed"
   expect_log "External repository 'g' is not up-to-date"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" "$genfiles/go"
   bazel build  @g//:g >& $TEST_log || fail "Build failed"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" "$genfiles/go"
 }
 
 # Helper function for setting up the workspace as follows
@@ -351,7 +355,7 @@ function setup_error_test() {
   mkdir -p planets
   cat > planets/planet_info.sh <<EOF
 #!/bin/bash
-cat external/pluto/info
+cat ../pluto/info
 EOF
 
   cat > planets/BUILD <<EOF
diff --git a/src/test/shell/bazel/local_repository_test.sh b/src/test/shell/bazel/local_repository_test.sh
index f01af32191..83518be2f0 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -570,9 +570,9 @@ genrule(
     visibility = ["//visibility:public"],
 )
 EOF
-  bazel fetch //external:best-turtle || fail "Fetch failed"
+  local execroot="$(bazel info execution_root)"
   bazel build //external:best-turtle &> $TEST_log || fail "First build failed"
-  assert_contains "Leonardo" bazel-genfiles/external/mutant/tmnt
+  assert_contains "Leonardo" "$execroot/../mutant/bazel-out/local-fastbuild/genfiles/tmnt"
 
   cat > mutant.BUILD <<EOF
 genrule(
@@ -583,7 +583,8 @@ genrule(
 )
 EOF
   bazel build //external:best-turtle &> $TEST_log || fail "Second build failed"
-  assert_contains "Donatello" bazel-genfiles/external/mutant/tmnt
+  execroot="$(bazel info execution_root)"
+  assert_contains "Donatello" "$execroot/../mutant/bazel-out/local-fastbuild/genfiles/tmnt"
 }
 
 function test_external_deps_in_remote_repo() {
@@ -620,7 +621,8 @@ genrule(
 EOF
 
  bazel build @r//:r || fail "build failed"
- assert_contains "GOLF" bazel-genfiles/external/r/r.out
+ local execroot="$(bazel info execution_root)"
+ assert_contains "GOLF" "$execroot/../r/bazel-out/local-fastbuild/genfiles/r.out"
 }
 
 function test_local_deps() {
@@ -971,7 +973,8 @@ local_repository(name='r', path='$r')
 EOF
 
   bazel build @r//a:b || fail "build failed"
-  cat bazel-genfiles/external/r/a/bo > $TEST_log
+  local execroot="$(bazel info execution_root)"
+  cat "$execroot/../r/bazel-out/local-fastbuild/genfiles/a/bo" > $TEST_log
   expect_log "@r a"
 }
 
diff --git a/src/test/shell/bazel/skylark_repository_test.sh b/src/test/shell/bazel/skylark_repository_test.sh
index 0e8ef1652d..95a612125d 100755
--- a/src/test/shell/bazel/skylark_repository_test.sh
+++ b/src/test/shell/bazel/skylark_repository_test.sh
@@ -286,7 +286,8 @@ EOF
   bazel build @foo//:bar >& $TEST_log || fail "Failed to build"
   expect_log "foo"
   expect_not_log "Workspace name in .*/WORKSPACE (@__main__) does not match the name given in the repository's definition (@foo)"
-  cat bazel-genfiles/external/foo/bar.txt >$TEST_log
+  local execution_root=$(bazel info execution_root)
+  cat "$execution_root/../foo/bazel-out/local-fastbuild/genfiles/bar.txt" >$TEST_log
   expect_log "foo"
 }
 
diff --git a/src/test/shell/bazel/workspace_test.sh b/src/test/shell/bazel/workspace_test.sh
index 3e6d6ed43f..31c6a60103 100755
--- a/src/test/shell/bazel/workspace_test.sh
+++ b/src/test/shell/bazel/workspace_test.sh
@@ -48,7 +48,8 @@ local_repository(
 EOF
 
   bazel build @x//:x || fail "build failed"
-  assert_contains "hi" bazel-genfiles/external/x/out
+  execroot="$(bazel info execution_root)"
+  assert_contains "hi" "$execroot/../x/bazel-out/local-fastbuild/genfiles/out"
 
   cat > WORKSPACE <<EOF
 local_repository(
@@ -58,7 +59,7 @@ local_repository(
 EOF
 
   bazel build @x//:x || fail "build failed"
-  assert_contains "bye" bazel-genfiles/external/x/out
+  assert_contains "bye" "$execroot/../x/bazel-out/local-fastbuild/genfiles/out"
 }
 
 
diff --git a/src/tools/singlejar/BUILD b/src/tools/singlejar/BUILD
index 63f6a4533b..230b285920 100644
--- a/src/tools/singlejar/BUILD
+++ b/src/tools/singlejar/BUILD
@@ -231,7 +231,7 @@ sh_test(
     args = [
         "src/test/shell",
         "$(location :singlejar)",
-        "$(location //external:jar)",
+        "../local_jdk/bin/jar",
     ],
     data = [
         ":singlejar",