Make the execution root match the runfiles tree structure for external repositories

One interesting side effect of how this is implemented is that for external
repositories, bin/ and genfiles/ are combined.  External repo output is under
bazel-out/local-fastbuild/repo_name for each repo.

Fixes #1262.

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

--
MOS_MIGRATED_REVID=125095799
diff --git a/scripts/bootstrap/compile.sh b/scripts/bootstrap/compile.sh
index 6faa330..a241213 100755
--- a/scripts/bootstrap/compile.sh
+++ b/scripts/bootstrap/compile.sh
@@ -271,7 +271,7 @@
       --output_base=${OUTPUT_DIR}/out \
       --install_md5= \
       --workspace_directory=${PWD} \
-      --nodeep_execroot --nofatal_event_bus_exceptions \
+      --nofatal_event_bus_exceptions \
       build \
       --ignore_unsupported_sandboxing \
       --startup_time=329 --extract_data_time=523 \
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 790cfbc..2c2401d 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,7 +14,7 @@
     outs = ["JavacBootclasspathLocations.java"],
     cmd = """
 declare -a paths=($(SRCS)) && paths=($${paths[@]#$(GENDIR)/}) &&
-paths=($$(echo $${paths[@]} | sed s_external/__g)) &&
+paths=($$(echo $${paths[@]} | sed 's_\.\./__g')) &&
 IFS=: &&
 cat > $@ <<EOF
 package com.google.devtools.build.java.bazel;
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 b3b8682..4c4a5e1 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
@@ -46,12 +46,13 @@
 /**
  * An Artifact represents a file used by the build system, whether it's a source
  * file or a derived (output) file. Not all Artifacts have a corresponding
- * FileTarget object in the <code>build.packages</code> API: for example,
+ * FileTarget object in the <code>build.lib.packages</code> API: for example,
  * low-level intermediaries internal to a given rule, such as a Java class files
  * or C++ object files. However all FileTargets have a corresponding Artifact.
  *
- * <p>In any given call to Builder#buildArtifacts(), no two Artifacts in the
- * action graph may refer to the same path.
+ * <p>In any given call to
+ * {@link com.google.devtools.build.lib.skyframe.SkyframeExecutor#buildArtifacts}, no two Artifacts
+ * in the action graph may refer to the same path.
  *
  * <p>Artifacts generally fall into two classifications, source and derived, but
  * there exist a few other cases that are fuzzy and difficult to classify. The
@@ -154,6 +155,64 @@
   private final PathFragment rootRelativePath;
   private final ArtifactOwner owner;
 
+  private static boolean pathEndsWith(PathFragment path, PathFragment suffix) {
+    if (suffix.isNormalized()) {
+      return path.endsWith(suffix);
+    }
+
+    for (int suffixIndex = suffix.segmentCount() - 1, pathIndex = path.segmentCount() - 1;
+         suffixIndex >= 0; suffixIndex--) {
+      if (suffix.getSegment(suffixIndex).equals("..")) {
+        if (suffixIndex > 0) {
+          // The path foo/bar/../baz matches the suffix foo/baz.
+          suffixIndex--;
+          continue;
+        } else {
+          // The path repo/foo matches the suffix ../repo/foo.
+          return true;
+        }
+      }
+      if (pathIndex < 0 || !path.getSegment(pathIndex).equals(suffix.getSegment(suffixIndex))) {
+        return false;
+      }
+      pathIndex--;
+    }
+
+    return true;
+  }
+
+  // Like startsWith, but allows prefix to match the path.getParentDirectory() instead of just
+  // path (so that bazel-out/config/repo/foo "starts with" bazel-out/config/bin).
+  private static boolean pathMostlyStartsWith(Path path, Path prefix) {
+    return path.startsWith(prefix) || path.startsWith(prefix.getParentDirectory());
+  }
+
+  private static PathFragment getRelativePath(PathFragment path, PathFragment ancestorDirectory) {
+    if (path.startsWith(ancestorDirectory)) {
+      // Local path.
+      return path.relativeTo(ancestorDirectory);
+    }
+
+    // External repository.
+    int ancestorLength = ancestorDirectory.segmentCount();
+
+    PathFragment builder = PathFragment.EMPTY_FRAGMENT;
+    int diffIndex = -1;
+    for (int i = 0; i < ancestorLength; i++) {
+      if (diffIndex == -1 && i < path.segmentCount()
+          && ancestorDirectory.getSegment(i).equals(path.getSegment(i))) {
+        continue;
+      }
+      diffIndex = i;
+      builder = builder.getRelative("..");
+    }
+    int tailIndex = diffIndex == -1 ? ancestorLength : diffIndex;
+    for (int i = tailIndex; i < path.segmentCount(); i++) {
+      builder = builder.getRelative(path.getSegment(i));
+    }
+    return builder;
+  }
+
   /**
    * Constructs an artifact for the specified path, root and execPath. The root must be an ancestor
    * of path, and execPath must be a non-absolute tail of path. Outside of testing, this method
@@ -166,18 +225,18 @@
    * </pre>
    *
    * <p>In a derived Artifact, the execPath will overlap with part of the root, which in turn will
-   * be below of the execRoot.
+   * be below the execRoot.
    * <pre>
    *  [path] == [/root][pathTail] == [/execRoot][execPath] == [/execRoot][rootPrefix][pathTail]
    * <pre>
    */
   @VisibleForTesting
   public Artifact(Path path, Root root, PathFragment execPath, ArtifactOwner owner) {
-    if (root == null || !path.startsWith(root.getPath())) {
+    if (root == null || !pathMostlyStartsWith(path, root.getPath())) {
       throw new IllegalArgumentException(root + ": illegal root for " + path
           + " (execPath: " + execPath + ")");
     }
-    if (execPath == null || execPath.isAbsolute() || !path.asFragment().endsWith(execPath)) {
+    if (execPath == null || execPath.isAbsolute() || !pathEndsWith(path.asFragment(), execPath)) {
       throw new IllegalArgumentException(execPath + ": illegal execPath for " + path
           + " (root: " + root + ")");
     }
@@ -188,12 +247,14 @@
     // These two lines establish the invariant that
     // execPath == rootRelativePath <=> execPath.equals(rootRelativePath)
     // This is important for isSourceArtifact.
-    PathFragment rootRel = path.relativeTo(root.getPath());
-    if (!execPath.endsWith(rootRel)) {
+    PathFragment rootRel = getRelativePath(path.asFragment(), root.getPath().asFragment());
+    if (!pathEndsWith(execPath, rootRel)) {
       throw new IllegalArgumentException(execPath + ": illegal execPath doesn't end with "
           + rootRel + " at " + path + " with root " + root);
     }
-    this.rootRelativePath = rootRel.equals(execPath) ? execPath : rootRel;
+
+    this.rootRelativePath = root.getPath().getRelative(rootRel).asFragment().normalize().equals(
+        root.getPath().getRelative(execPath).asFragment().normalize()) ? execPath : rootRel;
     this.owner = Preconditions.checkNotNull(owner, path);
   }
 
@@ -498,16 +559,10 @@
   /**
    * For targets in external repositories, this returns the path the artifact live at in the
    * runfiles tree. For local targets, it returns the rootRelativePath.
+   * TODO(kchodorow): remove.
    */
   public final PathFragment getRunfilesPath() {
-    PathFragment relativePath = rootRelativePath;
-    if (relativePath.segmentCount() > 1
-        && relativePath.getSegment(0).equals(Label.EXTERNAL_PATH_PREFIX)) {
-      // Turn external/repo/foo into ../repo/foo.
-      relativePath = relativePath.relativeTo(Label.EXTERNAL_PATH_PREFIX);
-      relativePath = new PathFragment("..").getRelative(relativePath);
-    }
-    return relativePath;
+    return getRootRelativePath();
   }
 
   @SkylarkCallable(
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
index 2642687..48960c5 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
@@ -200,7 +201,8 @@
 
   private void validatePath(PathFragment rootRelativePath, Root root) {
     Preconditions.checkArgument(!rootRelativePath.isAbsolute(), rootRelativePath);
-    Preconditions.checkArgument(rootRelativePath.isNormalized(), rootRelativePath);
+    Preconditions.checkArgument(
+        root.getWorkspaceDirectory().getRelative(rootRelativePath).normalize().isNormalized());
     Preconditions.checkArgument(root.getPath().startsWith(execRoot), "%s %s", root, execRoot);
     Preconditions.checkArgument(!root.getPath().equals(execRoot), "%s %s", root, execRoot);
     // TODO(bazel-team): this should only accept roots from derivedRoots.
@@ -314,7 +316,9 @@
     PathFragment execPath =
         baseExecPath == null ? relativePath : baseExecPath.getRelative(relativePath);
     execPath = execPath.normalize();
-    if (execPath.containsUplevelReferences()) {
+    if (execPath.containsUplevelReferences()
+        && (execPath.segmentCount() >= 2
+        && !execPath.startsWith(new PathFragment(Label.EXTERNAL_PATH_PREFIX)))) {
       // Source exec paths cannot escape the source root.
       return null;
     }
@@ -375,8 +379,9 @@
 
     for (PathFragment execPath : execPaths) {
       PathFragment execPathNormalized = execPath.normalize();
-      if (execPathNormalized.containsUplevelReferences()) {
-        // Source exec paths cannot escape the source root.
+      if (execPathNormalized.subFragment(1, execPathNormalized.segmentCount())
+          .containsUplevelReferences()) {
+        // Source exec paths cannot escape the execution root.
         result.put(execPath, null);
         continue;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Root.java b/src/main/java/com/google/devtools/build/lib/actions/Root.java
index b09dfa3..f92e4bd 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Root.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Root.java
@@ -122,6 +122,10 @@
     return execPath;
   }
 
+  public PathFragment getWorkspaceDirectory() {
+    return new PathFragment(isSourceRoot() ? path.getBaseName() : execRoot.getBaseName());
+  }
+
   @SkylarkCallable(name = "path", structField = true,
       doc = "Returns the relative path from the exec root to the actual root.")
   public String getExecPathString() {
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 d1f1434..273506f 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
@@ -428,7 +428,7 @@
     Map<PathFragment, Artifact> manifest = getSymlinksAsMap(checker);
     // Add unconditional artifacts (committed to inclusion on construction of runfiles).
     for (Artifact artifact : getUnconditionalArtifactsWithoutMiddlemen()) {
-      checker.put(manifest, artifact.getRootRelativePath(), artifact);
+      checker.put(manifest, artifact.getRootRelativePath().normalize(), artifact);
     }
 
     // Add conditional artifacts (only included if they appear in a pruning manifest).
@@ -485,7 +485,7 @@
     // workspace.
     private boolean sawWorkspaceName;
 
-    public ManifestBuilder(
+    ManifestBuilder(
         PathFragment workspaceName, boolean legacyExternalRunfiles) {
       this.manifest = new HashMap<>();
       this.workspaceName = workspaceName;
@@ -496,20 +496,18 @@
     /**
      * Adds a map under the workspaceName.
      */
-    public void addUnderWorkspace(
+    void addUnderWorkspace(
         Map<PathFragment, Artifact> inputManifest, ConflictChecker checker) {
       for (Map.Entry<PathFragment, Artifact> entry : inputManifest.entrySet()) {
         PathFragment path = entry.getKey();
         if (isUnderWorkspace(path)) {
           sawWorkspaceName = true;
-          checker.put(manifest, workspaceName.getRelative(path), entry.getValue());
-        } else {
-          if (legacyExternalRunfiles) {
-            checker.put(manifest, workspaceName.getRelative(path), entry.getValue());
-          }
-          // Always add the non-legacy .runfiles/repo/whatever path.
-          checker.put(manifest, getExternalPath(path), entry.getValue());
+        } else if (legacyExternalRunfiles) {
+          // Turn ../repo/foo info wsname/external/repo/foo.
+          checker.put(manifest, workspaceName.getRelative(Label.EXTERNAL_PACKAGE_NAME)
+              .getRelative(workspaceName).getRelative(path).normalize(), entry.getValue());
         }
+        checker.put(manifest, workspaceName.getRelative(path).normalize(), entry.getValue());
       }
     }
 
@@ -536,17 +534,14 @@
       return manifest;
     }
 
-    private PathFragment getExternalPath(PathFragment path) {
-      return checkForWorkspace(path.relativeTo(Label.EXTERNAL_PACKAGE_NAME));
-    }
-
     private PathFragment checkForWorkspace(PathFragment path) {
-      sawWorkspaceName = sawWorkspaceName || path.getSegment(0).equals(workspaceName);
+      sawWorkspaceName = sawWorkspaceName
+          || path.getSegment(0).equals(workspaceName.getPathString());
       return path;
     }
 
     private static boolean isUnderWorkspace(PathFragment path) {
-      return !path.startsWith(Label.EXTERNAL_PACKAGE_NAME);
+      return !path.startsWith(new PathFragment(Label.EXTERNAL_PATH_PREFIX));
     }
   }
 
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 e906c11..8168651 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
@@ -205,7 +205,7 @@
                 }
                 PathFragment relPath =
                     ruleContext.getRule().getLabel().getPackageIdentifier().getPathFragment();
-                return dir.getRelative(relPath).getPathString();
+                return dir.getRelative(relPath).normalize().getPathString();
               }
             } else {
               return super.lookupMakeVariable(name);
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 a11cd65..0346514 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
@@ -18,7 +18,6 @@
 import com.google.common.base.Stopwatch;
 import com.google.common.base.Throwables;
 import com.google.common.base.Verify;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.BuildFailedException;
 import com.google.devtools.build.lib.actions.TestExecException;
 import com.google.devtools.build.lib.analysis.AnalysisPhaseCompleteEvent;
@@ -73,11 +72,8 @@
 import com.google.devtools.build.lib.util.AbruptExitException;
 import com.google.devtools.build.lib.util.ExitCode;
 import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.lib.vfs.Path;
-import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.Collection;
-import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.TimeUnit;
 import java.util.logging.Logger;
@@ -204,7 +200,7 @@
       if (needsExecutionPhase(request.getBuildOptions())) {
         env.getSkyframeExecutor().injectTopLevelContext(request.getTopLevelArtifactContext());
         executionTool.executeBuild(request.getId(), analysisResult, result,
-            configurations, transformPackageRoots(analysisResult.getPackageRoots()));
+            configurations, analysisResult.getPackageRoots());
       }
 
       String delayedErrorMsg = analysisResult.getError();
@@ -299,15 +295,6 @@
     }
   }
 
-  private ImmutableMap<PathFragment, Path> transformPackageRoots(
-      ImmutableMap<PackageIdentifier, Path> packageRoots) {
-    ImmutableMap.Builder<PathFragment, Path> builder = ImmutableMap.builder();
-    for (Map.Entry<PackageIdentifier, Path> entry : packageRoots.entrySet()) {
-      builder.put(entry.getKey().getPathFragment(), entry.getValue());
-    }
-    return builder.build();
-  }
-
   private void reportExceptionError(Exception e) {
     if (e.getMessage() != null) {
       getReporter().handle(Event.error(e.getMessage()));
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
index a07fb9d..c809e64 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionTool.java
@@ -61,6 +61,7 @@
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection;
 import com.google.devtools.build.lib.buildtool.buildevent.ExecutionPhaseCompleteEvent;
 import com.google.devtools.build.lib.buildtool.buildevent.ExecutionStartingEvent;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.EventKind;
@@ -121,6 +122,7 @@
  * @see BuildView
  */
 public class ExecutionTool {
+
   private static class StrategyConverter {
     private Table<Class<? extends ActionContext>, String, ActionContext> classMap =
         HashBasedTable.create();
@@ -333,9 +335,9 @@
    * creation
    */
   void executeBuild(UUID buildId, AnalysisResult analysisResult,
-      BuildResult buildResult,
-      BuildConfigurationCollection configurations,
-      ImmutableMap<PathFragment, Path> packageRoots)
+                    BuildResult buildResult,
+                    BuildConfigurationCollection configurations,
+                    Map<PackageIdentifier, Path> packageRoots)
       throws BuildFailedException, InterruptedException, TestExecException, AbruptExitException {
     Stopwatch timer = Stopwatch.createStarted();
     prepare(packageRoots);
@@ -495,8 +497,7 @@
     }
   }
 
-  private void prepare(ImmutableMap<PathFragment, Path> packageRoots)
-      throws ExecutorInitException {
+  private void prepare(Map<PackageIdentifier, Path> packageRoots) throws ExecutorInitException {
     // Prepare for build.
     Profiler.instance().markPhase(ProfilePhase.PREPARE);
 
@@ -515,12 +516,12 @@
     }
   }
 
-  private void plantSymlinkForest(ImmutableMap<PathFragment, Path> packageRoots)
+  private void plantSymlinkForest(Map<PackageIdentifier, Path> packageRoots)
       throws ExecutorInitException {
     try {
-      FileSystemUtils.deleteTreesBelowNotPrefixed(getExecRoot(),
-          new String[] { ".", "_", runtime.getProductName() + "-"});
-      FileSystemUtils.plantLinkForest(packageRoots, getExecRoot(), runtime.getProductName());
+      SymlinkForest forest = new SymlinkForest(
+          packageRoots, getExecRoot(), runtime.getProductName());
+      forest.plantLinkForest();
     } catch (IOException e) {
       throw new ExecutorInitException("Source forest creation failed", e);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/SymlinkForest.java b/src/main/java/com/google/devtools/build/lib/buildtool/SymlinkForest.java
new file mode 100644
index 0000000..4cf27eb
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/SymlinkForest.java
@@ -0,0 +1,206 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.buildtool;
+
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.io.IOException;
+import java.util.Map;
+import java.util.Set;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+/**
+ * Creates a symlink forest based on a package path map.
+ */
+class SymlinkForest {
+
+  private static final Logger LOG = Logger.getLogger(SymlinkForest.class.getName());
+  private static final boolean LOG_FINER = LOG.isLoggable(Level.FINER);
+
+  private final Map<PackageIdentifier, Path> packageRoots;
+  private final Path workspace;
+  private final String productName;
+
+  SymlinkForest(
+      Map<PackageIdentifier, Path> packageRoots, Path workspace, String productName) {
+    this.packageRoots = packageRoots;
+    this.workspace = workspace;
+    this.productName = productName;
+  }
+
+  /**
+   * Takes a map of directory fragments to root paths, and creates a symlink
+   * forest under an existing linkRoot to the corresponding source dirs or
+   * files. Symlink are made at the highest dir possible, linking files directly
+   * only when needed with nested packages.
+   */
+  void plantLinkForest() throws IOException {
+    deleteExisting();
+
+    // Create a sorted map of all dirs (packages and their ancestors) to sets of their roots.
+    // Packages come from exactly one root, but their shared ancestors may come from more.
+    // The map is maintained sorted lexicographically, so parents are before their children.
+    Map<PackageIdentifier, Set<Path>> dirRootsMap = Maps.newTreeMap();
+    for (Map.Entry<PackageIdentifier, Path> entry : packageRoots.entrySet()) {
+      PackageIdentifier packageIdentifier = entry.getKey();
+      PathFragment pkgDir = packageIdentifier.getPackageFragment();
+      Path pkgRoot = entry.getValue();
+      for (int i = 0; i <= pkgDir.segmentCount(); i++) {
+        PackageIdentifier dir = PackageIdentifier.create(
+            packageIdentifier.getRepository(), pkgDir.subFragment(0, i));
+        Set<Path> roots = dirRootsMap.get(dir);
+        if (roots == null) {
+          roots = Sets.newHashSet();
+          dirRootsMap.put(dir, roots);
+        }
+        roots.add(pkgRoot);
+      }
+    }
+    // Now add in roots for all non-pkg dirs that are in between two packages, and missed above.
+    for (Map.Entry<PackageIdentifier, Set<Path>> entry : dirRootsMap.entrySet()) {
+      PackageIdentifier packageIdentifier = entry.getKey();
+      if (!packageRoots.containsKey(packageIdentifier)) {
+        PackageIdentifier pkgDir = longestPathPrefix(packageIdentifier, packageRoots.keySet());
+        if (pkgDir != null) {
+          entry.getValue().add(packageRoots.get(pkgDir));
+        }
+      }
+    }
+    // Create output dirs for all dirs that have more than one root and need to be split.
+    for (Map.Entry<PackageIdentifier, Set<Path>> entry : dirRootsMap.entrySet()) {
+      PathFragment dir = entry.getKey().getPathFragment();
+      if (entry.getValue().size() > 1) {
+        if (LOG_FINER) {
+          LOG.finer("mkdir " + workspace.getRelative(dir));
+        }
+        FileSystemUtils.createDirectoryAndParents(workspace.getRelative(dir));
+      }
+    }
+    // Make dir links for single rooted dirs.
+    for (Map.Entry<PackageIdentifier, Set<Path>> entry : dirRootsMap.entrySet()) {
+      PackageIdentifier pkgId = entry.getKey();
+      Path linkRoot = workspace.getRelative(pkgId.getRepository().getPathFragment());
+      PathFragment dir = entry.getKey().getPackageFragment();
+      Set<Path> roots = entry.getValue();
+      // Simple case of one root for this dir.
+      if (roots.size() == 1) {
+        // Special case: the main repository is not deleted (because it contains symlinks to
+        // bazel-out et al) so don't attempt to symlink it in.
+        if (pkgId.equals(PackageIdentifier.EMPTY_PACKAGE_IDENTIFIER)) {
+          symlinkEmptyPackage(roots.iterator().next());
+          continue;
+        }
+        if (dir.segmentCount() > 0) {
+          PackageIdentifier parent = PackageIdentifier.create(
+              pkgId.getRepository(), dir.getParentDirectory());
+          if (dir.segmentCount() > 0 && dirRootsMap.get(parent).size() == 1) {
+            continue;  // skip--an ancestor will link this one in from above
+          }
+        }
+
+        // This is the top-most dir that can be linked to a single root. Make it so.
+        Path root = roots.iterator().next();  // lone root in set
+        if (LOG_FINER) {
+          LOG.finer("ln -s " + root.getRelative(dir) + " " + linkRoot.getRelative(dir));
+        }
+        linkRoot.getRelative(dir).createSymbolicLink(root.getRelative(dir));
+      }
+    }
+    // Make links for dirs within packages, skip parent-only dirs.
+    for (Map.Entry<PackageIdentifier, Set<Path>> entry : dirRootsMap.entrySet()) {
+      Path linkRoot = workspace.getRelative(entry.getKey().getRepository().getPathFragment());
+      PathFragment dir = entry.getKey().getPackageFragment();
+      if (entry.getValue().size() > 1) {
+        // If this dir is at or below a package dir, link in its contents.
+        PackageIdentifier pkgDir = longestPathPrefix(entry.getKey(), packageRoots.keySet());
+        if (pkgDir != null) {
+          Path root = packageRoots.get(pkgDir);
+          try {
+            Path absdir = root.getRelative(dir);
+            if (absdir.isDirectory()) {
+              if (LOG_FINER) {
+                LOG.finer("ln -s " + absdir + "/* " + linkRoot.getRelative(dir) + "/");
+              }
+              for (Path target : absdir.getDirectoryEntries()) {
+                PackageIdentifier dirent = PackageIdentifier.create(
+                    pkgDir.getRepository(), target.relativeTo(root));
+                if (!dirRootsMap.containsKey(dirent)) {
+                  linkRoot.getRelative(dirent.getPackageFragment()).createSymbolicLink(target);
+                }
+              }
+            } else {
+              LOG.fine("Symlink planting skipping dir '" + absdir + "'");
+            }
+          } catch (IOException e) {
+            e.printStackTrace();
+          }
+          // Otherwise its just an otherwise empty common parent dir.
+        }
+      }
+    }
+  }
+
+  private void deleteExisting() throws IOException {
+    FileSystemUtils.createDirectoryAndParents(workspace);
+    FileSystemUtils.deleteTreesBelowNotPrefixed(workspace,
+        new String[] { ".", "_", productName + "-"});
+    for (Map.Entry<PackageIdentifier, Path> entry : packageRoots.entrySet()) {
+      RepositoryName repo = entry.getKey().getRepository();
+      Path repoPath = workspace.getRelative(repo.getPathFragment());
+      if (!repo.isMain() && repoPath.exists()) {
+        FileSystemUtils.deleteTree(repoPath);
+      }
+    }
+  }
+
+  /**
+   * For the top-level directory, generate symlinks to everything in the directory instead of the
+   * directory itself.
+   */
+  private void symlinkEmptyPackage(Path emptyPackagePath) throws IOException {
+    for (Path target : emptyPackagePath.getDirectoryEntries()) {
+      String baseName = target.getBaseName();
+      // Create any links that don't exist yet and don't start with bazel-.
+      if (!baseName.startsWith(productName + "-")
+          && !workspace.getRelative(baseName).exists()) {
+        workspace.getRelative(baseName).createSymbolicLink(target);
+      }
+    }
+  }
+
+  /**
+   * Returns the longest prefix from a given set of 'prefixes' that are
+   * contained in 'path'. I.e the closest ancestor directory containing path.
+   * Returns null if none found.
+   */
+  static PackageIdentifier longestPathPrefix(
+      PackageIdentifier packageIdentifier, Set<PackageIdentifier> prefixes) {
+    PathFragment pkg = packageIdentifier.getPackageFragment();
+    for (int i = pkg.segmentCount(); i >= 0; i--) {
+      PackageIdentifier prefix = PackageIdentifier.create(
+          packageIdentifier.getRepository(), pkg.subFragment(0, i));
+      if (prefixes.contains(prefix)) {
+        return prefix;
+      }
+    }
+    return null;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
index 73c7e5ec..75b7b29 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
@@ -65,7 +65,7 @@
   public static final PackageIdentifier EXTERNAL_PACKAGE_IDENTIFIER =
       PackageIdentifier.createInMainRepo(EXTERNAL_PACKAGE_NAME);
 
-  public static final String EXTERNAL_PATH_PREFIX = "external";
+  public static final String EXTERNAL_PATH_PREFIX = "..";
 
   private static final Interner<Label> LABEL_INTERNER = Interners.newWeakInterner();
 
@@ -310,7 +310,7 @@
       doc = "Returns the execution root for the workspace of this label, relative to the execroot. "
       + "For instance:<br>"
       + "<pre class=language-python>Label(\"@repo//pkg/foo:abc\").workspace_root =="
-      + " \"external/repo\"</pre>")
+      + " \"../repo\"</pre>")
   public String getWorkspaceRoot() {
     return packageIdentifier.getRepository().getPathFragment().toString();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java b/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java
index 74cd6fa..4f0652a 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
@@ -48,14 +48,17 @@
     return INTERNER.intern(new PackageIdentifier(repository, pkgName));
   }
 
-  public static final String DEFAULT_REPOSITORY = "";
-  public static final RepositoryName DEFAULT_REPOSITORY_NAME;
+  static final String DEFAULT_REPOSITORY = "";
   public static final RepositoryName MAIN_REPOSITORY_NAME;
+  public static final RepositoryName DEFAULT_REPOSITORY_NAME;
+  public static final PackageIdentifier EMPTY_PACKAGE_IDENTIFIER;
 
   static {
     try {
       DEFAULT_REPOSITORY_NAME = RepositoryName.create(DEFAULT_REPOSITORY);
       MAIN_REPOSITORY_NAME = RepositoryName.create("@");
+      EMPTY_PACKAGE_IDENTIFIER =
+          PackageIdentifier.create(MAIN_REPOSITORY_NAME, PathFragment.EMPTY_FRAGMENT);
     } catch (LabelSyntaxException e) {
       throw new IllegalStateException(e);
     }
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 6b89a6e..eab5320 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
@@ -205,10 +205,10 @@
    * 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.
+   * TODO(kchodorow): remove this.
    */
   public PathFragment getRunfilesPath() {
-    return isDefault() || isMain()
-        ? PathFragment.EMPTY_FRAGMENT : new PathFragment("..").getRelative(strippedName());
+    return getPathFragment();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index 44d9e30..ae0915e 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -294,7 +294,7 @@
     this.filename = builder.getFilename();
     this.packageDirectory = filename.getParentDirectory();
 
-    this.sourceRoot = getSourceRoot(filename, packageIdentifier.getPathFragment());
+    this.sourceRoot = getSourceRoot(filename, packageIdentifier.getPackageFragment());
     if ((sourceRoot == null
         || !sourceRoot.getRelative(packageIdentifier.getPathFragment()).equals(packageDirectory))
         && !filename.getBaseName().equals("WORKSPACE")) {
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
index f00606d..687ed98 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
@@ -18,6 +18,7 @@
 import com.google.common.base.Verify;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
@@ -110,8 +111,11 @@
       // $OUTPUT_BASE/external, which is created by the appropriate RepositoryDirectoryValue. This
       // is true for the invocation in GlobCache, but not for the locator.getBuildFileForPackage()
       // invocation in Parser#include().
-      Path buildFile = outputBase.getRelative(
-          packageIdentifier.getPathFragment()).getRelative("BUILD");
+      Path buildFile = outputBase
+          .getRelative(Label.EXTERNAL_PACKAGE_NAME)
+          .getRelative(packageIdentifier.getRepository().strippedName())
+          .getRelative(packageIdentifier.getPackageFragment())
+          .getRelative("BUILD");
       FileStatus stat = cache.get().statNullable(buildFile, Symlinks.FOLLOW);
       if (stat != null && stat.isFile()) {
         return buildFile;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java
index c067d36..130f7a8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java
@@ -432,11 +432,11 @@
    */
   private Artifact postprocessPartialJackAndAddResources(
       Artifact partialJackLibrary, Artifact resources) {
-    Artifact result = ruleContext.getUniqueDirectoryArtifact(
-        JACK_DIRECTORY,
-        partialJackLibrary.getRootRelativePath().relativeTo(
-            ruleContext.getUniqueDirectory(PARTIAL_JACK_DIRECTORY)),
-        ruleContext.getBinOrGenfilesDirectory());
+    PathFragment partialPath = new PathFragment(
+        partialJackLibrary.getRootRelativePath().getPathString()
+            .replace(PARTIAL_JACK_DIRECTORY, JACK_DIRECTORY));
+    Artifact result = ruleContext.getDerivedArtifact(
+        partialPath, ruleContext.getBinOrGenfilesDirectory());
     CustomCommandLine.Builder builder =
         CustomCommandLine.builder()
             // Have jack double-check its behavior and crash rather than producing invalid output
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
index 8ccd6e1..fb1ca8c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
@@ -397,9 +397,12 @@
         continue;
       }
       PathFragment includesPath = packageFragment.getRelative(includesAttr).normalize();
-      if (!includesPath.isNormalized()) {
+      // It's okay for the includes path to start with ../workspace-name for external repos.
+      if ((packageIdentifier.getRepository().isMain() && !includesPath.isNormalized())
+          || (!packageIdentifier.getRepository().isMain()
+              && !includesPath.startsWith(packageIdentifier.getRepository().getPathFragment()))) {
         ruleContext.attributeError("includes",
-            "Path references a path above the execution root.");
+            includesAttr + " references a path above the execution root (" + includesPath + ").");
       }
       if (includesPath.segmentCount() == 0) {
         ruleContext.attributeError(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 5d273fe..bb2149e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -947,7 +947,12 @@
           // are, it's probably due to a non-hermetic #include, & we should stop
           // the build with an error.
           if (execPath.startsWith(execRoot)) {
-            execPathFragment = execPath.relativeTo(execRoot); // funky but tolerable path
+            // funky but tolerable path
+            execPathFragment = execPath.relativeTo(execRoot);
+          } else if (execPath.startsWith(execRoot.getParentDirectory())) {
+            // External repository.
+            execPathFragment = new PathFragment("..")
+                .getRelative(execPath.relativeTo(execRoot.getParentDirectory()));
           } else {
             problems.add(execPathFragment.getPathString());
             continue;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
index d0da0c4..9cf27c9 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
@@ -468,7 +468,8 @@
     String basename = FileSystemUtils.removeExtension(outputJar.getExecPath().getBaseName());
     return getConfiguration().getBinDirectory().getExecPath()
         .getRelative(ruleContext.getUniqueDirectory("_javac"))
-        .getRelative(basename + suffix);
+        .getRelative(basename + suffix)
+        .normalize();
   }
 
   /**
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 ae43116..05e479d 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
@@ -437,7 +437,7 @@
     }
 
     PathFragment workspaceName = new PathFragment(ruleContext.getRule().getWorkspaceName());
-    return workspaceName.getRelative(mainArtifact.getRunfilesPath()).getPathString();
+    return workspaceName.getRelative(mainArtifact.getRunfilesPath()).normalize().getPathString();
   }
 
   public Artifact getExecutable() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java
index 043bd0f..7f28eb5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryFunction.java
@@ -262,7 +262,7 @@
 
   /**
    * Uses a remote repository name to fetch the corresponding Rule describing how to get it.
-   * 
+   *
    * This should be the unique entry point for resolving a remote repository function.
    */
   @Nullable
@@ -352,9 +352,7 @@
   }
 
   public static Path getExternalRepositoryDirectory(BlazeDirectories directories) {
-    return directories
-        .getOutputBase()
-        .getRelative(Label.EXTERNAL_PATH_PREFIX);
+    return directories.getOutputBase().getRelative(Label.EXTERNAL_PACKAGE_NAME);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java
index 792cc5f..9a35fba 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalFilesHelper.java
@@ -138,7 +138,7 @@
       return FileType.EXTERNAL_MUTABLE;
     }
     if (rootedPath.asPath().startsWith(outputBase)) {
-      Path externalRepoDir = outputBase.getRelative(Label.EXTERNAL_PATH_PREFIX);
+      Path externalRepoDir = outputBase.getRelative(Label.EXTERNAL_PACKAGE_NAME);
       if (rootedPath.asPath().startsWith(externalRepoDir)) {
         anyNonOutputExternalFilesSeen = true;
         return FileType.EXTERNAL_REPO;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java
index 604ef07..f8aea5a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageLoaderWithValueEnvironment.java
@@ -74,7 +74,7 @@
   @Override
   public void addDependency(Package pkg, String fileName) throws LabelSyntaxException, IOException {
     RootedPath fileRootedPath = RootedPath.toRootedPath(pkg.getSourceRoot(),
-        pkg.getPackageIdentifier().getPathFragment().getRelative(fileName));
+        pkg.getPackageIdentifier().getPackageFragment().getRelative(fileName));
     FileValue result = (FileValue) env.getValue(FileValue.key(fileRootedPath));
     if (result != null && !result.exists()) {
       throw new IOException();
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java b/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java
index 0facfef..aaac850 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java
@@ -16,9 +16,6 @@
 import static java.nio.charset.StandardCharsets.ISO_8859_1;
 
 import com.google.common.base.Predicate;
-import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Maps;
-import com.google.common.collect.Sets;
 import com.google.common.io.ByteSink;
 import com.google.common.io.ByteSource;
 import com.google.common.io.ByteStreams;
@@ -35,10 +32,6 @@
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.List;
-import java.util.Map;
-import java.util.Set;
-import java.util.logging.Level;
-import java.util.logging.Logger;
 
 /**
  * Helper functions that implement often-used complex operations on file
@@ -47,9 +40,6 @@
 @ConditionallyThreadSafe // ThreadSafe except for deleteTree.
 public class FileSystemUtils {
 
-  static final Logger LOG = Logger.getLogger(FileSystemUtils.class.getName());
-  static final boolean LOG_FINER = LOG.isLoggable(Level.FINER);
-
   private FileSystemUtils() {}
 
   /****************************************************************************
@@ -137,21 +127,6 @@
   }
 
   /**
-   * Returns the longest prefix from a given set of 'prefixes' that are
-   * contained in 'path'. I.e the closest ancestor directory containing path.
-   * Returns null if none found.
-   */
-  static PathFragment longestPathPrefix(PathFragment path, Set<PathFragment> prefixes) {
-    for (int i = path.segmentCount(); i >= 0; i--) {
-      PathFragment prefix = path.subFragment(0, i);
-      if (prefixes.contains(prefix)) {
-        return prefix;
-      }
-    }
-    return null;
-  }
-
-  /**
    * Removes the shortest suffix beginning with '.' from the basename of the
    * filename string. If the basename contains no '.', the filename is returned
    * unchanged.
@@ -676,120 +651,6 @@
     return true;
   }
 
-  /**
-   * Takes a map of directory fragments to root paths, and creates a symlink
-   * forest under an existing linkRoot to the corresponding source dirs or
-   * files. Symlink are made at the highest dir possible, linking files directly
-   * only when needed with nested packages.
-   */
-  public static void plantLinkForest(ImmutableMap<PathFragment, Path> packageRootMap,
-      Path linkRoot, String productName)
-      throws IOException {
-    Path emptyPackagePath = null;
-
-    // Create a sorted map of all dirs (packages and their ancestors) to sets of their roots.
-    // Packages come from exactly one root, but their shared ancestors may come from more.
-    // The map is maintained sorted lexicographically, so parents are before their children.
-    Map<PathFragment, Set<Path>> dirRootsMap = Maps.newTreeMap();
-    for (Map.Entry<PathFragment, Path> entry : packageRootMap.entrySet()) {
-      PathFragment pkgDir = entry.getKey();
-      Path pkgRoot = entry.getValue();
-      if (pkgDir.segmentCount() == 0) {
-        emptyPackagePath = entry.getValue();
-      }
-      for (int i = 1; i <= pkgDir.segmentCount(); i++) {
-        PathFragment dir = pkgDir.subFragment(0, i);
-        Set<Path> roots = dirRootsMap.get(dir);
-        if (roots == null) {
-          roots = Sets.newHashSet();
-          dirRootsMap.put(dir, roots);
-        }
-        roots.add(pkgRoot);
-      }
-    }
-    // Now add in roots for all non-pkg dirs that are in between two packages, and missed above.
-    for (Map.Entry<PathFragment, Set<Path>> entry : dirRootsMap.entrySet()) {
-      PathFragment dir = entry.getKey();
-      if (!packageRootMap.containsKey(dir)) {
-        PathFragment pkgDir = longestPathPrefix(dir, packageRootMap.keySet());
-        if (pkgDir != null) {
-          entry.getValue().add(packageRootMap.get(pkgDir));
-        }
-      }
-    }
-    // Create output dirs for all dirs that have more than one root and need to be split.
-    for (Map.Entry<PathFragment, Set<Path>> entry : dirRootsMap.entrySet()) {
-      PathFragment dir = entry.getKey();
-      if (entry.getValue().size() > 1) {
-        if (LOG_FINER) {
-          LOG.finer("mkdir " + linkRoot.getRelative(dir));
-        }
-        createDirectoryAndParents(linkRoot.getRelative(dir));
-      }
-    }
-    // Make dir links for single rooted dirs.
-    for (Map.Entry<PathFragment, Set<Path>> entry : dirRootsMap.entrySet()) {
-      PathFragment dir = entry.getKey();
-      Set<Path> roots = entry.getValue();
-      // Simple case of one root for this dir.
-      if (roots.size() == 1) {
-        if (dir.segmentCount() > 1 && dirRootsMap.get(dir.getParentDirectory()).size() == 1) {
-          continue;  // skip--an ancestor will link this one in from above
-        }
-        // This is the top-most dir that can be linked to a single root. Make it so.
-        Path root = roots.iterator().next();  // lone root in set
-        if (LOG_FINER) {
-          LOG.finer("ln -s " + root.getRelative(dir) + " " + linkRoot.getRelative(dir));
-        }
-        linkRoot.getRelative(dir).createSymbolicLink(root.getRelative(dir));
-      }
-    }
-    // Make links for dirs within packages, skip parent-only dirs.
-    for (Map.Entry<PathFragment, Set<Path>> entry : dirRootsMap.entrySet()) {
-      PathFragment dir = entry.getKey();
-      if (entry.getValue().size() > 1) {
-        // If this dir is at or below a package dir, link in its contents.
-        PathFragment pkgDir = longestPathPrefix(dir, packageRootMap.keySet());
-        if (pkgDir != null) {
-          Path root = packageRootMap.get(pkgDir);
-          try {
-            Path absdir = root.getRelative(dir);
-            if (absdir.isDirectory()) {
-              if (LOG_FINER) {
-                LOG.finer("ln -s " + absdir + "/* " + linkRoot.getRelative(dir) + "/");
-              }
-              for (Path target : absdir.getDirectoryEntries()) {
-                PathFragment p = target.relativeTo(root);
-                if (!dirRootsMap.containsKey(p)) {
-                  //LOG.finest("ln -s " + target + " " + linkRoot.getRelative(p));
-                  linkRoot.getRelative(p).createSymbolicLink(target);
-                }
-              }
-            } else {
-              LOG.fine("Symlink planting skipping dir '" + absdir + "'");
-            }
-          } catch (IOException e) {
-            e.printStackTrace();
-          }
-          // Otherwise its just an otherwise empty common parent dir.
-        }
-      }
-    }
-
-    if (emptyPackagePath != null) {
-      // For the top-level directory, generate symlinks to everything in the directory instead of
-      // the directory itself.
-      for (Path target : emptyPackagePath.getDirectoryEntries()) {
-        String baseName = target.getBaseName();
-        // Create any links that don't exist yet and don't start with bazel-.
-        if (!baseName.startsWith(productName + "-")
-            && !linkRoot.getRelative(baseName).exists()) {
-          linkRoot.getRelative(baseName).createSymbolicLink(target);
-        }
-      }
-    }
-  }
-
   /****************************************************************************
    * Whole-file I/O utilities for characters and bytes. These convenience
    * methods are not efficient and should not be used for large amounts of data!
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
index f9c31ca..317051b 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactFactoryTest.java
@@ -150,25 +150,26 @@
   }
 
   @Test
-  public void testResolveArtifactWithUpLevelFailsCleanly() throws Exception {
+  public void testResolveArtifactWithUpLevel() throws Exception {
     // We need a package in the root directory to make every exec path (even one with up-level
     // references) be in a package.
     Map<PackageIdentifier, Root> packageRoots = ImmutableMap.of(
-        PackageIdentifier.createInMainRepo(new PathFragment("")), clientRoot);
+        PackageIdentifier.create("@workspace", new PathFragment("")), clientRoot,
+        PackageIdentifier.create("@repo", new PathFragment("dir")), clientRoot);
     artifactFactory.setPackageRoots(packageRoots);
-    PathFragment outsideWorkspace = new PathFragment("../foo");
-    PathFragment insideWorkspace =
-        new PathFragment("../" + clientRoot.getPath().getBaseName() + "/foo");
-    assertNull(artifactFactory.resolveSourceArtifact(outsideWorkspace));
-    assertNull("Up-level-containing paths that descend into the right workspace aren't allowed",
-            artifactFactory.resolveSourceArtifact(insideWorkspace));
+    PathFragment topLevel = new PathFragment("../workspace/foo");
+    PathFragment subdir = new PathFragment("../repo/dir/foo");
+    Artifact topLevelArtifact = artifactFactory.resolveSourceArtifact(topLevel);
+    assertThat(topLevelArtifact).isNotNull();
+    Artifact subdirArtifact = artifactFactory.resolveSourceArtifact(subdir);
+    assertThat(subdirArtifact).isNotNull();
     MockPackageRootResolver packageRootResolver = new MockPackageRootResolver();
     packageRootResolver.setPackageRoots(packageRoots);
     Map<PathFragment, Artifact> result = new HashMap<>();
-    result.put(insideWorkspace, null);
-    result.put(outsideWorkspace, null);
+    result.put(topLevel, topLevelArtifact);
+    result.put(subdir, subdirArtifact);
     assertThat(
-        artifactFactory.resolveSourceArtifacts(ImmutableList.of(insideWorkspace, outsideWorkspace),
+        artifactFactory.resolveSourceArtifacts(ImmutableList.of(topLevel, subdir),
             packageRootResolver).entrySet()).containsExactlyElementsIn(result.entrySet());
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
index e43ddd1..676eab4 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
@@ -57,13 +57,12 @@
   }
 
   @Test
-  public void testConstruction_badRootDir() throws IOException {
+  public void testConstruction_UplevelRootDir() throws IOException {
     Path f1 = scratch.file("/exec/dir/file.ext");
     Path bogusDir = scratch.file("/exec/dir/bogus");
-    try {
-      new Artifact(f1, Root.asDerivedRoot(bogusDir), f1.relativeTo(execDir));
-      fail("Expected IllegalArgumentException constructing artifact with a bad root dir");
-    } catch (IllegalArgumentException expected) {}
+    Artifact artifact = new Artifact(f1, Root.asDerivedRoot(bogusDir), f1.relativeTo(execDir));
+    assertThat(artifact.getExecPath()).isEqualTo(new PathFragment("dir/file.ext"));
+    assertThat(artifact.getRootRelativePath()).isEqualTo(new PathFragment("../file.ext"));
   }
 
   @Test
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 1f83f28..9be7495 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
@@ -323,7 +323,7 @@
   public void testLegacyRunfilesStructure() {
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     PathFragment workspaceName = new PathFragment("wsname");
-    PathFragment pathB = new PathFragment("external/repo/b");
+    PathFragment pathB = new PathFragment(Label.EXTERNAL_PATH_PREFIX).getRelative("repo/b");
     Artifact artifactB = new Artifact(pathB, root);
 
     Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(workspaceName, true);
@@ -335,7 +335,7 @@
     builder.addUnderWorkspace(inputManifest, checker);
 
     assertThat(builder.build().entrySet()).containsExactly(
-        Maps.immutableEntry(workspaceName.getRelative(pathB), artifactB),
+        Maps.immutableEntry(workspaceName.getRelative("external/repo/b"), artifactB),
         Maps.immutableEntry(new PathFragment("repo/b"), artifactB));
     assertNoEvents();
   }
@@ -344,7 +344,7 @@
   public void testRunfileAdded() {
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     PathFragment workspaceName = new PathFragment("wsname");
-    PathFragment pathB = new PathFragment("external/repo/b");
+    PathFragment pathB = new PathFragment(Label.EXTERNAL_PATH_PREFIX).getRelative("repo/b");
     Artifact artifactB = new Artifact(pathB, root);
 
     Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(workspaceName, false);
@@ -361,29 +361,4 @@
         Maps.immutableEntry(new PathFragment("repo/b"), artifactB));
     assertNoEvents();
   }
-
-  // TODO(kchodorow): remove this once the default workspace name is always set.
-  @Test
-  public void testConflictWithExternal() {
-    Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
-    PathFragment pathB = new PathFragment("repo/b");
-    PathFragment externalPathB = Label.EXTERNAL_PACKAGE_NAME.getRelative(pathB);
-    Artifact artifactB = new Artifact(pathB, root);
-    Artifact artifactExternalB = new Artifact(externalPathB, root);
-
-    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
-        PathFragment.EMPTY_FRAGMENT, false);
-
-    Map<PathFragment, Artifact> inputManifest = ImmutableMap.<PathFragment, Artifact>builder()
-        .put(pathB, artifactB)
-        .put(externalPathB, artifactExternalB)
-        .build();
-    Runfiles.ConflictChecker checker = new Runfiles.ConflictChecker(
-        Runfiles.ConflictPolicy.WARN, reporter, null);
-    builder.addUnderWorkspace(inputManifest, checker);
-
-    assertThat(builder.build().entrySet()).containsExactly(
-        Maps.immutableEntry(new PathFragment("repo/b"), artifactExternalB));
-    checkConflictWarning();
-  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index 9460d95..f09b50a 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -716,7 +716,7 @@
   protected Rule scratchRule(String packageName, String ruleName, String... lines)
       throws Exception {
     String buildFilePathString = packageName + "/BUILD";
-    if (packageName.equals(Label.EXTERNAL_PATH_PREFIX)) {
+    if (packageName.equals(Label.EXTERNAL_PACKAGE_NAME.getPathString())) {
       buildFilePathString = "WORKSPACE";
       scratch.overwriteFile(buildFilePathString, lines);
     } else {
diff --git a/src/test/java/com/google/devtools/build/lib/buildtool/BUILD b/src/test/java/com/google/devtools/build/lib/buildtool/BUILD
new file mode 100644
index 0000000..3b4268a
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/buildtool/BUILD
@@ -0,0 +1,27 @@
+java_library(
+    name = "testutil",
+    srcs = glob(["util/*.java"]),
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib:bazel-main",
+        "//src/main/java/com/google/devtools/build/lib:runtime",
+        "//src/test/java/com/google/devtools/build/lib:packages_testutil",
+        "//src/test/java/com/google/devtools/build/lib:testutil",
+    ],
+)
+
+java_test(
+    name = "BuildtoolTests",
+    srcs = glob(["*.java"]),
+    test_class = "com.google.devtools.build.lib.AllTests",
+    runtime_deps = ["//src/test/java/com/google/devtools/build/lib:test_runner"],
+    deps = [
+        ":testutil",
+        "//src/main/java/com/google/devtools/build/lib:inmemoryfs",
+        "//src/main/java/com/google/devtools/build/lib:packages-internal",
+        "//src/main/java/com/google/devtools/build/lib:runtime",
+        "//src/main/java/com/google/devtools/build/lib:vfs",
+        "//src/test/java/com/google/devtools/build/lib:packages_testutil",
+        "//src/test/java/com/google/devtools/build/lib:testutil",
+        "//third_party:junit4",
+    ],
+)
diff --git a/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java b/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java
new file mode 100644
index 0000000..365759d
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java
@@ -0,0 +1,159 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.buildtool;
+
+import static com.google.devtools.build.lib.vfs.FileSystemUtils.createDirectoryAndParents;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.testutil.ManualClock;
+import com.google.devtools.build.lib.testutil.TestConstants;
+import com.google.devtools.build.lib.vfs.FileSystem;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Symlinks;
+import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.io.IOException;
+import java.io.PrintStream;
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * Tests creating the execution root symlink forest.
+ */
+@RunWith(JUnit4.class)
+public class SymlinkForestTest {
+  private FileSystem fileSystem;
+
+  @Before
+  public final void initializeFileSystem() throws Exception  {
+    ManualClock clock = new ManualClock();
+    fileSystem = new InMemoryFileSystem(clock);
+  }
+
+  private static PackageIdentifier createPkgId(String path) {
+    return PackageIdentifier.create(PackageIdentifier.MAIN_REPOSITORY_NAME, new PathFragment(path));
+  }
+
+  private static String longestPathPrefixStr(String path, String... prefixStrs) {
+    Set<PackageIdentifier> prefixes = new HashSet<>();
+    for (String prefix : prefixStrs) {
+      prefixes.add(createPkgId(prefix));
+    }
+    PackageIdentifier longest = SymlinkForest.longestPathPrefix(createPkgId(path), prefixes);
+    return longest != null ? longest.getPackageFragment().getPathString() : null;
+  }
+
+  private PackageIdentifier createPkg(Path rootA, Path rootB, String pkg) throws IOException {
+    if (rootA != null) {
+      createDirectoryAndParents(rootA.getRelative(pkg));
+      FileSystemUtils.createEmptyFile(rootA.getRelative(pkg).getChild("file"));
+    }
+    if (rootB != null) {
+      createDirectoryAndParents(rootB.getRelative(pkg));
+      FileSystemUtils.createEmptyFile(rootB.getRelative(pkg).getChild("file"));
+    }
+    return createPkgId(pkg);
+  }
+
+  private void assertLinksTo(Path fromRoot, Path toRoot, String relpart) throws IOException {
+    assertTrue(fromRoot.getRelative(relpart).isSymbolicLink());
+    assertEquals(toRoot.getRelative(relpart).asFragment(),
+        fromRoot.getRelative(relpart).readSymbolicLink());
+  }
+
+  private void assertIsDir(Path root, String relpart) {
+    assertTrue(root.getRelative(relpart).isDirectory(Symlinks.NOFOLLOW));
+  }
+
+  void dumpTree(Path root, PrintStream out) throws IOException {
+    out.println("\n" + root);
+    for (Path p : FileSystemUtils.traverseTree(root, Predicates.alwaysTrue())) {
+      if (p.isDirectory(Symlinks.NOFOLLOW)) {
+        out.println("  " + p + "/");
+      } else if (p.isSymbolicLink()) {
+        out.println("  " + p + " => " + p.readSymbolicLink());
+      } else {
+        out.println("  " + p + " [" + p.resolveSymbolicLinks() + "]");
+      }
+    }
+  }
+
+  @Test
+  public void testLongestPathPrefix() {
+    assertEquals("A", longestPathPrefixStr("A/b", "A", "B")); // simple parent
+    assertEquals("A", longestPathPrefixStr("A", "A", "B")); // self
+    assertEquals("A/B", longestPathPrefixStr("A/B/c", "A", "A/B"));  // want longest
+    assertNull(longestPathPrefixStr("C/b", "A", "B"));  // not found in other parents
+    assertNull(longestPathPrefixStr("A", "A/B", "B"));  // not found in child
+    assertEquals("A/B/C", longestPathPrefixStr("A/B/C/d/e/f.h", "A/B/C", "B/C/d"));
+    assertEquals("", longestPathPrefixStr("A/f.h", "", "B/C/d"));
+  }
+
+  @Test
+  public void testPlantLinkForest() throws IOException {
+    Path rootA = fileSystem.getPath("/A");
+    Path rootB = fileSystem.getPath("/B");
+
+    ImmutableMap<PackageIdentifier, Path> packageRootMap =
+        ImmutableMap.<PackageIdentifier, Path>builder()
+        .put(createPkg(rootA, rootB, "pkgA"), rootA)
+        .put(createPkg(rootA, rootB, "dir1/pkgA"), rootA)
+        .put(createPkg(rootA, rootB, "dir1/pkgB"), rootB)
+        .put(createPkg(rootA, rootB, "dir2/pkg"), rootA)
+        .put(createPkg(rootA, rootB, "dir2/pkg/pkg"), rootB)
+        .put(createPkg(rootA, rootB, "pkgB"), rootB)
+        .put(createPkg(rootA, rootB, "pkgB/dir/pkg"), rootA)
+        .put(createPkg(rootA, rootB, "pkgB/pkg"), rootA)
+        .put(createPkg(rootA, rootB, "pkgB/pkg/pkg"), rootA)
+        .build();
+    createPkg(rootA, rootB, "pkgB/dir");  // create a file in there
+
+    //dumpTree(rootA, System.err);
+    //dumpTree(rootB, System.err);
+
+    Path linkRoot = fileSystem.getPath("/linkRoot");
+    createDirectoryAndParents(linkRoot);
+    SymlinkForest forest = new SymlinkForest(packageRootMap, linkRoot, TestConstants.PRODUCT_NAME);
+    forest.plantLinkForest();
+
+    //dumpTree(linkRoot, System.err);
+
+    assertLinksTo(linkRoot, rootA, "pkgA");
+    assertIsDir(linkRoot, "dir1");
+    assertLinksTo(linkRoot, rootA, "dir1/pkgA");
+    assertLinksTo(linkRoot, rootB, "dir1/pkgB");
+    assertIsDir(linkRoot, "dir2");
+    assertIsDir(linkRoot, "dir2/pkg");
+    assertLinksTo(linkRoot, rootA, "dir2/pkg/file");
+    assertLinksTo(linkRoot, rootB, "dir2/pkg/pkg");
+    assertIsDir(linkRoot, "pkgB");
+    assertIsDir(linkRoot, "pkgB/dir");
+    assertLinksTo(linkRoot, rootB, "pkgB/dir/file");
+    assertLinksTo(linkRoot, rootA, "pkgB/dir/pkg");
+    assertLinksTo(linkRoot, rootA, "pkgB/pkg");
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
index 47dd0b1..d451370 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/LabelTest.java
@@ -440,6 +440,6 @@
     Label label = Label.parseAbsolute("//bar/baz");
     assertThat(label.getWorkspaceRoot()).isEmpty();
     label = Label.parseAbsolute("@repo//bar/baz");
-    assertThat(label.getWorkspaceRoot()).isEqualTo("external/repo");
+    assertThat(label.getWorkspaceRoot()).isEqualTo("../repo");
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java
index 5d32df7..790af45 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
@@ -39,8 +39,7 @@
     PackageIdentifier fooA = PackageIdentifier.parse("@foo//a");
     assertThat(fooA.getRepository().strippedName()).isEqualTo("foo");
     assertThat(fooA.getPackageFragment().getPathString()).isEqualTo("a");
-    assertThat(fooA.getRepository().getPathFragment()).isEqualTo(
-        new PathFragment("external/foo"));
+    assertThat(fooA.getRepository().getPathFragment()).isEqualTo(new PathFragment("../foo"));
 
     PackageIdentifier absoluteA = PackageIdentifier.parse("//a");
     assertThat(absoluteA.getRepository().strippedName()).isEqualTo("");
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonConfiguredTargetTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonConfiguredTargetTest.java
index 464ce57..f618a3c 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonConfiguredTargetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcCommonConfiguredTargetTest.java
@@ -745,7 +745,7 @@
     checkError(
         "test",
         "bad_relative_include",
-        "Path references a path above the execution root.",
+        "../.. references a path above the execution root (..).",
         "cc_library(name='bad_relative_include', srcs=[], includes=['../..'])");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
index 69c68f5..80cb217 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
@@ -322,7 +322,7 @@
   @Test
   public void testAbsoluteSymlinkToExternal() throws Exception {
     String externalPath =
-        outputBase.getRelative(Label.EXTERNAL_PATH_PREFIX).getRelative("a/b").getPathString();
+        outputBase.getRelative(Label.EXTERNAL_PACKAGE_NAME).getRelative("a/b").getPathString();
     symlink("a", externalPath);
     file("b");
     file(externalPath);
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
index c96a65e..caab482 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
@@ -343,7 +343,7 @@
     reporter.removeHandler(failFastHandler);
     getConfiguredTarget("@r//:cclib");
     assertContainsEvent(
-        "/external/r/BUILD:2:10: Label '@r//:sub/my_sub_lib.h' crosses boundary of "
+        "/r/BUILD:2:10: Label '@r//:sub/my_sub_lib.h' crosses boundary of "
             + "subpackage '@r//sub' (perhaps you meant to put the colon here: "
             + "'@r//sub:my_sub_lib.h'?)");
   }
diff --git a/src/test/java/com/google/devtools/build/lib/testutil/TestConstants.java b/src/test/java/com/google/devtools/build/lib/testutil/TestConstants.java
index 717c0b1..1edeaba 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
@@ -67,7 +67,7 @@
 
   public static final boolean THIS_IS_BAZEL = true;
 
-  public static final String GCC_INCLUDE_PATH = "external/bazel_tools/tools/cpp/gcc3";
+  public static final String GCC_INCLUDE_PATH = "../bazel_tools/tools/cpp/gcc3";
 
   public static final String TOOLS_REPOSITORY = "@bazel_tools";
 
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/FileSystemUtilsTest.java b/src/test/java/com/google/devtools/build/lib/vfs/FileSystemUtilsTest.java
index 23e0510..246f8c0 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/FileSystemUtilsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/FileSystemUtilsTest.java
@@ -20,8 +20,6 @@
 import static com.google.devtools.build.lib.vfs.FileSystemUtils.createDirectoryAndParents;
 import static com.google.devtools.build.lib.vfs.FileSystemUtils.deleteTree;
 import static com.google.devtools.build.lib.vfs.FileSystemUtils.deleteTreesBelowNotPrefixed;
-import static com.google.devtools.build.lib.vfs.FileSystemUtils.longestPathPrefix;
-import static com.google.devtools.build.lib.vfs.FileSystemUtils.plantLinkForest;
 import static com.google.devtools.build.lib.vfs.FileSystemUtils.relativePath;
 import static com.google.devtools.build.lib.vfs.FileSystemUtils.removeExtension;
 import static com.google.devtools.build.lib.vfs.FileSystemUtils.touchFile;
@@ -37,11 +35,9 @@
 
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.testutil.BlazeTestUtils;
 import com.google.devtools.build.lib.testutil.ManualClock;
-import com.google.devtools.build.lib.testutil.TestConstants;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
 
 import org.junit.Before;
@@ -51,12 +47,9 @@
 
 import java.io.FileNotFoundException;
 import java.io.IOException;
-import java.io.PrintStream;
 import java.nio.charset.StandardCharsets;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.HashSet;
-import java.util.Set;
 
 /**
  * This class tests the file system utilities.
@@ -191,26 +184,6 @@
     assertEquals("../../../file-4", relativePath(innerDir, file4).getPathString());
   }
 
-  private static String longestPathPrefixStr(String path, String... prefixStrs) {
-    Set<PathFragment> prefixes = new HashSet<>();
-    for (String prefix : prefixStrs) {
-      prefixes.add(new PathFragment(prefix));
-    }
-    PathFragment longest = longestPathPrefix(new PathFragment(path), prefixes);
-    return longest != null ? longest.getPathString() : null;
-  }
-
-  @Test
-  public void testLongestPathPrefix() {
-    assertEquals("A", longestPathPrefixStr("A/b", "A", "B")); // simple parent
-    assertEquals("A", longestPathPrefixStr("A", "A", "B")); // self
-    assertEquals("A/B", longestPathPrefixStr("A/B/c", "A", "A/B"));  // want longest
-    assertNull(longestPathPrefixStr("C/b", "A", "B"));  // not found in other parents
-    assertNull(longestPathPrefixStr("A", "A/B", "B"));  // not found in child
-    assertEquals("A/B/C", longestPathPrefixStr("A/B/C/d/e/f.h", "A/B/C", "B/C/d"));
-    assertEquals("", longestPathPrefixStr("A/f.h", "", "B/C/d"));
-  }
-
   @Test
   public void testRemoveExtension_Strings() throws Exception {
     assertEquals("foo", removeExtension("foo.c"));
@@ -699,83 +672,6 @@
     assertTrue(createDirectoryAndParents(theHierarchy));
   }
 
-  PathFragment createPkg(Path rootA, Path rootB, String pkg) throws IOException {
-    if (rootA != null) {
-      createDirectoryAndParents(rootA.getRelative(pkg));
-      FileSystemUtils.createEmptyFile(rootA.getRelative(pkg).getChild("file"));
-    }
-    if (rootB != null) {
-      createDirectoryAndParents(rootB.getRelative(pkg));
-      FileSystemUtils.createEmptyFile(rootB.getRelative(pkg).getChild("file"));
-    }
-    return new PathFragment(pkg);
-  }
-
-  void assertLinksTo(Path fromRoot, Path toRoot, String relpart) throws IOException {
-    assertTrue(fromRoot.getRelative(relpart).isSymbolicLink());
-    assertEquals(toRoot.getRelative(relpart).asFragment(),
-                 fromRoot.getRelative(relpart).readSymbolicLink());
-  }
-
-  void assertIsDir(Path root, String relpart) {
-    assertTrue(root.getRelative(relpart).isDirectory(Symlinks.NOFOLLOW));
-  }
-
-  void dumpTree(Path root, PrintStream out) throws IOException {
-    out.println("\n" + root);
-    for (Path p : FileSystemUtils.traverseTree(root, Predicates.alwaysTrue())) {
-      if (p.isDirectory(Symlinks.NOFOLLOW)) {
-        out.println("  " + p + "/");
-      } else if (p.isSymbolicLink()) {
-        out.println("  " + p + " => " + p.readSymbolicLink());
-      } else {
-        out.println("  " + p + " [" + p.resolveSymbolicLinks() + "]");
-      }
-    }
-  }
-
-  @Test
-  public void testPlantLinkForest() throws IOException {
-    Path rootA = fileSystem.getPath("/A");
-    Path rootB = fileSystem.getPath("/B");
-
-    ImmutableMap<PathFragment, Path> packageRootMap = ImmutableMap.<PathFragment, Path>builder()
-        .put(createPkg(rootA, rootB, "pkgA"), rootA)
-        .put(createPkg(rootA, rootB, "dir1/pkgA"), rootA)
-        .put(createPkg(rootA, rootB, "dir1/pkgB"), rootB)
-        .put(createPkg(rootA, rootB, "dir2/pkg"), rootA)
-        .put(createPkg(rootA, rootB, "dir2/pkg/pkg"), rootB)
-        .put(createPkg(rootA, rootB, "pkgB"), rootB)
-        .put(createPkg(rootA, rootB, "pkgB/dir/pkg"), rootA)
-        .put(createPkg(rootA, rootB, "pkgB/pkg"), rootA)
-        .put(createPkg(rootA, rootB, "pkgB/pkg/pkg"), rootA)
-        .build();
-    createPkg(rootA, rootB, "pkgB/dir");  // create a file in there
-
-    //dumpTree(rootA, System.err);
-    //dumpTree(rootB, System.err);
-
-    Path linkRoot = fileSystem.getPath("/linkRoot");
-    createDirectoryAndParents(linkRoot);
-    plantLinkForest(packageRootMap, linkRoot, TestConstants.PRODUCT_NAME);
-
-    //dumpTree(linkRoot, System.err);
-
-    assertLinksTo(linkRoot, rootA, "pkgA");
-    assertIsDir(linkRoot, "dir1");
-    assertLinksTo(linkRoot, rootA, "dir1/pkgA");
-    assertLinksTo(linkRoot, rootB, "dir1/pkgB");
-    assertIsDir(linkRoot, "dir2");
-    assertIsDir(linkRoot, "dir2/pkg");
-    assertLinksTo(linkRoot, rootA, "dir2/pkg/file");
-    assertLinksTo(linkRoot, rootB, "dir2/pkg/pkg");
-    assertIsDir(linkRoot, "pkgB");
-    assertIsDir(linkRoot, "pkgB/dir");
-    assertLinksTo(linkRoot, rootB, "pkgB/dir/file");
-    assertLinksTo(linkRoot, rootA, "pkgB/dir/pkg");
-    assertLinksTo(linkRoot, rootA, "pkgB/pkg");
-  }
-
   @Test
   public void testWriteIsoLatin1() throws Exception {
     Path file = fileSystem.getPath("/does/not/exist/yet.txt");
diff --git a/src/test/shell/bazel/bazel_rules_test.sh b/src/test/shell/bazel/bazel_rules_test.sh
index 6b7c04e..ccbe87c 100755
--- a/src/test/shell/bazel/bazel_rules_test.sh
+++ b/src/test/shell/bazel/bazel_rules_test.sh
@@ -294,8 +294,8 @@
 EOF
 
   bazel build @r//package:hi >$TEST_log 2>&1 || fail "Should build"
-  expect_log bazel-genfiles/external/r/package/a/b
-  expect_log bazel-genfiles/external/r/package/c/d
+  expect_log bazel-out/local-fastbuild/r/package/a/b
+  expect_log bazel-out/local-fastbuild/r/package/c/d
 }
 
 function test_python_with_workspace_name() {
diff --git a/src/test/shell/bazel/bazel_sandboxing_test.sh b/src/test/shell/bazel/bazel_sandboxing_test.sh
index 9e6bc85..650512d 100755
--- a/src/test/shell/bazel/bazel_sandboxing_test.sh
+++ b/src/test/shell/bazel/bazel_sandboxing_test.sh
@@ -80,8 +80,8 @@
    name = "tooldir",
    srcs = [],
    outs = ["tooldir.txt"],
-   cmd = "ls -l external/bazel_tools/tools/genrule | tee $@ >&2; " +
-       "cat external/bazel_tools/tools/genrule/genrule-setup.sh >&2",
+   cmd = "ls -l ../bazel_tools/tools/genrule | tee $@ >&2; " +
+       "cat ../bazel_tools/tools/genrule/genrule-setup.sh >&2",
 )
 
 genrule(
diff --git a/src/test/shell/bazel/external_correctness_test.sh b/src/test/shell/bazel/external_correctness_test.sh
index 6d79320..0797c60 100755
--- a/src/test/shell/bazel/external_correctness_test.sh
+++ b/src/test/shell/bazel/external_correctness_test.sh
@@ -140,8 +140,8 @@
 )
 EOF
   bazel build @a//b/c:echo-d &> $TEST_log || fail "Build failed"
-  assert_contains "bazel-out/local.*-fastbuild/genfiles/external/a/b/c" \
-    "bazel-genfiles/external/a/b/c/d"
+  assert_contains "bazel-out/local.*-fastbuild/a/b/c" \
+    "bazel-out/local-fastbuild/a/b/c/d"
 }
 
 function test_package_group_in_external_repos() {
@@ -200,7 +200,7 @@
 EOF
 
   bazel build @remote2//:x &> $TEST_log || fail "Build failed"
-  assert_contains 1.0 bazel-genfiles/external/remote2/x.out
+  assert_contains 1.0 bazel-out/local-fastbuild/remote2/x.out
 }
 
 function test_visibility_attributes_in_external_repos() {
@@ -275,15 +275,15 @@
 EOF
 
   bazel build @r//a:gr || fail "build failed"
-  assert_contains "default" bazel-genfiles/external/r/a/gro
+  assert_contains "default" bazel-out/local-fastbuild/r/a/gro
   bazel build @r//a:gr --define=ARG=one|| fail "build failed"
-  assert_contains "one" bazel-genfiles/external/r/a/gro
+  assert_contains "one" bazel-out/local-fastbuild/r/a/gro
   bazel build @r//a:gr --define=ARG=two || fail "build failed"
-  assert_contains "two" bazel-genfiles/external/r/a/gro
+  assert_contains "two" bazel-out/local-fastbuild/r/a/gro
   bazel build @r//a:gr --define=ARG=three || fail "build failed"
-  assert_contains "three" bazel-genfiles/external/r/a/gro
+  assert_contains "three" bazel-out/local-fastbuild/r/a/gro
   bazel build @r//a:gr --define=ARG=four || fail "build failed"
-  assert_contains "four" bazel-genfiles/external/r/a/gro
+  assert_contains "four" bazel-out/local-fastbuild/r/a/gro
 
 }
 
@@ -311,11 +311,11 @@
   touch ../r/three
   bazel "$batch_flag" build @r//:fg &> $TEST_log || \
     fail "Expected build to succeed"
-  assert_contains "external/r/three" bazel-genfiles/external/r/fg.out
+  assert_contains "../r/three" bazel-out/local-fastbuild/r/fg.out
   touch ../r/subdir/four
   bazel "$batch_flag" build @r//:fg &> $TEST_log || \
     fail "Expected build to succeed"
-  assert_contains "external/r/subdir/four" bazel-genfiles/external/r/fg.out
+  assert_contains "../r/subdir/four" bazel-out/local-fastbuild/r/fg.out
 }
 
 function test_top_level_dir_changes_batch() {
diff --git a/src/test/shell/bazel/external_integration_test.sh b/src/test/shell/bazel/external_integration_test.sh
index 4873710..5f46302 100755
--- a/src/test/shell/bazel/external_integration_test.sh
+++ b/src/test/shell/bazel/external_integration_test.sh
@@ -145,7 +145,7 @@
   kill_nc
   expect_log $what_does_the_fox_say
 
-  base_external_path=bazel-out/../external/endangered/fox
+  base_external_path="$(bazel info output_base)/external/endangered/fox"
   assert_files_same ${base_external_path}/male ${base_external_path}/male_relative
   assert_files_same ${base_external_path}/male ${base_external_path}/male_absolute
 }
@@ -630,7 +630,7 @@
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  assert_contains "abc" bazel-out/local-fastbuild/x/catter.out
 }
 
 function test_prefix_stripping_zip() {
@@ -659,7 +659,7 @@
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  assert_contains "abc" bazel-out/local-fastbuild/x/catter.out
 }
 
 function test_prefix_stripping_existing_repo() {
@@ -688,7 +688,7 @@
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  assert_contains "abc" bazel-out/local-fastbuild/x/catter.out
 }
 
 function test_moving_build_file() {
@@ -715,14 +715,14 @@
 EOF
 
   bazel build @x//:catter &> $TEST_log || fail "Build 1 failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  assert_contains "abc" bazel-out/local-fastbuild/x/catter.out
   mv x.BUILD x.BUILD.new || fail "Moving x.BUILD failed"
   sed 's/x.BUILD/x.BUILD.new/g' WORKSPACE > WORKSPACE.tmp || \
     fail "Editing WORKSPACE failed"
   mv WORKSPACE.tmp WORKSPACE
   serve_file x.tar.gz
   bazel build @x//:catter &> $TEST_log || fail "Build 2 failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  assert_contains "abc" bazel-out/local-fastbuild/x/catter.out
 }
 
 function test_changing_build_file() {
@@ -759,13 +759,13 @@
 EOF
 
   bazel build @x//:catter || fail "Build 1 failed"
-  assert_contains "abc" bazel-genfiles/external/x/catter.out
+  assert_contains "abc" bazel-out/local-fastbuild/x/catter.out
   sed 's/x.BUILD/x.BUILD.new/g' WORKSPACE > WORKSPACE.tmp || \
     fail "Editing WORKSPACE failed"
   mv WORKSPACE.tmp WORKSPACE
   serve_file x.tar.gz
   bazel build @x//:catter &> $TEST_log || fail "Build 2 failed"
-  assert_contains "def" bazel-genfiles/external/x/catter.out
+  assert_contains "def" bazel-out/local-fastbuild/x/catter.out
 }
 
 function test_truncated() {
diff --git a/src/test/shell/bazel/git_repository_test.sh b/src/test/shell/bazel/git_repository_test.sh
index 2c862b7..407797a 100755
--- a/src/test/shell/bazel/git_repository_test.sh
+++ b/src/test/shell/bazel/git_repository_test.sh
@@ -267,17 +267,17 @@
 
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" bazel-out/local-fastbuild/g/go
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_not_log "Cloning"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" bazel-out/local-fastbuild/g/go
   cat > WORKSPACE <<EOF
 git_repository(name='g', remote='$repo_dir', commit='62777acc')
 EOF
 
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" bazel-out/local-fastbuild/g/go
 
   cat > WORKSPACE <<EOF
 # This comment line is to change the line numbers, which should not cause Bazel
@@ -287,7 +287,7 @@
 
   bazel --batch build @g//:g >& $TEST_log || fail "Build failed"
   expect_not_log "Cloning"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" bazel-out/local-fastbuild/g/go
 
 }
 
@@ -302,7 +302,7 @@
 
   bazel build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" bazel-out/local-fastbuild/g/go
 
   cat > WORKSPACE <<EOF
 git_repository(name='g', remote='$repo_dir', commit='62777acc')
@@ -311,7 +311,7 @@
 
   bazel build @g//:g >& $TEST_log || fail "Build failed"
   expect_log "Cloning"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" bazel-out/local-fastbuild/g/go
 }
 
 function test_git_repository_and_nofetch() {
@@ -325,7 +325,7 @@
   bazel build --nofetch @g//:g >& $TEST_log && fail "Build succeeded"
   expect_log "fetching repositories is disabled"
   bazel build @g//:g >& $TEST_log || fail "Build failed"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" bazel-out/local-fastbuild/g/go
 
   cat > WORKSPACE <<EOF
 git_repository(name='g', remote='$repo_dir', commit='62777acc')
@@ -334,9 +334,9 @@
 
   bazel build --nofetch @g//:g >& $TEST_log || fail "Build failed"
   expect_log "External repository 'g' is not up-to-date"
-  assert_contains "GIT 1" bazel-genfiles/external/g/go
+  assert_contains "GIT 1" bazel-out/local-fastbuild/g/go
   bazel build  @g//:g >& $TEST_log || fail "Build failed"
-  assert_contains "GIT 2" bazel-genfiles/external/g/go
+  assert_contains "GIT 2" bazel-out/local-fastbuild/g/go
 }
 
 # Helper function for setting up the workspace as follows
@@ -351,7 +351,7 @@
   mkdir -p planets
   cat > planets/planet_info.sh <<EOF
 #!/bin/bash
-cat external/pluto/info
+cat ../pluto/info
 EOF
 
   cat > planets/BUILD <<EOF
diff --git a/src/test/shell/bazel/local_repository_test.sh b/src/test/shell/bazel/local_repository_test.sh
index d078cad..efda28c 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -550,7 +550,7 @@
 EOF
   bazel fetch //external:best-turtle || fail "Fetch failed"
   bazel build //external:best-turtle &> $TEST_log || fail "First build failed"
-  assert_contains "Leonardo" bazel-genfiles/external/mutant/tmnt
+  assert_contains "Leonardo" bazel-out/local-fastbuild/mutant/tmnt
 
   cat > mutant.BUILD <<EOF
 genrule(
@@ -561,7 +561,7 @@
 )
 EOF
   bazel build //external:best-turtle &> $TEST_log || fail "Second build failed"
-  assert_contains "Donatello" bazel-genfiles/external/mutant/tmnt
+  assert_contains "Donatello" bazel-out/local-fastbuild/mutant/tmnt
 }
 
 function test_external_deps_in_remote_repo() {
@@ -598,7 +598,7 @@
 EOF
 
  bazel build @r//:r || fail "build failed"
- assert_contains "GOLF" bazel-genfiles/external/r/r.out
+ assert_contains "GOLF" bazel-out/local-fastbuild/r/r.out
 }
 
 function test_local_deps() {
@@ -948,7 +948,7 @@
 EOF
 
   bazel build @r//a:b || fail "build failed"
-  cat bazel-genfiles/external/r/a/bo > $TEST_log
+  cat bazel-out/local-fastbuild/r/a/bo > $TEST_log
   expect_log "@r a"
 }
 
diff --git a/src/test/shell/bazel/skylark_repository_test.sh b/src/test/shell/bazel/skylark_repository_test.sh
index 51d738b..fe1d05e 100755
--- a/src/test/shell/bazel/skylark_repository_test.sh
+++ b/src/test/shell/bazel/skylark_repository_test.sh
@@ -286,7 +286,7 @@
   bazel build @foo//:bar >& $TEST_log || fail "Failed to build"
   expect_log "foo"
   expect_not_log "Workspace name in .*/WORKSPACE (@__main__) does not match the name given in the repository's definition (@foo)"
-  cat bazel-genfiles/external/foo/bar.txt >$TEST_log
+  cat bazel-out/local-fastbuild/foo/bar.txt >$TEST_log
   expect_log "foo"
 }
 
diff --git a/src/test/shell/bazel/workspace_test.sh b/src/test/shell/bazel/workspace_test.sh
index 9c63e38..8f1895f 100755
--- a/src/test/shell/bazel/workspace_test.sh
+++ b/src/test/shell/bazel/workspace_test.sh
@@ -48,7 +48,7 @@
 EOF
 
   bazel build @x//:x || fail "build failed"
-  assert_contains "hi" bazel-genfiles/external/x/out
+  assert_contains "hi" bazel-workspace/bazel-out/local-fastbuild/x/out
 
   cat > WORKSPACE <<EOF
 local_repository(
@@ -58,7 +58,7 @@
 EOF
 
   bazel build @x//:x || fail "build failed"
-  assert_contains "bye" bazel-genfiles/external/x/out
+  assert_contains "bye" bazel-workspace/bazel-out/local-fastbuild/x/out
 }
 
 
diff --git a/third_party/ijar/test/BUILD b/third_party/ijar/test/BUILD
index da06173..b0c8a9c 100644
--- a/third_party/ijar/test/BUILD
+++ b/third_party/ijar/test/BUILD
@@ -9,12 +9,11 @@
     size = "enormous",
     srcs = ["ijar_test.sh"],
     args = [
-        "../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)",
+        "$(location @local_jdk//:bin/javac)",
+        "$(location @local_jdk//:bin/java)",
+        "$(location @local_jdk//:bin/jar)",
+        "$(location @local_jdk//:bin/javap)",
+        "$(location //third_party/ijar)",
         # We assume unzip and zip to be on the path
         "unzip",
         "zip",
@@ -43,7 +42,10 @@
         # wrong.
         "libwrongcentraldir.jar",
         "//tools/defaults:jdk",
-        "//tools/jdk:langtools",
+        "@local_jdk//:bin/javac",
+        "@local_jdk//:bin/java",
+        "@local_jdk//:bin/jar",
+        "@local_jdk//:bin/javap",
     ],
     shard_count = 5,
     tags = ["zip"],
diff --git a/third_party/ijar/test/ijar_test.sh b/third_party/ijar/test/ijar_test.sh
index 89f9a4b..2fb2480 100755
--- a/third_party/ijar/test/ijar_test.sh
+++ b/third_party/ijar/test/ijar_test.sh
@@ -26,9 +26,7 @@
 shift
 JAVAP=$1
 shift
-IJAR=$TEST_SRCDIR/$1
-shift
-LANGTOOLS8=$TEST_SRCDIR/$1
+IJAR=$1
 shift
 UNZIP=$1
 shift
@@ -343,7 +341,7 @@
   $JAVAP -classpath $TYPEANN2_IJAR -v Util >& $TEST_log || fail "javap failed"
   expect_log "RuntimeVisibleTypeAnnotations" "RuntimeVisibleTypeAnnotations not preserved!"
   cp $TYPEANN2_JAVA $TEST_TMPDIR/TypeAnnotationTest2.java
-  $JAVAC -J-Xbootclasspath/p:$LANGTOOLS8 $TEST_TMPDIR/TypeAnnotationTest2.java -cp $TYPEANN2_IJAR ||
+  $JAVAC $TEST_TMPDIR/TypeAnnotationTest2.java -cp $TYPEANN2_IJAR ||
     fail "javac failed"
 }