Move the runfiles for external repositories to under the x.runfiles/ directory

This also sets the Bazel workspace name to io_bazel_source.

Fixes #848.

Relevant to #1116, #1124,

RELNOTES[INC]: All repositories are now directly under the x.runfiles directory in the runfiles tree (previously, external repositories were at x.runfiles/main-repo/external/other-repo. This simplifies handling remote repository runfiles considerably, but will break existing references to external repository runfiles.
---
Furthermore, if a Bazel project does not provide a workspace name in the WORKSPACE file, Bazel will now default to using __main__ as the workspace name (instead of "", as previously). The repository's runfiles will appear under x.runfiles/__main__/.

--
MOS_MIGRATED_REVID=120224534

62 files changed, 623 insertions, 328 deletions

diff --git a/WORKSPACE b/WORKSPACE
index 05c5117286..df44900387 100644
--- a/WORKSPACE
+++ b/WORKSPACE
@@ -1,3 +1,5 @@
+workspace(name = "io_bazel")
+
 load("/tools/build_defs/jsonnet/jsonnet", "jsonnet_repositories")
 load("/tools/build_rules/rust/rust", "rust_repositories")
 
diff --git a/examples/java-skylark/src/main/java/com/example/myproject/Greeter.java b/examples/java-skylark/src/main/java/com/example/myproject/Greeter.java
index b4d8516dc9..143a71dfd4 100644
--- a/examples/java-skylark/src/main/java/com/example/myproject/Greeter.java
+++ b/examples/java-skylark/src/main/java/com/example/myproject/Greeter.java
@@ -29,7 +29,8 @@ public class Greeter {
   public void hello(String obj) throws Exception {
     String greeting = "Hello";
     try {
-      String greetFile = getRunfiles() + "/examples/java-skylark/src/main/resources/greeting.txt";
+      String greetFile = getRunfiles()
+          + "/io_bazel/examples/java-skylark/src/main/resources/greeting.txt";
       greeting = convertStreamToString(new FileInputStream(greetFile));
     } catch (FileNotFoundException e) {
       // use default.
diff --git a/examples/shell/bin.sh b/examples/shell/bin.sh
index 02345b0157..5b51ccf06c 100755
--- a/examples/shell/bin.sh
+++ b/examples/shell/bin.sh
@@ -18,9 +18,8 @@ set -eu
 
 # This allows the script to be both a binary and a library script. If our binary has defined
 # RUNFILES then we use it, otherwise we look for our own runfiles.
-RUNFILES=${RUNFILES:-$0.runfiles}
+RUNFILES=${RUNFILES:-$0.runfiles/io_bazel}
 
 source "${RUNFILES}/examples/shell/lib.sh"
 
 showfile
-
diff --git a/examples/shell/lib.sh b/examples/shell/lib.sh
index 979a2c6b67..495ef3d422 100755
--- a/examples/shell/lib.sh
+++ b/examples/shell/lib.sh
@@ -18,9 +18,8 @@ set -eu
 
 # This allows the script to be both a binary and a library script. If our binary has defined
 # RUNFILES then we use it, otherwise we look for our own runfiles.
-RUNFILES=${RUNFILES:-$0.runfiles}
+RUNFILES=${RUNFILES:-$0.runfiles/io_bazel}
 
 function showfile {
   cat "${RUNFILES}/examples/shell/data/file.txt"
 }
-
diff --git a/scripts/bash_completion_test.sh b/scripts/bash_completion_test.sh
index 3eed6fbc86..82a0fa3411 100755
--- a/scripts/bash_completion_test.sh
+++ b/scripts/bash_completion_test.sh
@@ -23,7 +23,7 @@ source ${DIR}/testenv.sh || { echo "testenv.sh not found!" >&2; exit 1; }
 : ${COMMAND_ALIASES:=bazel}
 
 # Completion script
-: ${COMPLETION:="$TEST_SRCDIR/scripts/bazel-complete.bash"}
+: ${COMPLETION:="$TEST_SRCDIR/io_bazel/scripts/bazel-complete.bash"}
 
 # Set this to test completion with package path (if enabled)
 : ${PACKAGE_PATH_PREFIX:=}
diff --git a/scripts/testenv.sh b/scripts/testenv.sh
index c45ee6a5e5..25fa4ebfd7 100755
--- a/scripts/testenv.sh
+++ b/scripts/testenv.sh
@@ -19,8 +19,8 @@
 [ -z "$TEST_SRCDIR" ] && { echo "TEST_SRCDIR not set!" >&2; exit 1; }
 
 # Load the unit-testing framework
-source "${TEST_SRCDIR}/src/test/shell/unittest.bash" || \
-  { echo "Failed to source unittest.bash" >&2; exit 1; }
+source "${TEST_SRCDIR}/io_bazel/src/test/shell/unittest.bash" \
+  || { echo "Failed to source unittest.bash" >&2; exit 1; }
 
 set_up() {
   mkdir -p $TEST_TMPDIR/workspace
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 22929e225a..790cfbc068 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
@@ -14,6 +14,7 @@ genrule(
     outs = ["JavacBootclasspathLocations.java"],
     cmd = """
 declare -a paths=($(SRCS)) && paths=($${paths[@]#$(GENDIR)/}) &&
+paths=($$(echo $${paths[@]} | sed s_external/__g)) &&
 IFS=: &&
 cat > $@ <<EOF
 package com.google.devtools.build.java.bazel;
@@ -44,7 +45,7 @@ genrule(
     srcs = ["//third_party/java/jdk/langtools:javac_jar"],
     outs = ["JavaLangtoolsLocation.java"],
     cmd = """
-path=$(SRCS) && path=$${path#$(GENDIR)/} &&
+path=$(SRCS) && path=$${path#$(GENDIR)/} && path="io_bazel/$${path}" &&
 cat > $@ <<EOF
 package com.google.devtools.build.java.bazel;
 public class JavaLangtoolsLocation {
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 f28683b451..9a132faa08 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
@@ -498,6 +498,21 @@ public class Artifact
   }
 
   /**
+   * For targets in external repositories, this returns the path the artifact live at in the
+   * runfiles tree. For local targets, it returns the rootRelativePath.
+   */
+  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;
+  }
+
+  /**
    * Returns this.getExecPath().getPathString().
    */
   @Override
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 5c14ec2dda..425a3eea30 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
@@ -20,6 +20,7 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
+import com.google.devtools.build.lib.cmdline.Label;
 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;
@@ -40,7 +41,6 @@ import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.Collections;
 import java.util.HashMap;
-import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.Map.Entry;
@@ -139,6 +139,11 @@ public final class Runfiles {
     public Artifact getArtifact() {
       return artifact;
     }
+
+    @Override
+    public String toString() {
+      return path + " -> " + artifact.getRunfilesPath();
+    }
   }
 
   // It is important to declare this *after* the DUMMY_SYMLINK_EXPANDER to avoid NPEs
@@ -151,7 +156,7 @@ public final class Runfiles {
    *
    * <p>This is either set to the workspace name, or is empty.
    */
-  private final String suffix;
+  private final PathFragment suffix;
 
   /**
    * The artifacts that should *always* be present in the runfiles directory. These are
@@ -203,7 +208,7 @@ public final class Runfiles {
    *
    * <p>If no EventHandler is available, all values are treated as IGNORE.
    */
-  public static enum ConflictPolicy {
+  public enum ConflictPolicy {
     IGNORE,
     WARN,
     ERROR,
@@ -262,13 +267,16 @@ public final class Runfiles {
    */
   private final NestedSet<PruningManifest> pruningManifests;
 
-  private Runfiles(String suffix,
+  private final boolean legacyRepositoryStructure;
+
+  private Runfiles(PathFragment suffix,
       NestedSet<Artifact> artifacts,
       NestedSet<SymlinkEntry> symlinks,
       NestedSet<SymlinkEntry> rootSymlinks,
       NestedSet<PruningManifest> pruningManifests,
       EmptyFilesSupplier emptyFilesSupplier,
-      ConflictPolicy conflictPolicy) {
+      ConflictPolicy conflictPolicy,
+      boolean legacyRepositoryStructure) {
     this.suffix = suffix;
     this.unconditionalArtifacts = Preconditions.checkNotNull(artifacts);
     this.symlinks = Preconditions.checkNotNull(symlinks);
@@ -276,12 +284,13 @@ public final class Runfiles {
     this.pruningManifests = Preconditions.checkNotNull(pruningManifests);
     this.emptyFilesSupplier = Preconditions.checkNotNull(emptyFilesSupplier);
     this.conflictPolicy = conflictPolicy;
+    this.legacyRepositoryStructure = legacyRepositoryStructure;
   }
 
   /**
    * Returns the runfiles' suffix.
    */
-  public String getSuffix() {
+  public PathFragment getSuffix() {
     return suffix;
   }
 
@@ -352,54 +361,10 @@ public final class Runfiles {
 
   /**
    * Returns the symlinks as a map from path fragment to artifact.
-   *
-   * @param checker If not null, check for conflicts using this checker.
    */
-  public Map<PathFragment, Artifact> getSymlinksAsMap(@Nullable ConflictChecker checker) {
-    return entriesToMap(symlinks, checker);
-  }
-
-  /**
-   * @param eventHandler Used for throwing an error if we have an obscuring runlink.
-   *                 May be null, in which case obscuring symlinks are silently discarded.
-   * @param location Location for reporter. Ignored if reporter is null.
-   * @param workingManifest Manifest to be checked for obscuring symlinks.
-   * @return map of source file names mapped to their location on disk.
-   */
-  @VisibleForTesting
-  static Map<PathFragment, Artifact> filterListForObscuringSymlinks(
-      EventHandler eventHandler, Location location, Map<PathFragment, Artifact> workingManifest) {
-    Map<PathFragment, Artifact> newManifest = new HashMap<>();
-
-    outer:
-    for (Iterator<Entry<PathFragment, Artifact>> i = workingManifest.entrySet().iterator();
-         i.hasNext(); ) {
-      Entry<PathFragment, Artifact> entry = i.next();
-      PathFragment source = entry.getKey();
-      Artifact symlink = entry.getValue();
-      // drop nested entries; warn if this changes anything
-      int n = source.segmentCount();
-      for (int j = 1; j < n; ++j) {
-        PathFragment prefix = source.subFragment(0, n - j);
-        Artifact ancestor = workingManifest.get(prefix);
-        if (ancestor != null) {
-          // This is an obscuring symlink, so just drop it and move on if there's no reporter.
-          if (eventHandler == null) {
-            continue outer;
-          }
-          PathFragment suffix = source.subFragment(n - j, n);
-          Path viaAncestor = ancestor.getPath().getRelative(suffix);
-          Path expected = symlink.getPath();
-          if (!viaAncestor.equals(expected)) {
-            eventHandler.handle(Event.warn(location, "runfiles symlink " + source + " -> "
-                + expected + " obscured by " + prefix + " -> " + ancestor.getPath()));
-          }
-          continue outer;
-        }
-      }
-      newManifest.put(entry.getKey(), entry.getValue());
-    }
-    return newManifest;
+  public Map<PathFragment, Artifact> getSymlinksAsMap() {
+    return new ManifestBuilder(ConflictChecker.IGNORE_CHECKER, suffix, legacyRepositoryStructure)
+        .putSymlinks(symlinks).build();
   }
 
   /**
@@ -414,11 +379,14 @@ public final class Runfiles {
    */
   public Map<PathFragment, Artifact> getRunfilesInputs(EventHandler eventHandler,
       Location location) throws IOException {
-    ConflictChecker checker = new ConflictChecker(conflictPolicy, eventHandler, location);
-    Map<PathFragment, Artifact> manifest = getSymlinksAsMap(checker);
+    ManifestBuilder builder = new ManifestBuilder(
+        new ConflictChecker(conflictPolicy, eventHandler, location),
+        suffix,
+        legacyRepositoryStructure);
+    builder.putSymlinks(symlinks);
     // Add unconditional artifacts (committed to inclusion on construction of runfiles).
     for (Artifact artifact : getUnconditionalArtifactsWithoutMiddlemen()) {
-      checker.put(manifest, artifact.getRootRelativePath(), artifact);
+      builder.put(RunfilesPath.resolve(artifact.getRootRelativePath(), suffix), artifact);
     }
 
     // Add conditional artifacts (only included if they appear in a pruning manifest).
@@ -434,39 +402,26 @@ public final class Runfiles {
         while ((line = reader.readLine()) != null) {
           Artifact artifact = allowedRunfiles.get(line);
           if (artifact != null) {
-            checker.put(manifest, artifact.getRootRelativePath(), artifact);
+            builder.put(RunfilesPath.resolve(artifact.getRootRelativePath(), suffix), artifact);
           }
         }
       }
     }
-    manifest = filterListForObscuringSymlinks(eventHandler, location, manifest);
+    builder.filterListForObscuringSymlinks(eventHandler, location);
 
     // TODO(bazel-team): Create /dev/null-like Artifact to avoid nulls?
-    for (PathFragment extraPath : emptyFilesSupplier.getExtraPaths(manifest.keySet())) {
-      checker.put(manifest, extraPath, null);
-    }
-
-    // Copy manifest map to another manifest map, prepending the workspace name to every path.
-    // E.g. for workspace "myworkspace", the runfile entry "mylib.so"->"/path/to/mylib.so" becomes
-    // "myworkspace/mylib.so"->"/path/to/mylib.so".
-    PathFragment suffixPath = new PathFragment(suffix);
-    Map<PathFragment, Artifact> rootManifest = new HashMap<>();
-    for (Map.Entry<PathFragment, Artifact> entry : manifest.entrySet()) {
-      checker.put(rootManifest, suffixPath.getRelative(entry.getKey()), entry.getValue());
+    for (PathFragment extraPath : emptyFilesSupplier.getExtraPaths(builder.getPaths())) {
+      builder.put(RunfilesPath.alreadyResolved(extraPath, suffix), null);
     }
 
     // Finally add symlinks relative to the root of the runfiles tree, on top of everything else.
     // This operation is always checked for conflicts, to match historical behavior.
     if (conflictPolicy == ConflictPolicy.IGNORE) {
-      checker = new ConflictChecker(ConflictPolicy.WARN, eventHandler, location);
-    }
-    for (Map.Entry<PathFragment, Artifact> entry : getRootSymlinksAsMap(checker).entrySet()) {
-      PathFragment mappedPath = entry.getKey();
-      Artifact mappedArtifact = entry.getValue();
-      checker.put(rootManifest, mappedPath, mappedArtifact);
+      builder.resetConflictPolicy(
+          new ConflictChecker(ConflictPolicy.WARN, eventHandler, location));
     }
-
-    return rootManifest;
+    builder.putRootSymlinks(rootSymlinks);
+    return builder.build();
   }
 
   /**
@@ -482,7 +437,9 @@ public final class Runfiles {
    * @param checker If not null, check for conflicts using this checker.
    */
   public Map<PathFragment, Artifact> getRootSymlinksAsMap(@Nullable ConflictChecker checker) {
-    return entriesToMap(rootSymlinks, checker);
+    return new ManifestBuilder(checker, suffix, legacyRepositoryStructure)
+        .putRootSymlinks(rootSymlinks)
+        .buildWithoutDummyFile();
   }
 
   /**
@@ -490,14 +447,15 @@ public final class Runfiles {
    * account.
    */
   public Map<PathFragment, Artifact> asMapWithoutRootSymlinks() {
-    Map<PathFragment, Artifact> result = entriesToMap(symlinks, null);
+    ManifestBuilder builder = new ManifestBuilder(
+        ConflictChecker.IGNORE_CHECKER, suffix, legacyRepositoryStructure).putSymlinks(symlinks);
     // If multiple artifacts have the same root-relative path, the last one in the list will win.
     // That is because the runfiles tree cannot contain the same artifact for different
     // configurations, because it only uses root-relative paths.
     for (Artifact artifact : Iterables.filter(unconditionalArtifacts, Artifact.MIDDLEMAN_FILTER)) {
-      result.put(artifact.getRootRelativePath(), artifact);
+      builder.put(RunfilesPath.resolve(artifact.getRootRelativePath(), suffix), artifact);
     }
-    return result;
+    return builder.build();
   }
 
   /**
@@ -542,24 +500,6 @@ public final class Runfiles {
         pruningManifests.isEmpty();
   }
 
-  /**
-   * Flatten a sequence of entries into a single map.
-   *
-   * @param entrySet Sequence of entries to add.
-   * @param checker If not null, check for conflicts with this checker, otherwise silently allow
-   *    entries to overwrite previous entries.
-   * @return Map<PathFragment, Artifact> Map of runfile entries.
-   */
-  private static Map<PathFragment, Artifact> entriesToMap(
-      Iterable<SymlinkEntry> entrySet, @Nullable ConflictChecker checker) {
-    checker = (checker != null) ? checker : ConflictChecker.IGNORE_CHECKER;
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
-    for (SymlinkEntry entry : entrySet) {
-      checker.put(map, entry.getPath(), entry.getArtifact());
-    }
-    return map;
-  }
-
   /** Returns currently policy for conflicting symlink entries. */
   public ConflictPolicy getConflictPolicy() {
     return this.conflictPolicy;
@@ -572,6 +512,189 @@ public final class Runfiles {
   }
 
   /**
+   * Helper class to make sure that every path added to runfiles is relative to the root of the
+   * runfiles tree.
+   */
+  @VisibleForTesting
+  static class RunfilesPath {
+
+    private final PathFragment path;
+    private final boolean external;
+
+    public static RunfilesPath resolve(PathFragment path, PathFragment workspaceName) {
+      return new RunfilesPath(makeRelativeToRunfilesDir(path, workspaceName), workspaceName);
+    }
+
+    public static RunfilesPath alreadyResolved(PathFragment path, PathFragment workspaceName) {
+      return new RunfilesPath(path, workspaceName);
+    }
+
+    private RunfilesPath(PathFragment path, PathFragment workspaceName) {
+      this.path = path;
+      this.external = path.segmentCount() > 1 && !path.startsWith(workspaceName);
+    }
+
+    public PathFragment getPath() {
+      return path;
+    }
+
+    /**
+     * Returns if this file is from an external repository.
+     */
+    public boolean isExternal() {
+      return external;
+    }
+
+    /**
+     * This takes an execution-root-relative path and turns it into a runfiles-relative path. For
+     * paths in the current repository, it prefixes them with the workspace name. For paths in
+     * external repositories, it turns the execution root path (external/repo-name/foo) into a
+     * runfiles path (repo-name/foo).
+     */
+    private static PathFragment makeRelativeToRunfilesDir(
+        PathFragment path, PathFragment mainWorkspace) {
+      if (path.getSegment(0).equals(Label.EXTERNAL_PATH_PREFIX)) {
+        path = path.relativeTo(Label.EXTERNAL_PACKAGE_NAME);
+      } else {
+        path = mainWorkspace.getRelative(path);
+      }
+      return path;
+    }
+  }
+
+  /**
+   * A builder to handle the logic of creating a manifest mapping.
+   */
+  @VisibleForTesting
+  static final class ManifestBuilder {
+    private final PathFragment workspaceName;
+    private final boolean legacyRunfilesStructure;
+
+    private Map<PathFragment, Artifact> map;
+    private ConflictChecker checker;
+    private boolean sawWorkspaceName;
+
+    ManifestBuilder(
+        ConflictChecker checker, PathFragment workspaceName, boolean legacyRepositoryStructure) {
+      this.workspaceName = workspaceName;
+      this.legacyRunfilesStructure = legacyRepositoryStructure;
+      this.map = new LinkedHashMap<>();
+      this.checker = checker == null ? ConflictChecker.IGNORE_CHECKER : checker;
+      this.sawWorkspaceName = false;
+    }
+
+    public void resetConflictPolicy(ConflictChecker checker) {
+      this.checker = checker;
+    }
+
+    public ManifestBuilder put(RunfilesPath runfilesPath, Artifact artifact) {
+      checker.check(map, runfilesPath, artifact);
+      PathFragment path = runfilesPath.getPath();
+      if (path.startsWith(workspaceName)) {
+        sawWorkspaceName = true;
+      }
+      if (runfilesPath.isExternal() && legacyRunfilesStructure) {
+        // Store runfiles at both .runfiles/wsname/external/foo and .runfiles/foo, to allow people
+        // time to migrate to the second form.
+        map.put(
+            workspaceName.getRelative(Label.EXTERNAL_PACKAGE_NAME).getRelative(path), artifact);
+      }
+      map.put(path, artifact);
+      return this;
+    }
+
+    /**
+     * Flatten a sequence of entries into a single map.
+     *
+     * @param symlinks Sequence of entries to add.
+     */
+    public ManifestBuilder putSymlinks(NestedSet<SymlinkEntry> symlinks) {
+      for (SymlinkEntry entry : symlinks) {
+        put(RunfilesPath.resolve(entry.getPath(), workspaceName), entry.getArtifact());
+      }
+      return this;
+    }
+
+    /**
+     * Flatten a sequence of entries into a single map. Symlink entries are relative to .runfiles,
+     * not .runfiles/wsname, so it's assumed that external workspace entries are already resolved.
+     *
+     * @param symlinks Sequence of entries to add.
+     */
+    public ManifestBuilder putRootSymlinks(NestedSet<SymlinkEntry> symlinks) {
+      for (SymlinkEntry entry : symlinks) {
+        put(RunfilesPath.alreadyResolved(entry.getPath(), workspaceName), entry.getArtifact());
+      }
+      return this;
+    }
+
+    /**
+     * This destroys the existing listing and replaces it with one that has no obscuring symlinks.
+     *
+     * @param eventHandler Used for throwing an error if we have an obscuring runlink.
+     *                 May be null, in which case obscuring symlinks are silently discarded.
+     * @param location Location for reporter. Ignored if reporter is null.
+     */
+    @VisibleForTesting
+    ManifestBuilder filterListForObscuringSymlinks(EventHandler eventHandler, Location location) {
+      Map<PathFragment, Artifact> newManifest = new HashMap<>();
+
+      outer:
+      for (Entry<PathFragment, Artifact> entry : map.entrySet()) {
+        PathFragment source = entry.getKey();
+        Artifact symlink = entry.getValue();
+        // drop nested entries; warn if this changes anything
+        int n = source.segmentCount();
+        for (int j = 1; j < n; ++j) {
+          PathFragment prefix = source.subFragment(0, n - j);
+          Artifact ancestor = map.get(prefix);
+          if (ancestor != null) {
+            // This is an obscuring symlink, so just drop it and move on if there's no reporter.
+            if (eventHandler == null) {
+              continue outer;
+            }
+            PathFragment suffixPath = source.subFragment(n - j, n);
+            Path viaAncestor = ancestor.getPath().getRelative(suffixPath);
+            Path expected = symlink.getPath();
+            if (!viaAncestor.equals(expected)) {
+              eventHandler.handle(Event.warn(location, "runfiles symlink " + source + " -> "
+                  + expected + " obscured by " + prefix + " -> " + ancestor.getPath()));
+            }
+            continue outer;
+          }
+        }
+        newManifest.put(entry.getKey(), entry.getValue());
+      }
+
+      map = newManifest;
+      return this;
+    }
+
+    public Set<PathFragment> getPaths() {
+      return map.keySet();
+    }
+
+    /**
+     * Returns the map without checking if the main repository's directory needs to be added to
+     * the runfiles tree.
+     */
+    public Map<PathFragment, Artifact> buildWithoutDummyFile() {
+      return map;
+    }
+
+    public Map<PathFragment, Artifact> build() {
+      if (!sawWorkspaceName && !map.isEmpty()) {
+        // If we haven't seen it and we have seen other files, add the workspace name directory.
+        // It might not be there if all of the runfiles are from other repos (and then running from
+        // x.runfiles/ws will fail, because ws won't exist). We can't tell Runfiles to create a
+        // directory, so instead this creates a hidden file inside the desired directory.
+        map.put(workspaceName.getRelative(".runfile"), null);
+      }
+      return map;
+    }
+  }
+
+  /**
    * Checks for conflicts between entries in a runfiles tree while putting them in a map.
    */
   public static final class ConflictChecker {
@@ -606,11 +729,11 @@ public final class Runfiles {
     /**
      * Add an entry to a Map of symlinks, optionally reporting conflicts.
      *
-     * @param map Manifest of runfile entries.
-     * @param path Path fragment to use as key in map.
+     * @param runfilesPath Path relative to the .runfiles directory, used as key in map.
      * @param artifact Artifact to store in map. This may be null to indicate an empty file.
      */
-    public void put(Map<PathFragment, Artifact> map, PathFragment path, Artifact artifact) {
+    void check(Map<PathFragment, Artifact> map, RunfilesPath runfilesPath, Artifact artifact) {
+      PathFragment path = runfilesPath.getPath();
       if (policy != ConflictPolicy.IGNORE && map.containsKey(path)) {
         // Previous and new entry might have value of null
         Artifact previous = map.get(path);
@@ -626,7 +749,6 @@ public final class Runfiles {
           eventHandler.handle(new Event(eventKind, location, message));
         }
       }
-      map.put(path, artifact);
     }
   }
 
@@ -636,7 +758,13 @@ public final class Runfiles {
   public static final class Builder {
 
     /** This is set to the workspace name */
-    private String suffix;
+    private PathFragment suffix;
+    /**
+     * If external runfiles should be under .runfiles/wsname/external/repo (in addition to
+     * .runfiles/repo).
+     * TODO(kchodorow): remove this once the old form is deprecated.
+     */
+    private final boolean legacyRepositoryStructure;
 
     /**
      * This must be COMPILE_ORDER because {@link #asMapWithoutRootSymlinks} overwrites earlier
@@ -659,15 +787,29 @@ public final class Runfiles {
      * Only used for Runfiles.EMPTY.
      */
     private Builder() {
-      this.suffix = "";
+      this.suffix = PathFragment.EMPTY_FRAGMENT;
+      this.legacyRepositoryStructure = false;
     }
 
     /**
-     * Creates a builder with the given suffix.
+     * Creates a builder with the given suffix. Transitional constructor so that new rules don't
+     * accidentally depend on the legacy repository structure, until that option is removed.
+     *
      * @param workspace is the string specified in workspace() in the WORKSPACE file.
      */
     public Builder(String workspace) {
-      this.suffix = workspace;
+      this(workspace, false);
+    }
+
+    /**
+     * Creates a builder with the given suffix.
+     * @param workspace is the string specified in workspace() in the WORKSPACE file.
+     * @param legacyRepositoryStructure if the wsname/external/repo symlinks should also be
+     *     created.
+     */
+    public Builder(String workspace, boolean legacyRepositoryStructure) {
+      this.suffix = new PathFragment(workspace);
+      this.legacyRepositoryStructure = legacyRepositoryStructure;
     }
 
     /**
@@ -676,7 +818,7 @@ public final class Runfiles {
     public Runfiles build() {
       return new Runfiles(suffix, artifactsBuilder.build(), symlinksBuilder.build(),
           rootSymlinksBuilder.build(), pruningManifestsBuilder.build(),
-          emptyFilesSupplier, conflictPolicy);
+          emptyFilesSupplier, conflictPolicy, legacyRepositoryStructure);
     }
 
     /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
index 07282a2bd0..513bc869d6 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
@@ -97,7 +97,8 @@ public class RunfilesSupport {
         && TargetUtils.isTestRule(ruleContext.getRule())) {
       TransitiveInfoCollection runUnderTarget =
           ruleContext.getPrerequisite(":run_under", Mode.DATA);
-      runfiles = new Runfiles.Builder(ruleContext.getWorkspaceName())
+      runfiles = new Runfiles.Builder(
+          ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
           .merge(getRunfiles(runUnderTarget))
           .merge(runfiles)
           .build();
@@ -233,6 +234,13 @@ public class RunfilesSupport {
   }
 
   /**
+   * Returns the name of the workspace that the build is occurring in.
+   */
+  public PathFragment getWorkspaceName() {
+    return runfiles.getSuffix();
+  }
+
+  /**
    * Returns the middleman artifact that depends on getExecutable(),
    * getRunfilesManifest(), and getRunfilesSymlinkTargets(). Anything which
    * needs to actually run the executable should depend on this.
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
index f1e633967f..513fdc4e21 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
@@ -192,17 +192,21 @@ public final class SourceManifestAction extends AbstractFileWriteAction {
   protected String computeKey() {
     Fingerprint f = new Fingerprint();
     f.addString(GUID);
-    Map<PathFragment, Artifact> symlinks = runfiles.getSymlinksAsMap(null);
+    Map<PathFragment, Artifact> symlinks = runfiles.getSymlinksAsMap();
     f.addInt(symlinks.size());
     for (Map.Entry<PathFragment, Artifact> symlink : symlinks.entrySet()) {
       f.addPath(symlink.getKey());
-      f.addPath(symlink.getValue().getPath());
+      if (symlink.getValue() != null) {
+        f.addPath(symlink.getValue().getPath());
+      }
     }
     Map<PathFragment, Artifact> rootSymlinks = runfiles.getRootSymlinksAsMap(null);
     f.addInt(rootSymlinks.size());
     for (Map.Entry<PathFragment, Artifact> rootSymlink : rootSymlinks.entrySet()) {
       f.addPath(rootSymlink.getKey());
-      f.addPath(rootSymlink.getValue().getPath());
+      if (rootSymlink.getValue() != null) {
+        f.addPath(rootSymlink.getValue().getPath());
+      }
     }
 
     for (Artifact artifact : runfiles.getArtifactsWithoutMiddlemen()) {
@@ -294,16 +298,18 @@ public final class SourceManifestAction extends AbstractFileWriteAction {
     private final Artifact output;
     private final Runfiles.Builder runfilesBuilder;
 
-    public Builder(String prefix, ManifestType manifestType, ActionOwner owner, Artifact output) {
-      this.runfilesBuilder = new Runfiles.Builder(prefix);
+    public Builder(
+        String prefix, ManifestType manifestType, ActionOwner owner, Artifact output,
+        boolean legacyExternalRunfiles) {
+      this.runfilesBuilder = new Runfiles.Builder(prefix, legacyExternalRunfiles);
       manifestWriter = manifestType;
       this.owner = owner;
       this.output = output;
     }
 
-    @VisibleForTesting
+    @VisibleForTesting  // Only used for testing.
     Builder(String prefix, ManifestWriter manifestWriter, ActionOwner owner, Artifact output) {
-      this.runfilesBuilder = new Runfiles.Builder(prefix);
+      this.runfilesBuilder = new Runfiles.Builder(prefix, false);
       this.manifestWriter = manifestWriter;
       this.owner = owner;
       this.output = output;
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 fd7671d06e..67e34abefc 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
@@ -708,6 +708,13 @@ public final class BuildConfiguration {
             + "If false, write only manifests when possible.")
     public boolean buildRunfiles;
 
+    @Option(name = "legacy_external_runfiles",
+        defaultValue = "true",
+        category = "strategy",
+        help = "If true, build runfiles symlink forests for external repositories under "
+            + ".runfiles/wsname/external/repo (in addition to .runfiles/repo).")
+    public boolean legacyExternalRunfiles;
+
     @Option(name = "test_arg",
         allowMultiple = true,
         defaultValue = "",
@@ -2180,6 +2187,13 @@ public final class BuildConfiguration {
     return options.buildRunfiles;
   }
 
+  /**
+   * Returns if we are building external runfiles symlinks using the old-style structure.
+   */
+  public boolean legacyExternalRunfiles() {
+    return options.legacyExternalRunfiles;
+  }
+
   public boolean getCheckFilesetDependenciesRecursively() {
     return options.checkFilesetDependenciesRecursively;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
index ef0bca705c..216f013081 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
@@ -245,7 +245,7 @@ public class BazelRuleClassProvider {
         .addBuildInfoFactory(new ObjcBuildInfoFactory())
         .setConfigurationCollectionFactory(new BazelConfigurationCollection())
         .setPrelude("//tools/build_rules:prelude_bazel")
-        .setRunfilesPrefix("")
+        .setRunfilesPrefix("__main__")
         .setToolsRepository("@bazel_tools")
         .setPrerequisiteValidator(new BazelPrerequisiteValidator())
         .setSkylarkAccessibleJavaClasses(skylarkBuiltinJavaObects);
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
index 119eb7838c..1448aee2ce 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
@@ -149,7 +149,10 @@ public class GenRule implements RuleConfiguredTargetFactory {
         // No need to visit the dependencies of a genrule. They cross from the target into the host
         // configuration, because the dependencies of a genrule are always built for the host
         // configuration.
-        new Runfiles.Builder(ruleContext.getWorkspaceName()).addTransitiveArtifacts(filesToBuild)
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
+            .addTransitiveArtifacts(filesToBuild)
             .build());
 
     return new RuleConfiguredTargetBuilder(ruleContext)
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
index fae681b68e..4e8513a1e1 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
@@ -204,7 +204,7 @@ public class BazelJavaSemantics implements JavaSemantics {
         buffer.append(delimiter);
       }
       buffer.append("${RUNPATH}");
-      buffer.append(artifact.getRootRelativePath().getPathString());
+      buffer.append(artifact.getRunfilesPath().getPathString());
     }
   }
 
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 5b72cbd473..f82c9fef76 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
@@ -72,7 +72,11 @@ public class BazelPythonSemantics implements PythonSemantics {
   @Override
   public List<PathFragment> getImports(RuleContext ruleContext) {
     List<PathFragment> result = new ArrayList<>();
-    PathFragment packageFragment = ruleContext.getLabel().getPackageIdentifier().getPathFragment();
+    PathFragment packageFragment = ruleContext.getLabel().getPackageIdentifier().getRunfilesPath();
+    // 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())
+        .getRelative(packageFragment);
     for (String importsAttr : ruleContext.attributes().get("imports", Type.STRING_LIST)) {
       importsAttr = ruleContext.expandMakeVariables("includes", importsAttr);
       if (importsAttr.startsWith("/")) {
@@ -83,7 +87,7 @@ public class BazelPythonSemantics implements PythonSemantics {
       PathFragment importsPath = packageFragment.getRelative(importsAttr).normalize();
       if (!importsPath.isNormalized()) {
         ruleContext.attributeError("imports",
-            "Path references a path above the execution root.");
+            "Path " + importsAttr + " references a path above the execution root");
       }
       result.add(importsPath);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt
index bdce83eebe..29e373c2ac 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt
@@ -73,18 +73,11 @@ def Main():
                          sys.argv[0])
 
   python_imports = '%imports%'
-  module_space_with_workspace_name = module_space
-  if '%workspace_name%' != '':
-    module_space_with_workspace_name = os.path.join(module_space, '%workspace_name%')
-
-  python_path_entries = CreatePythonPathEntries(
-    python_imports, module_space_with_workspace_name)
-
-  external_dir = os.path.join(module_space_with_workspace_name, 'external')
-  if os.path.isdir(external_dir):
-    external_entries = [os.path.join(external_dir, d) for d in os.listdir(external_dir)]
-    repositories = [d for d in external_entries if os.path.isdir(d)]
-    python_path_entries += repositories
+  python_path_entries = CreatePythonPathEntries(python_imports, module_space)
+
+  repo_dirs = [os.path.join(module_space, d) for d in os.listdir(module_space)]
+  repositories = [d for d in repo_dirs if os.path.isdir(d)]
+  python_path_entries += repositories
 
   old_python_path = os.environ.get('PYTHONPATH')
   separator = ';' if IsWindows() else ':'
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShBinary.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShBinary.java
index 5bd542eb64..cd2a48ee06 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShBinary.java
@@ -56,7 +56,8 @@ public class ShBinary implements RuleConfiguredTargetFactory {
         .add(src)
         .add(symlink)
         .build();
-    Runfiles runfiles = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles runfiles = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         .addTransitiveArtifacts(filesToBuild)
         .addRunfiles(ruleContext, RunfilesProvider.DEFAULT_RUNFILES)
         .build();
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShLibrary.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShLibrary.java
index 496917775b..9e94d4591a 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/sh/ShLibrary.java
@@ -36,7 +36,8 @@ public class ShLibrary implements RuleConfiguredTargetFactory {
         .addAll(ruleContext.getPrerequisiteArtifacts("deps", Mode.TARGET).list())
         .addAll(ruleContext.getPrerequisiteArtifacts("data", Mode.DATA).list())
         .build();
-    Runfiles runfiles = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles runfiles = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         .addTransitiveArtifacts(filesToBuild)
         .build();
     return new RuleConfiguredTargetBuilder(ruleContext)
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 021845cbc6..2fa4494192 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
@@ -129,6 +129,14 @@ public final class PackageIdentifier implements Comparable<PackageIdentifier>, S
     return repository.getPathFragment().getRelative(pkgName);
   }
 
+  /**
+   * Returns the runfiles path for this repository (relative to the x.runfiles/main-repo/
+   * directory).
+   */
+  public PathFragment getRunfilesPath() {
+    return getRepository().getRunfilesPath().getRelative(getPackageFragment());
+  }
+
   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 9a4e5a7ca1..6b89a6ee7a 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
@@ -202,6 +202,16 @@ public final class RepositoryName implements Serializable {
   }
 
   /**
+   * Returns the runfiles path for this repository (relative to the x.runfiles/main-repo/
+   * directory). 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 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/rules/SkylarkRuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
index db0f9709f6..263fc49468 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
@@ -334,7 +334,9 @@ public final class SkylarkRuleConfiguredTargetBuilder {
     if (executable == null) {
       return runfiles;
     }
-    return new Runfiles.Builder(ruleContext.getWorkspaceName()).addArtifact(executable)
+    return new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
+        .addArtifact(executable)
         .merge(runfiles).build();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
index a0e00ff62d..44f637f3e7 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
@@ -563,7 +563,9 @@ public class SkylarkRuleImplementationFunctions {
         Boolean collectData, Boolean collectDefault,
         SkylarkDict<?, ?> symlinks, SkylarkDict<?, ?> rootSymlinks,
         Location loc) throws EvalException, ConversionException {
-      Runfiles.Builder builder = new Runfiles.Builder(ctx.getRuleContext().getWorkspaceName());
+      Runfiles.Builder builder = new Runfiles.Builder(
+          ctx.getRuleContext().getWorkspaceName(),
+          ctx.getConfiguration().legacyExternalRunfiles());
       boolean checkConflicts = false;
       if (EvalUtils.toBoolean(collectData)) {
         builder.addRunfiles(ctx.getRuleContext(), RunfilesProvider.DATA_RUNFILES);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
index 8c9fc5f2e0..0e668560f6 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
@@ -621,7 +621,9 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
         .add(
             RunfilesProvider.class,
             RunfilesProvider.simple(
-                new Runfiles.Builder(ruleContext.getWorkspaceName())
+                new Runfiles.Builder(
+                    ruleContext.getWorkspaceName(),
+                    ruleContext.getConfiguration().legacyExternalRunfiles())
                     .addRunfiles(ruleContext, RunfilesProvider.DEFAULT_RUNFILES)
                     .addTransitiveArtifacts(filesToBuild)
                     .build()))
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
index a1bd85521c..80606ce237 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
@@ -702,7 +702,8 @@ public class AndroidCommon {
   private Runfiles getRunfiles() {
     // TODO(bazel-team): why return any Runfiles in the neverlink case?
     if (asNeverLink) {
-      return new Runfiles.Builder(ruleContext.getWorkspaceName())
+      return new Runfiles.Builder(
+          ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
           .addRunfiles(ruleContext, RunfilesProvider.DEFAULT_RUNFILES)
           .build();
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java b/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
index dbcf0bfa98..dd0df2245a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
@@ -149,7 +149,7 @@ public final class NativeLibs {
     Artifact inputManifest = AndroidBinary.getDxArtifact(ruleContext, "native_symlinks.manifest");
     ruleContext.registerAction(new SourceManifestAction.Builder(
         ruleContext.getWorkspaceName(), ManifestType.SOURCE_SYMLINKS, ruleContext.getActionOwner(),
-        inputManifest)
+        inputManifest, ruleContext.getConfiguration().legacyExternalRunfiles())
             .addRootSymlinks(symlinks)
             .build());
     Artifact outputManifest = AndroidBinary.getDxArtifact(ruleContext, "native_symlinks/MANIFEST");
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
index eda0dfbc73..7b5e4a3ba7 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
@@ -97,7 +97,8 @@ public abstract class CcBinary implements RuleConfiguredTargetFactory {
       Iterable<Artifact> fakeLinkerInputs,
       boolean fake,
       ImmutableList<Pair<Artifact, Label>> cAndCppSources) {
-    Runfiles.Builder builder = new Runfiles.Builder(context.getWorkspaceName());
+    Runfiles.Builder builder = new Runfiles.Builder(
+        context.getWorkspaceName(), context.getConfiguration().legacyExternalRunfiles());
     Function<TransitiveInfoCollection, Runfiles> runfilesMapping =
         CppRunfilesProvider.runfilesFunction(linkStaticness != LinkStaticness.DYNAMIC);
     boolean linkshared = isLinkShared(context);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibrary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibrary.java
index fe6428b1b7..d6a34ca5d2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLibrary.java
@@ -75,7 +75,8 @@ public abstract class CcLibrary implements RuleConfiguredTargetFactory {
       CcLinkingOutputs ccLinkingOutputs,
       boolean neverLink, boolean addDynamicRuntimeInputArtifactsToRunfiles,
       boolean linkingStatically) {
-    Runfiles.Builder builder = new Runfiles.Builder(context.getWorkspaceName());
+    Runfiles.Builder builder = new Runfiles.Builder(
+        context.getWorkspaceName(), context.getConfiguration().legacyExternalRunfiles());
 
     // neverlink= true creates a library that will never be linked into any binary that depends on
     // it, but instead be loaded as an extension. So we need the dynamic library for this in the
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 dc7f035353..6fdcc36f29 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
@@ -1037,7 +1037,8 @@ public final class CcLibraryHelper {
 
   private Runfiles collectCppRunfiles(
       CcLinkingOutputs ccLinkingOutputs, boolean linkingStatically) {
-    Runfiles.Builder builder = new Runfiles.Builder(ruleContext.getWorkspaceName());
+    Runfiles.Builder builder = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles());
     builder.addTargets(implementationDeps, RunfilesProvider.DEFAULT_RUNFILES);
     builder.addTargets(implementationDeps, CppRunfilesProvider.runfilesFunction(linkingStatically));
     // Add the shared libraries to the runfiles.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java b/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java
index b42a918fc8..fb4d990fcf 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/filegroup/Filegroup.java
@@ -56,11 +56,16 @@ public class Filegroup implements RuleConfiguredTargetFactory {
             InstrumentedFilesCollector.NO_METADATA_COLLECTOR, filesToBuild);
 
     RunfilesProvider runfilesProvider = RunfilesProvider.withData(
-        new Runfiles.Builder(ruleContext.getWorkspaceName())
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
             .addRunfiles(ruleContext, RunfilesProvider.DEFAULT_RUNFILES)
             .build(),
         // If you're visiting a filegroup as data, then we also visit its data as data.
-        new Runfiles.Builder(ruleContext.getWorkspaceName()).addTransitiveArtifacts(filesToBuild)
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
+            .addTransitiveArtifacts(filesToBuild)
             .addDataDeps(ruleContext).build());
 
     return new RuleConfiguredTargetBuilder(ruleContext)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index 3f2cd64703..3e4bfbd349 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -157,7 +157,9 @@ public class GenQuery implements RuleConfiguredTargetFactory {
     return new RuleConfiguredTargetBuilder(ruleContext)
         .setFilesToBuild(filesToBuild)
         .add(RunfilesProvider.class, RunfilesProvider.simple(
-            new Runfiles.Builder(ruleContext.getWorkspaceName())
+            new Runfiles.Builder(
+                ruleContext.getWorkspaceName(),
+                ruleContext.getConfiguration().legacyExternalRunfiles())
                 .addTransitiveArtifacts(filesToBuild).build()))
         .build();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java
index 79ae9bb656..2a0560ef65 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaBinary.java
@@ -66,7 +66,8 @@ public class JavaBinary implements RuleConfiguredTargetFactory {
   public ConfiguredTarget create(RuleContext ruleContext) throws InterruptedException {
     final JavaCommon common = new JavaCommon(ruleContext, semantics);
     DeployArchiveBuilder deployArchiveBuilder =  new DeployArchiveBuilder(semantics, ruleContext);
-    Runfiles.Builder runfilesBuilder = new Runfiles.Builder(ruleContext.getWorkspaceName());
+    Runfiles.Builder runfilesBuilder = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles());
     List<String> jvmFlags = new ArrayList<>();
 
     JavaTargetAttributes.Builder attributesBuilder = common.initCommon();
@@ -266,7 +267,11 @@ public class JavaBinary implements RuleConfiguredTargetFactory {
 
     RunfilesProvider runfilesProvider = RunfilesProvider.withData(
         defaultRunfiles,
-        new Runfiles.Builder(ruleContext.getWorkspaceName()).merge(runfilesSupport).build());
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
+            .merge(runfilesSupport)
+            .build());
 
     ImmutableList<String> deployManifestLines =
         getDeployManifestLines(ruleContext, originalMainClass);
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 8a9cff0259..cd9378ca36 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
@@ -459,7 +459,7 @@ public class JavaCommon {
     if (launcher != null) {
       javaExecutable = launcher.getRootRelativePath();
     } else {
-      javaExecutable = ruleContext.getFragment(Jvm.class).getJavaExecutable();
+      javaExecutable = ruleContext.getFragment(Jvm.class).getRunfilesJavaExecutable();
     }
 
     String pathPrefix = javaExecutable.isAbsolute() ? "" : "${JAVA_RUNFILES}/"
@@ -718,7 +718,8 @@ public class JavaCommon {
     if (neverLink) {
       return Runfiles.EMPTY;
     }
-    Runfiles.Builder runfilesBuilder = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles.Builder runfilesBuilder = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         .addArtifacts(javaArtifacts.getRuntimeJars());
     runfilesBuilder.addRunfiles(ruleContext, RunfilesProvider.DEFAULT_RUNFILES);
     runfilesBuilder.add(ruleContext, JavaRunfilesProvider.TO_RUNFILES);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java
index 46e4d815e2..b6ac48ec1a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaImport.java
@@ -94,7 +94,9 @@ public class JavaImport implements RuleConfiguredTargetFactory {
     // runfiles from this target or its dependencies.
     Runfiles runfiles = neverLink ?
         Runfiles.EMPTY :
-        new Runfiles.Builder(ruleContext.getWorkspaceName())
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
             // add the jars to the runfiles
             .addArtifacts(javaArtifacts.getRuntimeJars())
             .addTargets(targets, RunfilesProvider.DEFAULT_RUNFILES)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java
index e66847e422..8b65c0436f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaLibraryHelper.java
@@ -371,7 +371,8 @@ public final class JavaLibraryHelper {
 
   private JavaRunfilesProvider collectJavaRunfiles(
       JavaCompilationArtifacts javaCompilationArtifacts) {
-    Runfiles runfiles = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles runfiles = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         // Compiled templates as well, for API.
         .addArtifacts(javaCompilationArtifacts.getRuntimeJars())
         .addTargets(deps, JavaRunfilesProvider.TO_RUNFILES)
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 e24266db5f..edecece6aa 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
@@ -39,6 +39,10 @@ public final class Jvm extends BuildConfiguration.Fragment {
   private final PathFragment jar;
   private final PathFragment java;
 
+  private static final String BIN_JAVAC = "bin/javac" + OsUtils.executableExtension();
+  private static final String BIN_JAR = "bin/jar" + OsUtils.executableExtension();
+  private static final String BIN_JAVA = "bin/java" + OsUtils.executableExtension();
+
   /**
    * Creates a Jvm instance. Either the {@code javaHome} parameter is absolute,
    * or the {@code jvmLabel} parameter must be non-null. This restriction might
@@ -48,9 +52,9 @@ public final class Jvm extends BuildConfiguration.Fragment {
     Preconditions.checkArgument(javaHome.isAbsolute() ^ (jvmLabel != null));
     this.javaHome = javaHome;
     this.jvmLabel = jvmLabel;
-    this.javac = getJavaHome().getRelative("bin/javac" + OsUtils.executableExtension());
-    this.jar = getJavaHome().getRelative("bin/jar" + OsUtils.executableExtension());
-    this.java = getJavaHome().getRelative("bin/java" + OsUtils.executableExtension());
+    this.javac = getJavaHome().getRelative(BIN_JAVAC);
+    this.jar = getJavaHome().getRelative(BIN_JAR);
+    this.java = getJavaHome().getRelative(BIN_JAVA);
   }
 
   /**
@@ -95,6 +99,17 @@ public final class Jvm extends BuildConfiguration.Fragment {
     return jvmLabel;
   }
 
+  /**
+   * If possible, resolves java relative to the jvmLabel's repository. Otherwise, returns the
+   * same thing as getJavaExecutable().
+   */
+  public PathFragment getRunfilesJavaExecutable() {
+    if (jvmLabel == null || jvmLabel.getPackageIdentifier().getRepository().isMain()) {
+      return getJavaExecutable();
+    }
+    return jvmLabel.getPackageIdentifier().getRepository().getRunfilesPath().getRelative(BIN_JAVA);
+  }
+
   @Override
   public void addGlobalMakeVariables(Builder<String, String> globalMakeEnvBuilder) {
     globalMakeEnvBuilder.put("JAVABASE", getJavaHome().getPathString());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/IosTest.java b/src/main/java/com/google/devtools/build/lib/rules/objc/IosTest.java
index 06d6d778ef..f5ca1a6da7 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/IosTest.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/IosTest.java
@@ -165,7 +165,9 @@ public final class IosTest implements RuleConfiguredTargetFactory {
     NestedSet<Artifact> filesToBuildSet = filesToBuild.build();
 
     Runfiles.Builder runfilesBuilder =
-        new Runfiles.Builder(ruleContext.getWorkspaceName())
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
             .addRunfiles(ruleContext, RunfilesProvider.DEFAULT_RUNFILES);
     NestedSetBuilder<Artifact> filesToBuildBuilder =
         NestedSetBuilder.<Artifact>stableOrder().addTransitive(filesToBuildSet);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java
index 76af1c2ce7..cb33acb6ec 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java
@@ -237,9 +237,13 @@ public class ObjcRuleClasses {
   static RuleConfiguredTargetBuilder ruleConfiguredTarget(RuleContext ruleContext,
       NestedSet<Artifact> filesToBuild) {
     RunfilesProvider runfilesProvider = RunfilesProvider.withData(
-        new Runfiles.Builder(ruleContext.getWorkspaceName())
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
             .addRunfiles(ruleContext, RunfilesProvider.DEFAULT_RUNFILES).build(),
-        new Runfiles.Builder(ruleContext.getWorkspaceName())
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
             .addTransitiveArtifacts(filesToBuild).build());
 
     return new RuleConfiguredTargetBuilder(ruleContext)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ReleaseBundlingSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ReleaseBundlingSupport.java
index 8b15f7ac6a..69ad78fc9e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ReleaseBundlingSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ReleaseBundlingSupport.java
@@ -688,7 +688,8 @@ public final class ReleaseBundlingSupport {
    * Returns a {@link RunfilesSupport} that uses the provided runner script as the executable.
    */
   RunfilesSupport runfilesSupport(Artifact runnerScript) throws InterruptedException {
-    Runfiles runfiles = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles runfiles = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         .addArtifact(releaseBundling.getIpaArtifact())
         .addArtifact(runnerScript)
         .addArtifact(attributes.iossim())
diff --git a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCommon.java b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCommon.java
index 42e02980e6..aa7a3e1064 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCommon.java
@@ -108,7 +108,9 @@ public class ProtoCommon {
       final NestedSet<Artifact> transitiveProtoSources, RuleContext ruleContext) {
     return RunfilesProvider.withData(
         Runfiles.EMPTY,
-        new Runfiles.Builder(ruleContext.getWorkspaceName())
+        new Runfiles.Builder(
+            ruleContext.getWorkspaceName(),
+            ruleContext.getConfiguration().legacyExternalRunfiles())
             // TODO(bazel-team): addArtifacts is deprecated, but addTransitive fails
             // due to nested set ordering restrictions. Figure this out.
             .addArtifacts(transitiveProtoSources)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyBinary.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyBinary.java
index ae048a0a03..f4e68f26d5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyBinary.java
@@ -75,7 +75,8 @@ public abstract class PyBinary implements RuleConfiguredTargetFactory {
     semantics.createExecutable(ruleContext, common, ccLinkParamsStore, imports);
     Runfiles commonRunfiles = collectCommonRunfiles(ruleContext, common, semantics);
 
-    Runfiles.Builder defaultRunfilesBuilder = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles.Builder defaultRunfilesBuilder = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         .merge(commonRunfiles);
     semantics.collectDefaultRunfilesForBinary(ruleContext, defaultRunfilesBuilder);
     Runfiles defaultRunfiles = defaultRunfilesBuilder.build();
@@ -90,7 +91,8 @@ public abstract class PyBinary implements RuleConfiguredTargetFactory {
     // Only include common runfiles and middleman. Default runfiles added by semantics are
     // excluded. The middleman is necessary to ensure the runfiles trees are generated for all
     // dependency binaries.
-    Runfiles dataRunfiles = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles dataRunfiles = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         .merge(commonRunfiles)
         .addArtifact(runfilesSupport.getRunfilesMiddleman())
         .build();
@@ -112,7 +114,8 @@ public abstract class PyBinary implements RuleConfiguredTargetFactory {
 
   private static Runfiles collectCommonRunfiles(RuleContext ruleContext, PyCommon common,
       PythonSemantics semantics) {
-    Runfiles.Builder builder = new Runfiles.Builder(ruleContext.getWorkspaceName());
+    Runfiles.Builder builder = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles());
     builder.addArtifact(common.getExecutable());
     if (common.getConvertedFiles() != null) {
       builder.addSymlinks(common.getConvertedFiles());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
index c375701f14..50aebce23b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
@@ -405,8 +405,8 @@ public final class PyCommon {
         } else {
           ruleContext.attributeError("srcs",
               buildMultipleMainMatchesErrorText(explicitMain, mainSourceName,
-                  mainArtifact.getRootRelativePath().toString(),
-                  outItem.getRootRelativePath().toString()));
+                  mainArtifact.getRunfilesPath().toString(),
+                  outItem.getRunfilesPath().toString()));
         }
       }
     }
@@ -417,7 +417,7 @@ public final class PyCommon {
     }
 
     PathFragment workspaceName = new PathFragment(ruleContext.getRule().getWorkspaceName());
-    return workspaceName.getRelative(mainArtifact.getRootRelativePath()).getPathString();
+    return workspaceName.getRelative(mainArtifact.getRunfilesPath()).getPathString();
   }
 
   public Artifact getExecutable() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyLibrary.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyLibrary.java
index 95f4c8364e..eedef4f38d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyLibrary.java
@@ -74,7 +74,8 @@ public abstract class PyLibrary implements RuleConfiguredTargetFactory {
       return null;
     }
 
-    Runfiles.Builder runfilesBuilder = new Runfiles.Builder(ruleContext.getWorkspaceName());
+    Runfiles.Builder runfilesBuilder = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles());
     if (common.getConvertedFiles() != null) {
       runfilesBuilder.addSymlinks(common.getConvertedFiles());
     } else {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java
index 73235cdac2..f8875255d6 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java
@@ -88,7 +88,7 @@ public final class TestActionBuilder {
     // heuristically sharding is currently experimental. Also, we do detect
     // false-positive cases and return an error.
     return runfilesSupport.getRunfilesSymlinkNames().contains(
-        new PathFragment("tools/test_sharding_compliant"));
+        runfilesSupport.getWorkspaceName().getRelative("tools/test_sharding_compliant"));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/test/TestSuite.java b/src/main/java/com/google/devtools/build/lib/rules/test/TestSuite.java
index 4b477cf70e..ed333a0058 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/test/TestSuite.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/test/TestSuite.java
@@ -74,7 +74,8 @@ public class TestSuite implements RuleConfiguredTargetFactory {
       directTestsAndSuitesBuilder.add(dep);
     }
 
-    Runfiles runfiles = new Runfiles.Builder(ruleContext.getWorkspaceName())
+    Runfiles runfiles = new Runfiles.Builder(
+        ruleContext.getWorkspaceName(), ruleContext.getConfiguration().legacyExternalRunfiles())
         .addTargets(directTestsAndSuitesBuilder, RunfilesProvider.DATA_RUNFILES)
         .build();
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesSupplierImplTest.java b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesSupplierImplTest.java
index 8626f6913e..70024c460e 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/RunfilesSupplierImplTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/RunfilesSupplierImplTest.java
@@ -86,7 +86,7 @@ public class RunfilesSupplierImplTest {
   }
 
   private static Runfiles mkRunfiles(Iterable<Artifact> artifacts) {
-    return new Runfiles.Builder("TESTING").addArtifacts(artifacts).build();
+    return new Runfiles.Builder("TESTING", false).addArtifacts(artifacts).build();
   }
 
   private static List<Artifact> mkArtifacts(Root rootDir, String... paths) {
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 7b806f371d..ef2373f6ae 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
@@ -22,16 +22,13 @@ import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.testutil.TestConstants;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.util.HashMap;
-import java.util.LinkedHashMap;
-import java.util.Map;
-
 /**
  * Test for {@link Runfiles}.
  */
@@ -45,79 +42,92 @@ public class RunfilesTest extends FoundationTestCase {
     assertEquals(EventKind.WARNING, Iterables.getOnlyElement(eventCollector).getKind());
   }
 
+  private Runfiles.RunfilesPath runfilesPath(String path) {
+    return runfilesPath(new PathFragment(path));
+  }
+
+  private Runfiles.RunfilesPath runfilesPath(PathFragment path) {
+    return Runfiles.RunfilesPath.alreadyResolved(
+        path, new PathFragment(TestConstants.WORKSPACE_NAME));
+  }
+
   @Test
   public void testFilterListForObscuringSymlinksCatchesBadObscurer() throws Exception {
-    Map<PathFragment, Artifact> obscuringMap = new HashMap<>();
     PathFragment pathA = new PathFragment("a");
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     Artifact artifactA = new Artifact(new PathFragment("a"), root);
-    obscuringMap.put(pathA, artifactA);
-    obscuringMap.put(new PathFragment("a/b"), new Artifact(new PathFragment("c/b"),
-        root));
-    assertThat(Runfiles.filterListForObscuringSymlinks(reporter, null, obscuringMap).entrySet())
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        null, PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath("a"), artifactA);
+    builder.put(runfilesPath("a/b"), new Artifact(new PathFragment("c/b"), root));
+    assertThat(builder.filterListForObscuringSymlinks(reporter, null).build().entrySet())
         .containsExactly(Maps.immutableEntry(pathA, artifactA)).inOrder();
     checkWarning();
   }
 
   @Test
   public void testFilterListForObscuringSymlinksCatchesBadGrandParentObscurer() throws Exception {
-    Map<PathFragment, Artifact> obscuringMap = new HashMap<>();
+    Runfiles.ManifestBuilder obscuringMap = new Runfiles.ManifestBuilder(
+        null, PathFragment.EMPTY_FRAGMENT, false);
     PathFragment pathA = new PathFragment("a");
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
-    Artifact artifactA = new Artifact(new PathFragment("a"),
-                                          root);
-    obscuringMap.put(pathA, artifactA);
-    obscuringMap.put(new PathFragment("a/b/c"), new Artifact(new PathFragment("b/c"),
-                                                         root));
-    assertThat(Runfiles.filterListForObscuringSymlinks(reporter, null, obscuringMap).entrySet())
+    Artifact artifactA = new Artifact(new PathFragment("a"), root);
+
+    obscuringMap.put(runfilesPath("a"), artifactA);
+    obscuringMap.put(runfilesPath("a/b/c"), new Artifact(new PathFragment("b/c"), root));
+    assertThat(obscuringMap.filterListForObscuringSymlinks(reporter, null).build().entrySet())
         .containsExactly(Maps.immutableEntry(pathA, artifactA)).inOrder();
     checkWarning();
   }
 
   @Test
   public void testFilterListForObscuringSymlinksCatchesBadObscurerNoListener() throws Exception {
-    Map<PathFragment, Artifact> obscuringMap = new HashMap<>();
+    Runfiles.ManifestBuilder obscuringMap = new Runfiles.ManifestBuilder(
+        null, PathFragment.EMPTY_FRAGMENT, false);
     PathFragment pathA = new PathFragment("a");
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     Artifact artifactA = new Artifact(new PathFragment("a"),
                                           root);
-    obscuringMap.put(pathA, artifactA);
-    obscuringMap.put(new PathFragment("a/b"), new Artifact(new PathFragment("c/b"),
-                                                         root));
-    assertThat(Runfiles.filterListForObscuringSymlinks(null, null, obscuringMap).entrySet())
+    obscuringMap.put(runfilesPath("a"), artifactA);
+    obscuringMap.put(runfilesPath("a/b"), new Artifact(new PathFragment("c/b"), root));
+    assertThat(obscuringMap.filterListForObscuringSymlinks(null, null).build().entrySet())
         .containsExactly(Maps.immutableEntry(pathA, artifactA)).inOrder();
   }
 
   @Test
   public void testFilterListForObscuringSymlinksIgnoresOkObscurer() throws Exception {
-    Map<PathFragment, Artifact> obscuringMap = new HashMap<>();
+    Runfiles.ManifestBuilder obscuringMap = new Runfiles.ManifestBuilder(
+        null, PathFragment.EMPTY_FRAGMENT, false);
     PathFragment pathA = new PathFragment("a");
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     Artifact artifactA = new Artifact(new PathFragment("a"),
                                           root);
-    obscuringMap.put(pathA, artifactA);
-    obscuringMap.put(new PathFragment("a/b"), new Artifact(new PathFragment("a/b"),
-                                                         root));
+    obscuringMap.put(runfilesPath("a"), artifactA);
+    obscuringMap.put(runfilesPath("a/b"), new Artifact(new PathFragment("a/b"), root));
 
-    assertThat(Runfiles.filterListForObscuringSymlinks(reporter, null, obscuringMap).entrySet())
+    assertThat(obscuringMap.filterListForObscuringSymlinks(reporter, null).build().entrySet())
         .containsExactly(Maps.immutableEntry(pathA, artifactA)).inOrder();
     assertNoEvents();
   }
 
   @Test
   public void testFilterListForObscuringSymlinksNoObscurers() throws Exception {
-    Map<PathFragment, Artifact> obscuringMap = new HashMap<>();
+    Runfiles.ManifestBuilder obscuringMap = new Runfiles.ManifestBuilder(
+        null, PathFragment.EMPTY_FRAGMENT, false);
     PathFragment pathA = new PathFragment("a");
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     Artifact artifactA = new Artifact(new PathFragment("a"),
                                           root);
-    obscuringMap.put(pathA, artifactA);
+    obscuringMap.put(
+        Runfiles.RunfilesPath.alreadyResolved(
+            pathA, new PathFragment(TestConstants.WORKSPACE_NAME)),
+        artifactA);
     PathFragment pathBC = new PathFragment("b/c");
     Artifact artifactBC = new Artifact(new PathFragment("a/b"),
                                        root);
-    obscuringMap.put(pathBC, artifactBC);
-    assertThat(Runfiles.filterListForObscuringSymlinks(reporter, null, obscuringMap)
-                          .entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactA),
+    obscuringMap.put(runfilesPath(pathBC), artifactBC);
+    assertThat(obscuringMap.filterListForObscuringSymlinks(reporter, null).build()
+        .entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactA),
         Maps.immutableEntry(pathBC, artifactBC));
     assertNoEvents();
   }
@@ -140,14 +150,15 @@ public class RunfilesTest extends FoundationTestCase {
     PathFragment pathA = new PathFragment("a");
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
     Artifact artifactC = new Artifact(new PathFragment("c"), root);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
-
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null);
-    checker.put(map, pathA, artifactB);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactB));
-    checker.put(map, pathA, artifactC);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
+
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+
+    builder.put(runfilesPath(pathA), artifactB);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactB));
+    builder.put(runfilesPath(pathA), artifactC);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
     checkConflictWarning();
   }
 
@@ -157,15 +168,15 @@ public class RunfilesTest extends FoundationTestCase {
     PathFragment pathA = new PathFragment("a");
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
     Artifact artifactC = new Artifact(new PathFragment("c"), root);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
     // Same as above but with ERROR not WARNING
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.ERROR, reporter, null);
-    checker.put(map, pathA, artifactB);
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.ERROR, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), artifactB);
     reporter.removeHandler(failFastHandler); // So it doesn't throw AssertionError
-    checker.put(map, pathA, artifactC);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
+    builder.put(runfilesPath(pathA), artifactC);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
     checkConflictError();
   }
 
@@ -174,13 +185,13 @@ public class RunfilesTest extends FoundationTestCase {
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     PathFragment pathA = new PathFragment("a");
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null);
-    checker.put(map, pathA, null);
-    checker.put(map, pathA, artifactB);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactB));
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), null);
+    builder.put(runfilesPath(pathA), artifactB);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactB));
     checkConflictWarning();
   }
 
@@ -189,14 +200,14 @@ public class RunfilesTest extends FoundationTestCase {
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     PathFragment pathA = new PathFragment("a");
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
     // Same as above but opposite order
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null);
-    checker.put(map, pathA, artifactB);
-    checker.put(map, pathA, null);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, null));
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), artifactB);
+    builder.put(runfilesPath(pathA), null);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, null));
     checkConflictWarning();
   }
 
@@ -206,13 +217,13 @@ public class RunfilesTest extends FoundationTestCase {
     PathFragment pathA = new PathFragment("a");
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
     Artifact artifactC = new Artifact(new PathFragment("c"), root);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.IGNORE, reporter, null);
-    checker.put(map, pathA, artifactB);
-    checker.put(map, pathA, artifactC);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.IGNORE, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), artifactB);
+    builder.put(runfilesPath(pathA), artifactC);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
     assertNoEvents();
   }
 
@@ -222,13 +233,13 @@ public class RunfilesTest extends FoundationTestCase {
     PathFragment pathA = new PathFragment("a");
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
     Artifact artifactC = new Artifact(new PathFragment("c"), root);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, null, null);
-    checker.put(map, pathA, artifactB);
-    checker.put(map, pathA, artifactC);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, null, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), artifactB);
+    builder.put(runfilesPath(pathA), artifactC);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactC));
     assertNoEvents();
   }
 
@@ -239,27 +250,27 @@ public class RunfilesTest extends FoundationTestCase {
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
     Artifact artifactB2 = new Artifact(new PathFragment("b"), root);
     assertEquals(artifactB, artifactB2);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null);
-    checker.put(map, pathA, artifactB);
-    checker.put(map, pathA, artifactB2);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactB2));
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), artifactB);
+    builder.put(runfilesPath(pathA), artifactB2);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, artifactB2));
     assertNoEvents();
   }
 
   @Test
   public void testPutIgnoresNullAndNull() {
     PathFragment pathA = new PathFragment("a");
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null);
-    checker.put(map, pathA, null);
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), null);
     // Add it again
-    checker.put(map, pathA, null);
-    assertThat(map.entrySet()).containsExactly(Maps.immutableEntry(pathA, null));
+    builder.put(runfilesPath(pathA), null);
+    assertThat(builder.build().entrySet()).containsExactly(Maps.immutableEntry(pathA, null));
     assertNoEvents();
   }
 
@@ -271,16 +282,16 @@ public class RunfilesTest extends FoundationTestCase {
     PathFragment pathC = new PathFragment("c");
     Artifact artifactA = new Artifact(new PathFragment("a"), root);
     Artifact artifactB = new Artifact(new PathFragment("b"), root);
-    Map<PathFragment, Artifact> map = new LinkedHashMap<>();
 
-    Runfiles.ConflictChecker checker =
-        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null);
-    checker.put(map, pathA, artifactA);
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null),
+        PathFragment.EMPTY_FRAGMENT, false);
+    builder.put(runfilesPath(pathA), artifactA);
     // Add different artifact under different path
-    checker.put(map, pathB, artifactB);
+    builder.put(runfilesPath(pathB), artifactB);
     // Add artifact again under different path
-    checker.put(map, pathC, artifactA);
-    assertThat(map.entrySet())
+    builder.put(runfilesPath(pathC), artifactA);
+    assertThat(builder.build().entrySet())
         .containsExactly(
             Maps.immutableEntry(pathA, artifactA),
             Maps.immutableEntry(pathB, artifactB),
@@ -291,29 +302,50 @@ public class RunfilesTest extends FoundationTestCase {
 
   @Test
   public void testBuilderMergeConflictPolicyDefault() {
-    Runfiles r1 = new Runfiles.Builder("TESTING").build();
-    Runfiles r2 = new Runfiles.Builder("TESTING").merge(r1).build();
+    Runfiles r1 = new Runfiles.Builder("TESTING", false).build();
+    Runfiles r2 = new Runfiles.Builder("TESTING", false).merge(r1).build();
     assertEquals(Runfiles.ConflictPolicy.IGNORE, r2.getConflictPolicy());
   }
 
   @Test
   public void testBuilderMergeConflictPolicyInherit() {
-    Runfiles r1 = new Runfiles.Builder("TESTING").build()
+    Runfiles r1 = new Runfiles.Builder("TESTING", false).build()
         .setConflictPolicy(Runfiles.ConflictPolicy.WARN);
-    Runfiles r2 = new Runfiles.Builder("TESTING").merge(r1).build();
+    Runfiles r2 = new Runfiles.Builder("TESTING", false).merge(r1).build();
     assertEquals(Runfiles.ConflictPolicy.WARN, r2.getConflictPolicy());
   }
 
   @Test
   public void testBuilderMergeConflictPolicyInheritStrictest() {
-    Runfiles r1 = new Runfiles.Builder("TESTING").build()
+    Runfiles r1 = new Runfiles.Builder("TESTING", false).build()
         .setConflictPolicy(Runfiles.ConflictPolicy.WARN);
-    Runfiles r2 = new Runfiles.Builder("TESTING").build()
+    Runfiles r2 = new Runfiles.Builder("TESTING", false).build()
         .setConflictPolicy(Runfiles.ConflictPolicy.ERROR);
-    Runfiles r3 = new Runfiles.Builder("TESTING").merge(r1).merge(r2).build();
+    Runfiles r3 = new Runfiles.Builder("TESTING", false).merge(r1).merge(r2).build();
     assertEquals(Runfiles.ConflictPolicy.ERROR, r3.getConflictPolicy());
     // Swap ordering
-    Runfiles r4 = new Runfiles.Builder("TESTING").merge(r2).merge(r1).build();
+    Runfiles r4 = new Runfiles.Builder("TESTING", false).merge(r2).merge(r1).build();
     assertEquals(Runfiles.ConflictPolicy.ERROR, r4.getConflictPolicy());
   }
+
+  @Test
+  public void testLegacyRunfilesStructure() {
+    Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
+    PathFragment workspaceName = new PathFragment("wsname");
+    PathFragment pathB = new PathFragment("repo/b");
+    Artifact artifactB = new Artifact(pathB, root);
+
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        new Runfiles.ConflictChecker(Runfiles.ConflictPolicy.WARN, reporter, null),
+        workspaceName,
+        true);
+
+    builder.put(runfilesPath(pathB), artifactB);
+
+    assertThat(builder.build().entrySet()).containsExactly(
+        Maps.immutableEntry(workspaceName.getRelative(".runfile"), null),
+        Maps.immutableEntry(workspaceName.getRelative("external").getRelative(pathB), artifactB),
+        Maps.immutableEntry(pathB, artifactB));
+    assertNoEvents();
+  }
 }
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 a2a133cb90..5d32df7f1b 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
@@ -99,4 +99,12 @@ public class PackageIdentifierTest {
     PackageIdentifier p2 = PackageIdentifier.create("@whatever", new PathFragment("foo/bar"));
     assertSame(p2.getPackageFragment(), p1.getPackageFragment());
   }
+
+  @Test
+  public void testRunfilesDir() throws Exception {
+    assertThat(PackageIdentifier.create("@foo", new PathFragment("bar/baz")).getRunfilesPath())
+        .isEqualTo(new PathFragment("../foo/bar/baz"));
+    assertThat(PackageIdentifier.create("@", new PathFragment("bar/baz")).getRunfilesPath())
+        .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 b84af2fde6..9a39bbfda1 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
@@ -18,6 +18,7 @@ import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
+import com.google.devtools.build.lib.vfs.PathFragment;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -56,4 +57,14 @@ public class RepositoryNameTest {
     assertNotValid("@foo\0", "workspace names may contain only A-Z, a-z, 0-9, '-', '_' and '.'");
   }
 
+  @Test
+  public void testRunfilesDir() throws Exception {
+    assertThat(RepositoryName.create("@foo").getRunfilesPath())
+        .isEqualTo(new PathFragment("../foo"));
+    assertThat(RepositoryName.create("@").getRunfilesPath())
+        .isEqualTo(PathFragment.EMPTY_FRAGMENT);
+    assertThat(RepositoryName.create("").getRunfilesPath())
+        .isEqualTo(PathFragment.EMPTY_FRAGMENT);
+  }
+
 }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/MockToolsConfig.java b/src/test/java/com/google/devtools/build/lib/packages/util/MockToolsConfig.java
index 6207fde742..8b57ff53dc 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/MockToolsConfig.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/MockToolsConfig.java
@@ -123,12 +123,12 @@ public final class MockToolsConfig {
    */
   public void linkTool(String relativePath, String dest) throws IOException {
     Preconditions.checkState(realFileSystem);
-    Path target = runfilesDirectory.getRelative(TestConstants.RUNFILES_PREFIX + "/" + relativePath);
+    Path target = runfilesDirectory.getRelative(TestConstants.WORKSPACE_NAME + "/" + relativePath);
     if (!target.exists()) {
       // In some cases we run tests in a special client with a ../READONLY/ path where we may also
       // find the runfiles. Try that, too.
       Path readOnlyClientPath = rootDirectory.getRelative(
-          "../READONLY/" + TestConstants.RUNFILES_PREFIX + "/" + relativePath);
+          "../READONLY/" + TestConstants.WORKSPACE_NAME + "/" + relativePath);
       if (!readOnlyClientPath.exists()) {
         throw new IOException("target does not exist " + target);
       } else {
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 6d4fb51bef..cab180b1a5 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
@@ -38,17 +38,12 @@ public class TestConstants {
    * Location in the bazel repo where embedded binaries come from.
    */
   public static final ImmutableList<String> EMBEDDED_SCRIPTS_PATHS = ImmutableList.of(
-      "src/main/tools");
-
-  /**
-   * Path within runfiles tree for finding everything else.
-   */
-  public static final String RUNFILES_PREFIX = "DOES-NOT-WORK-YET";
+      "io_bazel/src/main/tools");
 
   /**
    * Default workspace name.
    */
-  public static final String WORKSPACE_NAME = "";
+  public static final String WORKSPACE_NAME = "__main__";
 
   /**
    * Name of a class with an INSTANCE field of type AnalysisMock to be used for analysis tests.
@@ -59,7 +54,7 @@ public class TestConstants {
   /**
    * Directory where we can find bazel's Java tests, relative to a test's runfiles directory.
    */
-  public static final String JAVATESTS_ROOT = "src/test/java/";
+  public static final String JAVATESTS_ROOT = "io_bazel/src/test/java/";
 
   public static final String TEST_RULE_CLASS_PROVIDER =
       "com.google.devtools.build.lib.bazel.rules.BazelRuleClassProvider";
diff --git a/src/test/shell/bazel/bazel_example_test.sh b/src/test/shell/bazel/bazel_example_test.sh
index b9d2aef276..93075fddb6 100755
--- a/src/test/shell/bazel/bazel_example_test.sh
+++ b/src/test/shell/bazel/bazel_example_test.sh
@@ -23,6 +23,9 @@ source $(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)/test-setup.sh \
 
 function set_up() {
   copy_examples
+  cat > WORKSPACE <<EOF
+workspace(name = "io_bazel")
+EOF
 }
 
 #
@@ -77,20 +80,6 @@ function test_java_test_with_junitrunner() {
   assert_test_ok "${java_native_tests}:custom_with_test_class"
 }
 
-function test_java_test_with_workspace_name() {
-  local java_pkg=examples/java-native/src/main/java/com/example/myproject
-  # Use named workspace and test if we can still execute hello-world
-  bazel clean
-
-  rm -f WORKSPACE
-  cat >WORKSPACE <<'EOF'
-workspace(name = "toto")
-EOF
-
-  assert_build_output ./bazel-bin/${java_pkg}/hello-world ${java_pkg}:hello-world
-  assert_binary_run_from_subdir "bazel-bin/${java_pkg}/hello-world foo" "Hello foo"
-}
-
 function test_genrule_and_genquery() {
   # The --javabase flag is to force the tools/jdk:jdk label to be used
   # so it appears in the dependency list.
diff --git a/src/test/shell/bazel/bazel_rules_test.sh b/src/test/shell/bazel/bazel_rules_test.sh
index b0f7e4e312..c82b9cd996 100755
--- a/src/test/shell/bazel/bazel_rules_test.sh
+++ b/src/test/shell/bazel/bazel_rules_test.sh
@@ -63,7 +63,7 @@ function test_extra_action() {
   # a program that parses the proto here.
   cat > mypkg/echoer.sh <<EOF
 #!/bin/bash
-if [[ ! -e \$0.runfiles/mypkg/runfile ]]; then
+if [[ ! -e \$0.runfiles/__main__/mypkg/runfile ]]; then
   echo "Runfile not found" >&2
   exit 1
 fi
@@ -357,8 +357,8 @@ def Fib(n):
 EOF
 
  cat > module2/bez.py <<EOF
-from external.remote.module_a import foo
-from external.remote.module_b import bar
+from remote.module_a import foo
+from remote.module_b import bar
 from module1 import fib
 
 print "The number is %d" % foo.GetNumber()
diff --git a/src/test/shell/bazel/bazel_sandboxing_test.sh b/src/test/shell/bazel/bazel_sandboxing_test.sh
index 27097bc9c1..9e6bc857d8 100755
--- a/src/test/shell/bazel/bazel_sandboxing_test.sh
+++ b/src/test/shell/bazel/bazel_sandboxing_test.sh
@@ -164,7 +164,7 @@ EOF
 #!/bin/sh
 
 set -e
-cp $(dirname $0)/tool.runfiles/examples/genrule/datafile $1
+cp $(dirname $0)/tool.runfiles/__main__/examples/genrule/datafile $1
 echo "Tools work!"
 EOF
   chmod +x examples/genrule/tool.sh
diff --git a/src/test/shell/bazel/external_integration_test.sh b/src/test/shell/bazel/external_integration_test.sh
index 6f3a6b03c0..e9c1bc6660 100755
--- a/src/test/shell/bazel/external_integration_test.sh
+++ b/src/test/shell/bazel/external_integration_test.sh
@@ -139,7 +139,7 @@ EOF
 
     cat > zoo/female.sh <<EOF
 #!/bin/bash
-./external/endangered/fox/male
+../endangered/fox/male
 EOF
     chmod +x zoo/female.sh
 fi
@@ -422,10 +422,10 @@ EOF
   cat > test/test.sh <<EOF
 #!/bin/bash
 echo "symlink:"
-ls -l external/toto/file
+ls -l ../toto/file
 echo "dest:"
-ls -l \$(readlink -f external/toto/file/toto)
-external/toto/file/toto
+ls -l \$(readlink -f ../toto/file/toto)
+../toto/file/toto
 EOF
 
   chmod +x test/test.sh
@@ -459,7 +459,7 @@ EOF
 
   cat > test/test.sh <<EOF
 #!/bin/bash
-cat external/toto/file/toto
+cat ../toto/file/toto
 EOF
 
   chmod +x test/test.sh
@@ -581,7 +581,7 @@ EOF
 
   cat > zoo/female.sh <<EOF
 #!/bin/bash
-cat external/endangered/fox/male
+cat ../endangered/fox/male
 EOF
   chmod +x zoo/female.sh
 
diff --git a/src/test/shell/bazel/generate_workspace_test.sh b/src/test/shell/bazel/generate_workspace_test.sh
index 18168459c9..584f3e04d8 100755
--- a/src/test/shell/bazel/generate_workspace_test.sh
+++ b/src/test/shell/bazel/generate_workspace_test.sh
@@ -24,8 +24,6 @@ source $src_dir/test-setup.sh \
 source $src_dir/remote_helpers.sh \
   || { echo "remote_helpers.sh not found!" >&2; exit 1; }
 
-export JAVA_RUNFILES=$TEST_SRCDIR
-
 function set_up() {
   # Set up custom repository directory.
   m2=$TEST_TMPDIR/my-m2
diff --git a/src/test/shell/bazel/git_repository_test.sh b/src/test/shell/bazel/git_repository_test.sh
index 67a630dd1b..2c862b7f7e 100755
--- a/src/test/shell/bazel/git_repository_test.sh
+++ b/src/test/shell/bazel/git_repository_test.sh
@@ -85,7 +85,7 @@ EOF
 
   cat > planets/planet_info.sh <<EOF
 #!/bin/bash
-cat external/pluto/info
+cat ../pluto/info
 EOF
   chmod +x planets/planet_info.sh
 
@@ -171,7 +171,7 @@ EOF
 
   cat > planets/planet_info.sh <<EOF
 #!/bin/bash
-cat external/pluto/info
+cat ../pluto/info
 EOF
   chmod +x planets/planet_info.sh
 
@@ -246,8 +246,8 @@ EOF
 
   cat > planets/planet_info.sh <<EOF
 #!/bin/bash
-cat external/outer_planets/neptune/info
-cat external/outer_planets/pluto/info
+cat ../outer_planets/neptune/info
+cat ../outer_planets/pluto/info
 EOF
   chmod +x planets/planet_info.sh
 
diff --git a/src/test/shell/bazel/local_repository_test.sh b/src/test/shell/bazel/local_repository_test.sh
index 0fad9c95f0..70f9be6769 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -95,7 +95,7 @@ EOF
 
   cat > zoo/dumper.sh <<EOF
 #!/bin/bash
-cat external/pandas/red/baby-panda
+cat ../pandas/red/baby-panda
 cat red/day-keeper
 EOF
   chmod +x zoo/dumper.sh
diff --git a/src/test/shell/bazel/testenv.sh b/src/test/shell/bazel/testenv.sh
index 14c39c0766..8820f93a6e 100755
--- a/src/test/shell/bazel/testenv.sh
+++ b/src/test/shell/bazel/testenv.sh
@@ -18,6 +18,7 @@
 #
 
 [ -z "$TEST_SRCDIR" ] && { echo "TEST_SRCDIR not set!" >&2; exit 1; }
+TEST_SRCDIR="$TEST_SRCDIR/io_bazel"
 
 # Load the unit-testing framework
 source "${TEST_SRCDIR}/src/test/shell/unittest.bash" || \
@@ -29,7 +30,7 @@ bazel="${TEST_SRCDIR}/src/bazel"
 bazel_data="${TEST_SRCDIR}"
 
 # Java
-jdk_dir="${TEST_SRCDIR}/external/local_jdk"
+jdk_dir="${TEST_SRCDIR}/../local_jdk"
 langtools="${TEST_SRCDIR}/src/test/shell/bazel/langtools.jar"
 
 # Tools directory location
diff --git a/src/test/shell/integration/runfiles_test.sh b/src/test/shell/integration/runfiles_test.sh
index 6821b30dcd..ee26ca130c 100755
--- a/src/test/shell/integration/runfiles_test.sh
+++ b/src/test/shell/integration/runfiles_test.sh
@@ -55,16 +55,16 @@ EOF
   bazel build pkg:py >&$TEST_log 2>&1 || fail "build failed"
 
   # we get a warning that hidden.py is inaccessible
-  expect_log_once "/genfiles/pkg/e/f/g/hidden.py obscured by pkg/e/f "
+  expect_log_once "/genfiles/pkg/e/f/g/hidden.py obscured by .*/pkg/e/f "
 }
 
 function test_foo_runfiles() {
-cat > BUILD << EOF
+  cat > BUILD << EOF
 py_library(name = "root",
            srcs = ["__init__.py"],
            visibility = ["//visibility:public"])
 EOF
-cat > pkg/BUILD << EOF
+  cat > pkg/BUILD << EOF
 sh_binary(name = "foo",
           srcs = [ "x/y/z.sh" ],
           data = [ ":py",
@@ -149,4 +149,3 @@ EOF
 }
 
 run_suite "runfiles"
-
diff --git a/third_party/ijar/test/BUILD b/third_party/ijar/test/BUILD
index f8ebb2a612..da06173368 100644
--- a/third_party/ijar/test/BUILD
+++ b/third_party/ijar/test/BUILD
@@ -9,12 +9,12 @@ sh_test(
     size = "enormous",
     srcs = ["ijar_test.sh"],
     args = [
-        "$(JAVABASE)/bin/javac",
-        "$(JAVA)",
-        "$(JAVABASE)/bin/jar",
-        "$(JAVABASE)/bin/javap",
-        "$(location //third_party/ijar)",
-        "$(location //tools/jdk:langtools)",
+        "../local_jdk/bin/javac",
+        "../local_jdk/bin/java",
+        "../local_jdk/bin/jar",
+        "../local_jdk/bin/javap",
+        "io_bazel/$(location //third_party/ijar)",
+        "io_bazel/$(location //tools/jdk:langtools)",
         # We assume unzip and zip to be on the path
         "unzip",
         "zip",
diff --git a/third_party/ijar/test/testenv.sh b/third_party/ijar/test/testenv.sh
index 66c4811428..235f2c5948 100755
--- a/third_party/ijar/test/testenv.sh
+++ b/third_party/ijar/test/testenv.sh
@@ -20,7 +20,7 @@
 [ -z "$TEST_SRCDIR" ] && { echo "TEST_SRCDIR not set!" >&2; exit 1; }
 
 # Load the unit-testing framework
-source "${TEST_SRCDIR}/src/test/shell/unittest.bash" || \
+source "${TEST_SRCDIR}/io_bazel/src/test/shell/unittest.bash" || \
   { echo "Failed to source unittest.bash" >&2; exit 1; }
 
 ## OSX/BSD stat and MD5