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 3ede677..8818072 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 @@
     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 4b7adbc..4378934 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
@@ -139,7 +139,6 @@
     throw new ComparisonException("Cannot compare artifact with " + EvalUtils.getDataTypeName(o));
   }
 
-
   /** An object that can expand middleman artifacts. */
   public interface ArtifactExpander {
 
@@ -211,7 +210,6 @@
     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.
@@ -221,6 +219,7 @@
           + rootRel + " at " + path + " with root " + root);
     }
     this.rootRelativePath = rootRel.equals(execPath) ? execPath : rootRel;
+    this.execPath = externalfy(execPath);
     this.owner = Preconditions.checkNotNull(owner, path);
   }
 
@@ -369,7 +368,12 @@
     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();
   }
 
   /**
@@ -540,15 +544,9 @@
    * 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(
@@ -582,7 +580,23 @@
             + "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);
   }
 
   /*
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 7d187f9..7a30ab7 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
@@ -337,7 +337,7 @@
       dir = repo.getSecond();
     }
 
-    while (dir != null && !dir.equals(baseExecPath)) {
+    while (packageRoots != null && dir != null && !dir.equals(baseExecPath)) {
       Root sourceRoot = packageRoots.get(PackageIdentifier.create(repositoryName, dir));
       if (sourceRoot != null) {
         return sourceRoot;
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 59010e9..aad6e6e 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
@@ -15,16 +15,15 @@
 package com.google.devtools.build.lib.actions;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 import java.io.Serializable;
 import java.util.Objects;
-
 import javax.annotation.Nullable;
 
 /**
@@ -148,7 +147,11 @@
    * the empty fragment.
    */
   public PathFragment getExecPath() {
-    return execPath;
+    if (isMainRepo || isSourceRoot()) {
+      return execPath;
+    }
+    return new PathFragment(Label.EXTERNAL_PATH_PREFIX)
+        .getRelative(execRoot.getBaseName()).getRelative(execPath);
   }
 
   @SkylarkCallable(name = "path", structField = true,
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 1abc893..ed01807 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
@@ -142,7 +142,7 @@
    * <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 8a1fddc..7e93108 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
@@ -21,7 +21,6 @@
 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;
-
 import java.util.List;
 
 /**
@@ -54,8 +53,8 @@
     }
     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 +86,8 @@
     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 e2fbee9..8cf2d37 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
@@ -149,9 +149,7 @@
         : 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);
@@ -202,7 +200,7 @@
     } 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/LocationExpander.java b/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
index 225b3e1..fc30d6a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
@@ -332,7 +332,7 @@
 
     for (Artifact artifact : artifacts) {
       PathFragment execPath =
-          takeExecPath ? artifact.getExecPath() : artifact.getRootRelativePath();
+          takeExecPath ? artifact.getExecPath() : artifact.getRunfilesPath();
       if (execPath != null) {  // omit middlemen etc
         paths.add(execPath.getCallablePathString());
       }
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 656ca25..4efcf03 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
@@ -87,6 +87,7 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.StringUtil;
 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 java.util.ArrayList;
 import java.util.Collection;
@@ -592,6 +593,19 @@
    * thus guaranteeing that it never clashes with artifacts created by rules in other packages.
    */
   public Artifact getPackageRelativeArtifact(PathFragment relative, Root root) {
+    // TODO: other root types, is this never a main repo?
+    if (relative.startsWith(new PathFragment(Label.EXTERNAL_PATH_PREFIX))) {
+      // This is an external path, use a different root.
+      if (root.isSourceRoot()) {
+        root = Root.asSourceRoot(root.getPath().getRelative(relative.subFragment(0, 2)));
+      } else {
+        boolean isMainRepo = false;
+        Path newExecRoot = root.getExecRoot().getRelative(relative.subFragment(0, 2));
+        root = Root.asDerivedRoot(
+            newExecRoot, newExecRoot.getRelative(root.getExecPath()), isMainRepo);
+      }
+      relative = relative.subFragment(2, relative.segmentCount());
+    }
     return getDerivedArtifact(getPackageDirectory().getRelative(relative), root);
   }
 
@@ -610,7 +624,7 @@
    * {@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 8f171a3..2e62eae 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
@@ -427,6 +427,19 @@
     return newManifest;
   }
 
+  private static PathFragment getRootRelativePath(Artifact artifact) {
+    Preconditions.checkArgument(artifact != null);
+    if (artifact.getRoot().isMainRepo()) {
+      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.
    *
@@ -443,7 +456,7 @@
     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).
@@ -500,7 +513,7 @@
     // workspace.
     private boolean sawWorkspaceName;
 
-    public ManifestBuilder(
+    ManifestBuilder(
         PathFragment workspaceName, boolean legacyExternalRunfiles) {
       this.manifest = new HashMap<>();
       this.workspaceName = workspaceName;
@@ -511,19 +524,27 @@
     /**
      * 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());
         }
       }
     }
@@ -551,17 +572,20 @@
       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 b16a4a6..93e9e8d 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
@@ -1001,7 +1001,7 @@
   /**
    * 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.
@@ -1067,15 +1067,15 @@
 
     Root getRoot(
         RepositoryName repositoryName, String outputDirName, BlazeDirectories directories) {
-      // e.g., execroot/repo1
-      Path execRoot = directories.getExecRoot();
-      // e.g., execroot/repo1/bazel-out/config/bin
+      // 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/repo1]/bazel-out/config/bin]
+      // e.g., [[execroot/repo2]/bazel-out/config/bin]
       return INTERNER.intern(
           Root.asDerivedRoot(execRoot, outputDir.getRelative(name), repositoryName.isMain()));
     }
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 06fe867..f2179c6 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 @@
   @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 48bc11c..686dcd9 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
@@ -498,8 +498,14 @@
 
     // 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 44cf5f1..56c40bb 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 @@
   }
 
   /**
-   * 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 @@
     // 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 @@
         // 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 @@
       }
       // 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 @@
       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 0fb7a08..7e36491 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 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 = BlazeInterners.newWeakInterner();
 
@@ -336,12 +336,12 @@
    * it will returns an empty string.
    */
   @SkylarkCallable(name = "workspace_root", structField = true,
-      doc = "Returns the execution root for the workspace of this label, relative to the execroot. "
-      + "For instance:<br>"
+      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();
+    return packageIdentifier.getRepository().getPathUnderExecRoot().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 1e2e3d0..f8dda81 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
@@ -20,10 +20,8 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Canonicalizer;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 import java.io.Serializable;
 import java.util.Objects;
-
 import javax.annotation.concurrent.Immutable;
 
 /**
@@ -127,14 +125,6 @@
     return repository.getPathUnderExecRoot().getRelative(pkgName);
   }
 
-  /**
-   * Returns the runfiles/execRoot path for this repository (relative to the x.runfiles/main-repo/
-   * directory).
-   */
-  public PathFragment getRunfilesPath() {
-    return repository.getRunfilesPath().getRelative(pkgName);
-  }
-
   public PackageIdentifier makeAbsolute() {
     if (!repository.isDefault()) {
       return this;
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 ba0f6b4..5f1421f 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
@@ -22,7 +22,6 @@
 import com.google.devtools.build.lib.util.StringCanonicalizer;
 import com.google.devtools.build.lib.util.StringUtilities;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
@@ -214,8 +213,8 @@
   }
 
   /**
-   * 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 +223,6 @@
   }
 
   /**
-   * 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 c5a70c6..758b9dd 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 @@
       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/ideinfo/AndroidStudioInfoAspect.java b/src/main/java/com/google/devtools/build/lib/ideinfo/AndroidStudioInfoAspect.java
index e1f31fa..e3b351d 100644
--- a/src/main/java/com/google/devtools/build/lib/ideinfo/AndroidStudioInfoAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/ideinfo/AndroidStudioInfoAspect.java
@@ -654,7 +654,7 @@
 
   /** Returns whether this {@link Label} refers to an external repository. */
   private static boolean isExternal(Label label) {
-    return label.getWorkspaceRoot().startsWith("external");
+    return label.getWorkspaceRoot().startsWith(Label.EXTERNAL_PATH_PREFIX);
   }
 
   private JavaIdeInfo makeJavaIdeInfo(
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 45fa5ca..609a5c3 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
@@ -290,9 +290,10 @@
     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 d4a1583..b5aff73 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
@@ -27,7 +27,6 @@
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.rules.android.ResourceContainer.ResourceType;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 import java.util.Collection;
 import java.util.LinkedHashSet;
 
@@ -163,8 +162,7 @@
         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)) {
@@ -192,8 +190,7 @@
       Artifact lastFile = null;
       for (FileProvider target : targets) {
         for (Artifact file : target.getFilesToBuild()) {
-          PathFragment packageFragment = file.getArtifactOwner().getLabel()
-              .getPackageIdentifier().getSourceRoot();
+          PathFragment packageFragment = file.getArtifactOwner().getLabel().getPackageFragment();
           PathFragment packageRelativePath =
               file.getRootRelativePath().relativeTo(packageFragment);
           PathFragment resourceDir = findResourceDir(file);
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 597e5dd..e9ef999 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
@@ -414,7 +414,7 @@
   List<PathFragment> getSystemIncludeDirs() {
     List<PathFragment> result = new ArrayList<>();
     PackageIdentifier packageIdentifier = ruleContext.getLabel().getPackageIdentifier();
-    PathFragment packageFragment = packageIdentifier.getPathUnderExecRoot();
+    PathFragment pathUnderExecRoot = packageIdentifier.getPathUnderExecRoot();
     for (String includesAttr : ruleContext.attributes().get("includes", Type.STRING_LIST)) {
       includesAttr = ruleContext.expandMakeVariables("includes", includesAttr);
       if (includesAttr.startsWith("/")) {
@@ -422,10 +422,14 @@
             "ignoring invalid absolute path '" + includesAttr + "'");
         continue;
       }
-      PathFragment includesPath = packageFragment.getRelative(includesAttr).normalize();
-      if (!includesPath.isNormalized()) {
+      PathFragment includesPath = pathUnderExecRoot.getRelative(includesAttr).normalize();
+      // 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(
@@ -435,7 +439,7 @@
                 + "' resolves to the workspace root, which would allow this rule and all of its "
                 + "transitive dependents to include any file in your workspace. Please include only"
                 + " what you need");
-      } else if (!includesPath.startsWith(packageFragment)) {
+      } else if (!includesPath.startsWith(pathUnderExecRoot)) {
         ruleContext.attributeWarning(
             "includes",
             "'"
@@ -443,11 +447,14 @@
                 + "' resolves to '"
                 + includesPath
                 + "' not below the relative path of its package '"
-                + packageFragment
+                + pathUnderExecRoot
                 + "'. This will be an error in the future");
       }
       result.add(includesPath);
-      result.add(ruleContext.getConfiguration().getGenfilesFragment().getRelative(includesPath));
+      result.add(packageIdentifier.getRepository().getPathUnderExecRoot()
+          .getRelative(ruleContext.getConfiguration().getGenfilesFragment())
+          .getRelative(packageIdentifier.getPackageFragment())
+          .getRelative(includesAttr));
     }
     return result;
   }
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 11fcd47..faed073 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
@@ -1264,7 +1264,7 @@
         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/CppCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
index 6e75edd..4d3af44 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
@@ -477,13 +477,14 @@
         continue;
       }
       // 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()
-          || !PathFragment.EMPTY_FRAGMENT.getRelative(include).normalize().isNormalized()) {
+      if (include.isAbsolute() || !include.normalize().isNormalized()) {
         ruleContext.ruleError(
-            "The include path '" + include + "' references a path outside of the execution root.");
+            "The include path '" + originalInclude
+                + "' references a path outside of the execution root.");
       }
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
index 9893dfc..c0a7f69 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
@@ -525,10 +525,6 @@
     PathFragment defaultSysroot = toolchain.getBuiltinSysroot().length() == 0
         ? null
         : new PathFragment(toolchain.getBuiltinSysroot());
-    if ((defaultSysroot != null) && !defaultSysroot.isNormalized()) {
-      throw new IllegalArgumentException("The built-in sysroot '" + defaultSysroot
-          + "' is not normalized.");
-    }
 
     if ((cppOptions.libcTop != null) && (defaultSysroot == null)) {
       throw new InvalidConfigurationException("The selected toolchain " + toolchainIdentifier
@@ -1071,7 +1067,7 @@
     if (packageEndIndex != -1 && s.startsWith(PACKAGE_START)) {
       String packageString = s.substring(PACKAGE_START.length(), packageEndIndex);
       try {
-        pathPrefix = PackageIdentifier.parse(packageString).getSourceRoot();
+        pathPrefix = PackageIdentifier.parse(packageString).getPathUnderExecRoot();
       } catch (LabelSyntaxException e) {
         throw new InvalidConfigurationException("The package '" + packageString + "' is not valid");
       }
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 8541778..6b3604d 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
@@ -491,7 +491,7 @@
         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));
       }
@@ -500,7 +500,8 @@
     }
     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/CppLinkActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
index 2746c64..d1fed5d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
@@ -50,6 +50,7 @@
 import com.google.devtools.build.lib.rules.cpp.LinkerInputs.LibraryToLink;
 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 java.util.ArrayList;
 import java.util.Collection;
@@ -1544,8 +1545,9 @@
       for (LinkerInput input : linkerInputs) {
         if (input.getArtifactCategory() == ArtifactCategory.DYNAMIC_LIBRARY) {
           PathFragment libDir = input.getArtifact().getExecPath().getParentDirectory();
+          Path rootPath = input.getArtifact().getRoot().getExecRoot();
           Preconditions.checkState(
-              libDir.startsWith(solibDir),
+              rootPath.getRelative(libDir).startsWith(rootPath.getRelative(solibDir)),
               "Artifact '%s' is not under directory '%s'.",
               input.getArtifact(),
               solibDir);
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 5b59a06..847c1f5 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.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;
@@ -99,10 +100,10 @@
       return inputs.build();
     }
     List<Path> systemIncludePrefixes = permittedSystemIncludePrefixes;
-
     // Check inclusions.
     IncludeProblems problems = new IncludeProblems();
     for (Path execPath : depSet.getDependencies()) {
+      RepositoryName repositoryName = RepositoryName.MAIN;
       PathFragment execPathFragment = execPath.asFragment();
       if (execPathFragment.isAbsolute()) {
         // Absolute includes from system paths are ignored.
@@ -114,15 +115,24 @@
         // are, it's probably due to a non-hermetic #include, & we should stop
         // the build with an error.
         if (execPath.startsWith(execRoot)) {
-          execPathFragment = execPath.relativeTo(execRoot); // funky but tolerable path
-        } else {
-          problems.add(execPathFragment.getPathString());
-          continue;
+          // Funky but tolerable path.
+          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);
+      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);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java
index 8abcaef..fd77e0c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java
@@ -280,18 +280,7 @@
     }
 
     private void createProtoCompileAction(SupportData supportData, Collection<Artifact> outputs) {
-      String genfilesPath =
-          ruleContext
-              .getConfiguration()
-              .getGenfilesFragment()
-              .getRelative(
-                  ruleContext
-                      .getLabel()
-                      .getPackageIdentifier()
-                      .getRepository()
-                      .getPathUnderExecRoot())
-              .getPathString();
-
+      String genfilesPath = ruleContext.getBinOrGenfilesDirectory().getExecPathString();
       ImmutableList.Builder<ToolchainInvocation> invocations = ImmutableList.builder();
       invocations.add(
           new ToolchainInvocation("C++", checkNotNull(getProtoToolchainProvider()), genfilesPath));
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java b/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java
index a81a38f..e4cf0da 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genrule/GenRuleBase.java
@@ -34,6 +34,7 @@
 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;
@@ -336,9 +337,9 @@
           } 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 if (JDK_MAKE_VARIABLE.matcher("$(" + name + ")").find()) {
         return new ConfigurationMakeVariableContext(
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 3447934..06f4def 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
@@ -504,7 +504,7 @@
     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 9195380..d4bbad6 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
@@ -69,7 +69,12 @@
   @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);
+    }
   }
 
   /**
@@ -83,17 +88,6 @@
     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 7ed45de..c8d0fd7 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
@@ -235,7 +235,7 @@
     if (javaBase.getPackageIdentifier().getRepository().isDefault()) {
       return javaBase.getPackageFragment();
     }
-    return javaBase.getPackageIdentifier().getSourceRoot();
+    return javaBase.getPackageIdentifier().getPathUnderExecRoot();
   }
 
   private static Jvm createLegacy(String javaHome) throws InvalidConfigurationException {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java
index fd1f95f..64594ad 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java
@@ -340,18 +340,7 @@
     public Iterable<String> argv() {
       ImmutableList.Builder<String> builder = ImmutableList.builder();
       for (Artifact artifact : transitiveImports) {
-        builder.add(
-            "-I"
-                + artifact
-                    .getRootRelativePath()
-                    .relativeTo(
-                        artifact
-                            .getOwnerLabel()
-                            .getPackageIdentifier()
-                            .getRepository()
-                            .getPathUnderExecRoot())
-                + "="
-                + artifact.getExecPathString());
+        builder.add("-I" + artifact.getRootRelativePath() + "=" + artifact.getExecPathString());
       }
       if (protosInDirectDependencies != null) {
         ArrayList<String> rootRelativePaths = new ArrayList<>();
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 44a05f0..13f9cf3 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
@@ -182,13 +182,12 @@
     ImmutableMap<String, String> spawnEnvironment =
         StandaloneSpawnStrategy.locallyDeterminedEnv(execRoot, productName, spawn.getEnvironment());
 
-    Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment());
-
     Path runUnderPath = getRunUnderPath(spawn);
 
     HardlinkedExecRoot hardlinkedExecRoot =
         new HardlinkedExecRoot(execRoot, sandboxPath, sandboxExecRoot, errWriter);
     ImmutableSet<PathFragment> outputs = SandboxHelpers.getOutputFiles(spawn);
+    Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment(), outputs);
     try {
       hardlinkedExecRoot.createFileSystem(
           getMounts(spawn, actionExecutionContext), outputs, writableDirs);
@@ -205,7 +204,7 @@
         new DarwinSandboxRunner(
             sandboxPath,
             sandboxExecRoot,
-            getWritableDirs(sandboxExecRoot, spawnEnvironment),
+            getWritableDirs(sandboxExecRoot, spawnEnvironment, outputs),
             getInaccessiblePaths(),
             runUnderPath,
             verboseFailures);
@@ -236,11 +235,12 @@
   }
 
   @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 e2a81c8..3a7f055 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
@@ -112,10 +112,9 @@
     Path sandboxExecRoot = sandboxPath.getRelative("execroot").getRelative(execRoot.getBaseName());
     Path sandboxTempDir = sandboxPath.getRelative("tmp");
 
-    Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment());
-
     SymlinkedExecRoot symlinkedExecRoot = new SymlinkedExecRoot(sandboxExecRoot);
     ImmutableSet<PathFragment> outputs = SandboxHelpers.getOutputFiles(spawn);
+    Set<Path> writableDirs = getWritableDirs(sandboxExecRoot, spawn.getEnvironment(), outputs);
     try {
       symlinkedExecRoot.createFileSystem(
           getMounts(spawn, actionExecutionContext), outputs, writableDirs);
@@ -124,7 +123,8 @@
       throw new UserExecException("I/O error during sandboxed execution", e);
     }
 
-    SandboxRunner runner = getSandboxRunner(spawn, sandboxPath, sandboxExecRoot, sandboxTempDir);
+    SandboxRunner runner = getSandboxRunner(
+        spawn, sandboxPath, sandboxExecRoot, sandboxTempDir, outputs);
     try {
       runSpawn(
           spawn,
@@ -152,7 +152,8 @@
   }
 
   private SandboxRunner getSandboxRunner(
-      Spawn spawn, Path sandboxPath, Path sandboxExecRoot, Path sandboxTempDir)
+      Spawn spawn, Path sandboxPath, Path sandboxExecRoot, Path sandboxTempDir,
+      ImmutableSet<PathFragment> outputs)
       throws UserExecException {
     if (fullySupported) {
       return new LinuxSandboxRunner(
@@ -160,7 +161,7 @@
           sandboxPath,
           sandboxExecRoot,
           sandboxTempDir,
-          getWritableDirs(sandboxExecRoot, spawn.getEnvironment()),
+          getWritableDirs(sandboxExecRoot, spawn.getEnvironment(), outputs),
           getInaccessiblePaths(),
           getTmpfsPaths(),
           getReadOnlyBindMounts(blazeDirs, sandboxExecRoot),
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 ce917f3..4af3c5d 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
@@ -115,12 +115,16 @@
   }
 
   /** 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 bc60eae..78e050a 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
@@ -92,7 +92,7 @@
       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/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 46b2b9d..e587f8f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -1443,7 +1443,7 @@
       EventHandler eventHandler, Label label, BuildConfiguration configuration) {
     if (memoizingEvaluator.getExistingValueForTesting(
         PrecomputedValue.WORKSPACE_STATUS_KEY.getKeyForTesting()) == null) {
-      injectWorkspaceStatusData(label.getWorkspaceRoot());
+      injectWorkspaceStatusData(label.getPackageIdentifier().getRepository().strippedName());
     }
 
     Dependency dep;
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 ceda171..57f19cf 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 @@
   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/main/tools/linux-sandbox-pid1.cc b/src/main/tools/linux-sandbox-pid1.cc
index 2aba127..d8ff454 100644
--- a/src/main/tools/linux-sandbox-pid1.cc
+++ b/src/main/tools/linux-sandbox-pid1.cc
@@ -297,7 +297,8 @@
 static bool ShouldBeWritable(char *mnt_dir) {
   mnt_dir += strlen(opt.sandbox_root_dir);
 
-  if (strcmp(mnt_dir, opt.working_dir) == 0) {
+  char *working_parent = dirname(strdupa(opt.working_dir));
+  if (strncmp(working_parent, mnt_dir, strlen(working_parent)) == 0) {
     return true;
   }
 
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 f6d1509..2c18fd3 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,15 +21,12 @@
 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 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;
@@ -321,37 +318,36 @@
 
   @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);
@@ -362,31 +358,6 @@
     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();
-  }
-
   @Test
   public void testMergeWithSymlinks() {
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
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 0312811..cecd220 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.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;
@@ -198,6 +199,8 @@
     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/bazel/rules/android/AndroidSdkRepositoryTest.java b/src/test/java/com/google/devtools/build/lib/bazel/rules/android/AndroidSdkRepositoryTest.java
index 0f33d2d..dc24118 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/rules/android/AndroidSdkRepositoryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/rules/android/AndroidSdkRepositoryTest.java
@@ -111,9 +111,9 @@
         androidDevicesFilegroupTarget.getProvider(FilesToRunProvider.class).getFilesToRun();
     assertThat(artifactsToStrings(systemImagesDirectories))
         .containsExactly(
-            "src external/androidsdk/system-images/android-25/default/armeabi-v7a",
-            "src external/androidsdk/system-images/android-24/google_apis/x86",
-            "src external/androidsdk/system-images/android-24/google_apis/x86_64");
+            "src system-images/android-25/default/armeabi-v7a",
+            "src system-images/android-24/google_apis/x86",
+            "src system-images/android-24/google_apis/x86_64");
   }
 
   @Test
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 d86d2be..5e0cda6 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.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 @@
   @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 @@
 
     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 @@
             .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 @@
   @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 @@
             .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 @@
             .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/LabelTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
index 3766a76..9fe683c 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
@@ -448,6 +448,6 @@
     Label label = Label.parseAbsolute("//bar/baz");
     assertThat(label.getWorkspaceRoot()).isEmpty();
     label = Label.parseAbsolute("@repo//bar/baz");
-    assertThat(label.getWorkspaceRoot()).isEqualTo("external/repo");
+    assertThat(label.getWorkspaceRoot()).isEqualTo("../repo");
   }
 }
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 a19ef4b..42642b8 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,12 +19,10 @@
 import static org.junit.Assert.assertSame;
 
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 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;
@@ -39,8 +37,7 @@
     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 @@
   }
 
   @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 9a39bbf..24a1917 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 @@
   }
 
   @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/ideinfo/AndroidStudioInfoAspectTest.java b/src/test/java/com/google/devtools/build/lib/ideinfo/AndroidStudioInfoAspectTest.java
index 4a80886..d317977 100644
--- a/src/test/java/com/google/devtools/build/lib/ideinfo/AndroidStudioInfoAspectTest.java
+++ b/src/test/java/com/google/devtools/build/lib/ideinfo/AndroidStudioInfoAspectTest.java
@@ -1814,7 +1814,9 @@
   public void testExternalRootCorrectlyIdentified() throws Exception {
     ArtifactLocation location =
         AndroidStudioInfoAspect.makeArtifactLocation(
-            Root.asSourceRoot(outputBase, false), new PathFragment("external/foo/bar.jar"), true);
+            Root.asSourceRoot(outputBase.getRelative("external/foo"), false),
+            new PathFragment("bar.jar"),
+            true);
     assertThat(location.getIsExternal()).isTrue();
   }
 
@@ -1853,13 +1855,13 @@
 
     TargetIdeInfo targetInfo = getTargetIdeInfoAndVerifyLabel("@r//:junit", targetIdeInfos);
     assertThat(targetInfo.getBuildFileArtifactLocation().getIsExternal()).isTrue();
-    assertThat(targetInfo.getBuildFileArtifactLocation().getRelativePath()).startsWith("external");
+    assertThat(targetInfo.getBuildFileArtifactLocation().getRelativePath()).isEqualTo("BUILD");
 
     JavaIdeInfo javaInfo = targetInfo.getJavaIdeInfo();
     assertThat(javaInfo.getJarsList()).hasSize(1);
     ArtifactLocation jar = javaInfo.getJars(0).getJar();
     assertThat(jar.getIsSource()).isTrue();
     assertThat(jar.getIsExternal()).isTrue();
-    assertThat(jar.getRelativePath()).isEqualTo("external/r/junit.jar");
+    assertThat(jar.getRelativePath()).isEqualTo("junit.jar");
   }
 }
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 466e061..25aa5b2 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
@@ -708,7 +708,7 @@
     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 0765419..bda5f6c 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
@@ -1050,8 +1050,8 @@
   @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/rules/cpp/proto/CcProtoLibraryTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoLibraryTest.java
index b138480..5951987 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoLibraryTest.java
@@ -166,7 +166,7 @@
     assertThat(protoCompileAction.getArguments())
         .contains(
             String.format(
-                "--cpp_out=%s/external/bla",
+                "--cpp_out=../bla/%s",
                 getTargetConfiguration().getGenfilesFragment().toString()));
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java b/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java
index 2bb3800..788488e 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilderTest.java
@@ -34,6 +34,7 @@
 import com.google.devtools.build.lib.rules.proto.ProtoCompileActionBuilder.ProtoCommandLineArgv;
 import com.google.devtools.build.lib.rules.proto.ProtoCompileActionBuilder.ToolchainInvocation;
 import com.google.devtools.build.lib.util.LazyString;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -302,12 +303,24 @@
    */
   @Test
   public void testIncludeMapsOfExternalFiles() throws Exception {
+    Label externalLabel = Label.parseAbsolute("@bla//foo:bar");
+    Root externalRoot = Root.asSourceRoot(
+        root.getPath().getRelative(
+            externalLabel.getPackageIdentifier().getRepository().getSourceRoot()),
+        false);
+    PathFragment externalPath = new PathFragment("foo/bar.proto");
+    System.out.println("Root: " + externalRoot + " path: " + externalPath);
+    Artifact externalArtifact = new Artifact(
+        externalRoot.getPath().getRelative(externalPath),
+        externalRoot,
+        externalRoot.getExecPath().getRelative(externalPath),
+        new LabelArtifactOwner(externalLabel));
     assertThat(
             new ProtoCommandLineArgv(
                     null /* protosInDirectoDependencies */,
-                    ImmutableList.of(artifact("@bla//foo:bar", "external/bla/foo/bar.proto")))
+                    ImmutableList.of(externalArtifact))
                 .argv())
-        .containsExactly("-Ifoo/bar.proto=external/bla/foo/bar.proto");
+        .containsExactly("-Ifoo/bar.proto=../bla/foo/bar.proto");
   }
 
   private Artifact artifact(String ownerLabel, String path) {
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 578db1b..35681ee 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
@@ -348,7 +348,7 @@
     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 64ede46..815b4f0 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
@@ -68,7 +68,7 @@
 
   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 c4efbf0..e266097 100755
--- a/src/test/shell/bazel/bazel_rules_test.sh
+++ b/src/test/shell/bazel/bazel_rules_test.sh
@@ -303,8 +303,8 @@
 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_genrule_toolchain_dependency {
diff --git a/src/test/shell/bazel/bazel_sandboxing_test.sh b/src/test/shell/bazel/bazel_sandboxing_test.sh
index c5e75f0..4d009b8 100755
--- a/src/test/shell/bazel/bazel_sandboxing_test.sh
+++ b/src/test/shell/bazel/bazel_sandboxing_test.sh
@@ -81,8 +81,8 @@
    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(
@@ -551,13 +551,14 @@
 
   # Replace the target_root_placeholder with the actual target_root
   sed -i "s|target_root_placeholder|$target_root|g" downloaded_toolchain/CROSSTOOL
+  sed -i "s|external/|../|g" downloaded_toolchain/CROSSTOOL
 
   # Prepare the bazel command flags
   flags="--crosstool_top=@x86_64_unknown_linux_gnu//:toolchain --verbose_failures --spawn_strategy=sandboxed"
   flags="${flags} --sandbox_add_mount_pair=${source}:${target}"
 
   # Execute the bazel build command without creating the target. Should fail.
-  bazel clean --expunge &> $TEST_log
+  rm -rf "$(dirname $target)"
   bazel build $flags //:hello-world &> $TEST_log && fail "Should fail"
   expect_log "Bazel only supports bind mounting on top of existing files/directories."
 
diff --git a/src/test/shell/bazel/external_correctness_test.sh b/src/test/shell/bazel/external_correctness_test.sh
index ea8ad05..1c311b5 100755
--- a/src/test/shell/bazel/external_correctness_test.sh
+++ b/src/test/shell/bazel/external_correctness_test.sh
@@ -142,8 +142,8 @@
 )
 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() {
@@ -202,7 +202,8 @@
 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() {
@@ -277,16 +278,16 @@
 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() {
@@ -308,16 +309,17 @@
 )
 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 21d5c0d..0e46ff5 100755
--- a/src/test/shell/bazel/external_integration_test.sh
+++ b/src/test/shell/bazel/external_integration_test.sh
@@ -146,7 +146,7 @@
   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
   case "${PLATFORM}" in
@@ -641,7 +641,8 @@
 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() {
@@ -670,7 +671,8 @@
 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() {
@@ -699,7 +701,8 @@
 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() {
@@ -726,14 +729,16 @@
 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() {
@@ -771,13 +776,14 @@
 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_android_sdk_basic_load() {
diff --git a/src/test/shell/bazel/git_repository_test.sh b/src/test/shell/bazel/git_repository_test.sh
index 033a683..c340d1c 100755
--- a/src/test/shell/bazel/git_repository_test.sh
+++ b/src/test/shell/bazel/git_repository_test.sh
@@ -27,6 +27,8 @@
 # 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
@@ -268,17 +270,17 @@
 
   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
@@ -288,7 +290,7 @@
 
   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"
 
 }
 
@@ -301,9 +303,10 @@
 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')
@@ -312,7 +315,7 @@
 
   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() {
@@ -323,10 +326,11 @@
 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')
@@ -335,9 +339,9 @@
 
   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
@@ -352,7 +356,7 @@
   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 8f77090..36f90be 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -492,9 +492,9 @@
     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(
@@ -505,7 +505,8 @@
 )
 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() {
@@ -542,7 +543,8 @@
 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() {
@@ -893,7 +895,8 @@
 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 0b79353..a3a9006 100755
--- a/src/test/shell/bazel/skylark_repository_test.sh
+++ b/src/test/shell/bazel/skylark_repository_test.sh
@@ -314,7 +314,8 @@
   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/testdata/bazel_toolchain_test_data/tools/arm_compiler/CROSSTOOL b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/CROSSTOOL
index bbd9c4d..1cffb1e 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/CROSSTOOL
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/CROSSTOOL
@@ -47,26 +47,26 @@
   tool_path { name: "objdump" path: "linaro_linux_gcc/arm-linux-gnueabihf-objdump" }
   tool_path { name: "strip" path: "linaro_linux_gcc/arm-linux-gnueabihf-strip" }
 
-  compiler_flag: "--sysroot=external/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc"
+  compiler_flag: "--sysroot=../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc"
   compiler_flag: "-mfloat-abi=hard"
 
   compiler_flag: "-nostdinc"
   compiler_flag: "-isystem"
-  compiler_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/lib/gcc/arm-linux-gnueabihf/5.3.1/include"
+  compiler_flag: "../org_linaro_components_toolchain_gcc_5_3_1/lib/gcc/arm-linux-gnueabihf/5.3.1/include"
   compiler_flag: "-isystem"
-  compiler_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/usr/include"
+  compiler_flag: "../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/usr/include"
   compiler_flag: "-isystem"
-  compiler_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/lib/gcc/arm-linux-gnueabihf/5.3.1/include-fixed"
+  compiler_flag: "../org_linaro_components_toolchain_gcc_5_3_1/lib/gcc/arm-linux-gnueabihf/5.3.1/include-fixed"
   compiler_flag: "-isystem"
-  compiler_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/usr/include"
+  compiler_flag: "../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/usr/include"
   cxx_flag: "-isystem"
-  cxx_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/include/c++/5.3.1/arm-linux-gnueabihf"
+  cxx_flag: "../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/include/c++/5.3.1/arm-linux-gnueabihf"
   cxx_flag: "-isystem"
-  cxx_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/include/c++/5.3.1"
+  cxx_flag: "../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/include/c++/5.3.1"
   cxx_flag: "-isystem"
-  cxx_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/include/c++/5.3.1/arm-linux-gnueabihf"
+  cxx_flag: "../org_linaro_components_toolchain_gcc_5_3_1/include/c++/5.3.1/arm-linux-gnueabihf"
   cxx_flag: "-isystem"
-  cxx_flag: "external/org_linaro_components_toolchain_gcc_5_3_1/include/c++/5.3.1"
+  cxx_flag: "../org_linaro_components_toolchain_gcc_5_3_1/include/c++/5.3.1"
 
   cxx_builtin_include_directory: "%package(@org_linaro_components_toolchain_gcc_5_3_1//include)%"
   cxx_builtin_include_directory: "%package(@org_linaro_components_toolchain_gcc_5_3_1//arm-linux-gnueabihf/libc/usr/include)%"
@@ -79,16 +79,16 @@
   cxx_builtin_include_directory: "%package(@org_linaro_components_toolchain_gcc_5_3_1//lib/gcc/arm-linux-gnueabihf/5.3.1/include-fixed)%"
   cxx_builtin_include_directory: "%package(@org_linaro_components_toolchain_gcc_5_3_1//arm-linux-gnueabihf/include)%/c++/5.3.1"
 
-  linker_flag: "--sysroot=external/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc"
+  linker_flag: "--sysroot=../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc"
   linker_flag: "-lstdc++"
   linker_flag: "-latomic"
   linker_flag: "-lm"
   linker_flag: "-lpthread"
   linker_flag: "-Ltools/arm_compiler/linaro_linux_gcc/clang_more_libs"
-  linker_flag: "-Lexternal/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/lib"
-  linker_flag: "-Lexternal/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/lib"
-  linker_flag: "-Lexternal/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/usr/lib"
-  linker_flag: "-Bexternal/org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/bin"
+  linker_flag: "-L../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/lib"
+  linker_flag: "-L../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/lib"
+  linker_flag: "-L../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/libc/usr/lib"
+  linker_flag: "-B../org_linaro_components_toolchain_gcc_5_3_1/arm-linux-gnueabihf/bin"
   linker_flag: "-Wl,--dynamic-linker=/lib/ld-linux-armhf.so.3"
 
   # Anticipated future default.
@@ -237,4 +237,3 @@
   }
   linking_mode_flags { mode: DYNAMIC }
 }
-
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ar b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ar
index c84ed27..d8006fc 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ar
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ar
@@ -1,5 +1,5 @@
 #!/bin/bash --norc
 
 exec -a arm-linux-gnueabihf-ar \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-ar \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-ar \
     "$@"
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-as b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-as
index 7738e76..1ad2650 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-as
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-as
@@ -1,5 +1,5 @@
 #!/bin/bash --norc
 
 exec -a arm-linux-gnueabihf-as \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-as \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-as \
     "$@"
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-gcc b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-gcc
index ffc3967..65106f5 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-gcc
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-gcc
@@ -1,6 +1,6 @@
 #!/bin/bash --norc
 
-PATH="external/org_linaro_components_toolchain_gcc_5_3_1/libexec/gcc/arm-linux-gnueabihf/4.9.3:$PATH" \
+PATH="../org_linaro_components_toolchain_gcc_5_3_1/libexec/gcc/arm-linux-gnueabihf/4.9.3:$PATH" \
     exec \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-gcc \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-gcc \
     "$@"
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ld b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ld
index b56a1c1..d1483f4 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ld
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-ld
@@ -1,5 +1,5 @@
 #!/bin/bash --norc
 
 exec -a arm-linux-gnueabihf-ld \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-ld \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-ld \
     "$@"
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-nm b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-nm
index c802e5b..660a824 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-nm
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-nm
@@ -1,5 +1,5 @@
 #!/bin/bash --norc
 
 exec -a arm-linux-gnueabihf-nm \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-nm \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-nm \
     "$@"
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objcopy b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objcopy
index 503184b..535de26 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objcopy
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objcopy
@@ -1,5 +1,5 @@
 #!/bin/bash --norc
 
 exec -a arm-linux-gnueabihf-objcopy \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-objcopy \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-objcopy \
     "$@"
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objdump b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objdump
index 5c9667a..bcebbae 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objdump
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-objdump
@@ -1,5 +1,5 @@
 #!/bin/bash --norc
 
 exec -a arm-linux-gnueabihf-objdump \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-objdump \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-objdump \
     "$@"
diff --git a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-strip b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-strip
index 9e71cbf..a2f3829 100644
--- a/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-strip
+++ b/src/test/shell/bazel/testdata/bazel_toolchain_test_data/tools/arm_compiler/linaro_linux_gcc/arm-linux-gnueabihf-strip
@@ -1,5 +1,5 @@
 #!/bin/bash --norc
 
 exec -a arm-linux-gnueabihf-strip \
-    external/org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-strip \
+    ../org_linaro_components_toolchain_gcc_5_3_1/bin/arm-linux-gnueabihf-strip \
     "$@"
diff --git a/src/test/shell/bazel/workspace_test.sh b/src/test/shell/bazel/workspace_test.sh
index a319cbb..c1b6150 100755
--- a/src/test/shell/bazel/workspace_test.sh
+++ b/src/test/shell/bazel/workspace_test.sh
@@ -49,7 +49,8 @@
 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(
@@ -59,7 +60,7 @@
 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/test/shell/integration/java_integration_test.sh b/src/test/shell/integration/java_integration_test.sh
index e86e90a..907dbf6 100755
--- a/src/test/shell/integration/java_integration_test.sh
+++ b/src/test/shell/integration/java_integration_test.sh
@@ -636,6 +636,13 @@
         '--g=$(JAVABASE)',
     ],
 )
+
+genrule(
+    name = "javabase",
+    srcs = [],
+    cmd = "echo $(JAVABASE) > $@",
+    outs = ["javabase.out"],
+)
 EOF
 
   cat >$pkg/java/com/google/jvmflags/Foo.java <<EOF
@@ -643,8 +650,9 @@
 public class Foo { public static void main(String[] args) {} }
 EOF
 
-  bazel build //$pkg/java/com/google/jvmflags:foo || fail "build failed"
+  bazel build //$pkg/java/com/google/jvmflags:all || fail "build failed"
 
+  javabase="$(cat ${PRODUCT_NAME}-genfiles/$pkg/java/com/google/jvmflags/javabase.out)"
   STUBSCRIPT=${PRODUCT_NAME}-bin/$pkg/java/com/google/jvmflags/foo
   [ -e $STUBSCRIPT ] || fail "$STUBSCRIPT not found"
 
@@ -655,7 +663,7 @@
       " --d=\"double_double\" " \
       ' --e=no_quotes ' \
       ' --f=stuff$to"escape\\ ' \
-      " --g=${runfiles_relative_javabase}" \
+      " --g=${javabase}" \
       ; do
     # NOTE: don't test the full path of the JDK, it's architecture-dependent.
     assert_contains $flag $STUBSCRIPT
diff --git a/tools/build_rules/test_rules.bzl b/tools/build_rules/test_rules.bzl
index ef93d62..d4ede3e 100644
--- a/tools/build_rules/test_rules.bzl
+++ b/tools/build_rules/test_rules.bzl
@@ -188,8 +188,11 @@
     prefix_parts = []
 
     if rule_.label.workspace_root:
-      # Create a prefix that is correctly relative to the output of this rule.
-      prefix_parts = ["..", strip_prefix("external/", rule_.label.workspace_root)]
+      if rule_.label.workspace_root.startswith(".."):
+        prefix_parts = [rule_.label.workspace_root]
+      else:
+        # Create a prefix that is correctly relative to the output of this rule.
+        prefix_parts = ["..", strip_prefix("external/", rule_.label.workspace_root)]
 
     if rule_.label.package:
       prefix_parts.append(rule_.label.package)