Rollback of commit bdfd58a8ca2ed5735d6aaa5b238fb0f689515724.

--
MOS_MIGRATED_REVID=125160288

13 files changed, 156 insertions, 212 deletions

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 317051b9d4..f9c31ca044 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,26 +150,25 @@ public class ArtifactFactoryTest {
   }
 
   @Test
-  public void testResolveArtifactWithUpLevel() throws Exception {
+  public void testResolveArtifactWithUpLevelFailsCleanly() 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.create("@workspace", new PathFragment("")), clientRoot,
-        PackageIdentifier.create("@repo", new PathFragment("dir")), clientRoot);
+        PackageIdentifier.createInMainRepo(new PathFragment("")), clientRoot);
     artifactFactory.setPackageRoots(packageRoots);
-    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();
+    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));
     MockPackageRootResolver packageRootResolver = new MockPackageRootResolver();
     packageRootResolver.setPackageRoots(packageRoots);
     Map<PathFragment, Artifact> result = new HashMap<>();
-    result.put(topLevel, topLevelArtifact);
-    result.put(subdir, subdirArtifact);
+    result.put(insideWorkspace, null);
+    result.put(outsideWorkspace, null);
     assertThat(
-        artifactFactory.resolveSourceArtifacts(ImmutableList.of(topLevel, subdir),
+        artifactFactory.resolveSourceArtifacts(ImmutableList.of(insideWorkspace, outsideWorkspace),
             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 676eab402a..e43ddd1b28 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,12 +57,13 @@ public class ArtifactTest {
   }
 
   @Test
-  public void testConstruction_UplevelRootDir() throws IOException {
+  public void testConstruction_badRootDir() throws IOException {
     Path f1 = scratch.file("/exec/dir/file.ext");
     Path bogusDir = scratch.file("/exec/dir/bogus");
-    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"));
+    try {
+      new Artifact(f1, Root.asDerivedRoot(bogusDir), f1.relativeTo(execDir));
+      fail("Expected IllegalArgumentException constructing artifact with a bad root dir");
+    } catch (IllegalArgumentException expected) {}
   }
 
   @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 9be749508a..1f83f28005 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 class RunfilesTest extends FoundationTestCase {
   public void testLegacyRunfilesStructure() {
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     PathFragment workspaceName = new PathFragment("wsname");
-    PathFragment pathB = new PathFragment(Label.EXTERNAL_PATH_PREFIX).getRelative("repo/b");
+    PathFragment pathB = new PathFragment("external/repo/b");
     Artifact artifactB = new Artifact(pathB, root);
 
     Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(workspaceName, true);
@@ -335,7 +335,7 @@ public class RunfilesTest extends FoundationTestCase {
     builder.addUnderWorkspace(inputManifest, checker);
 
     assertThat(builder.build().entrySet()).containsExactly(
-        Maps.immutableEntry(workspaceName.getRelative("external/repo/b"), artifactB),
+        Maps.immutableEntry(workspaceName.getRelative(pathB), artifactB),
         Maps.immutableEntry(new PathFragment("repo/b"), artifactB));
     assertNoEvents();
   }
@@ -344,7 +344,7 @@ public class RunfilesTest extends FoundationTestCase {
   public void testRunfileAdded() {
     Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
     PathFragment workspaceName = new PathFragment("wsname");
-    PathFragment pathB = new PathFragment(Label.EXTERNAL_PATH_PREFIX).getRelative("repo/b");
+    PathFragment pathB = new PathFragment("external/repo/b");
     Artifact artifactB = new Artifact(pathB, root);
 
     Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(workspaceName, false);
@@ -361,4 +361,29 @@ public class RunfilesTest extends FoundationTestCase {
         Maps.immutableEntry(new PathFragment("repo/b"), artifactB));
     assertNoEvents();
   }
+
+  // TODO(kchodorow): remove this once the default workspace name is always set.
+  @Test
+  public void testConflictWithExternal() {
+    Root root = Root.asSourceRoot(scratch.resolve("/workspace"));
+    PathFragment pathB = new PathFragment("repo/b");
+    PathFragment externalPathB = Label.EXTERNAL_PACKAGE_NAME.getRelative(pathB);
+    Artifact artifactB = new Artifact(pathB, root);
+    Artifact artifactExternalB = new Artifact(externalPathB, root);
+
+    Runfiles.ManifestBuilder builder = new Runfiles.ManifestBuilder(
+        PathFragment.EMPTY_FRAGMENT, false);
+
+    Map<PathFragment, Artifact> inputManifest = ImmutableMap.<PathFragment, Artifact>builder()
+        .put(pathB, artifactB)
+        .put(externalPathB, artifactExternalB)
+        .build();
+    Runfiles.ConflictChecker checker = new Runfiles.ConflictChecker(
+        Runfiles.ConflictPolicy.WARN, reporter, null);
+    builder.addUnderWorkspace(inputManifest, checker);
+
+    assertThat(builder.build().entrySet()).containsExactly(
+        Maps.immutableEntry(new PathFragment("repo/b"), artifactExternalB));
+    checkConflictWarning();
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index f09b50a6e7..9460d95ab3 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 @@ public abstract class BuildViewTestCase extends FoundationTestCase {
   protected Rule scratchRule(String packageName, String ruleName, String... lines)
       throws Exception {
     String buildFilePathString = packageName + "/BUILD";
-    if (packageName.equals(Label.EXTERNAL_PACKAGE_NAME.getPathString())) {
+    if (packageName.equals(Label.EXTERNAL_PATH_PREFIX)) {
       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
deleted file mode 100644
index 3b4268ade6..0000000000
--- a/src/test/java/com/google/devtools/build/lib/buildtool/BUILD
+++ /dev/null
@@ -1,27 +0,0 @@
-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
deleted file mode 100644
index 365759de0f..0000000000
--- a/src/test/java/com/google/devtools/build/lib/buildtool/SymlinkForestTest.java
+++ /dev/null
@@ -1,159 +0,0 @@
-// 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 d45137029d..47dd0b1d67 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 @@ public class LabelTest {
     Label label = Label.parseAbsolute("//bar/baz");
     assertThat(label.getWorkspaceRoot()).isEmpty();
     label = Label.parseAbsolute("@repo//bar/baz");
-    assertThat(label.getWorkspaceRoot()).isEqualTo("../repo");
+    assertThat(label.getWorkspaceRoot()).isEqualTo("external/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 790af454de..5d32df7f1b 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/PackageIdentifierTest.java
@@ -39,7 +39,8 @@ public class PackageIdentifierTest {
     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("../foo"));
+    assertThat(fooA.getRepository().getPathFragment()).isEqualTo(
+        new PathFragment("external/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 f618a3cf8f..464ce57a4d 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 @@ public class CcCommonConfiguredTargetTest extends BuildViewTestCase {
     checkError(
         "test",
         "bad_relative_include",
-        "../.. references a path above the execution root (..).",
+        "Path 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 80cb217e09..69c68f5a8d 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 @@ public class FileFunctionTest {
   @Test
   public void testAbsoluteSymlinkToExternal() throws Exception {
     String externalPath =
-        outputBase.getRelative(Label.EXTERNAL_PACKAGE_NAME).getRelative("a/b").getPathString();
+        outputBase.getRelative(Label.EXTERNAL_PATH_PREFIX).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 caab4823a1..c96a65e50b 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 @@ public class SkylarkRuleContextTest extends SkylarkTestCase {
     reporter.removeHandler(failFastHandler);
     getConfiguredTarget("@r//:cclib");
     assertContainsEvent(
-        "/r/BUILD:2:10: Label '@r//:sub/my_sub_lib.h' crosses boundary of "
+        "/external/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 1edeaba9e9..717c0b1c3a 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 class TestConstants {
 
   public static final boolean THIS_IS_BAZEL = true;
 
-  public static final String GCC_INCLUDE_PATH = "../bazel_tools/tools/cpp/gcc3";
+  public static final String GCC_INCLUDE_PATH = "external/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 246f8c0931..23e05102dd 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,6 +20,8 @@ import static com.google.devtools.build.lib.vfs.FileSystemUtils.copyTool;
 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;
@@ -35,9 +37,11 @@ import static org.junit.Assert.fail;
 
 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;
@@ -47,9 +51,12 @@ import org.junit.runners.JUnit4;
 
 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.
@@ -184,6 +191,26 @@ public class FileSystemUtilsTest {
     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"));
@@ -672,6 +699,83 @@ public class FileSystemUtilsTest {
     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");