diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BUILD b/src/main/java/com/google/devtools/build/lib/analysis/BUILD
index 570f0c2..6d9af59 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BUILD
@@ -359,6 +359,7 @@
         ":starlark/starlark_toolchain_context",
         ":starlark/starlark_transition",
         ":starlark/template_dict",
+        ":symlink_entry",
         ":target_and_configuration",
         ":template_variable_info",
         ":test/analysis_failure",
@@ -1041,6 +1042,7 @@
     deps = [
         ":actions/abstract_file_write_action",
         ":actions/deterministic_writer",
+        ":symlink_entry",
         "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/lib/actions:artifacts",
         "//src/main/java/com/google/devtools/build/lib/actions:commandline_item",
@@ -1144,6 +1146,18 @@
 )
 
 java_library(
+    name = "symlink_entry",
+    srcs = ["SymlinkEntry.java"],
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib/actions:artifacts",
+        "//src/main/java/com/google/devtools/build/lib/starlarkbuildapi",
+        "//src/main/java/com/google/devtools/build/lib/vfs:pathfragment",
+        "//src/main/java/net/starlark/java/eval",
+        "//third_party:guava",
+    ],
+)
+
+java_library(
     name = "target_and_configuration",
     srcs = ["TargetAndConfiguration.java"],
     deps = [
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RepoMappingManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/RepoMappingManifestAction.java
index 59534d2..347999e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RepoMappingManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RepoMappingManifestAction.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.analysis;
 
-import static com.google.common.collect.ImmutableSet.toImmutableSet;
 import static com.google.common.collect.ImmutableSortedMap.toImmutableSortedMap;
 import static java.nio.charset.StandardCharsets.ISO_8859_1;
 import static java.util.Comparator.comparing;
@@ -30,6 +29,7 @@
 import com.google.devtools.build.lib.actions.ExecException;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
 import com.google.devtools.build.lib.analysis.actions.DeterministicWriter;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -63,8 +63,19 @@
             });
       };
 
+  private static final MapFn<Artifact> OWNER_REPO_FN =
+      (artifact, args) -> {
+        args.accept(
+            artifact.getOwner() != null ? artifact.getOwner().getRepository().getName() : "");
+      };
+
+  private static final MapFn<SymlinkEntry> FIRST_SEGMENT_FN =
+      (symlink, args) -> args.accept(symlink.getPath().getSegment(0));
+
   private final NestedSet<Package> transitivePackages;
   private final NestedSet<Artifact> runfilesArtifacts;
+  private final boolean hasRunfilesSymlinks;
+  private final NestedSet<SymlinkEntry> runfilesRootSymlinks;
   private final String workspaceName;
 
   public RepoMappingManifestAction(
@@ -72,10 +83,15 @@
       Artifact output,
       NestedSet<Package> transitivePackages,
       NestedSet<Artifact> runfilesArtifacts,
+      NestedSet<SymlinkEntry> runfilesSymlinks,
+      NestedSet<SymlinkEntry> runfilesRootSymlinks,
       String workspaceName) {
-    super(owner, NestedSetBuilder.emptySet(Order.STABLE_ORDER), output, /*makeExecutable=*/ false);
+    super(
+        owner, NestedSetBuilder.emptySet(Order.STABLE_ORDER), output, /* makeExecutable= */ false);
     this.transitivePackages = transitivePackages;
     this.runfilesArtifacts = runfilesArtifacts;
+    this.hasRunfilesSymlinks = !runfilesSymlinks.isEmpty();
+    this.runfilesRootSymlinks = runfilesRootSymlinks;
     this.workspaceName = workspaceName;
   }
 
@@ -97,7 +113,9 @@
       throws CommandLineExpansionException, EvalException, InterruptedException {
     fp.addUUID(MY_UUID);
     actionKeyContext.addNestedSetToFingerprint(REPO_AND_MAPPING_DIGEST_FN, fp, transitivePackages);
-    actionKeyContext.addNestedSetToFingerprint(fp, runfilesArtifacts);
+    actionKeyContext.addNestedSetToFingerprint(OWNER_REPO_FN, fp, runfilesArtifacts);
+    fp.addBoolean(hasRunfilesSymlinks);
+    actionKeyContext.addNestedSetToFingerprint(FIRST_SEGMENT_FN, fp, runfilesRootSymlinks);
     fp.addString(workspaceName);
   }
 
@@ -107,11 +125,28 @@
     return out -> {
       PrintWriter writer = new PrintWriter(out, /* autoFlush= */ false, ISO_8859_1);
 
-      ImmutableSet<RepositoryName> reposContributingRunfiles =
-          runfilesArtifacts.toList().stream()
-              .filter(a -> a.getOwner() != null)
-              .map(a -> a.getOwner().getRepository())
-              .collect(toImmutableSet());
+      var reposInRunfilePaths = ImmutableSet.<String>builder();
+
+      // The runfiles paths of symlinks are always prefixed with the main workspace name, *not* the
+      // name of the repository adding the symlink.
+      if (hasRunfilesSymlinks) {
+        reposInRunfilePaths.add(RepositoryName.MAIN.getName());
+      }
+
+      // Since root symlinks are the only way to stage a runfile at a specific path under the
+      // current repository's runfiles directory, recognize canonical repository names that appear
+      // as the first segment of their runfiles paths.
+      for (SymlinkEntry symlink : runfilesRootSymlinks.toList()) {
+        reposInRunfilePaths.add(symlink.getPath().getSegment(0));
+      }
+
+      for (Artifact artifact : runfilesArtifacts.toList()) {
+        Label owner = artifact.getOwner();
+        if (owner != null) {
+          reposInRunfilePaths.add(owner.getRepository().getName());
+        }
+      }
+
       transitivePackages.toList().stream()
           .collect(
               toImmutableSortedMap(
@@ -123,14 +158,14 @@
                   (first, second) -> first))
           .forEach(
               (repoName, mapping) ->
-                  writeRepoMapping(writer, reposContributingRunfiles, repoName, mapping));
+                  writeRepoMapping(writer, reposInRunfilePaths.build(), repoName, mapping));
       writer.flush();
     };
   }
 
   private void writeRepoMapping(
       PrintWriter writer,
-      ImmutableSet<RepositoryName> reposContributingRunfiles,
+      ImmutableSet<String> reposInRunfilesPaths,
       RepositoryName repoName,
       RepositoryMapping repoMapping) {
     for (Entry<String, RepositoryName> mappingEntry :
@@ -140,8 +175,8 @@
         // Rlocation paths can't reference an empty apparent name anyway.
         continue;
       }
-      if (!reposContributingRunfiles.contains(mappingEntry.getValue())) {
-        // We only write entries for repos that actually contribute runfiles.
+      if (!reposInRunfilesPaths.contains(mappingEntry.getValue().getName())) {
+        // We only write entries for repos whose canonical names appear in runfiles paths.
         continue;
       }
       // The canonical name of the main repo is the empty string, which is not a valid name for a
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 f48c350..142f813 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
@@ -41,7 +41,6 @@
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
 import com.google.devtools.build.lib.starlarkbuildapi.RunfilesApi;
-import com.google.devtools.build.lib.starlarkbuildapi.SymlinkEntryApi;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
@@ -56,7 +55,6 @@
 import java.util.UUID;
 import javax.annotation.Nullable;
 import net.starlark.java.eval.EvalException;
-import net.starlark.java.eval.Printer;
 import net.starlark.java.eval.Sequence;
 import net.starlark.java.eval.Starlark;
 import net.starlark.java.eval.StarlarkSemantics;
@@ -93,73 +91,6 @@
   @SerializationConstant @AutoCodec.VisibleForSerialization
   static final EmptyFilesSupplier DUMMY_EMPTY_FILES_SUPPLIER = new DummyEmptyFilesSupplier();
 
-  /**
-   * An entry in the runfiles map.
-   *
-   * <p>build-runfiles.cc enforces the following constraints: The PathFragment must not be an
-   * absolute path, nor contain "..". Overlapping runfiles links are also refused. This is the case
-   * where you ask to create a link to "foo" and also "foo/bar.txt". I.e. you're asking it to make
-   * "foo" both a file (symlink) and a directory.
-   *
-   * <p>Links to directories are heavily discouraged.
-   */
-  //
-  // O intrepid fixer or bugs and implementor of features, dare not to add a .equals() method
-  // to this class, lest you condemn yourself, or a fellow other developer to spending two
-  // delightful hours in a fancy hotel on a Chromebook that is utterly unsuitable for Java
-  // development to figure out what went wrong, just like I just did.
-  //
-  // The semantics of the symlinks nested set dictates that later entries overwrite earlier
-  // ones. However, the semantics of nested sets dictate that if there are duplicate entries, they
-  // are only returned once in the iterator.
-  //
-  // These two things, innocent when taken alone, result in the effect that when there are three
-  // entries for the same path, the first one and the last one the same, and the middle one
-  // different, the *middle* one will take effect: the middle one overrides the first one, and the
-  // first one prevents the last one from appearing on the iterator.
-  //
-  // The lack of a .equals() method prevents this by making the first entry in the above case not
-  // equal to the third one if they are not the same instance (which they almost never are).
-  //
-  // Goodnight, prince(ss)?, and sweet dreams.
-  public static final class SymlinkEntry implements SymlinkEntryApi {
-    private final PathFragment path;
-    private final Artifact artifact;
-
-    SymlinkEntry(PathFragment path, Artifact artifact) {
-      this.path = Preconditions.checkNotNull(path);
-      this.artifact = Preconditions.checkNotNull(artifact);
-    }
-
-    @Override
-    public String getPathString() {
-      return path.getPathString();
-    }
-
-    public PathFragment getPath() {
-      return path;
-    }
-
-    @Override
-    public Artifact getArtifact() {
-      return artifact;
-    }
-
-    @Override
-    public boolean isImmutable() {
-      return true;
-    }
-
-    @Override
-    public void repr(Printer printer) {
-      printer.append("SymlinkEntry(path = ");
-      printer.repr(getPathString());
-      printer.append(", target_file = ");
-      artifact.repr(printer);
-      printer.append(")");
-    }
-  }
-
   // It is important to declare this *after* the DUMMY_SYMLINK_EXPANDER to avoid NPEs
   public static final Runfiles EMPTY = new Builder().build();
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
index 827ddde..a9d0d07 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
@@ -554,7 +554,9 @@
                 ruleContext.getActionOwner(),
                 repoMappingManifest,
                 ruleContext.getTransitivePackagesForRunfileRepoMappingManifest(),
-                runfiles.getAllArtifacts(),
+                runfiles.getArtifacts(),
+                runfiles.getSymlinks(),
+                runfiles.getRootSymlinks(),
                 ruleContext.getWorkspaceName()));
     return repoMappingManifest;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SymlinkEntry.java b/src/main/java/com/google/devtools/build/lib/analysis/SymlinkEntry.java
new file mode 100644
index 0000000..619309f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SymlinkEntry.java
@@ -0,0 +1,88 @@
+// Copyright 2014 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.analysis;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.starlarkbuildapi.SymlinkEntryApi;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import net.starlark.java.eval.Printer;
+
+/**
+ * An entry in the runfiles map.
+ *
+ * <p>build-runfiles.cc enforces the following constraints: The PathFragment must not be an absolute
+ * path, nor contain "..". Overlapping runfiles links are also refused. This is the case where you
+ * ask to create a link to "foo" and also "foo/bar.txt". I.e. you're asking it to make "foo" both a
+ * file (symlink) and a directory.
+ *
+ * <p>Links to directories are heavily discouraged.
+ */
+//
+// O intrepid fixer or bugs and implementor of features, dare not to add a .equals() method
+// to this class, lest you condemn yourself, or a fellow other developer to spending two
+// delightful hours in a fancy hotel on a Chromebook that is utterly unsuitable for Java
+// development to figure out what went wrong, just like I just did.
+//
+// The semantics of the symlinks nested set dictates that later entries overwrite earlier
+// ones. However, the semantics of nested sets dictate that if there are duplicate entries, they
+// are only returned once in the iterator.
+//
+// These two things, innocent when taken alone, result in the effect that when there are three
+// entries for the same path, the first one and the last one the same, and the middle one
+// different, the *middle* one will take effect: the middle one overrides the first one, and the
+// first one prevents the last one from appearing on the iterator.
+//
+// The lack of a .equals() method prevents this by making the first entry in the above case not
+// equal to the third one if they are not the same instance (which they almost never are).
+//
+// Goodnight, prince(ss)?, and sweet dreams.
+public final class SymlinkEntry implements SymlinkEntryApi {
+  private final PathFragment path;
+  private final Artifact artifact;
+
+  SymlinkEntry(PathFragment path, Artifact artifact) {
+    this.path = Preconditions.checkNotNull(path);
+    this.artifact = Preconditions.checkNotNull(artifact);
+  }
+
+  @Override
+  public String getPathString() {
+    return path.getPathString();
+  }
+
+  public PathFragment getPath() {
+    return path;
+  }
+
+  @Override
+  public Artifact getArtifact() {
+    return artifact;
+  }
+
+  @Override
+  public boolean isImmutable() {
+    return true;
+  }
+
+  @Override
+  public void repr(Printer printer) {
+    printer.append("SymlinkEntry(path = ");
+    printer.repr(getPathString());
+    printer.append(", target_file = ");
+    artifact.repr(printer);
+    printer.append(")");
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java
index 9c22766..95c776f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleContext.java
@@ -41,9 +41,9 @@
 import com.google.devtools.build.lib.analysis.ResolvedToolchainContext;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.Runfiles;
-import com.google.devtools.build.lib.analysis.Runfiles.SymlinkEntry;
 import com.google.devtools.build.lib.analysis.RunfilesProvider;
 import com.google.devtools.build.lib.analysis.ShToolchain;
+import com.google.devtools.build.lib.analysis.SymlinkEntry;
 import com.google.devtools.build.lib.analysis.ToolchainCollection;
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationValue;
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
index 0c63756..0ae7e02 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
@@ -79,7 +79,11 @@
       return "<empty>";
     }
     StringBuilder sb = new StringBuilder();
-    sb.append("order: ").append(nestedSet.getOrder()).append('\n');
+    sb.append("order: ")
+        .append(nestedSet.getOrder())
+        .append(
+            " (fingerprinting considers internal"
+                + " nested set structure, which is not reflected in values reported below)\n");
     ImmutableList<T> list = nestedSet.toList();
     sb.append("size: ").append(list.size()).append('\n');
     for (T item : list) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyBuiltins.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyBuiltins.java
index cc0190c..1686043 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyBuiltins.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyBuiltins.java
@@ -322,7 +322,9 @@
                 ruleContext.getActionOwner(),
                 repoMappingManifest,
                 ruleContext.getTransitivePackagesForRunfileRepoMappingManifest(),
-                runfiles.getAllArtifacts(),
+                runfiles.getArtifacts(),
+                runfiles.getSymlinks(),
+                runfiles.getRootSymlinks(),
                 ruleContext.getWorkspaceName()));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkRuleContextApi.java b/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkRuleContextApi.java
index 4b92f7e..6410570 100644
--- a/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkRuleContextApi.java
+++ b/src/main/java/com/google/devtools/build/lib/starlarkbuildapi/StarlarkRuleContextApi.java
@@ -557,8 +557,10 @@
               @ParamType(type = Depset.class, generic1 = SymlinkEntryApi.class)
             },
             doc =
-                "Either a SymlinkEntry depset or the map of symlinks, prefixed by workspace name,"
-                    + " to be added to the runfiles. See <a"
+                "Either a SymlinkEntry depset or the map of symlinks to be added to the runfiles."
+                    + " Symlinks are always added under the main workspace's runfiles directory"
+                    + " (e.g. <code>&lt;runfiles_root>/_main/&lt;symlink_path></code>, <b>not</b>"
+                    + " the directory corresponding to the current target's repository. See <a"
                     + " href=\"https://bazel.build/extending/rules#runfiles_symlinks\">Runfiles"
                     + " symlinks</a> in the rules guide."),
         @Param(