diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/DecompressorFactory.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/DecompressorFactory.java
index d3001a4..947e224 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/DecompressorFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/DecompressorFactory.java
@@ -42,13 +42,14 @@
  */
 public abstract class DecompressorFactory {
 
-  public static Decompressor create(String targetKind, String targetName, Path archivePath)
+  public static Decompressor create(
+      String targetKind, String targetName, Path archivePath, Path repositoryPath)
       throws DecompressorException {
     String baseName = archivePath.getBaseName();
 
     if (targetKind.startsWith(HttpJarRule.NAME + " ")) {
       if (baseName.endsWith(".jar")) {
-        return new JarDecompressor(targetKind, targetName, archivePath);
+        return new JarDecompressor(targetKind, targetName, archivePath, repositoryPath);
       } else {
         throw new DecompressorException(
             "Expected " + HttpJarRule.NAME + " " + targetName
@@ -95,34 +96,36 @@
   static class JarDecompressor extends Decompressor {
     private final String targetKind;
     private final String targetName;
+    private final Path repositoryDir;
 
-    public JarDecompressor(String targetKind, String targetName, Path archiveFile) {
+    public JarDecompressor(
+        String targetKind, String targetName, Path archiveFile, Path repositoryDir) {
       super(archiveFile);
       this.targetKind = targetKind;
       this.targetName = targetName;
+      this.repositoryDir = repositoryDir;
     }
 
     /**
      * The .jar can be used compressed, so this just exposes it in a way Bazel can use.
      *
-     * <p>It moves the jar from some-name/foo.jar to some-name/repository/jar/foo.jar and creates a
-     * BUILD file containing one entry: a .jar.
+     * <p>It moves the jar from some-name/x/y/z/foo.jar to some-name/jar/foo.jar and creates a
+     * BUILD file containing one entry: the .jar.
      */
     @Override
     public Path decompress() throws DecompressorException {
-      Path destinationDirectory = archiveFile.getParentDirectory().getRelative("repository");
       // Example: archiveFile is .external-repository/some-name/foo.jar.
       String baseName = archiveFile.getBaseName();
 
       try {
-        FileSystemUtils.createDirectoryAndParents(destinationDirectory);
-        // .external-repository/some-name/repository/WORKSPACE.
-        Path workspaceFile = destinationDirectory.getRelative("WORKSPACE");
+        FileSystemUtils.createDirectoryAndParents(repositoryDir);
+        // .external-repository/some-name/WORKSPACE.
+        Path workspaceFile = repositoryDir.getRelative("WORKSPACE");
         FileSystemUtils.writeContent(workspaceFile, Charset.forName("UTF-8"),
             "# DO NOT EDIT: automatically generated WORKSPACE file for " + targetKind
                 + " rule " + targetName);
-        // .external-repository/some-name/repository/jar.
-        Path jarDirectory = destinationDirectory.getRelative("jar");
+        // .external-repository/some-name/jar.
+        Path jarDirectory = repositoryDir.getRelative("jar");
         FileSystemUtils.createDirectoryAndParents(jarDirectory);
         // .external-repository/some-name/repository/jar/foo.jar is a symbolic link to the jar in
         // .external-repository/some-name.
@@ -141,9 +144,10 @@
             "    visibility = ['//visibility:public']",
             ")");
       } catch (IOException e) {
-        throw new DecompressorException(e.getMessage());
+        throw new DecompressorException(
+            "Error auto-creating jar repo structure: " + e.getMessage());
       }
-      return destinationDirectory;
+      return repositoryDir;
     }
   }
 
@@ -169,7 +173,7 @@
      */
     @Override
     public Path decompress() throws DecompressorException {
-      Path destinationDirectory = archiveFile.getParentDirectory().getRelative("repository");
+      Path destinationDirectory = archiveFile.getParentDirectory();
       try (InputStream is = new FileInputStream(archiveFile.getPathString())) {
         ArchiveInputStream in = new ArchiveStreamFactory().createArchiveInputStream(
             ArchiveStreamFactory.ZIP, is);
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/HttpArchiveFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/HttpArchiveFunction.java
index a8beb56..4ecb299 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/HttpArchiveFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/HttpArchiveFunction.java
@@ -90,7 +90,7 @@
     try {
       Path archiveFile = downloader.download();
       outputDirectory = DecompressorFactory.create(
-          rule.getTargetKind(), rule.getName(), archiveFile).decompress();
+          rule.getTargetKind(), rule.getName(), archiveFile, outputDirectory).decompress();
     } catch (IOException e) {
       // Assumes all IO errors transient.
       throw new RepositoryFunctionException(e, Transience.TRANSIENT);
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/LocalRepositoryFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/LocalRepositoryFunction.java
index 1a72dad..3a2fda0 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/LocalRepositoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/LocalRepositoryFunction.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.skyframe.FileValue;
 import com.google.devtools.build.lib.skyframe.RepositoryValue;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunctionException;
@@ -56,7 +57,18 @@
               "In " + rule + " the 'path' attribute must specify an absolute path"),
           Transience.PERSISTENT);
     }
-    Path repositoryPath = getOutputBase().getFileSystem().getPath(pathFragment);
+    Path repositoryPath = getExternalRepositoryDirectory().getRelative(rule.getName());
+    try {
+      FileSystemUtils.createDirectoryAndParents(repositoryPath.getParentDirectory());
+      if (repositoryPath.exists()) {
+        repositoryPath.delete();
+      }
+      repositoryPath.createSymbolicLink(pathFragment);
+    } catch (IOException e) {
+      throw new RepositoryFunctionException(
+          new IOException("Could not create symlink to repository " + pathFragment + ": "
+              + e.getMessage()), Transience.TRANSIENT);
+    }
     FileValue repositoryValue = getRepositoryDirectory(repositoryPath, env);
     if (repositoryValue == null) {
       return null;
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenJarFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenJarFunction.java
index 72834bf..e7571cf 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenJarFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenJarFunction.java
@@ -110,7 +110,8 @@
 
     // Add a WORKSPACE file & BUILD file to the Maven jar.
     JarDecompressor decompressor = new JarDecompressor(
-        MavenJarRule.NAME, downloader.getName(), repositoryJar);
+        MavenJarRule.NAME, downloader.getName(), repositoryJar,
+        outputDirectoryValue.realRootedPath().asPath());
     Path repositoryDirectory = null;
     try {
       repositoryDirectory = decompressor.decompress();
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/NewHttpArchiveFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/NewHttpArchiveFunction.java
index af9ad22..daa0046 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/NewHttpArchiveFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/NewHttpArchiveFunction.java
@@ -69,7 +69,8 @@
     Path decompressedDirectory;
     try {
       decompressedDirectory = DecompressorFactory.create(
-          rule.getTargetKind(), rule.getName(), downloadedFileValue.getPath()).decompress();
+          rule.getTargetKind(), rule.getName(), downloadedFileValue.getPath(), outputDirectory)
+          .decompress();
     } catch (DecompressorFactory.DecompressorException e) {
       throw new RepositoryFunctionException(
           new IOException(e.getMessage()), SkyFunctionException.Transience.TRANSIENT);
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/NewLocalRepositoryFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/NewLocalRepositoryFunction.java
index 510d36c..807857e 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/NewLocalRepositoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/NewLocalRepositoryFunction.java
@@ -20,13 +20,16 @@
 import com.google.devtools.build.lib.packages.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Type;
+import com.google.devtools.build.lib.skyframe.FileSymlinkCycleException;
 import com.google.devtools.build.lib.skyframe.FileValue;
+import com.google.devtools.build.lib.skyframe.InconsistentFilesystemException;
 import com.google.devtools.build.lib.skyframe.RepositoryValue;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -66,8 +69,10 @@
     //     w -> /some/path/to/y/w
     //     v -> /some/path/to/y/v
     //
+    // Create x/
     Path repositoryDirectory = getExternalRepositoryDirectory().getRelative(rule.getName());
     try {
+      FileSystemUtils.deleteTree(repositoryDirectory);
       FileSystemUtils.createDirectoryAndParents(repositoryDirectory);
     } catch (IOException e) {
       throw new RepositoryFunctionException(e, Transience.TRANSIENT);
@@ -158,9 +163,21 @@
         from.createSymbolicLink(to);
       }
     } catch (IOException e) {
-      throw new RepositoryFunctionException(e, Transience.TRANSIENT);
+      throw new RepositoryFunctionException(
+          new IOException("Error creating symbolic link from " + from + " to " + to + ": "
+              + e.getMessage()), Transience.TRANSIENT);
     }
-    return getRepositoryDirectory(from, env);
+
+    SkyKey outputDirectoryKey = FileValue.key(RootedPath.toRootedPath(
+        from, PathFragment.EMPTY_FRAGMENT));
+    try {
+      return (FileValue) env.getValueOrThrow(outputDirectoryKey, IOException.class,
+          FileSymlinkCycleException.class, InconsistentFilesystemException.class);
+    } catch (IOException | FileSymlinkCycleException | InconsistentFilesystemException e) {
+      throw new RepositoryFunctionException(
+          new IOException("Could not access " + from + ": " + e.getMessage()),
+          Transience.PERSISTENT);
+    }
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java
index 632aa0d..0ccf02e 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java
@@ -30,6 +30,7 @@
 import com.google.devtools.build.lib.skyframe.PackageFunction;
 import com.google.devtools.build.lib.skyframe.PackageValue;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -137,27 +138,46 @@
   /**
    * Adds the repository's directory to the graph and, if it's a symlink, resolves it to an
    * actual directory.
+   *
+   * <p>Also creates a symlink from x/external/x to x, where x is the directory containing a
+   * WORKSPACE file. This is used in the execution root.</p>
    */
   @Nullable
   protected static FileValue getRepositoryDirectory(Path repositoryDirectory, Environment env)
       throws RepositoryFunctionException {
     SkyKey outputDirectoryKey = FileValue.key(RootedPath.toRootedPath(
         repositoryDirectory, PathFragment.EMPTY_FRAGMENT));
+    FileValue value;
     try {
-      return (FileValue) env.getValueOrThrow(outputDirectoryKey, IOException.class,
+      value = (FileValue) env.getValueOrThrow(outputDirectoryKey, IOException.class,
           FileSymlinkCycleException.class, InconsistentFilesystemException.class);
     } catch (IOException | FileSymlinkCycleException | InconsistentFilesystemException e) {
       throw new RepositoryFunctionException(
           new IOException("Could not access " + repositoryDirectory + ": " + e.getMessage()),
           Transience.PERSISTENT);
     }
+
+    String targetName = repositoryDirectory.getBaseName();
+    try {
+      Path backlink = repositoryDirectory.getRelative("external").getRelative(targetName);
+      FileSystemUtils.createDirectoryAndParents(backlink.getParentDirectory());
+      if (backlink.exists()) {
+        backlink.delete();
+      }
+      backlink.createSymbolicLink(repositoryDirectory);
+    } catch (IOException e) {
+      throw new RepositoryFunctionException(new IOException(
+          "Error creating execution root symlink for " + targetName + ": " + e.getMessage()),
+          Transience.TRANSIENT);
+    }
+    return value;
   }
 
   /**
    * Exception thrown when something goes wrong accessing a remote repository.
    *
-   * This exception should be used by child classes to limit the types of exceptions
-   * {@link RepositoryDelegatorFunction} has to know how to catch.
+   * <p>This exception should be used by child classes to limit the types of exceptions
+   * {@link RepositoryDelegatorFunction} has to know how to catch.</p>
    */
   static final class RepositoryFunctionException extends SkyFunctionException {
     public RepositoryFunctionException(NoSuchPackageException cause, Transience transience) {
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java
index 63c17df..a9c3ec8 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java
@@ -294,7 +294,7 @@
       ImmutableMap<PackageIdentifier, Path> second) {
     Map<PathFragment, Path> builder = Maps.newHashMap();
     for (Map.Entry<PackageIdentifier, Path> entry : first.entrySet()) {
-      builder.put(entry.getKey().getPackageFragment(), entry.getValue());
+      builder.put(entry.getKey().getPathFragment(), entry.getValue());
     }
     for (Map.Entry<PackageIdentifier, Path> entry : second.entrySet()) {
       if (first.containsKey(entry.getKey())) {
diff --git a/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java b/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
index aa089e5..913959e 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
@@ -40,7 +40,7 @@
   private Map<RepositoryName, Rule> repositoryMap;
 
   ExternalPackage() {
-    super(PackageIdentifier.createInDefaultRepo("external"));
+    super(PackageIdentifier.createInDefaultRepo(NAME));
   }
 
   /**
@@ -93,7 +93,7 @@
      * Checks if the label is bound, i.e., starts with {@code //external:}.
      */
     public static boolean isBoundLabel(Label label) {
-      return label.getPackageName().equals("external");
+      return label.getPackageName().equals(NAME);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/InputFile.java b/src/main/java/com/google/devtools/build/lib/packages/InputFile.java
index 130e2b7..89f1c0d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/InputFile.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/InputFile.java
@@ -99,7 +99,7 @@
    * Returns the exec path of the file, i.e. the path relative to the package source root.
    */
   public PathFragment getExecPath() {
-    return label.toPathFragment();
+    return label.getPackageIdentifier().getPathFragment().getRelative(label.getName());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java b/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java
index 5ff17ae..fd9d0ea 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java
@@ -233,6 +233,16 @@
   }
 
   /**
+   * Returns a relative path that should be unique across all remote and packages, based on the
+   * repository and package names.
+   */
+  public PathFragment getPathFragment() {
+    return repository.isDefault() ? pkgName
+        : new PathFragment(ExternalPackage.NAME).getRelative(repository.strippedName())
+            .getRelative(pkgName);
+  }
+
+  /**
    * Returns the name of this package.
    *
    * <p>There are certain places that expect the path fragment as the package name ('foo/bar') as a
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java
index 69dc41b..ace7deb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java
@@ -129,8 +129,8 @@
 
   private Artifact getIjarArtifact(Artifact jar, boolean addPrefix) {
     if (addPrefix) {
-      PathFragment ruleBase = ruleContext.getLabel().getPackageFragment().getRelative(
-          ruleContext.getLabel().getName()).getRelative("_ijars");
+      PathFragment ruleBase = ruleContext.getLabel().getPackageIdentifier().getPathFragment()
+              .getRelative(ruleContext.getLabel().getName()).getRelative("_ijars");
       PathFragment artifactDirFragment = jar.getRootRelativePath().getParentDirectory();
       String ijarBasename = FileSystemUtils.removeExtension(jar.getFilename()) + "-ijar.jar";
       return getAnalysisEnvironment().getDerivedArtifact(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java b/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java
index ec7e926..d2f7c27 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JvmConfigurationLoader.java
@@ -114,7 +114,7 @@
             if (jvmTarget.getLabel().getPackageIdentifier().getRepository().isDefault()) {
               javaHomePath = jvmLabel.getPackageFragment();
             } else {
-              javaHomePath = jvmTarget.getLabel().getPackageFragment();
+              javaHomePath = jvmTarget.getLabel().getPackageIdentifier().getPathFragment();
             }
 
             if ((jvmTarget instanceof Rule) &&