diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java
index b4a02a2..8aa0160 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/RepositoryFunction.java
@@ -264,7 +264,7 @@
     } catch (NoSuchPackageException e) {
       throw new RepositoryFunctionException(
           new BuildFileNotFoundException(
-              ExternalPackage.NAME, "Could not load //external package"),
+              ExternalPackage.PACKAGE_IDENTIFIER, "Could not load //external package"),
           Transience.PERSISTENT);
     }
     if (packageValue == null) {
@@ -275,7 +275,7 @@
     if (rule == null) {
       throw new RepositoryFunctionException(
           new BuildFileContainsErrorsException(
-              ExternalPackage.NAME,
+              ExternalPackage.PACKAGE_IDENTIFIER,
               "The repository named '" + repositoryName + "' could not be resolved"),
           Transience.PERSISTENT);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/BuildFileContainsErrorsException.java b/src/main/java/com/google/devtools/build/lib/packages/BuildFileContainsErrorsException.java
index d9283c3..c116898 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/BuildFileContainsErrorsException.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/BuildFileContainsErrorsException.java
@@ -24,17 +24,17 @@
 
   private Package pkg;
 
-  public BuildFileContainsErrorsException(String packageName, String message) {
-    super(packageName, "error loading package", message);
+  public BuildFileContainsErrorsException(PackageIdentifier packageIdentifier, String message) {
+    super(packageIdentifier, "error loading package", message);
   }
 
-  public BuildFileContainsErrorsException(String packageName, String message,
+  public BuildFileContainsErrorsException(PackageIdentifier packageIdentifier, String message,
       Throwable cause) {
-    super(packageName, "error loading package", message, cause);
+    super(packageIdentifier, "error loading package", message, cause);
   }
 
   public BuildFileContainsErrorsException(Package pkg, String msg) {
-    this(pkg.getName(), msg);
+    this(pkg.getPackageIdentifier(), msg);
     this.pkg = pkg;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/BuildFileNotFoundException.java b/src/main/java/com/google/devtools/build/lib/packages/BuildFileNotFoundException.java
index 2c70a4e..e425013 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/BuildFileNotFoundException.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/BuildFileNotFoundException.java
@@ -20,12 +20,12 @@
  */
 public class BuildFileNotFoundException extends NoSuchPackageException {
 
-  public BuildFileNotFoundException(String packageName, String message) {
-    super(packageName, message);
+  public BuildFileNotFoundException(PackageIdentifier packageIdentifier, String message) {
+    super(packageIdentifier, message);
   }
 
-  public BuildFileNotFoundException(String packageName, String message,
+  public BuildFileNotFoundException(PackageIdentifier packageIdentifier, String message,
       Throwable cause) {
-    super(packageName, message, cause);
+    super(packageIdentifier, message, cause);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/DuplicatePackageException.java b/src/main/java/com/google/devtools/build/lib/packages/DuplicatePackageException.java
index dc21cba..8dff44f 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/DuplicatePackageException.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/DuplicatePackageException.java
@@ -22,11 +22,12 @@
 // longer a child of NoSuchPackageException.
 public class DuplicatePackageException extends NoSuchPackageException {
 
-  public DuplicatePackageException(String packageName, String message) {
-    super(packageName, message);
+  public DuplicatePackageException(PackageIdentifier packageIdentifier, String message) {
+    super(packageIdentifier, message);
   }
 
-  public DuplicatePackageException(String packageName, String message, Throwable cause) {
-    super(packageName, message, cause);
+  public DuplicatePackageException(PackageIdentifier packageIdentifier, String message,
+                                   Throwable cause) {
+    super(packageIdentifier, message, cause);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java b/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
index 68d098b..f90d2a6 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/ExternalPackage.java
@@ -35,12 +35,14 @@
  */
 public class ExternalPackage extends Package {
   public static final String NAME = "external";
+  public static final PackageIdentifier PACKAGE_IDENTIFIER =
+      PackageIdentifier.createInDefaultRepo(NAME);
 
   private Map<Label, Binding> bindMap;
   private Map<RepositoryName, Rule> repositoryMap;
 
   ExternalPackage() {
-    super(PackageIdentifier.createInDefaultRepo(NAME));
+    super(PACKAGE_IDENTIFIER);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/packages/InvalidPackageNameException.java b/src/main/java/com/google/devtools/build/lib/packages/InvalidPackageNameException.java
index 69561b8..d4ef8ce 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/InvalidPackageNameException.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/InvalidPackageNameException.java
@@ -19,11 +19,12 @@
  */
 public class InvalidPackageNameException extends NoSuchPackageException {
 
-  public InvalidPackageNameException(String packageName, String message) {
-    super(packageName, message);
+  public InvalidPackageNameException(PackageIdentifier packageIdentifier, String message) {
+    super(packageIdentifier, message);
   }
 
-  public InvalidPackageNameException(String packageName, String message, Throwable cause) {
-    super(packageName, message, cause);
+  public InvalidPackageNameException(
+      PackageIdentifier packageIdentifier, String message, Throwable cause) {
+    super(packageIdentifier, message, cause);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/NoSuchPackageException.java b/src/main/java/com/google/devtools/build/lib/packages/NoSuchPackageException.java
index 720d3d5..8db0db6 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/NoSuchPackageException.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/NoSuchPackageException.java
@@ -22,30 +22,31 @@
  */
 public abstract class NoSuchPackageException extends NoSuchThingException {
 
-  private final String packageName;
+  private final PackageIdentifier packageId;
 
-  public NoSuchPackageException(String packageName, String message) {
-    this(packageName, "no such package", message);
+  public NoSuchPackageException(PackageIdentifier packageId, String message) {
+    this(packageId, "no such package", message);
   }
 
-  public NoSuchPackageException(String packageName, String message,
+  public NoSuchPackageException(PackageIdentifier packageId, String message,
       Throwable cause) {
-    this(packageName, "no such package", message, cause);
+    this(packageId, "no such package", message, cause);
   }
 
-  protected NoSuchPackageException(String packageName, String messagePrefix, String message) {
-    super(messagePrefix + " '" + packageName + "': " + message);
-    this.packageName = packageName;
+  protected NoSuchPackageException(
+      PackageIdentifier packageId, String messagePrefix, String message) {
+    super(messagePrefix + " '" + packageId + "': " + message);
+    this.packageId = packageId;
   }
 
-  protected NoSuchPackageException(String packageName, String messagePrefix, String message,
-      Throwable cause) {
-    super(messagePrefix + " '" + packageName + "': " + message, cause);
-    this.packageName = packageName;
+  protected NoSuchPackageException(PackageIdentifier packageId, String messagePrefix,
+      String message, Throwable cause) {
+    super(messagePrefix + " '" + packageId + "': " + message, cause);
+    this.packageId = packageId;
   }
 
-  public String getPackageName() {
-    return packageName;
+  public PackageIdentifier getPackageId() {
+    return packageId;
   }
 
   /**
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 871b3d7..f42a21b 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
@@ -1072,11 +1072,11 @@
         packageId.getPackageFragment().getPathString());
     if (error != null) {
       throw new BuildFileNotFoundException(
-          packageId.toString(), "illegal package name: '" + packageId + "' (" + error + ")");
+          packageId, "illegal package name: '" + packageId + "' (" + error + ")");
     }
     ParserInputSource inputSource = maybeGetParserInputSource(buildFile, eventHandler);
     if (inputSource == null) {
-      throw new BuildFileContainsErrorsException(packageId.toString(), "IOException occured");
+      throw new BuildFileContainsErrorsException(packageId, "IOException occured");
     }
 
     Package result = createPackage((new ExternalPackage.Builder(
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RelativePackageNameResolver.java b/src/main/java/com/google/devtools/build/lib/packages/RelativePackageNameResolver.java
index ade196b..2cab8a3 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RelativePackageNameResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RelativePackageNameResolver.java
@@ -56,7 +56,8 @@
       isAbsolute = true;
       relativePkg = pkg.substring(2);
     } else if (pkg.startsWith("/")) {
-      throw new InvalidPackageNameException(pkg,
+      throw new InvalidPackageNameException(
+          PackageIdentifier.createInDefaultRepo(pkg),
           "package name cannot start with a single slash");
     } else {
       isAbsolute = false;
@@ -72,7 +73,8 @@
     PathFragment result = isAbsolute ? relative : offset.getRelative(relative);
     result = result.normalize();
     if (result.containsUplevelReferences()) {
-      throw new InvalidPackageNameException(pkg,
+      throw new InvalidPackageNameException(
+          PackageIdentifier.createInDefaultRepo(pkg),
           "package name contains too many '..' segments");
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
index c503d23..c8204c6 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -89,7 +90,8 @@
   public Path getPackageBuildFile(String packageName) throws NoSuchPackageException {
     Path buildFile  = getPackageBuildFileNullable(packageName, UnixGlob.DEFAULT_SYSCALLS_REF);
     if (buildFile == null) {
-      throw new BuildFileNotFoundException(packageName, "BUILD file not found on package path");
+      throw new BuildFileNotFoundException(PackageIdentifier.createInDefaultRepo(packageName),
+          "BUILD file not found on package path");
     }
     return buildFile;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index 04810ee..68fb4b8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -422,7 +422,7 @@
           transitiveChildException = e;
         }
       } catch (NoSuchPackageException e) {
-        if (depLabel.getPackageName().equals(e.getPackageName())) {
+        if (depLabel.getPackageIdentifier().equals(e.getPackageId())) {
           directChildException = e;
         } else {
           childKey = entry.getKey();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
index d36953f..e2c83a0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
@@ -62,8 +62,7 @@
     } else {
       // If the package key does not exist in the graph, then it must not correspond to any package,
       // because the SkyQuery environment has already loaded the universe.
-      throw new BuildFileNotFoundException(packageName.toString(),
-          "BUILD file not found on package path");
+      throw new BuildFileNotFoundException(packageName, "BUILD file not found on package path");
     }
     return pkgValue.getPackage();
   }
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 121e114..7dc81e8 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
@@ -31,13 +31,13 @@
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
 import com.google.devtools.build.lib.packages.CachingPackageLocator;
+import com.google.devtools.build.lib.packages.ExternalPackage;
 import com.google.devtools.build.lib.packages.InvalidPackageNameException;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.packages.PackageFactory.Globber;
 import com.google.devtools.build.lib.packages.PackageIdentifier;
-import com.google.devtools.build.lib.packages.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.packages.Preprocessor;
 import com.google.devtools.build.lib.packages.RuleVisibility;
 import com.google.devtools.build.lib.packages.Target;
@@ -112,11 +112,11 @@
     this.numPackagesLoaded = numPackagesLoaded;
   }
 
-  private static void maybeThrowFilesystemInconsistency(String packageName,
+  private static void maybeThrowFilesystemInconsistency(PackageIdentifier packageIdentifier,
       Exception skyframeException, boolean packageWasInError)
           throws InternalInconsistentFilesystemException {
     if (!packageWasInError) {
-      throw new InternalInconsistentFilesystemException(packageName, "Encountered error '"
+      throw new InternalInconsistentFilesystemException(packageIdentifier, "Encountered error '"
           + skyframeException.getMessage() + "' but didn't encounter it when doing the same thing "
           + "earlier in the build");
     }
@@ -130,7 +130,8 @@
    * don't care about any skyframe errors since the package knows whether it's in error or not.
    */
   private static Pair<? extends Map<PathFragment, PackageLookupValue>, Boolean>
-  getPackageLookupDepsAndPropagateInconsistentFilesystemExceptions(String packageName,
+  getPackageLookupDepsAndPropagateInconsistentFilesystemExceptions(
+      PackageIdentifier packageIdentifier,
       Iterable<SkyKey> depKeys, Environment env, boolean packageWasInError)
           throws InternalInconsistentFilesystemException {
     Preconditions.checkState(
@@ -149,9 +150,9 @@
           builder.put(pkgName, value);
         }
       } catch (BuildFileNotFoundException e) {
-        maybeThrowFilesystemInconsistency(packageName, e, packageWasInError);
+        maybeThrowFilesystemInconsistency(packageIdentifier, e, packageWasInError);
       } catch (InconsistentFilesystemException e) {
-        throw new InternalInconsistentFilesystemException(packageName, e);
+        throw new InternalInconsistentFilesystemException(packageIdentifier, e);
       } catch (FileSymlinkCycleException e) {
         // Legacy doesn't detect symlink cycles.
         packageShouldBeInError = true;
@@ -161,8 +162,8 @@
   }
 
   private static boolean markFileDepsAndPropagateInconsistentFilesystemExceptions(
-      String packageName, Iterable<SkyKey> depKeys, Environment env, boolean packageWasInError)
-          throws InternalInconsistentFilesystemException {
+      PackageIdentifier packageIdentifier, Iterable<SkyKey> depKeys, Environment env,
+      boolean packageWasInError) throws InternalInconsistentFilesystemException {
     Preconditions.checkState(
         Iterables.all(depKeys, SkyFunctions.isSkyFunction(SkyFunctions.FILE)), depKeys);
     boolean packageShouldBeInError = packageWasInError;
@@ -172,20 +173,20 @@
       try {
         entry.getValue().get();
       } catch (IOException e) {
-        maybeThrowFilesystemInconsistency(packageName, e, packageWasInError);
+        maybeThrowFilesystemInconsistency(packageIdentifier, e, packageWasInError);
       } catch (FileSymlinkCycleException e) {
         // Legacy doesn't detect symlink cycles.
         packageShouldBeInError = true;
       } catch (InconsistentFilesystemException e) {
-        throw new InternalInconsistentFilesystemException(packageName, e);
+        throw new InternalInconsistentFilesystemException(packageIdentifier, e);
       }
     }
     return packageShouldBeInError;
   }
 
   private static boolean markGlobDepsAndPropagateInconsistentFilesystemExceptions(
-      String packageName, Iterable<SkyKey> depKeys, Environment env, boolean packageWasInError)
-          throws InternalInconsistentFilesystemException {
+      PackageIdentifier packageIdentifier, Iterable<SkyKey> depKeys, Environment env,
+      boolean packageWasInError) throws InternalInconsistentFilesystemException {
     Preconditions.checkState(
         Iterables.all(depKeys, SkyFunctions.isSkyFunction(SkyFunctions.GLOB)), depKeys);
     boolean packageShouldBeInError = packageWasInError;
@@ -196,12 +197,12 @@
       try {
         entry.getValue().get();
       } catch (IOException | BuildFileNotFoundException e) {
-        maybeThrowFilesystemInconsistency(packageName, e, packageWasInError);
+        maybeThrowFilesystemInconsistency(packageIdentifier, e, packageWasInError);
       } catch (FileSymlinkCycleException e) {
         // Legacy doesn't detect symlink cycles.
         packageShouldBeInError = true;
       } catch (InconsistentFilesystemException e) {
-        throw new InternalInconsistentFilesystemException(packageName, e);
+        throw new InternalInconsistentFilesystemException(packageIdentifier, e);
       }
     }
     return packageShouldBeInError;
@@ -234,8 +235,9 @@
       subincludePackageLookupDepKeys.add(PackageLookupValue.key(label.getPackageFragment()));
     }
     Pair<? extends Map<PathFragment, PackageLookupValue>, Boolean> subincludePackageLookupResult =
-        getPackageLookupDepsAndPropagateInconsistentFilesystemExceptions(pkg.getName(),
-            subincludePackageLookupDepKeys, env, packageWasOriginallyInError);
+        getPackageLookupDepsAndPropagateInconsistentFilesystemExceptions(
+            pkg.getPackageIdentifier(), subincludePackageLookupDepKeys, env,
+            packageWasOriginallyInError);
     Map<PathFragment, PackageLookupValue> subincludePackageLookupDeps =
         subincludePackageLookupResult.getFirst();
     packageShouldBeInError |= subincludePackageLookupResult.getSecond();
@@ -253,15 +255,16 @@
         if (subincludeFilePath != null) {
           if (!subincludePackageLookupValue.packageExists()) {
             // Legacy blaze puts a non-null path when only when the package does indeed exist.
-            throw new InternalInconsistentFilesystemException(pkg.getName(), String.format(
-                "Unexpected package in %s. Was it modified during the build?", subincludeFilePath));
+            throw new InternalInconsistentFilesystemException(pkg.getPackageIdentifier(),
+                String.format("Unexpected package in %s. Was it modified during the build?",
+                    subincludeFilePath));
           }
           // Sanity check for consistency of Skyframe and legacy blaze.
           Path subincludeFilePathSkyframe =
               subincludePackageLookupValue.getRoot().getRelative(label.toPathFragment());
           if (!subincludeFilePathSkyframe.equals(subincludeFilePath)) {
-            throw new InternalInconsistentFilesystemException(pkg.getName(), String.format(
-                "Inconsistent package location for %s: '%s' vs '%s'. "
+            throw new InternalInconsistentFilesystemException(pkg.getPackageIdentifier(),
+                String.format("Inconsistent package location for %s: '%s' vs '%s'. "
                 + "Was the source tree modified during the build?",
                 label.getPackageFragment(), subincludeFilePathSkyframe, subincludeFilePath));
           }
@@ -275,7 +278,7 @@
       }
     }
     packageShouldBeInError |= markFileDepsAndPropagateInconsistentFilesystemExceptions(
-        pkg.getName(), subincludeFileDepKeys, env, packageWasOriginallyInError);
+        pkg.getPackageIdentifier(), subincludeFileDepKeys, env, packageWasOriginallyInError);
 
     // TODO(bazel-team): In the long term, we want to actually resolve the glob patterns within
     // Skyframe. For now, just logging the glob requests provides correct incrementality and
@@ -295,7 +298,7 @@
       globDepKeys.add(globSkyKey);
     }
     packageShouldBeInError |= markGlobDepsAndPropagateInconsistentFilesystemExceptions(
-        pkg.getName(), globDepKeys, env, packageWasOriginallyInError);
+        pkg.getPackageIdentifier(), globDepKeys, env, packageWasOriginallyInError);
     return packageShouldBeInError;
   }
 
@@ -326,8 +329,8 @@
     Package pkg = workspace.getPackage();
     Event.replayEventsOn(env.getListener(), pkg.getEvents());
     if (pkg.containsErrors()) {
-      throw new PackageFunctionException(new BuildFileContainsErrorsException("external",
-          "Package 'external' contains errors"),
+      throw new PackageFunctionException(new BuildFileContainsErrorsException(
+          ExternalPackage.PACKAGE_IDENTIFIER, "Package 'external' contains errors"),
           pkg.containsTemporaryErrors() ? Transience.TRANSIENT : Transience.PERSISTENT);
     }
 
@@ -352,7 +355,7 @@
     } catch (InconsistentFilesystemException e) {
       // This error is not transient from the perspective of the PackageFunction.
       throw new PackageFunctionException(
-          new InternalInconsistentFilesystemException(packageName, e), Transience.PERSISTENT);
+          new InternalInconsistentFilesystemException(packageId, e), Transience.PERSISTENT);
     }
     if (packageLookupValue == null) {
       return null;
@@ -363,10 +366,10 @@
         case NO_BUILD_FILE:
         case DELETED_PACKAGE:
         case NO_EXTERNAL_PACKAGE:
-          throw new PackageFunctionException(new BuildFileNotFoundException(packageName,
+          throw new PackageFunctionException(new BuildFileNotFoundException(packageId,
               packageLookupValue.getErrorMsg()), Transience.PERSISTENT);
         case INVALID_PACKAGE_NAME:
-          throw new PackageFunctionException(new InvalidPackageNameException(packageName,
+          throw new PackageFunctionException(new InvalidPackageNameException(packageId,
               packageLookupValue.getErrorMsg()), Transience.PERSISTENT);
         default:
           // We should never get here.
@@ -428,7 +431,7 @@
       astLookupValue = (ASTFileLookupValue) env.getValueOrThrow(astLookupKey,
           ErrorReadingSkylarkExtensionException.class, InconsistentFilesystemException.class);
     } catch (ErrorReadingSkylarkExtensionException | InconsistentFilesystemException e) {
-      throw new PackageFunctionException(new BadPreludeFileException(packageName, e.getMessage()),
+      throw new PackageFunctionException(new BadPreludeFileException(packageId, e.getMessage()),
           Transience.PERSISTENT);
     }
     if (astLookupValue == null) {
@@ -452,10 +455,10 @@
       env.getListener().handle(Event.error(Location.fromFile(buildFilePath), e.getMessage()));
       // Note that we did this work, so we should conservatively report this error as transient.
       throw new PackageFunctionException(new BuildFileContainsErrorsException(
-          packageName, e.getMessage()), Transience.TRANSIENT);
+          packageId, e.getMessage()), Transience.TRANSIENT);
     }
     SkylarkImportResult importResult = fetchImportsFromBuildFile(buildFilePath, buildFileFragment,
-        packageId.getRepository(), preludeStatements, inputSource, packageName, env);
+        packageId, preludeStatements, inputSource, env);
     if (importResult == null) {
       return null;
     }
@@ -507,9 +510,9 @@
   }
 
   private SkylarkImportResult fetchImportsFromBuildFile(Path buildFilePath,
-      PathFragment buildFileFragment, RepositoryName repo,
-      List<Statement> preludeStatements, ParserInputSource inputSource,
-      String packageName, Environment env) throws PackageFunctionException {
+      PathFragment buildFileFragment, PackageIdentifier packageIdentifier,
+      List<Statement> preludeStatements, ParserInputSource inputSource, Environment env)
+      throws PackageFunctionException {
     StoredEventHandler eventHandler = new StoredEventHandler();
     BuildFileAST buildFileAST = BuildFileAST.parseBuildFile(
           inputSource, preludeStatements, eventHandler, null, true);
@@ -528,8 +531,8 @@
     ImmutableList.Builder<SkylarkFileDependency> fileDependencies = ImmutableList.builder();
     try {
       for (PathFragment importFile : imports) {
-        SkyKey importsLookupKey =
-            SkylarkImportLookupValue.key(repo, buildFileFragment, importFile);
+        SkyKey importsLookupKey = SkylarkImportLookupValue.key(
+            packageIdentifier.getRepository(), buildFileFragment, importFile);
         SkylarkImportLookupValue importLookupValue = (SkylarkImportLookupValue)
             env.getValueOrThrow(importsLookupKey, SkylarkImportFailedException.class,
                 InconsistentFilesystemException.class, ASTLookupInputException.class,
@@ -541,14 +544,14 @@
       }
     } catch (SkylarkImportFailedException e) {
       env.getListener().handle(Event.error(Location.fromFile(buildFilePath), e.getMessage()));
-      throw new PackageFunctionException(new BuildFileContainsErrorsException(packageName,
+      throw new PackageFunctionException(new BuildFileContainsErrorsException(packageIdentifier,
           e.getMessage()), Transience.PERSISTENT);
     } catch (InconsistentFilesystemException e) {
-      throw new PackageFunctionException(new InternalInconsistentFilesystemException(packageName,
-          e), Transience.PERSISTENT);
+      throw new PackageFunctionException(new InternalInconsistentFilesystemException(
+          packageIdentifier, e), Transience.PERSISTENT);
     } catch (ASTLookupInputException e) {
       // The load syntax is bad in the BUILD file so BuildFileContainsErrorsException is OK.
-      throw new PackageFunctionException(new BuildFileContainsErrorsException(packageName,
+      throw new PackageFunctionException(new BuildFileContainsErrorsException(packageIdentifier,
           e.getMessage()), Transience.PERSISTENT);
     } catch (BuildFileNotFoundException e) {
       throw new PackageFunctionException(e, Transience.PERSISTENT);
@@ -622,7 +625,7 @@
       }
       ContainingPackageLookupValue containingPackageLookupValue =
           getContainingPkgLookupValueAndPropagateInconsistentFilesystemExceptions(
-              pkgId.getPackageFragment().getPathString(), containingPkgLookupValues.get(key), env);
+              pkgId, containingPkgLookupValues.get(key), env);
       if (maybeAddEventAboutLabelCrossingSubpackage(pkgBuilder, pkgRoot, target.getLabel(),
           target.getLocation(), containingPackageLookupValue)) {
         pkgBuilder.removeTarget(target);
@@ -636,7 +639,7 @@
       }
       ContainingPackageLookupValue containingPackageLookupValue =
           getContainingPkgLookupValueAndPropagateInconsistentFilesystemExceptions(
-              pkgId.getPackageFragment().getPathString(), containingPkgLookupValues.get(key), env);
+              pkgId, containingPkgLookupValues.get(key), env);
       if (maybeAddEventAboutLabelCrossingSubpackage(pkgBuilder, pkgRoot, subincludeLabel,
           /*location=*/null, containingPackageLookupValue)) {
         pkgBuilder.setContainsErrors();
@@ -646,7 +649,8 @@
 
   @Nullable
   private static ContainingPackageLookupValue
-  getContainingPkgLookupValueAndPropagateInconsistentFilesystemExceptions(String packageName,
+  getContainingPkgLookupValueAndPropagateInconsistentFilesystemExceptions(
+      PackageIdentifier packageIdentifier,
       ValueOrException3<BuildFileNotFoundException, InconsistentFilesystemException,
       FileSymlinkCycleException> containingPkgLookupValueOrException, Environment env)
           throws InternalInconsistentFilesystemException {
@@ -656,7 +660,7 @@
       env.getListener().handle(Event.error(null, e.getMessage()));
       return null;
     } catch (InconsistentFilesystemException e) {
-      throw new InternalInconsistentFilesystemException(packageName, e);
+      throw new InternalInconsistentFilesystemException(packageIdentifier, e);
     }
   }
 
@@ -745,17 +749,17 @@
      * Used to represent a filesystem inconsistency discovered outside the
      * {@link PackageFunction}.
      */
-    public InternalInconsistentFilesystemException(String packageName,
+    public InternalInconsistentFilesystemException(PackageIdentifier packageIdentifier,
         InconsistentFilesystemException e) {
-      super(packageName, e.getMessage(), e);
+      super(packageIdentifier, e.getMessage(), e);
       // This is not a transient error from the perspective of the PackageFunction.
       this.isTransient = false;
     }
 
     /** Used to represent a filesystem inconsistency discovered by the {@link PackageFunction}. */
-    public InternalInconsistentFilesystemException(String packageName,
+    public InternalInconsistentFilesystemException(PackageIdentifier packageIdentifier,
         String inconsistencyMessage) {
-      this(packageName, new InconsistentFilesystemException(inconsistencyMessage));
+      this(packageIdentifier, new InconsistentFilesystemException(inconsistencyMessage));
       this.isTransient = true;
     }
 
@@ -766,13 +770,14 @@
 
   private static class BadWorkspaceFileException extends NoSuchPackageException {
     private BadWorkspaceFileException(String message) {
-      super("external", "Error encountered while dealing with the WORKSPACE file: " + message);
+      super(ExternalPackage.PACKAGE_IDENTIFIER,
+          "Error encountered while dealing with the WORKSPACE file: " + message);
     }
   }
 
   private static class BadPreludeFileException extends NoSuchPackageException {
-    private BadPreludeFileException(String packageName, String message) {
-      super(packageName, "Error encountered while reading the prelude file: " + message);
+    private BadPreludeFileException(PackageIdentifier packageIdentifier, String message) {
+      super(packageIdentifier, "Error encountered while reading the prelude file: " + message);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
index 6191c81..a4996a4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
@@ -52,19 +52,19 @@
     PathPackageLocator pkgLocator = PrecomputedValue.PATH_PACKAGE_LOCATOR.get(env);
     PackageIdentifier packageKey = (PackageIdentifier) skyKey.argument();
     if (!packageKey.getRepository().isDefault()) {
-      return computeExternalPackageLookupValue(skyKey, env);
+      return computeExternalPackageLookupValue(skyKey, env, packageKey);
     } else if (packageKey.getPackageFragment().equals(new PathFragment(ExternalPackage.NAME))) {
-      return computeWorkspaceLookupValue(env);
+      return computeWorkspaceLookupValue(env, packageKey);
     }
-    PathFragment pkg = packageKey.getPackageFragment();
-    String pkgName = pkg.getPathString();
-    String packageNameErrorMsg = LabelValidator.validatePackageName(pkgName);
+
+    String packageNameErrorMsg = LabelValidator.validatePackageName(
+        packageKey.getPackageFragment().getPathString());
     if (packageNameErrorMsg != null) {
-      return PackageLookupValue.invalidPackageName("Invalid package name '" + pkgName + "': "
+      return PackageLookupValue.invalidPackageName("Invalid package name '" + packageKey + "': "
           + packageNameErrorMsg);
     }
 
-    if (deletedPackages.get().contains(pkg.getPathString())) {
+    if (deletedPackages.get().contains(packageKey.getPackageFragment().toString())) {
       return PackageLookupValue.deletedPackage();
     }
 
@@ -73,7 +73,7 @@
     // the missing value keys, more dependencies than necessary will be declared. This wart can be
     // fixed once we have nicer continuation support [skyframe-loading]
     for (Path packagePathEntry : pkgLocator.getPathEntries()) {
-      PackageLookupValue value = getPackageLookupValue(env, packagePathEntry, pkg);
+      PackageLookupValue value = getPackageLookupValue(env, packagePathEntry, packageKey);
       if (value == null || value.packageExists()) {
         return value;
       }
@@ -88,7 +88,8 @@
   }
 
   @Nullable
-  private FileValue getFileValue(RootedPath buildFileRootedPath, Environment env)
+  private FileValue getFileValue(
+      RootedPath buildFileRootedPath, Environment env, PackageIdentifier packageIdentifier)
       throws PackageLookupFunctionException {
     String basename = buildFileRootedPath.asPath().getBaseName();
     SkyKey fileSkyKey = FileValue.key(buildFileRootedPath);
@@ -97,16 +98,14 @@
       fileValue = (FileValue) env.getValueOrThrow(fileSkyKey, IOException.class,
           FileSymlinkCycleException.class, InconsistentFilesystemException.class);
     } catch (IOException e) {
-      String pkgName = buildFileRootedPath.getRelativePath().getParentDirectory().getPathString();
       // TODO(bazel-team): throw an IOException here and let PackageFunction wrap that into a
       // BuildFileNotFoundException.
-      throw new PackageLookupFunctionException(new BuildFileNotFoundException(pkgName,
+      throw new PackageLookupFunctionException(new BuildFileNotFoundException(packageIdentifier,
           "IO errors while looking for " + basename + " file reading "
               + buildFileRootedPath.asPath() + ": " + e.getMessage(), e),
           Transience.PERSISTENT);
     } catch (FileSymlinkCycleException e) {
-      String pkgName = buildFileRootedPath.asPath().getPathString();
-      throw new PackageLookupFunctionException(new BuildFileNotFoundException(pkgName,
+      throw new PackageLookupFunctionException(new BuildFileNotFoundException(packageIdentifier,
           "Symlink cycle detected while trying to find " + basename + " file "
               + buildFileRootedPath.asPath()),
           Transience.PERSISTENT);
@@ -118,11 +117,11 @@
   }
 
   private PackageLookupValue getPackageLookupValue(Environment env, Path packagePathEntry,
-      PathFragment pkgFragment) throws PackageLookupFunctionException {
-    PathFragment buildFileFragment = pkgFragment.getChild("BUILD");
+      PackageIdentifier packageIdentifier) throws PackageLookupFunctionException {
+    PathFragment buildFileFragment = packageIdentifier.getPackageFragment().getChild("BUILD");
     RootedPath buildFileRootedPath = RootedPath.toRootedPath(packagePathEntry,
         buildFileFragment);
-    FileValue fileValue = getFileValue(buildFileRootedPath, env);
+    FileValue fileValue = getFileValue(buildFileRootedPath, env, packageIdentifier);
     if (fileValue == null) {
       return null;
     }
@@ -135,11 +134,12 @@
   /**
    * Gets a PackageLookupValue from a different Bazel repository.
    *
-   * To do this, it looks up the "external" package and finds a path mapping for the repository
-   * name.
+   * <p>To do this, it looks up the "external" package and finds a path mapping for the repository
+   * name.</p>
    */
   private PackageLookupValue computeExternalPackageLookupValue(
-      SkyKey skyKey, Environment env) throws PackageLookupFunctionException {
+      SkyKey skyKey, Environment env, PackageIdentifier packageIdentifier)
+      throws PackageLookupFunctionException {
     PackageIdentifier id = (PackageIdentifier) skyKey.argument();
     SkyKey repositoryKey = RepositoryValue.key(id.getRepository());
     RepositoryValue repositoryValue = null;
@@ -149,16 +149,14 @@
       if (repositoryValue == null) {
         return null;
       }
-    } catch (NoSuchPackageException e) {
-      throw new PackageLookupFunctionException(e, Transience.PERSISTENT);
-    } catch (IOException | EvalException e) {
-      throw new PackageLookupFunctionException(new BuildFileNotFoundException(
-          ExternalPackage.NAME, e.getMessage()), Transience.PERSISTENT);
+    } catch (NoSuchPackageException | IOException | EvalException e) {
+      throw new PackageLookupFunctionException(new BuildFileNotFoundException(id, e.getMessage()),
+          Transience.PERSISTENT);
     }
     PathFragment buildFileFragment = id.getPackageFragment().getChild("BUILD");
     RootedPath buildFileRootedPath = RootedPath.toRootedPath(repositoryValue.getPath(),
         buildFileFragment);
-    FileValue fileValue = getFileValue(buildFileRootedPath, env);
+    FileValue fileValue = getFileValue(buildFileRootedPath, env, packageIdentifier);
     if (fileValue == null) {
       return null;
     }
@@ -177,7 +175,8 @@
    * Look for a WORKSPACE file on each package path.  If none is found, use the last package path
    * and pretend it was found there.
    */
-  private SkyValue computeWorkspaceLookupValue(Environment env)
+  private SkyValue computeWorkspaceLookupValue(
+      Environment env, PackageIdentifier packageIdentifier)
       throws PackageLookupFunctionException {
     PathPackageLocator pkgLocator = PrecomputedValue.PATH_PACKAGE_LOCATOR.get(env);
     Path lastPackagePath = null;
@@ -185,7 +184,7 @@
       lastPackagePath = packagePathEntry;
       RootedPath workspacePath = RootedPath.toRootedPath(
           packagePathEntry, new PathFragment("WORKSPACE"));
-      FileValue value = getFileValue(workspacePath, env);
+      FileValue value = getFileValue(workspacePath, env, packageIdentifier);
       if (value == null) {
         return null;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 5f6963e..2a1352e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -1256,8 +1256,8 @@
             reportCycles(result.getError().getCycleInfo(), key);
             // This can only happen if a package is freshly loaded outside of the target parsing
             // or loading phase
-            throw new BuildFileContainsErrorsException(pkgName.toString(),
-                "Cycle encountered while loading package " + pkgName);
+            throw new BuildFileContainsErrorsException(
+                pkgName, "Cycle encountered while loading package " + pkgName);
           }
           Throwable e = error.getException();
           // PackageFunction should be catching, swallowing, and rethrowing all transitive
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerFunction.java
index 3f9f22f..53bbc56 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerFunction.java
@@ -64,7 +64,7 @@
         // This means the label's package doesn't exist. E.g. there is no package 'a' and we are
         // trying to build the target for label 'a:b/foo'.
         throw new TargetMarkerFunctionException(new BuildFileNotFoundException(
-            pkgForLabel.getPathString(), "BUILD file not found on package path for '"
+            label.getPackageIdentifier(), "BUILD file not found on package path for '"
                 + pkgForLabel.getPathString() + "'"));
       }
       if (!containingPackageLookupValue.getContainingPackageName().equals(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
index ae5ca36..8d2ffe8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
@@ -275,7 +275,7 @@
       }
     } else if (e instanceof NoSuchPackageException) {
       NoSuchPackageException nspe = (NoSuchPackageException) e;
-      if (nspe.getPackageName().equals(depLabel.getPackageName())) {
+      if (nspe.getPackageId().equals(depLabel.getPackageIdentifier())) {
         eventHandler.handle(Event.error(TargetUtils.getLocationMaybe(target),
             TargetUtils.formatMissingEdge(target, depLabel, e)));
       }
@@ -364,8 +364,8 @@
      * In nokeep_going mode, used to propagate an error from a direct target dependency to the
      * target that depended on it.
      *
-     * In keep_going mode, used the same way, but only for targets that could not be loaded at all
-     * (we proceed with transitive loading on targets that contain errors).
+     * <p>In keep_going mode, used the same way, but only for targets that could not be loaded at
+     * all (we proceed with transitive loading on targets that contain errors).</p>
      */
     public TransitiveTargetFunctionException(NoSuchTargetException e) {
       super(e, Transience.PERSISTENT);
diff --git a/src/test/shell/bazel/local_repository_test.sh b/src/test/shell/bazel/local_repository_test.sh
index 668c0d0..5a587e6 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -144,6 +144,23 @@
   expect_log "Tra-la!"
 }
 
+function test_non_existent_external_ref() {
+  mkdir zoo
+  touch zoo/BallPit.java
+  cat > zoo/BUILD <<EOF
+java_binary(
+    name = "ball-pit",
+    srcs = ["BallPit.java"],
+    main_class = "BallPit",
+    deps = ["@common//carnivore:mongoose"],
+)
+EOF
+
+  bazel build //zoo:ball-pit >& $TEST_log && \
+    fail "Expected build to fail"
+  expect_log "no such package '@common//carnivore'"
+}
+
 function test_new_local_repository() {
   bazel clean