diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
index 1c88ca3..e203a82 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
@@ -44,7 +44,7 @@
 import com.google.devtools.build.lib.analysis.starlark.StarlarkModules;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.graph.Digraph;
 import com.google.devtools.build.lib.graph.Node;
 import com.google.devtools.build.lib.packages.BazelStarlarkContext;
@@ -948,9 +948,7 @@
 
   @Override
   public void setStarlarkThreadContext(
-      StarlarkThread thread,
-      Label fileLabel,
-      ImmutableMap<RepositoryName, RepositoryName> repoMapping) {
+      StarlarkThread thread, Label fileLabel, RepositoryMapping repoMapping) {
     new BazelStarlarkContext(
             BazelStarlarkContext.Phase.LOADING,
             toolsRepository,
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java b/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
index 0b7c755..f8f5b78 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
@@ -28,7 +28,7 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.util.ShellEscaper;
@@ -68,13 +68,13 @@
 
   private final RuleErrorConsumer ruleErrorConsumer;
   private final ImmutableMap<String, LocationFunction> functions;
-  private final ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
+  private final RepositoryMapping repositoryMapping;
 
   @VisibleForTesting
   LocationExpander(
       RuleErrorConsumer ruleErrorConsumer,
       Map<String, LocationFunction> functions,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+      RepositoryMapping repositoryMapping) {
     this.ruleErrorConsumer = ruleErrorConsumer;
     this.functions = ImmutableMap.copyOf(functions);
     this.repositoryMapping = repositoryMapping;
@@ -86,7 +86,7 @@
       Supplier<Map<Label, Collection<Artifact>>> locationMap,
       boolean execPaths,
       boolean legacyExternalRunfiles,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+      RepositoryMapping repositoryMapping) {
     this(
         ruleErrorConsumer,
         allLocationFunctions(root, locationMap, execPaths, legacyExternalRunfiles),
@@ -260,8 +260,7 @@
      * @param repositoryMapping map of {@code RepositoryName}s defined in the main workspace
      * @return The expanded value
      */
-    public String apply(
-        String arg, ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+    public String apply(String arg, RepositoryMapping repositoryMapping) {
       Label label;
       try {
         label = root.getRelativeWithRemapping(arg, repositoryMapping);
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/LocationTemplateContext.java b/src/main/java/com/google/devtools/build/lib/analysis/LocationTemplateContext.java
index 494d39a..22d0097 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/LocationTemplateContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/LocationTemplateContext.java
@@ -23,7 +23,7 @@
 import com.google.devtools.build.lib.analysis.stringtemplate.ExpansionException;
 import com.google.devtools.build.lib.analysis.stringtemplate.TemplateContext;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import java.util.Collection;
 import java.util.Map;
 import javax.annotation.Nullable;
@@ -48,7 +48,7 @@
 final class LocationTemplateContext implements TemplateContext {
   private final TemplateContext delegate;
   private final ImmutableMap<String, LocationFunction> functions;
-  private final ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
+  private final RepositoryMapping repositoryMapping;
   private final boolean windowsPath;
 
   private LocationTemplateContext(
@@ -57,7 +57,7 @@
       Supplier<Map<Label, Collection<Artifact>>> locationMap,
       boolean execPaths,
       boolean legacyExternalRunfiles,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping,
+      RepositoryMapping repositoryMapping,
       boolean windowsPath) {
     this.delegate = delegate;
     this.functions =
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/StarlarkDefinedConfigTransition.java b/src/main/java/com/google/devtools/build/lib/analysis/config/StarlarkDefinedConfigTransition.java
index e9725b8..ac8a957 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/StarlarkDefinedConfigTransition.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/StarlarkDefinedConfigTransition.java
@@ -24,7 +24,7 @@
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.BazelStarlarkContext;
@@ -81,7 +81,7 @@
   private StarlarkDefinedConfigTransition(
       List<String> inputs,
       List<String> outputs,
-      ImmutableMap<RepositoryName, RepositoryName> repoMapping,
+      RepositoryMapping repoMapping,
       Label parentLabel,
       Location location)
       throws EvalException {
@@ -99,7 +99,7 @@
    * //command_line_option:<option-name>).
    */
   private static String canonicalizeSetting(
-      String setting, ImmutableMap<RepositoryName, RepositoryName> repoMapping, Label parentLabel)
+      String setting, RepositoryMapping repoMapping, Label parentLabel)
       throws LabelSyntaxException {
     String canonicalizedString = setting;
     // native options
@@ -121,7 +121,7 @@
    *     "//command_line_option:<option-name>"
    */
   private static ImmutableMap<String, String> getCanonicalizedSettings(
-      ImmutableMap<RepositoryName, RepositoryName> repoMapping,
+      RepositoryMapping repoMapping,
       Label parentLabel,
       List<String> settings,
       Settings inputsOrOutputs)
@@ -213,7 +213,7 @@
 
   public static StarlarkDefinedConfigTransition newAnalysisTestTransition(
       Map<String, Object> changedSettings,
-      ImmutableMap<RepositoryName, RepositoryName> repoMapping,
+      RepositoryMapping repoMapping,
       Label parentLabel,
       Location location)
       throws EvalException {
@@ -225,7 +225,7 @@
 
     public AnalysisTestTransition(
         Map<String, Object> changedSettings,
-        ImmutableMap<RepositoryName, RepositoryName> repoMapping,
+        RepositoryMapping repoMapping,
         Label parentLabel,
         Location location)
         throws EvalException {
@@ -280,7 +280,7 @@
   public static class RegularTransition extends StarlarkDefinedConfigTransition {
     private final StarlarkCallable impl;
     private final StarlarkSemantics semantics;
-    private final ImmutableMap<RepositoryName, RepositoryName> repoMapping;
+    private final RepositoryMapping repoMapping;
     private final Label parentLabel;
 
     RegularTransition(
@@ -290,7 +290,7 @@
         StarlarkSemantics semantics,
         Label parentLabel,
         Location location,
-        ImmutableMap<RepositoryName, RepositoryName> repoMapping)
+        RepositoryMapping repoMapping)
         throws EvalException {
       super(inputs, outputs, repoMapping, parentLabel, location);
       this.impl = impl;
@@ -484,7 +484,7 @@
      */
     private static ImmutableMap<String, Object> canonicalizeTransitionOutputDict(
         Map<String, Object> dict,
-        ImmutableMap<RepositoryName, RepositoryName> repoMapping,
+        RepositoryMapping repoMapping,
         Label parentLabel,
         List<String> outputs)
         throws EvalException, ValidationException {
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/BUILD b/src/main/java/com/google/devtools/build/lib/cmdline/BUILD
index d61a46b..bd3fff0 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/BUILD
@@ -52,6 +52,7 @@
         "LabelConstants.java",
         "LabelSyntaxException.java",
         "PackageIdentifier.java",
+        "RepositoryMapping.java",
         "RepositoryName.java",
     ],
     deps = [
@@ -62,6 +63,7 @@
         "//src/main/java/com/google/devtools/build/lib/util",
         "//src/main/java/com/google/devtools/build/lib/util:string",
         "//src/main/java/com/google/devtools/build/lib/vfs:pathfragment",
+        "//third_party:auto_value",
         "//third_party:caffeine",
         "//third_party:guava",
         "//third_party:jsr305",
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 8991586..fbd4c3d 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
@@ -105,10 +105,18 @@
    * @param repositoryMapping map of repository names from the local name found in the current
    *     repository to the global name declared in the main repository
    */
+  public static Label parseAbsolute(String absName, RepositoryMapping repositoryMapping)
+      throws LabelSyntaxException {
+    return parseAbsolute(absName, /*defaultToMain=*/ true, repositoryMapping);
+  }
+
   public static Label parseAbsolute(
       String absName, ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
       throws LabelSyntaxException {
-    return parseAbsolute(absName, /*defaultToMain=*/ true, repositoryMapping);
+    return parseAbsolute(
+        absName,
+        /*defaultToMain=*/ true,
+        RepositoryMapping.createAllowingFallback(repositoryMapping));
   }
 
   /**
@@ -133,9 +141,7 @@
    *     repository to the global name declared in the main repository
    */
   public static Label parseAbsolute(
-      String absName,
-      boolean defaultToMain,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
+      String absName, boolean defaultToMain, RepositoryMapping repositoryMapping)
       throws LabelSyntaxException {
     Preconditions.checkNotNull(repositoryMapping);
     String repo = defaultToMain ? "@" : RepositoryName.DEFAULT_REPOSITORY;
@@ -159,8 +165,10 @@
               labelParts.getPackageName(), labelParts.getTargetName(), repo, repositoryMapping);
       PathFragment packageFragment = pkgId.getPackageFragment();
       if (repo.isEmpty() && ABSOLUTE_PACKAGE_NAMES.contains(packageFragment)) {
-        RepositoryName globalRepo =
-            repositoryMapping.getOrDefault(RepositoryName.MAIN, RepositoryName.MAIN);
+        RepositoryName globalRepo = repositoryMapping.get(RepositoryName.MAIN);
+        if (globalRepo == null) {
+          globalRepo = RepositoryName.MAIN;
+        }
         pkgId = PackageIdentifier.create(globalRepo, packageFragment);
       }
       return create(pkgId, labelParts.getTargetName());
@@ -169,6 +177,15 @@
     }
   }
 
+  public static Label parseAbsolute(
+      String absName,
+      boolean defaultToMain,
+      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
+      throws LabelSyntaxException {
+    return parseAbsolute(
+        absName, defaultToMain, RepositoryMapping.createAllowingFallback(repositoryMapping));
+  }
+
   /**
    * Alternate factory method for Labels from absolute strings. This is a convenience method for
    * cases when a Label needs to be initialized statically, so the declared exception is
@@ -253,7 +270,7 @@
       throws LabelSyntaxException {
     Preconditions.checkArgument(!workspaceRelativePath.isAbsolute());
     if (LabelValidator.isAbsolute(label)) {
-      return parseAbsolute(label, ImmutableMap.of());
+      return parseAbsolute(label, RepositoryMapping.ALWAYS_FALLBACK);
     }
     int index = label.indexOf(':');
     if (index < 0) {
@@ -299,10 +316,7 @@
    * it is valid. Otherwise it throws a SyntaxException.
    */
   private static PackageIdentifier validatePackageName(
-      String packageIdentifier,
-      String name,
-      String repo,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
+      String packageIdentifier, String name, String repo, RepositoryMapping repositoryMapping)
       throws LabelSyntaxException {
     try {
       return PackageIdentifier.parse(packageIdentifier, repo, repositoryMapping);
@@ -548,7 +562,7 @@
    * that type here because logically it belongs in Bazel, above this package.
    */
   public interface HasRepoMapping {
-    ImmutableMap<RepositoryName, RepositoryName> getRepoMapping();
+    RepositoryMapping getRepoMapping();
   }
 
   /**
@@ -565,8 +579,7 @@
    * @param repositoryMapping the map of local repository names in external repository to global
    *     repository names in main repo; can be empty, but not null
    */
-  public Label getRelativeWithRemapping(
-      String relName, ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
+  public Label getRelativeWithRemapping(String relName, RepositoryMapping repositoryMapping)
       throws LabelSyntaxException {
     Preconditions.checkNotNull(repositoryMapping);
     if (relName.isEmpty()) {
@@ -587,6 +600,13 @@
     }
   }
 
+  public Label getRelativeWithRemapping(
+      String relName, ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
+      throws LabelSyntaxException {
+    return getRelativeWithRemapping(
+        relName, RepositoryMapping.createAllowingFallback(repositoryMapping));
+  }
+
   /**
    * Resolves the repository of a label in the context of another label.
    *
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 78a6157..5c1196d 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
@@ -16,7 +16,6 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ComparisonChain;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
@@ -120,8 +119,7 @@
   }
 
   public static PackageIdentifier parse(
-      String input, String repo, ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
-      throws LabelSyntaxException {
+      String input, String repo, RepositoryMapping repositoryMapping) throws LabelSyntaxException {
     String packageName;
     int packageStartPos = input.indexOf("//");
     if (repo != null) {
@@ -150,12 +148,12 @@
     }
 
     if (repositoryMapping != null) {
-      RepositoryName repositoryName = RepositoryName.create(repo);
-      repositoryName = repositoryMapping.getOrDefault(repositoryName, repositoryName);
-      return create(repositoryName, PathFragment.create(packageName));
-    } else {
-      return create(repo, PathFragment.create(packageName));
+      RepositoryName mappedRepo = repositoryMapping.get(RepositoryName.create(repo));
+      if (mappedRepo != null) {
+        return create(mappedRepo, PathFragment.create(packageName));
+      }
     }
+    return create(repo, PathFragment.create(packageName));
   }
 
   public RepositoryName getRepository() {
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryMapping.java b/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryMapping.java
new file mode 100644
index 0000000..c7cb874
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryMapping.java
@@ -0,0 +1,60 @@
+// Copyright 2021 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.cmdline;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableMap;
+import java.util.Map;
+import javax.annotation.Nullable;
+
+/**
+ * A class to distinguish repository mappings for repos from WORKSPACE and Bzlmod.
+ *
+ * <p>For repositories from the WORKSPACE file, if the requested repo doesn't exist in the mapping,
+ * we fallback to the requested name. For repositories from Bzlmod, we return null to let the caller
+ * decide what to do. This class won't be needed if one day we don't define external repositories in
+ * the WORKSPACE file since {@code fallback} would always be false.
+ */
+@AutoValue
+public abstract class RepositoryMapping {
+
+  // Always fallback to the requested name
+  public static final RepositoryMapping ALWAYS_FALLBACK = createAllowingFallback(ImmutableMap.of());
+
+  abstract ImmutableMap<RepositoryName, RepositoryName> repositoryMapping();
+
+  abstract boolean fallback();
+
+  public static RepositoryMapping create(Map<RepositoryName, RepositoryName> repositoryMapping) {
+    return new AutoValue_RepositoryMapping(
+        ImmutableMap.copyOf(Preconditions.checkNotNull(repositoryMapping)), /* fallback= */ false);
+  }
+
+  public static RepositoryMapping createAllowingFallback(
+      Map<RepositoryName, RepositoryName> repositoryMapping) {
+    return new AutoValue_RepositoryMapping(
+        ImmutableMap.copyOf(Preconditions.checkNotNull(repositoryMapping)), /* fallback= */ true);
+  }
+
+  @Nullable
+  public RepositoryName get(RepositoryName repositoryName) {
+    if (fallback()) {
+      return repositoryMapping().getOrDefault(repositoryName, repositoryName);
+    } else {
+      return repositoryMapping().get(repositoryName);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
index c3fc185..dc11bfb 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
@@ -40,7 +40,6 @@
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
-import java.util.Map;
 import java.util.Objects;
 import java.util.regex.Pattern;
 import javax.annotation.concurrent.Immutable;
@@ -818,8 +817,7 @@
    * part of the pattern is not syntactically valid, the renaming simply does not match and the
    * string is returned unchanged.
    */
-  public static String renameRepository(
-      String pattern, Map<RepositoryName, RepositoryName> renaming) {
+  public static String renameRepository(String pattern, RepositoryMapping renaming) {
     if (!pattern.startsWith("@")) {
       return pattern;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/BazelStarlarkContext.java b/src/main/java/com/google/devtools/build/lib/packages/BazelStarlarkContext.java
index e8dd362..ed66d7b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/BazelStarlarkContext.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/BazelStarlarkContext.java
@@ -20,7 +20,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.RuleDefinitionEnvironment;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import java.util.HashMap;
 import java.util.Optional;
 import javax.annotation.Nullable;
@@ -63,7 +63,7 @@
   @Nullable private final String toolsRepository;
   // Only necessary for loading phase threads to construct configuration_field.
   @Nullable private final ImmutableMap<String, Class<?>> fragmentNameToClass;
-  private final ImmutableMap<RepositoryName, RepositoryName> repoMapping;
+  private final RepositoryMapping repoMapping;
   private final HashMap<String, Label> convertedLabelsInPackage;
   private final SymbolGenerator<?> symbolGenerator;
   @Nullable private final Label analysisRuleLabel;
@@ -97,7 +97,7 @@
       Phase phase,
       @Nullable String toolsRepository,
       @Nullable ImmutableMap<String, Class<?>> fragmentNameToClass,
-      ImmutableMap<RepositoryName, RepositoryName> repoMapping,
+      RepositoryMapping repoMapping,
       HashMap<String, Label> convertedLabelsInPackage,
       SymbolGenerator<?> symbolGenerator,
       @Nullable Label analysisRuleLabel,
@@ -130,7 +130,7 @@
    * in the BUILD files and the values are new repository names chosen by the main repository.
    */
   @Override
-  public ImmutableMap<RepositoryName, RepositoryName> getRepoMapping() {
+  public RepositoryMapping getRepoMapping() {
     return repoMapping;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/BuildType.java b/src/main/java/com/google/devtools/build/lib/packages/BuildType.java
index 6482c7a..6999256 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/BuildType.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/BuildType.java
@@ -21,7 +21,7 @@
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.packages.License.DistributionType;
 import com.google.devtools.build.lib.packages.License.LicenseParsingException;
 import com.google.devtools.build.lib.packages.Type.ConversionException;
@@ -157,12 +157,12 @@
   /** Context in which to evaluate a label with repository remappings */
   public static class LabelConversionContext {
     private final Label label;
-    private final ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
+    private final RepositoryMapping repositoryMapping;
     private final HashMap<String, Label> convertedLabelsInPackage;
 
     public LabelConversionContext(
         Label label,
-        ImmutableMap<RepositoryName, RepositoryName> repositoryMapping,
+        RepositoryMapping repositoryMapping,
         HashMap<String, Label> convertedLabelsInPackage) {
       this.label = label;
       this.repositoryMapping = repositoryMapping;
@@ -187,7 +187,7 @@
       return converted;
     }
 
-    ImmutableMap<RepositoryName, RepositoryName> getRepositoryMapping() {
+    RepositoryMapping getRepositoryMapping() {
       return repositoryMapping;
     }
 
@@ -444,7 +444,7 @@
       try {
         // Enforce value is relative to the context.
         Label currentRule;
-        ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
+        RepositoryMapping repositoryMapping;
         if (context instanceof LabelConversionContext) {
           currentRule = ((LabelConversionContext) context).getLabel();
           repositoryMapping = ((LabelConversionContext) context).getRepositoryMapping();
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 7b19826..6f919b5 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
@@ -33,6 +33,7 @@
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
@@ -228,10 +229,10 @@
       externalPackageRepositoryMappings;
 
   /**
-   * The map of repository reassignments for BUILD packages. This will be empty for packages
-   * within the main workspace.
+   * The map of repository reassignments for BUILD packages. This will be empty for packages within
+   * the main workspace.
    */
-  private ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
+  private RepositoryMapping repositoryMapping;
 
   private Set<Label> defaultCompatibleWith = ImmutableSet.of();
   private Set<Label> defaultRestrictedTo = ImmutableSet.of();
@@ -307,7 +308,7 @@
   }
 
   /** Get the repository mapping for this package. */
-  public ImmutableMap<RepositoryName, RepositoryName> getRepositoryMapping() {
+  public RepositoryMapping getRepositoryMapping() {
     return repositoryMapping;
   }
 
@@ -858,7 +859,7 @@
             LabelConstants.EXTERNAL_PACKAGE_IDENTIFIER,
             workspaceName,
             starlarkSemantics.getBool(BuildLanguageOptions.INCOMPATIBLE_NO_IMPLICIT_FILE_EXPORT),
-            Builder.EMPTY_REPOSITORY_MAPPING)
+            RepositoryMapping.ALWAYS_FALLBACK)
         .setFilename(workspacePath);
   }
 
@@ -942,7 +943,7 @@
      * It contains an entry from "@<main workspace name>" to "@" for packages within the main
      * workspace.
      */
-    private final ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
+    private final RepositoryMapping repositoryMapping;
 
     private RootedPath filename = null;
     private Label buildFileLabel = null;
@@ -1066,7 +1067,7 @@
         PackageIdentifier id,
         String workspaceName,
         boolean noImplicitFileExport,
-        ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+        RepositoryMapping repositoryMapping) {
       this.pkg = new Package(id, workspaceName, packageSettings.succinctTargetNotFoundErrors());
       this.noImplicitFileExport = noImplicitFileExport;
       this.repositoryMapping = repositoryMapping;
@@ -1124,7 +1125,7 @@
     }
 
     /** Get the repository mapping for this package */
-    ImmutableMap<RepositoryName, RepositoryName> getRepositoryMapping() {
+    RepositoryMapping getRepositoryMapping() {
       return this.repositoryMapping;
     }
 
@@ -1159,12 +1160,12 @@
      * are only discovered while constructing the external package (e.g., the mapping of the name of
      * the main workspace to the canonical main name '@').
      */
-    ImmutableMap<RepositoryName, RepositoryName> getRepositoryMappingFor(RepositoryName name) {
+    RepositoryMapping getRepositoryMappingFor(RepositoryName name) {
       Map<RepositoryName, RepositoryName> mapping = externalPackageRepositoryMappings.get(name);
       if (mapping == null) {
-        return ImmutableMap.of();
+        return RepositoryMapping.ALWAYS_FALLBACK;
       } else {
-        return ImmutableMap.copyOf(mapping);
+        return RepositoryMapping.createAllowingFallback(mapping);
       }
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index c6354c4..aa2ca22 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -24,7 +24,7 @@
 import com.google.devtools.build.lib.actions.ThreadStateReceiver;
 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.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.concurrent.NamedForkJoinPool;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
@@ -458,7 +458,7 @@
       PackageIdentifier packageId,
       String workspaceName,
       StarlarkSemantics starlarkSemantics,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+      RepositoryMapping repositoryMapping) {
     return new Package.Builder(
         packageSettings,
         packageId,
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index 0f36553..581da69 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -42,7 +42,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.NullEventHandler;
 import com.google.devtools.build.lib.packages.Attribute.ComputedDefault;
@@ -2156,7 +2156,7 @@
    */
   private <T> BitSet populateDefinedRuleAttributeValues(
       Rule rule,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping,
+      RepositoryMapping repositoryMapping,
       AttributeValues<T> attributeValues,
       Interner<ImmutableList<?>> listInterner,
       HashMap<String, Label> convertedLabelsInPackage,
@@ -2494,7 +2494,7 @@
       Rule rule,
       Attribute attr,
       Object buildLangValue,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping,
+      RepositoryMapping repositoryMapping,
       Interner<ImmutableList<?>> listInterner,
       HashMap<String, Label> convertedLabelsInPackage)
       throws ConversionException {
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java
index ad0ed09..bc68664 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClassProvider.java
@@ -17,7 +17,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.RuleDefinitionEnvironment;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.packages.RuleClass.Builder.ThirdPartyLicenseExistencePolicy;
 import com.google.devtools.build.lib.vfs.Root;
 import java.util.Map;
@@ -67,8 +67,7 @@
    * @param label the label of the .bzl file
    * @param repoMapping map of RepositoryNames to be remapped
    */
-  void setStarlarkThreadContext(
-      StarlarkThread thread, Label label, ImmutableMap<RepositoryName, RepositoryName> repoMapping);
+  void setStarlarkThreadContext(StarlarkThread thread, Label label, RepositoryMapping repoMapping);
 
   /**
    * Returns all the predeclared top-level symbols (for .bzl files) that belong to native rule sets,
diff --git a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
index f2d9b89..ff69a23 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.NullEventHandler;
@@ -137,7 +138,7 @@
               BazelStarlarkContext.Phase.WORKSPACE,
               /*toolsRepository=*/ null,
               /*fragmentNameToClass=*/ null,
-              /*repoMapping=*/ ImmutableMap.of(),
+              /*repoMapping=*/ RepositoryMapping.ALWAYS_FALLBACK,
               /*convertedLabelsInPackage=*/ new HashMap<>(),
               new SymbolGenerator<>(workspaceFileKey),
               /*analysisRuleLabel=*/ null,
diff --git a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceGlobals.java b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceGlobals.java
index 233dd0c..dc4eb35 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceGlobals.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceGlobals.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.LabelValidator;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
 import com.google.devtools.build.lib.packages.Package.NameConflictException;
@@ -236,7 +237,7 @@
     BazelModuleContext bzlModule =
         BazelModuleContext.of(Module.ofInnermostEnclosingStarlarkFunction(thread));
     RepositoryName myName = getRepositoryName((bzlModule != null ? bzlModule.label() : null));
-    Map<RepositoryName, RepositoryName> renaming = builder.getRepositoryMappingFor(myName);
+    RepositoryMapping renaming = builder.getRepositoryMappingFor(myName);
     return patterns.stream()
         .map(patternEntry -> TargetPattern.renameRepository(patternEntry, renaming))
         .collect(ImmutableList.toImmutableList());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/config/ConfigGlobalLibrary.java b/src/main/java/com/google/devtools/build/lib/rules/config/ConfigGlobalLibrary.java
index 6ffa0f9..a7ad193 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/config/ConfigGlobalLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/config/ConfigGlobalLibrary.java
@@ -16,12 +16,11 @@
 
 import static com.google.devtools.build.lib.analysis.config.StarlarkDefinedConfigTransition.COMMAND_LINE_OPTION_PREFIX;
 
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.analysis.config.StarlarkDefinedConfigTransition;
 import com.google.devtools.build.lib.analysis.config.StarlarkDefinedConfigTransition.Settings;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.packages.BazelModuleContext;
 import com.google.devtools.build.lib.packages.BazelStarlarkContext;
 import com.google.devtools.build.lib.starlarkbuildapi.config.ConfigGlobalLibraryApi;
@@ -74,8 +73,7 @@
     Map<String, Object> changedSettingsMap =
         Dict.cast(changedSettings, String.class, Object.class, "changed_settings dict");
     validateBuildSettingKeys(changedSettingsMap.keySet(), Settings.OUTPUTS);
-    ImmutableMap<RepositoryName, RepositoryName> repoMapping =
-        BazelStarlarkContext.from(thread).getRepoMapping();
+    RepositoryMapping repoMapping = BazelStarlarkContext.from(thread).getRepoMapping();
     Label parentLabel =
         BazelModuleContext.of(Module.ofInnermostEnclosingStarlarkFunction(thread)).label();
     Location location = thread.getCallerLocation();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BzlLoadFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/BzlLoadFunction.java
index 55f3a89..e9ccf18 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BzlLoadFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BzlLoadFunction.java
@@ -28,7 +28,7 @@
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
@@ -726,7 +726,7 @@
 
     // Determine dependency BzlLoadValue keys for the load statements in this bzl.
     // Labels are resolved relative to the current repo mapping.
-    ImmutableMap<RepositoryName, RepositoryName> repoMapping = getRepositoryMapping(key, env);
+    RepositoryMapping repoMapping = getRepositoryMapping(key, env);
     if (repoMapping == null) {
       return null;
     }
@@ -803,26 +803,25 @@
     return new BzlLoadValue(module, transitiveDigest);
   }
 
-  private static ImmutableMap<RepositoryName, RepositoryName> getRepositoryMapping(
-      BzlLoadValue.Key key, Environment env) throws InterruptedException {
+  private static RepositoryMapping getRepositoryMapping(BzlLoadValue.Key key, Environment env)
+      throws InterruptedException {
     if (key.isBuiltins()) {
       // Builtins .bzls never have a repo mapping defined for them, so return without requesting a
       // RepositoryMappingValue. (NB: In addition to being a slight optimization, this avoids
       // adding a reverse dependency on the special //external package, which helps avoid tickling
       // some peculiarities of the Google-internal Skyframe implementation; see b/182293526 for
       // details.)
-      return ImmutableMap.of();
+      return RepositoryMapping.ALWAYS_FALLBACK;
     }
 
     Label enclosingFileLabel = key.getLabel();
 
-    ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
     if (key instanceof BzlLoadValue.KeyForWorkspace) {
       // Still during workspace file evaluation
       BzlLoadValue.KeyForWorkspace keyForWorkspace = (BzlLoadValue.KeyForWorkspace) key;
       if (keyForWorkspace.getWorkspaceChunk() == 0) {
         // There is no previous workspace chunk
-        repositoryMapping = ImmutableMap.of();
+        return RepositoryMapping.ALWAYS_FALLBACK;
       } else {
         SkyKey workspaceFileKey =
             WorkspaceFileValue.key(
@@ -830,27 +829,28 @@
         WorkspaceFileValue workspaceFileValue = (WorkspaceFileValue) env.getValue(workspaceFileKey);
         // Note: we know for sure that the requested WorkspaceFileValue is fully computed so we do
         // not need to check if it is null
-        repositoryMapping =
+        return RepositoryMapping.create(
             workspaceFileValue
                 .getRepositoryMapping()
-                .getOrDefault(enclosingFileLabel.getRepository(), ImmutableMap.of());
+                .getOrDefault(enclosingFileLabel.getRepository(), ImmutableMap.of()));
       }
-    } else if (key instanceof BzlLoadValue.KeyForBzlmod) {
-      // TODO(pcloudy): Implement repo mapping for bzlmod repos
-      return ImmutableMap.of();
-    } else {
-      // We are fully done with workspace evaluation so we should get the mappings from the
-      // final RepositoryMappingValue
-      PackageIdentifier packageIdentifier = enclosingFileLabel.getPackageIdentifier();
-      RepositoryMappingValue repositoryMappingValue =
-          (RepositoryMappingValue)
-              env.getValue(RepositoryMappingValue.key(packageIdentifier.getRepository()));
-      if (repositoryMappingValue == null) {
-        return null;
-      }
-      repositoryMapping = repositoryMappingValue.getRepositoryMapping();
     }
-    return repositoryMapping;
+
+    if (key instanceof BzlLoadValue.KeyForBzlmod) {
+      // TODO(pcloudy): Implement repo mapping for Bzlmod repos
+      return RepositoryMapping.ALWAYS_FALLBACK;
+    }
+
+    // We are fully done with workspace evaluation so we should get the mappings from the
+    // final RepositoryMappingValue
+    PackageIdentifier packageIdentifier = enclosingFileLabel.getPackageIdentifier();
+    RepositoryMappingValue repositoryMappingValue =
+        (RepositoryMappingValue)
+            env.getValue(RepositoryMappingValue.key(packageIdentifier.getRepository()));
+    if (repositoryMappingValue == null) {
+      return null;
+    }
+    return repositoryMappingValue.getRepositoryMapping();
   }
 
   /**
@@ -864,7 +864,7 @@
       EventHandler handler,
       ImmutableList<Pair<String, Location>> loads,
       PackageIdentifier base,
-      ImmutableMap<RepositoryName, RepositoryName> repoMapping) {
+      RepositoryMapping repoMapping) {
     Preconditions.checkArgument(!base.getRepository().isDefault());
 
     // It's redundant that getRelativeWithRemapping needs a Label;
@@ -1061,7 +1061,7 @@
       Map<String, Module> loadedModules,
       StarlarkSemantics starlarkSemantics,
       ExtendedEventHandler skyframeEventHandler,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping)
+      RepositoryMapping repositoryMapping)
       throws BzlLoadFailedException, InterruptedException {
     try (Mutability mu = Mutability.create("loading", label)) {
       StarlarkThread thread = new StarlarkThread(mu, starlarkSemantics);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BzlmodRepoRuleFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/BzlmodRepoRuleFunction.java
index a9b2d5d..fae317c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BzlmodRepoRuleFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BzlmodRepoRuleFunction.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.Package;
@@ -174,7 +175,10 @@
 
     ImmutableList<Label> loadLabels =
         BzlLoadFunction.getLoadLabels(
-            env.getListener(), programLoads, ROOT_PACKAGE, /*repoMapping=*/ ImmutableMap.of());
+            env.getListener(),
+            programLoads,
+            ROOT_PACKAGE,
+            /*repoMapping=*/ RepositoryMapping.ALWAYS_FALLBACK);
     if (loadLabels == null) {
       NoSuchPackageException e =
           PackageFunction.PackageFunctionException.builder()
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 63a2da6..ab8ca3f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -33,7 +33,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler.Postable;
@@ -494,8 +494,7 @@
     }
 
     String workspaceName = workspaceNameValue.getName();
-    ImmutableMap<RepositoryName, RepositoryName> repositoryMapping =
-        repositoryMappingValue.getRepositoryMapping();
+    RepositoryMapping repositoryMapping = repositoryMappingValue.getRepositoryMapping();
 
     Label preludeLabel = null;
     // Can be null in tests.
@@ -1239,7 +1238,7 @@
   @Nullable
   private LoadedPackageCacheEntry loadPackage(
       String workspaceName,
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping,
+      RepositoryMapping repositoryMapping,
       ImmutableSet<PathFragment> repositoryIgnoredPatterns,
       PackageIdentifier packageId,
       RootedPath buildFilePath,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunction.java
index 07f3317..b5ac487 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunction.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.bazel.bzlmod.ModuleKey;
 import com.google.devtools.build.lib.bazel.bzlmod.SelectionValue;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.Package;
@@ -50,8 +51,7 @@
         return null;
       }
 
-      Optional<ImmutableMap<RepositoryName, RepositoryName>> mapping =
-          computeFromBzlmod(repositoryName, selectionValue);
+      Optional<RepositoryMapping> mapping = computeFromBzlmod(repositoryName, selectionValue);
       if (mapping.isPresent()) {
         return RepositoryMappingValue.withMapping(mapping.get());
       }
@@ -72,7 +72,7 @@
    * @return the repo mappings for the repo if it's generated by Bzlmod, otherwise return
    *     Optional.empty().
    */
-  private Optional<ImmutableMap<RepositoryName, RepositoryName>> computeFromBzlmod(
+  private Optional<RepositoryMapping> computeFromBzlmod(
       RepositoryName repositoryName, SelectionValue selectionValue) {
     ModuleKey moduleKey =
         repositoryName.isMain()
@@ -97,7 +97,7 @@
           RepositoryName.createFromValidStrippedName(expectedRepoName),
           RepositoryName.createFromValidStrippedName(canonicalRepoName));
     }
-    return Optional.of(repoMapping.build());
+    return Optional.of(RepositoryMapping.create(repoMapping.build()));
   }
 
   private SkyValue computeFromWorkspace(
@@ -111,7 +111,8 @@
     }
     if (selectionValue == null) {
       return RepositoryMappingValue.withMapping(
-          externalPackage.getRepositoryMapping(repositoryName));
+          RepositoryMapping.createAllowingFallback(
+              externalPackage.getRepositoryMapping(repositoryName)));
     }
     // If bzlmod is in play, we need to transform mappings to "foo" into mappings for "foo.1.3" (if
     // there is a module called "foo" in the dep graph and its version is 1.3, that is).
@@ -136,7 +137,8 @@
           RepositoryName.createFromValidStrippedName(entry.getKey()),
           RepositoryName.createFromValidStrippedName(entry.getValue().getCanonicalRepoName()));
     }
-    return RepositoryMappingValue.withMapping(ImmutableMap.copyOf(mapping));
+    return RepositoryMappingValue.withMapping(
+        RepositoryMapping.createAllowingFallback(ImmutableMap.copyOf(mapping)));
   }
 
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingValue.java
index ee0f9c4..6ab436e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryMappingValue.java
@@ -15,8 +15,8 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
@@ -49,15 +49,15 @@
  */
 public class RepositoryMappingValue implements SkyValue {
 
-  private final ImmutableMap<RepositoryName, RepositoryName> repositoryMapping;
+  private final RepositoryMapping repositoryMapping;
 
-  private RepositoryMappingValue(ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+  private RepositoryMappingValue(RepositoryMapping repositoryMapping) {
     Preconditions.checkNotNull(repositoryMapping);
     this.repositoryMapping = repositoryMapping;
   }
 
   /** Returns the workspace mappings. */
-  public ImmutableMap<RepositoryName, RepositoryName> getRepositoryMapping() {
+  public RepositoryMapping getRepositoryMapping() {
     return repositoryMapping;
   }
 
@@ -67,8 +67,7 @@
   }
 
   /** Returns a {@link RepositoryMappingValue} for a workspace with the given name. */
-  public static RepositoryMappingValue withMapping(
-      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+  public static RepositoryMappingValue withMapping(RepositoryMapping repositoryMapping) {
     return new RepositoryMappingValue(Preconditions.checkNotNull(repositoryMapping));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseFunction.java
index 6cd4c78..54d1833 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternPhaseFunction.java
@@ -26,6 +26,7 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 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.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
@@ -270,7 +271,7 @@
   private static List<ExpandedPattern> getTargetsToBuild(
       Environment env,
       TargetPatternPhaseKey options,
-      ImmutableMap<RepositoryName, RepositoryName> repoMapping,
+      RepositoryMapping repoMapping,
       List<String> failedPatterns)
       throws InterruptedException {
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
index 722a7d3..b6e64ad 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
@@ -28,6 +28,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler.Postable;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
@@ -265,7 +266,7 @@
         BzlLoadFunction.getLoadsFromStarlarkFiles(chunk);
     ImmutableList<Label> loadLabels =
         BzlLoadFunction.getLoadLabels(
-            env.getListener(), programLoads, rootPackage, /*repoMapping=*/ ImmutableMap.of());
+            env.getListener(), programLoads, rootPackage, RepositoryMapping.ALWAYS_FALLBACK);
     if (loadLabels == null) {
       NoSuchPackageException e =
           PackageFunction.PackageFunctionException.builder()
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/LocationExpanderTest.java b/src/test/java/com/google/devtools/build/lib/analysis/LocationExpanderTest.java
index 2e92de0..fdf64e6 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/LocationExpanderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/LocationExpanderTest.java
@@ -18,6 +18,7 @@
 
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.LocationExpander.LocationFunction;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import java.util.ArrayList;
 import java.util.List;
@@ -73,7 +74,7 @@
         ImmutableMap.<String, LocationFunction>of(
             "location", f1,
             "locations", f2),
-        ImmutableMap.of());
+        RepositoryMapping.ALWAYS_FALLBACK);
   }
 
   private String expand(String input) throws Exception {
@@ -133,10 +134,11 @@
         RepositoryName.create("@foo"),
         RepositoryName.create("@bar"));
 
-    LocationExpander locationExpander = new LocationExpander(
-        new Capture(),
-        ImmutableMap.<String, LocationFunction>of("location", f1),
-        repositoryMapping);
+    LocationExpander locationExpander =
+        new LocationExpander(
+            new Capture(),
+            ImmutableMap.<String, LocationFunction>of("location", f1),
+            RepositoryMapping.createAllowingFallback(repositoryMapping));
 
     String value = locationExpander.expand("$(location @foo//a)");
     assertThat(value).isEqualTo("src/a");
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/LocationFunctionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/LocationFunctionTest.java
index 311ae2e..c333ad7 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/LocationFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/LocationFunctionTest.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.analysis.LocationExpander.LocationFunction;
 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.vfs.DigestHashFunction;
 import com.google.devtools.build.lib.vfs.FileSystem;
@@ -47,23 +48,25 @@
   public void absoluteAndRelativeLabels() throws Exception {
     LocationFunction func =
         new LocationFunctionBuilder("//foo", false).add("//foo", "/exec/src/bar").build();
-    assertThat(func.apply("//foo", ImmutableMap.of())).isEqualTo("src/bar");
-    assertThat(func.apply(":foo", ImmutableMap.of())).isEqualTo("src/bar");
-    assertThat(func.apply("foo", ImmutableMap.of())).isEqualTo("src/bar");
+    assertThat(func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK)).isEqualTo("src/bar");
+    assertThat(func.apply(":foo", RepositoryMapping.ALWAYS_FALLBACK)).isEqualTo("src/bar");
+    assertThat(func.apply("foo", RepositoryMapping.ALWAYS_FALLBACK)).isEqualTo("src/bar");
   }
 
   @Test
   public void pathUnderExecRootUsesDotSlash() throws Exception {
     LocationFunction func =
         new LocationFunctionBuilder("//foo", false).add("//foo", "/exec/bar").build();
-    assertThat(func.apply("//foo", ImmutableMap.of())).isEqualTo("./bar");
+    assertThat(func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK)).isEqualTo("./bar");
   }
 
   @Test
   public void noSuchLabel() throws Exception {
     LocationFunction func = new LocationFunctionBuilder("//foo", false).build();
     IllegalStateException expected =
-        assertThrows(IllegalStateException.class, () -> func.apply("//bar", ImmutableMap.of()));
+        assertThrows(
+            IllegalStateException.class,
+            () -> func.apply("//bar", RepositoryMapping.ALWAYS_FALLBACK));
     assertThat(expected)
         .hasMessageThat()
         .isEqualTo(
@@ -75,7 +78,9 @@
   public void emptyList() throws Exception {
     LocationFunction func = new LocationFunctionBuilder("//foo", false).add("//foo").build();
     IllegalStateException expected =
-        assertThrows(IllegalStateException.class, () -> func.apply("//foo", ImmutableMap.of()));
+        assertThrows(
+            IllegalStateException.class,
+            () -> func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK));
     assertThat(expected)
         .hasMessageThat()
         .isEqualTo("label '//foo:foo' in $(location) expression expands to no files");
@@ -86,7 +91,9 @@
     LocationFunction func =
         new LocationFunctionBuilder("//foo", false).add("//foo", "/exec/1", "/exec/2").build();
     IllegalStateException expected =
-        assertThrows(IllegalStateException.class, () -> func.apply("//foo", ImmutableMap.of()));
+        assertThrows(
+            IllegalStateException.class,
+            () -> func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK));
     assertThat(expected)
         .hasMessageThat()
         .isEqualTo(
@@ -99,7 +106,9 @@
   public void noSuchLabelMultiple() throws Exception {
     LocationFunction func = new LocationFunctionBuilder("//foo", true).build();
     IllegalStateException expected =
-        assertThrows(IllegalStateException.class, () -> func.apply("//bar", ImmutableMap.of()));
+        assertThrows(
+            IllegalStateException.class,
+            () -> func.apply("//bar", RepositoryMapping.ALWAYS_FALLBACK));
     assertThat(expected)
         .hasMessageThat()
         .isEqualTo(
@@ -111,7 +120,8 @@
   public void fileWithSpace() throws Exception {
     LocationFunction func =
         new LocationFunctionBuilder("//foo", false).add("//foo", "/exec/file/with space").build();
-    assertThat(func.apply("//foo", ImmutableMap.of())).isEqualTo("'file/with space'");
+    assertThat(func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK))
+        .isEqualTo("'file/with space'");
   }
 
   @Test
@@ -119,7 +129,8 @@
     LocationFunction func = new LocationFunctionBuilder("//foo", true)
         .add("//foo", "/exec/foo/bar", "/exec/out/foo/foobar")
         .build();
-    assertThat(func.apply("//foo", ImmutableMap.of())).isEqualTo("foo/bar foo/foobar");
+    assertThat(func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK))
+        .isEqualTo("foo/bar foo/foobar");
   }
 
   @Test
@@ -127,7 +138,7 @@
     LocationFunction func = new LocationFunctionBuilder("//foo", true)
         .add("//foo", "/exec/file/with space", "/exec/file/with spaces ")
         .build();
-    assertThat(func.apply("//foo", ImmutableMap.of()))
+    assertThat(func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK))
         .isEqualTo("'file/with space' 'file/with spaces '");
   }
 
@@ -137,7 +148,8 @@
         .setExecPaths(true)
         .add("//foo", "/exec/bar", "/exec/out/foobar")
         .build();
-    assertThat(func.apply("//foo", ImmutableMap.of())).isEqualTo("./bar out/foobar");
+    assertThat(func.apply("//foo", RepositoryMapping.ALWAYS_FALLBACK))
+        .isEqualTo("./bar out/foobar");
   }
 
   @Test
@@ -147,7 +159,8 @@
     ImmutableMap<RepositoryName, RepositoryName> repositoryMapping = ImmutableMap.of(a, b);
     LocationFunction func =
         new LocationFunctionBuilder("//foo", false).add("@b//foo", "/exec/src/bar").build();
-    assertThat(func.apply("@a//foo", repositoryMapping)).isEqualTo("src/bar");
+    assertThat(func.apply("@a//foo", RepositoryMapping.createAllowingFallback(repositoryMapping)))
+        .isEqualTo("src/bar");
   }
 
   @Test
@@ -157,7 +170,9 @@
     ImmutableMap<RepositoryName, RepositoryName> repositoryMapping = ImmutableMap.of(a, b);
     LocationFunction func =
         new LocationFunctionBuilder("//foo", false).add("@potato//foo", "/exec/src/bar").build();
-    assertThat(func.apply("@potato//foo", repositoryMapping)).isEqualTo("src/bar");
+    assertThat(
+            func.apply("@potato//foo", RepositoryMapping.createAllowingFallback(repositoryMapping)))
+        .isEqualTo("src/bar");
   }
 }
 
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/RepositoryMappingTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/RepositoryMappingTest.java
new file mode 100644
index 0000000..c7cb715
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/RepositoryMappingTest.java
@@ -0,0 +1,47 @@
+// Copyright 2021 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.cmdline;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.ImmutableMap;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for @{link RepositoryMapping}. */
+@RunWith(JUnit4.class)
+public final class RepositoryMappingTest {
+
+  @Test
+  public void maybeFallback() throws Exception {
+    RepositoryMapping mapping =
+        RepositoryMapping.createAllowingFallback(
+            ImmutableMap.of(RepositoryName.create("@A"), RepositoryName.create("@com_foo_bar_a")));
+    assertThat(mapping.get(RepositoryName.create("@A")))
+        .isEqualTo(RepositoryName.create("@com_foo_bar_a"));
+    assertThat(mapping.get(RepositoryName.create("@B"))).isEqualTo(RepositoryName.create("@B"));
+  }
+
+  @Test
+  public void neverFallback() throws Exception {
+    RepositoryMapping mapping =
+        RepositoryMapping.create(
+            ImmutableMap.of(RepositoryName.create("@A"), RepositoryName.create("@com_foo_bar_a")));
+    assertThat(mapping.get(RepositoryName.create("@A")))
+        .isEqualTo(RepositoryName.create("@com_foo_bar_a"));
+    assertThat(mapping.get(RepositoryName.create("@B"))).isNull();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java b/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
index 4b07663..b7654fa 100644
--- a/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
+++ b/src/test/java/com/google/devtools/build/lib/cmdline/TargetPatternTest.java
@@ -20,7 +20,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.TargetPattern.TargetsBelowDirectory;
 import com.google.devtools.build.lib.cmdline.TargetPattern.TargetsBelowDirectory.ContainsResult;
-import java.util.Map;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -167,10 +166,11 @@
 
   @Test
   public void testRenameRepository() throws Exception {
-    Map<RepositoryName, RepositoryName> renaming =
-        ImmutableMap.of(
-            RepositoryName.create("@foo"), RepositoryName.create("@bar"),
-            RepositoryName.create("@myworkspace"), RepositoryName.create("@"));
+    RepositoryMapping renaming =
+        RepositoryMapping.createAllowingFallback(
+            ImmutableMap.of(
+                RepositoryName.create("@foo"), RepositoryName.create("@bar"),
+                RepositoryName.create("@myworkspace"), RepositoryName.create("@")));
 
     // Expecting renaming
     assertThat(TargetPattern.renameRepository("@foo//package:target", renaming))
diff --git a/src/test/java/com/google/devtools/build/lib/packages/BuildTypeTest.java b/src/test/java/com/google/devtools/build/lib/packages/BuildTypeTest.java
index 8b54a24..316936d 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/BuildTypeTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/BuildTypeTest.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.packages.BuildType.LabelConversionContext;
 import com.google.devtools.build.lib.packages.BuildType.Selector;
@@ -46,7 +47,7 @@
   private final LabelConversionContext labelConversionContext =
       new LabelConversionContext(
           currentRule,
-          /*repositoryMapping=*/ ImmutableMap.of(),
+          RepositoryMapping.ALWAYS_FALLBACK,
           /*convertedLabelsInPackage=*/ new HashMap<>());
 
   @Test
@@ -273,8 +274,9 @@
     LabelConversionContext context =
         new LabelConversionContext(
             currentRule,
-            ImmutableMap.of(
-                RepositoryName.create("@orig_repo"), RepositoryName.create("@new_repo")),
+            RepositoryMapping.createAllowingFallback(
+                ImmutableMap.of(
+                    RepositoryName.create("@orig_repo"), RepositoryName.create("@new_repo"))),
             /* convertedLabelsInPackage= */ new HashMap<>());
     Label label = BuildType.LABEL.convert("@orig_repo//foo:bar", null, context);
     assertThat(label)
diff --git a/src/test/java/com/google/devtools/build/lib/packages/PackageTest.java b/src/test/java/com/google/devtools/build/lib/packages/PackageTest.java
index 8b8f190..3d33e49 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/PackageTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/PackageTest.java
@@ -18,9 +18,9 @@
 import static org.mockito.Mockito.mock;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.Package.Builder.DefaultPackageSettings;
 import com.google.devtools.build.lib.packages.RuleClass.Builder.RuleClassType;
@@ -164,7 +164,7 @@
             PackageIdentifier.createInMainRepo(name),
             "workspace",
             /*noImplicitFileExport=*/ true,
-            ImmutableMap.of());
+            RepositoryMapping.ALWAYS_FALLBACK);
     result.setFilename(
         RootedPath.toRootedPath(
             Root.fromPath(fileSystem.getPath("/irrelevantRoot")), PathFragment.create(name)));
diff --git a/src/test/java/com/google/devtools/build/lib/packages/RuleClassTest.java b/src/test/java/com/google/devtools/build/lib/packages/RuleClassTest.java
index eddb34c..23a8192 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/RuleClassTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/RuleClassTest.java
@@ -45,6 +45,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventCollector;
 import com.google.devtools.build.lib.events.EventKind;
@@ -264,7 +265,7 @@
             PackageIdentifier.createInMainRepo(TEST_PACKAGE_NAME),
             "TESTING",
             StarlarkSemantics.DEFAULT,
-            /*repositoryMapping=*/ ImmutableMap.of())
+            RepositoryMapping.ALWAYS_FALLBACK)
         .setFilename(RootedPath.toRootedPath(root, testBuildfilePath));
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/packages/RuleFactoryTest.java b/src/test/java/com/google/devtools/build/lib/packages/RuleFactoryTest.java
index 52c9666..df85e78 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/RuleFactoryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/RuleFactoryTest.java
@@ -26,6 +26,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelConstants;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.packages.RuleFactory.BuildLangTypedAttributeValuesMap;
 import com.google.devtools.build.lib.packages.util.PackageLoadingTestCase;
@@ -58,7 +59,7 @@
   private Package.Builder newBuilder(PackageIdentifier id, Path filename) {
     return packageFactory
         .newPackageBuilder(
-            id, "TESTING", StarlarkSemantics.DEFAULT, /* repositoryMapping= */ ImmutableMap.of())
+            id, "TESTING", StarlarkSemantics.DEFAULT, RepositoryMapping.ALWAYS_FALLBACK)
         .setFilename(RootedPath.toRootedPath(root, filename));
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunctionTest.java
index 1f65555..45ddd97 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RepositoryMappingFunctionTest.java
@@ -26,6 +26,7 @@
 import com.google.devtools.build.lib.bazel.bzlmod.FakeRegistry;
 import com.google.devtools.build.lib.bazel.bzlmod.ModuleFileFunction;
 import com.google.devtools.build.lib.bazel.bzlmod.Version.ParseException;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
@@ -71,6 +72,17 @@
         getSkyframeExecutor().getDifferencerForTesting(), ImmutableList.of(registry.getUrl()));
   }
 
+  public static RepositoryMappingValue withMapping(
+      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+    return RepositoryMappingValue.withMapping(RepositoryMapping.create(repositoryMapping));
+  }
+
+  public static RepositoryMappingValue withMappingAllowingFallback(
+      ImmutableMap<RepositoryName, RepositoryName> repositoryMapping) {
+    return RepositoryMappingValue.withMapping(
+        RepositoryMapping.createAllowingFallback(repositoryMapping));
+  }
+
   @Test
   public void testSimpleMapping() throws Exception {
     scratch.overwriteFile(
@@ -89,7 +101,7 @@
     assertThatEvaluationResult(result)
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(
                     RepositoryName.create("@a"),
                     RepositoryName.create("@b"),
@@ -113,7 +125,7 @@
     assertThatEvaluationResult(result)
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMapping(
                 ImmutableMap.of(
                     RepositoryName.create("@com_foo_bar_b"), RepositoryName.create("@B.1.0"))));
   }
@@ -140,7 +152,7 @@
     assertThatEvaluationResult(result)
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMapping(
                 ImmutableMap.of(
                     RepositoryName.create("@com_foo_bar_b"), RepositoryName.create("@B.1.0"))));
   }
@@ -162,8 +174,7 @@
     assertThatEvaluationResult(result)
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
-                ImmutableMap.of(RepositoryName.create("@A"), RepositoryName.create("@"))));
+            withMapping(ImmutableMap.of(RepositoryName.create("@A"), RepositoryName.create("@"))));
   }
 
   @Test
@@ -188,10 +199,12 @@
     assertThatEvaluationResult(result)
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMapping(
                 ImmutableMap.of(
-                    RepositoryName.create("@B1"), RepositoryName.create("@B.1.0"),
-                    RepositoryName.create("@B2"), RepositoryName.create("@B.2.0"))));
+                    RepositoryName.create("@B1"),
+                    RepositoryName.create("@B.1.0"),
+                    RepositoryName.create("@B2"),
+                    RepositoryName.create("@B.2.0"))));
   }
 
   @Test
@@ -222,9 +235,8 @@
     assertThatEvaluationResult(result)
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
-                ImmutableMap.of(
-                    RepositoryName.create("@D"), RepositoryName.create("@D.1.0"))));
+            withMapping(
+                ImmutableMap.of(RepositoryName.create("@D"), RepositoryName.create("@D.1.0"))));
   }
 
   @Test
@@ -253,7 +265,7 @@
     assertThatEvaluationResult(result)
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMapping(
                 ImmutableMap.of(
                     RepositoryName.create("@com_foo_bar_c"), RepositoryName.create("@C.1.0"))));
   }
@@ -281,7 +293,7 @@
     assertThatEvaluationResult(eval(skyKey1))
         .hasEntryThat(skyKey1)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(
                     RepositoryName.create("@a"),
                     RepositoryName.create("@b"),
@@ -290,7 +302,7 @@
     assertThatEvaluationResult(eval(skyKey2))
         .hasEntryThat(skyKey2)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(
                     RepositoryName.create("@x"),
                     RepositoryName.create("@y"),
@@ -314,7 +326,7 @@
     assertThatEvaluationResult(eval(skyKey))
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(
                     RepositoryName.create("@a"),
                     RepositoryName.create("@b"),
@@ -360,7 +372,7 @@
     assertThatEvaluationResult(eval(skyKey))
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.<RepositoryName, RepositoryName>builder()
                     .put(RepositoryName.create("@root"), RepositoryName.MAIN)
                     // mappings to @B get remapped to @B.1.0 because of module B@1.0
@@ -413,7 +425,7 @@
     assertThatEvaluationResult(eval(skyKey))
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(
                     RepositoryName.createFromValidStrippedName(TestConstants.WORKSPACE_NAME),
                     RepositoryName.MAIN)));
@@ -434,7 +446,7 @@
     assertThatEvaluationResult(eval(skyKey))
         .hasEntryThat(skyKey)
         .isEqualTo(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(RepositoryName.create("@good"), RepositoryName.MAIN)));
   }
 
@@ -442,14 +454,14 @@
   public void testEqualsAndHashCode() throws Exception {
     new EqualsTester()
         .addEqualityGroup(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(RepositoryName.create("@foo"), RepositoryName.create("@bar"))),
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(RepositoryName.create("@foo"), RepositoryName.create("@bar"))))
         .addEqualityGroup(
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(RepositoryName.create("@fizz"), RepositoryName.create("@buzz"))),
-            RepositoryMappingValue.withMapping(
+            withMappingAllowingFallback(
                 ImmutableMap.of(RepositoryName.create("@fizz"), RepositoryName.create("@buzz"))))
         .testEquals();
   }
diff --git a/src/test/java/com/google/devtools/build/lib/starlark/util/BazelEvaluationTestCase.java b/src/test/java/com/google/devtools/build/lib/starlark/util/BazelEvaluationTestCase.java
index 088ef64..7ee391b 100644
--- a/src/test/java/com/google/devtools/build/lib/starlark/util/BazelEvaluationTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/starlark/util/BazelEvaluationTestCase.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.starlark.StarlarkModules;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventCollector;
 import com.google.devtools.build.lib.events.EventKind;
@@ -127,7 +128,7 @@
             BazelStarlarkContext.Phase.LOADING,
             TestConstants.TOOLS_REPOSITORY,
             /*fragmentNameToClass=*/ null,
-            /*repoMapping=*/ ImmutableMap.of(),
+            /*repoMapping=*/ RepositoryMapping.ALWAYS_FALLBACK,
             /*convertedLabelsInPackage=*/ new HashMap<>(),
             new SymbolGenerator<>(new Object()),
             /*analysisRuleLabel=*/ null,