diff --git a/src/main/java/com/google/devtools/build/lib/packages/CachingPackageLocator.java b/src/main/java/com/google/devtools/build/lib/packages/CachingPackageLocator.java
index f6badad..3d677990 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/CachingPackageLocator.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/CachingPackageLocator.java
@@ -40,6 +40,6 @@
    * <p> This method must be thread-safe.
    */
   @ThreadSafe
-  Path getBuildFileForPackage(String packageName);
+  Path getBuildFileForPackage(PackageIdentifier packageName);
 
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
index de9bfdf..43669a8 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
@@ -23,7 +23,6 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.Path;
-import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Symlinks;
 import com.google.devtools.build.lib.vfs.UnixGlob;
 
@@ -107,7 +106,6 @@
     this.syscalls = syscalls == null ? new AtomicReference<>(UnixGlob.DEFAULT_SYSCALLS) : syscalls;
 
     Preconditions.checkNotNull(locator);
-    final PathFragment pkgNameFrag = packageId.getPackageFragment();
     childDirectoryPredicate = new Predicate<Path>() {
       @Override
       public boolean apply(Path directory) {
@@ -115,7 +113,9 @@
           return true;
         }
 
-        PathFragment pkgName = pkgNameFrag.getRelative(directory.relativeTo(packageDirectory));
+        PackageIdentifier subPackageId = new PackageIdentifier(
+            packageId.getRepository(),
+            packageId.getPackageFragment().getRelative(directory.relativeTo(packageDirectory)));
         UnixGlob.FilesystemCalls syscalls = GlobCache.this.syscalls.get();
         if (syscalls != UnixGlob.DEFAULT_SYSCALLS) {
           // This is needed because in case the BUILD file exists, we do not call readdir() on its
@@ -134,7 +134,7 @@
           syscalls.statNullable(directory.getChild("BUILD"), Symlinks.FOLLOW);
         }
 
-        return locator.getBuildFileForPackage(pkgName.getPathString()) == null;
+        return locator.getBuildFileForPackage(subPackageId) == null;
       }
     };
   }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java b/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java
index f2f5b8e..803fb48 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageIdentifier.java
@@ -16,6 +16,7 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ComparisonChain;
+import com.google.devtools.build.lib.cmdline.LabelValidator;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
 import com.google.devtools.build.lib.util.StringCanonicalizer;
 import com.google.devtools.build.lib.util.StringUtilities;
@@ -217,6 +218,34 @@
     this.pkgName = Canonicalizer.fragments().intern(pkgName.normalize());
   }
 
+  public static PackageIdentifier parse(String input) throws SyntaxException {
+    String repo;
+    String packageName;
+    int packageStartPos = input.indexOf("//");
+    if (packageStartPos > 0) {
+      repo = input.substring(0, packageStartPos);
+      packageName = input.substring(packageStartPos + 2);
+    } else if (packageStartPos == 0) {
+      repo = PackageIdentifier.DEFAULT_REPOSITORY;
+      packageName = input.substring(2);
+    } else {
+      repo = PackageIdentifier.DEFAULT_REPOSITORY;
+      packageName = input;
+    }
+
+    String error = RepositoryName.validate(repo);
+    if (error != null) {
+      throw new SyntaxException(error);
+    }
+
+    error = LabelValidator.validatePackageName(packageName);
+    if (error != null) {
+      throw new SyntaxException(error);
+    }
+
+    return new PackageIdentifier(repo, new PathFragment(packageName));
+  }
+
   private Object writeReplace() throws ObjectStreamException {
     return new SerializationProxy(this);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheOptions.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheOptions.java
index e57fe0d..daba8f1 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheOptions.java
@@ -16,6 +16,7 @@
 
 import com.google.devtools.build.lib.Constants;
 import com.google.devtools.build.lib.packages.ConstantRuleVisibility;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
 import com.google.devtools.build.lib.packages.RuleVisibility;
 import com.google.devtools.build.lib.syntax.CommaSeparatedPackageNameListConverter;
 import com.google.devtools.common.options.Converter;
@@ -110,7 +111,7 @@
           + "encounters a label '//x:y/z' if that is still provided by another "
           + "package_path entry.  Specifying --deleted_packages x/y avoids this "
           + "problem.")
-  public List<String> deletedPackages;
+  public List<PackageIdentifier> deletedPackages;
 
   @Option(name = "default_visibility",
       defaultValue = "private",
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageProvider.java
index 5363cb5..9bce541 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageProvider.java
@@ -59,5 +59,5 @@
    * @param eventHandler the eventHandler on which to report warnings and errors
    * @param packageName the name of the package.
    */
-  boolean isPackage(EventHandler eventHandler, String packageName);
+  boolean isPackage(EventHandler eventHandler, PackageIdentifier packageName);
 }
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 c8204c6..0c8b174 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
@@ -13,6 +13,9 @@
 // limitations under the License.
 package com.google.devtools.build.lib.pkgcache;
 
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Objects;
+import com.google.common.base.Verify;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.events.Event;
@@ -45,33 +48,29 @@
 
   public static final Set<String> DEFAULT_TOP_LEVEL_EXCLUDES = ImmutableSet.of("experimental");
 
-  /**
-   * An interface which accepts {@link PathFragment}s.
-   */
-  public interface AcceptsPathFragment {
-
-    /**
-     * Accept a {@link PathFragment}.
-     *
-     * @param fragment The path fragment.
-     */
-    void accept(PathFragment fragment);
-  }
-
   private final ImmutableList<Path> pathEntries;
+  // Transient because this is an injected value in Skyframe, and as such, its serialized
+  // representation is used as a key. We want a change to output base not to invalidate things.
+  private final transient Path outputBase;
+
+  private PathPackageLocator(Path outputBase, List<Path> pathEntries) {
+    this.outputBase = outputBase;
+    this.pathEntries = ImmutableList.copyOf(pathEntries);
+  }
 
   /**
    * Constructs a PathPackageLocator based on the specified list of package root directories.
    */
+  @VisibleForTesting
   public PathPackageLocator(List<Path> pathEntries) {
-    this.pathEntries = ImmutableList.copyOf(pathEntries);
+    this(null, pathEntries);
   }
 
   /**
    * Constructs a PathPackageLocator based on the specified array of package root directories.
    */
   public PathPackageLocator(Path... pathEntries) {
-    this(Arrays.asList(pathEntries));
+    this(null, Arrays.asList(pathEntries));
   }
 
   /**
@@ -87,11 +86,10 @@
    * <p>If the same package exists beneath multiple package path entries, the
    * first path that matches always wins.
    */
-  public Path getPackageBuildFile(String packageName) throws NoSuchPackageException {
+  public Path getPackageBuildFile(PackageIdentifier packageName) throws NoSuchPackageException {
     Path buildFile  = getPackageBuildFileNullable(packageName, UnixGlob.DEFAULT_SYSCALLS_REF);
     if (buildFile == null) {
-      throw new BuildFileNotFoundException(PackageIdentifier.createInDefaultRepo(packageName),
-          "BUILD file not found on package path");
+      throw new BuildFileNotFoundException(packageName, "BUILD file not found on package path");
     }
     return buildFile;
   }
@@ -102,9 +100,28 @@
    * @param packageName the name of the package.
    * @param cache a filesystem-level cache of stat() calls.
    */
-  public Path getPackageBuildFileNullable(String packageName,
+  public Path getPackageBuildFileNullable(PackageIdentifier packageName,
       AtomicReference<? extends UnixGlob.FilesystemCalls> cache)  {
-    return getFilePath(new PathFragment(packageName).getRelative("BUILD"), cache);
+    if (packageName.getRepository().isDefault()) {
+      return getFilePath(packageName.getPackageFragment().getRelative("BUILD"), cache);
+    } else if (!packageName.getRepository().isDefault()) {
+      Verify.verify(outputBase != null, String.format(
+          "External package '%s' needs to be loaded but this PathPackageLocator instance does not "
+          + "support external packages",   packageName));
+      // This works only to some degree, because it relies on the presence of the repository under
+      // $OUTPUT_BASE/external, which is created by the appropriate RepositoryValue. This is true
+      // for the invocation in GlobCache, but not for the locator.getBuildFileForPackage()
+      // invocation in Parser#include().
+      Path buildFile = outputBase.getRelative(packageName.getPathFragment()).getRelative("BUILD");
+      FileStatus stat = cache.get().statNullable(buildFile, Symlinks.FOLLOW);
+      if (stat != null && stat.isFile()) {
+        return buildFile;
+      } else {
+        return null;
+      }
+    } else {
+      return null;
+    }
   }
 
 
@@ -124,6 +141,7 @@
    * A factory of PathPackageLocators from a list of path elements.  Elements
    * may contain "%workspace%", indicating the workspace.
    *
+   * @param outputBase the output base. Can be null if remote repositories are not in use.
    * @param pathElements Each element must be an absolute path, relative path,
    *                     or some string "%workspace%" + relative, where relative is itself a
    *                     relative path.  The special symbol "%workspace%" means to interpret
@@ -135,7 +153,8 @@
    * @param clientWorkingDirectory The client's working directory.
    * @return a list of {@link Path}s.
    */
-  public static PathPackageLocator create(List<String> pathElements,
+  public static PathPackageLocator create(Path outputBase,
+                                          List<String> pathElements,
                                           EventHandler eventHandler,
                                           Path workspace,
                                           Path clientWorkingDirectory) {
@@ -164,7 +183,7 @@
         resolvedPaths.add(rootPath);
       }
     }
-    return new PathPackageLocator(resolvedPaths);
+    return new PathPackageLocator(outputBase, resolvedPaths);
   }
 
   /**
@@ -194,7 +213,7 @@
 
   @Override
   public int hashCode() {
-    return pathEntries.hashCode();
+    return Objects.hashCode(pathEntries, outputBase);
   }
 
   @Override
@@ -205,6 +224,7 @@
     if (!(other instanceof PathPackageLocator)) {
       return false;
     }
-    return this.getPathEntries().equals(((PathPackageLocator) other).getPathEntries());
+    return this.getPathEntries().equals(((PathPackageLocator) other).getPathEntries())
+        && Objects.equal(this.outputBase, ((PathPackageLocator) other).outputBase);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index 2aae12f..bbc432e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -461,7 +461,7 @@
     }
 
     @Override
-    public boolean isPackage(EventHandler eventHandler, String packageName) {
+    public boolean isPackage(EventHandler eventHandler, PackageIdentifier packageName) {
       throw new UnsupportedOperationException();
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
index fca2ae9..fcd11e5 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
@@ -1014,7 +1014,7 @@
     if (!skyframeExecutor.hasIncrementalState()) {
       clearSkyframeRelevantCaches();
     }
-    skyframeExecutor.sync(packageCacheOptions, getWorkingDirectory(),
+    skyframeExecutor.sync(packageCacheOptions, getOutputBase(), getWorkingDirectory(),
         defaultsPackageContents, getCommandId());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/commands/ProjectFileSupport.java b/src/main/java/com/google/devtools/build/lib/runtime/commands/ProjectFileSupport.java
index bec0deb..133179f 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/commands/ProjectFileSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/commands/ProjectFileSupport.java
@@ -63,8 +63,11 @@
       // relative to the cwd instead.
       PathFragment projectFilePath = new PathFragment(targets.get(0).substring(1));
       List<Path> packagePath = PathPackageLocator.create(
-          optionsParser.getOptions(PackageCacheOptions.class).packagePath, runtime.getReporter(),
-          runtime.getWorkspace(), runtime.getWorkingDirectory()).getPathEntries();
+          runtime.getOutputBase(),
+          optionsParser.getOptions(PackageCacheOptions.class).packagePath,
+          runtime.getReporter(),
+          runtime.getWorkspace(),
+          runtime.getWorkingDirectory()).getPathEntries();
       ProjectFile projectFile = projectFileProvider.getProjectFile(packagePath, projectFilePath);
       runtime.getReporter().handle(Event.info("Using " + projectFile.getName()));
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
index 9ea6210..ac5b6a2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
@@ -64,9 +64,9 @@
   }
 
   @Override
-  public boolean isPackage(EventHandler eventHandler, String packageName)
+  public boolean isPackage(EventHandler eventHandler, PackageIdentifier packageId)
       throws MissingDepException {
-    SkyKey packageLookupKey = PackageLookupValue.key(new PathFragment(packageName));
+    SkyKey packageLookupKey = PackageLookupValue.key(packageId);
     try {
       PackageLookupValue packageLookupValue =
           (PackageLookupValue) env.getValueOrThrow(packageLookupKey, NoSuchPackageException.class,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
index d1ee81c..942a201 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
@@ -18,6 +18,7 @@
 import com.google.common.cache.CacheBuilder;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
 import com.google.devtools.build.lib.vfs.Dirent;
 import com.google.devtools.build.lib.vfs.Dirent.Type;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -60,8 +61,9 @@
     PathFragment globSubdir = glob.getSubdir();
     if (!globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) {
       PackageLookupValue globSubdirPkgLookupValue = (PackageLookupValue) env.getValue(
-          PackageLookupValue.key(glob.getPackageId().getPackageFragment()
-              .getRelative(globSubdir)));
+          PackageLookupValue.key(new PackageIdentifier(
+              glob.getPackageId().getRepository(),
+              glob.getPackageId().getPackageFragment().getRelative(globSubdir))));
       if (globSubdirPkgLookupValue == null) {
         return null;
       }
@@ -220,7 +222,8 @@
         PathFragment directory = glob.getPackageId().getPackageFragment()
             .getRelative(glob.getSubdir()).getRelative(fileName);
         PackageLookupValue pkgLookupValue = (PackageLookupValue)
-            env.getValue(PackageLookupValue.key(directory));
+            env.getValue(PackageLookupValue.key(new PackageIdentifier(
+                glob.getPackageId().getRepository(), directory)));
         if (pkgLookupValue == null) {
           return;
         }
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 c4e8c49..c029a1d 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
@@ -79,8 +79,8 @@
   }
 
   @Override
-  public boolean isPackage(EventHandler eventHandler, String packageName) {
-    SkyKey packageLookupKey = PackageLookupValue.key(new PathFragment(packageName));
+  public boolean isPackage(EventHandler eventHandler, PackageIdentifier packageName) {
+    SkyKey packageLookupKey = PackageLookupValue.key(packageName);
     if (!graph.exists(packageLookupKey)) {
       // If the package lookup key does not exist in the graph, then it must not correspond to any
       // package, because the SkyQuery environment has already loaded the universe.
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 db3e7c1..2c8cc8e 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
@@ -41,9 +41,9 @@
  */
 class PackageLookupFunction implements SkyFunction {
 
-  private final AtomicReference<ImmutableSet<String>> deletedPackages;
+  private final AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages;
 
-  PackageLookupFunction(AtomicReference<ImmutableSet<String>> deletedPackages) {
+  PackageLookupFunction(AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages) {
     this.deletedPackages = deletedPackages;
   }
 
@@ -64,7 +64,7 @@
           + packageNameErrorMsg);
     }
 
-    if (deletedPackages.get().contains(packageKey.getPackageFragment().toString())) {
+    if (deletedPackages.get().contains(packageKey)) {
       return PackageLookupValue.deletedPackage();
     }
 
@@ -142,7 +142,7 @@
       throws PackageLookupFunctionException {
     PackageIdentifier id = (PackageIdentifier) skyKey.argument();
     SkyKey repositoryKey = RepositoryValue.key(id.getRepository());
-    RepositoryValue repositoryValue = null;
+    RepositoryValue repositoryValue;
     try {
       repositoryValue = (RepositoryValue) env.getValueOrThrow(
           repositoryKey, NoSuchPackageException.class, IOException.class, EvalException.class);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
index 5230d09..6fbfe57 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
@@ -193,7 +193,10 @@
 
     @Override
     public boolean isPackage(String packageName) {
-      return packageProvider.isPackage(env.getListener(), packageName);
+      // TODO(bazel-team): this should get the whole PackageIdentifier. Using only the package name
+      // makes it impossible to use wildcards to refer to targets in remote repositories.
+      return packageProvider.isPackage(env.getListener(),
+          PackageIdentifier.createInDefaultRepo(packageName));
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
index 942ed83..b913628 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
@@ -132,7 +132,10 @@
 
   @Override
   public boolean isPackage(String packageName) {
-    return recursivePackageProvider.isPackage(eventHandler, packageName);
+    // TODO(bazel-team): this should get the whole PackageIdentifier. Using only the package name
+    // makes it impossible to use the //... wildcard to refer to targets in remote repositories.
+    return recursivePackageProvider.isPackage(
+        eventHandler, PackageIdentifier.createInDefaultRepo(packageName));
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index ef22ab9..a1ac8e2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -211,11 +211,12 @@
   }
 
   @Override
-  public void sync(PackageCacheOptions packageCacheOptions, Path workingDirectory,
+  public void sync(PackageCacheOptions packageCacheOptions, Path outputBase, Path workingDirectory,
                    String defaultsPackageContents, UUID commandId)
       throws InterruptedException, AbruptExitException {
     this.valueCacheEvictionLimit = packageCacheOptions.minLoadedPkgCountForCtNodeEviction;
-    super.sync(packageCacheOptions, workingDirectory, defaultsPackageContents, commandId);
+    super.sync(
+        packageCacheOptions, outputBase, workingDirectory, defaultsPackageContents, commandId);
     handleDiffs();
   }
 
@@ -243,11 +244,10 @@
     recordingDiffer.invalidate(Iterables.filter(memoizingEvaluator.getValues().keySet(), pred));
   }
 
-  private void invalidateDeletedPackages(Iterable<String> deletedPackages) {
+  private void invalidateDeletedPackages(Iterable<PackageIdentifier> deletedPackages) {
     ArrayList<SkyKey> packagesToInvalidate = Lists.newArrayList();
-    for (String deletedPackage : deletedPackages) {
-      PathFragment pathFragment = new PathFragment(deletedPackage);
-      packagesToInvalidate.add(PackageLookupValue.key(pathFragment));
+    for (PackageIdentifier deletedPackage : deletedPackages) {
+      packagesToInvalidate.add(PackageLookupValue.key(deletedPackage));
     }
     recordingDiffer.invalidate(packagesToInvalidate);
   }
@@ -257,7 +257,7 @@
    */
   @Override
   @VisibleForTesting  // productionVisibility = Visibility.PRIVATE
-  public void setDeletedPackages(Iterable<String> pkgs) {
+  public void setDeletedPackages(Iterable<PackageIdentifier> pkgs) {
     // Invalidate the old deletedPackages as they may exist now.
     invalidateDeletedPackages(deletedPackages.get());
     deletedPackages.set(ImmutableSet.copyOf(pkgs));
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 96c39ef..601d7ec 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
@@ -180,8 +180,8 @@
       new AtomicReference<>(UnixGlob.DEFAULT_SYSCALLS);
   protected final AtomicReference<PathPackageLocator> pkgLocator =
       new AtomicReference<>();
-  protected final AtomicReference<ImmutableSet<String>> deletedPackages =
-      new AtomicReference<>(ImmutableSet.<String>of());
+  protected final AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages =
+      new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
   private final AtomicReference<EventBus> eventBus = new AtomicReference<>();
 
   private final ImmutableList<BuildInfoFactory> buildInfoFactories;
@@ -753,7 +753,7 @@
    * Sets the packages that should be treated as deleted and ignored.
    */
   @VisibleForTesting  // productionVisibility = Visibility.PRIVATE
-  public abstract void setDeletedPackages(Iterable<String> pkgs);
+  public abstract void setDeletedPackages(Iterable<PackageIdentifier> pkgs);
 
   /**
    * Prepares the evaluator for loading.
@@ -1299,7 +1299,7 @@
     /**
      * Returns whether the given package should be consider deleted and thus should be ignored.
      */
-    public boolean isPackageDeleted(String packageName) {
+    public boolean isPackageDeleted(PackageIdentifier packageName) {
       return deletedPackages.get().contains(packageName);
     }
 
@@ -1349,12 +1349,13 @@
   @ThreadCompatible
   public abstract void updateLoadedPackageSet(Set<PackageIdentifier> loadedPackages);
 
-  public void sync(PackageCacheOptions packageCacheOptions, Path workingDirectory,
+  public void sync(PackageCacheOptions packageCacheOptions, Path outputBase, Path workingDirectory,
       String defaultsPackageContents, UUID commandId) throws InterruptedException,
       AbruptExitException{
 
     preparePackageLoading(
-        createPackageLocator(packageCacheOptions, directories.getWorkspace(), workingDirectory),
+        createPackageLocator(
+            packageCacheOptions, outputBase, directories.getWorkspace(), workingDirectory),
         packageCacheOptions.defaultVisibility, packageCacheOptions.showLoadingProgress,
         packageCacheOptions.globbingThreads, defaultsPackageContents, commandId);
     setDeletedPackages(ImmutableSet.copyOf(packageCacheOptions.deletedPackages));
@@ -1364,9 +1365,9 @@
   }
 
   protected PathPackageLocator createPackageLocator(PackageCacheOptions packageCacheOptions,
-      Path workspace, Path workingDirectory) throws AbruptExitException{
+      Path outputBase, Path workspace, Path workingDirectory) throws AbruptExitException {
     return PathPackageLocator.create(
-        packageCacheOptions.packagePath, getReporter(), workspace, workingDirectory);
+        outputBase, packageCacheOptions.packagePath, getReporter(), workspace, workingDirectory);
   }
 
   private CyclesReporter createCyclesReporter() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageManager.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageManager.java
index 3e9b6ca..7ffb79ce 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageManager.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframePackageManager.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.devtools.build.lib.cmdline.LabelValidator;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
@@ -136,7 +135,7 @@
   }
 
   @Override
-  public boolean isPackage(EventHandler eventHandler, String packageName) {
+  public boolean isPackage(EventHandler eventHandler, PackageIdentifier packageName) {
     return getBuildFileForPackage(packageName) != null;
   }
 
@@ -147,11 +146,10 @@
 
   @ThreadSafe
   @Override
-  public Path getBuildFileForPackage(String packageName) {
+  public Path getBuildFileForPackage(PackageIdentifier packageName) {
     // Note that this method needs to be thread-safe, as it is currently used concurrently by
     // legacy blaze code.
-    if (packageLoader.isPackageDeleted(packageName)
-        || LabelValidator.validatePackageName(packageName) != null) {
+    if (packageLoader.isPackageDeleted(packageName)) {
       return null;
     }
     // TODO(bazel-team): Use a PackageLookupValue here [skyframe-loading]
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/CommaSeparatedPackageNameListConverter.java b/src/main/java/com/google/devtools/build/lib/syntax/CommaSeparatedPackageNameListConverter.java
index 070e928..ce7680c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/CommaSeparatedPackageNameListConverter.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/CommaSeparatedPackageNameListConverter.java
@@ -16,7 +16,7 @@
 import com.google.common.base.Splitter;
 import com.google.common.base.Strings;
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.cmdline.LabelValidator;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
 import com.google.devtools.common.options.Converter;
 import com.google.devtools.common.options.OptionsParsingException;
 
@@ -26,22 +26,22 @@
  * A converter from strings containing comma-separated names of packages to lists of strings.
  */
 public class CommaSeparatedPackageNameListConverter
-    implements Converter<List<String>> {
+    implements Converter<List<PackageIdentifier>> {
 
   private static final Splitter SPACE_SPLITTER = Splitter.on(',');
 
   @Override
-  public List<String> convert(String input) throws OptionsParsingException {
+  public List<PackageIdentifier> convert(String input) throws OptionsParsingException {
     if (Strings.isNullOrEmpty(input)) {
       return ImmutableList.of();
     }
-    ImmutableList.Builder<String> list = ImmutableList.builder();
+    ImmutableList.Builder<PackageIdentifier> list = ImmutableList.builder();
     for (String s : SPACE_SPLITTER.split(input)) {
-      String errorMessage = LabelValidator.validatePackageName(s);
-      if (errorMessage != null) {
-        throw new OptionsParsingException(errorMessage);
+      try {
+        list.add(PackageIdentifier.parse(s));
+      } catch (Label.SyntaxException e) {
+        throw new OptionsParsingException(e.getMessage());
       }
-      list.add(s);
     }
     return list.build();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java b/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
index 4966fb8..f91222c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvaluationContext.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.packages.CachingPackageLocator;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
 import com.google.devtools.build.lib.syntax.Environment.NoSuchVariableException;
 import com.google.devtools.build.lib.vfs.Path;
 
@@ -90,7 +91,7 @@
   /** Mock package locator */
   private static final class EmptyPackageLocator implements CachingPackageLocator {
     @Override
-    public Path getBuildFileForPackage(String packageName) {
+    public Path getBuildFileForPackage(PackageIdentifier packageName) {
       return null;
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
index 2a9d103..f2f7c2c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
@@ -612,10 +612,13 @@
 
     try {
       Label label = Label.parseAbsolute(labelName);
-      String packageName = label.getPackageFragment().getPathString();
-      Path packagePath = locator.getBuildFileForPackage(packageName);
+      // Note that this doesn't really work if the label belongs to a different repository, because
+      // there is no guarantee that its RepositoryValue has been evaluated. In an ideal world, we
+      // could put a Skyframe dependency the appropriate PackageLookupValue, but we can't do that
+      // because package loading is not completely Skyframized.
+      Path packagePath = locator.getBuildFileForPackage(label.getPackageIdentifier());
       if (packagePath == null) {
-        reportError(location, "Package '" + packageName + "' not found");
+        reportError(location, "Package '" + label.getPackageIdentifier() + "' not found");
         list.add(mocksubincludeExpression(labelName, "", location));
         return;
       }