Use Labels, rather than PathFragments, to represent Skylark loads internally. The load location for a Skylark Aspect is specified via a PathFragment, for consistency with current non-Aspect Skylark loads.

This should be a semantics-preserving change for users. In a subsequent CL, I'll change the Skylark syntax to allow load statements to use labels as well as paths, with the goal of eventually deprecating the latter.

Also:

- Removed the hack for handling relative loads in the prelude file.

- Refactored some redundant functionality in PackageFunction and SkylarkImportLookupFunction for handling loads.

- Removed the ability to put the BUILD file for the package containing a Skylark file under a different package root than the Skylark file itself. This functionality isn't currently used and is inconsistent with Blaze's handling of the package path elsewhere.

- Added BUILD files to a number of tests that load Skylark files; this is consistent with the requirement that all Skylark files need to be part of some package.

- Changed the constants used to set the location of the prelude file from paths to labels.

--
MOS_MIGRATED_REVID=107741568
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 76ad8d1..7eb45f7 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -42,7 +42,6 @@
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
 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.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
@@ -456,15 +455,10 @@
       // Syntax: label%aspect
       int delimiterPosition = aspect.indexOf('%');
       if (delimiterPosition >= 0) {
-        PackageIdentifier bzlFile;
-        try {
-          bzlFile =
-              PackageIdentifier.create(
-                  PackageIdentifier.DEFAULT_REPOSITORY,
-                  new PathFragment(aspect.substring(0, delimiterPosition)));
-        } catch (LabelSyntaxException e) {
-          throw new ViewCreationFailedException("Error", e);
-        }
+        // TODO(jfield): For consistency with Skylark loads, the aspect should be specified
+        // as an absolute path. Also, we probably need to do at least basic validation of
+        // path well-formedness here.
+        PathFragment bzlFile = new PathFragment("/" + aspect.substring(0, delimiterPosition));
 
         String skylarkFunctionName = aspect.substring(delimiterPosition + 1);
         for (ConfiguredTargetKey targetSpec : targetSpecs) {
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 9d0cd4c..616c60c 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
@@ -18,7 +18,6 @@
 import static com.google.devtools.build.lib.packages.RuleClass.Builder.RuleClassType.ABSTRACT;
 import static com.google.devtools.build.lib.packages.RuleClass.Builder.RuleClassType.TEST;
 
-import com.google.common.base.Preconditions;
 import com.google.common.cache.CacheBuilder;
 import com.google.common.cache.CacheLoader;
 import com.google.common.cache.LoadingCache;
@@ -81,7 +80,7 @@
    */
   public static class Builder implements RuleDefinitionEnvironment {
     private final StringBuilder defaultWorkspaceFile = new StringBuilder();
-    private PathFragment preludePath;
+    private Label preludeLabel;
     private String runfilesPrefix;
     private final List<ConfigurationFragmentFactory> configurationFragments = new ArrayList<>();
     private final List<BuildInfoFactory> buildInfoFactories = new ArrayList<>();
@@ -105,11 +104,14 @@
       defaultWorkspaceFile.append(contents);
     }
 
-    public Builder setPrelude(String workspaceRelativePath) {
-      PathFragment preludePathFragment = new PathFragment(workspaceRelativePath);
-      Preconditions.checkArgument(!preludePathFragment.isAbsolute());
-      Preconditions.checkArgument(preludePathFragment.isNormalized());
-      this.preludePath = preludePathFragment;
+    public Builder setPrelude(String preludeLabelString) {
+      try {
+        this.preludeLabel = Label.parseAbsolute(preludeLabelString);
+      } catch (LabelSyntaxException e) {
+        String errorMsg =
+            String.format("Prelude label '%s' is invalid: %s", preludeLabelString, e.getMessage());
+        throw new IllegalArgumentException(errorMsg);
+      }
       return this;
     }
 
@@ -226,7 +228,7 @@
       }
 
       return new ConfiguredRuleClassProvider(
-          preludePath,
+          preludeLabel,
           runfilesPrefix,
           ImmutableMap.copyOf(ruleClassMap),
           ImmutableMap.copyOf(ruleDefinitionMap),
@@ -269,9 +271,9 @@
   String defaultWorkspaceFile;
 
   /**
-   * Workspace-relative path to the prelude.
+   * Label for the prelude file.
    */
-  private final PathFragment preludePath;
+  private final Label preludeLabel;
 
   /**
    * The default runfiles prefix.
@@ -315,7 +317,7 @@
   private final Environment.Frame globals;
 
   public ConfiguredRuleClassProvider(
-      PathFragment preludePath,
+      Label preludeLabel,
       String runfilesPrefix,
       ImmutableMap<String, RuleClass> ruleClassMap,
       ImmutableMap<String, Class<? extends RuleDefinition>> ruleDefinitionMap,
@@ -327,7 +329,7 @@
       ConfigurationCollectionFactory configurationCollectionFactory,
       PrerequisiteValidator prerequisiteValidator,
       ImmutableMap<String, SkylarkType> skylarkAccessibleJavaClasses) {
-    this.preludePath = preludePath;
+    this.preludeLabel = preludeLabel;
     this.runfilesPrefix = runfilesPrefix;
     this.ruleClassMap = ruleClassMap;
     this.ruleDefinitionMap = ruleDefinitionMap;
@@ -346,8 +348,8 @@
   }
 
   @Override
-  public PathFragment getPreludePath() {
-    return preludePath;
+  public Label getPreludeLabel() {
+    return preludeLabel;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
index 3ce6ee0..03948e4 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
@@ -229,7 +229,7 @@
         .addBuildInfoFactory(new CppBuildInfo())
         .addBuildInfoFactory(new ObjcBuildInfoFactory())
         .setConfigurationCollectionFactory(new BazelConfigurationCollection())
-        .setPrelude("tools/build_rules/prelude_bazel")
+        .setPrelude("//tools/build_rules:prelude_bazel")
         .setRunfilesPrefix("")
         .setPrerequisiteValidator(new BazelPrerequisiteValidator());
 
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 db69c24..55aa950 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
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.packages;
 
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.NativeAspectClass.NativeAspectFactory;
 import com.google.devtools.build.lib.syntax.Environment;
@@ -31,9 +32,9 @@
 public interface RuleClassProvider {
 
   /**
-   * Workspace relative path to the prelude file.
+   * Label referencing the prelude file.
    */
-  PathFragment getPreludePath();
+  Label getPreludeLabel();
 
   /**
    * The default runfiles prefix (may be overwritten by the WORKSPACE file).
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
index 80185e0..ed58924 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
@@ -41,7 +41,6 @@
 import com.google.devtools.build.lib.analysis.config.RunUnder;
 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.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.AspectClass;
@@ -85,7 +84,6 @@
 import com.google.devtools.build.lib.syntax.SkylarkValue;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
-import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.HashMap;
 import java.util.Map;
@@ -373,7 +371,7 @@
     // This is fine since we don't modify the builder from here.
     private final RuleClass.Builder builder;
     private final RuleClassType type;
-    private PathFragment skylarkFile;
+    private Label skylarkLabel;
     private String ruleClassName;
 
     public RuleFunction(Builder builder, RuleClassType type) {
@@ -389,7 +387,7 @@
         throws EvalException, InterruptedException, ConversionException {
       env.checkLoadingPhase(getName(), ast.getLocation());
       try {
-        if (ruleClassName == null || skylarkFile == null) {
+        if (ruleClassName == null || skylarkLabel == null) {
           throw new EvalException(ast.getLocation(),
               "Invalid rule class hasn't been exported by a Skylark file");
         }
@@ -409,8 +407,8 @@
     /**
      * Export a RuleFunction from a Skylark file with a given name.
      */
-    void export(PathFragment skylarkFile, String ruleClassName) {
-      this.skylarkFile = skylarkFile;
+    void export(Label skylarkLabel, String ruleClassName) {
+      this.skylarkLabel = skylarkLabel;
       this.ruleClassName = ruleClassName;
     }
 
@@ -420,20 +418,20 @@
     }
   }
 
-  public static void exportRuleFunctionsAndAspects(Environment env, PackageIdentifier skylarkFile) {
+  public static void exportRuleFunctionsAndAspects(Environment env, Label skylarkLabel) {
     for (String name : env.getGlobals().getDirectVariableNames()) {
       try {
         Object value = env.lookup(name);
         if (value instanceof RuleFunction) {
           RuleFunction function = (RuleFunction) value;
-          if (function.skylarkFile == null) {
-            function.export(skylarkFile.getPackageFragment(), name);
+          if (function.skylarkLabel == null) {
+            function.export(skylarkLabel, name);
           }
         }
         if (value instanceof SkylarkAspect) {
           SkylarkAspect skylarkAspect = (SkylarkAspect) value;
           if (!skylarkAspect.isExported()) {
-            skylarkAspect.export(skylarkFile, name);
+            skylarkAspect.export(skylarkLabel, name);
           }
         }
       } catch (NoSuchVariableException e) {
@@ -606,17 +604,17 @@
       return exported != null ? exported.toString() : "<skylark aspect>";
     }
 
-    void export(PackageIdentifier extensionFile, String name) {
-      this.exported = new Exported(extensionFile, name);
+    void export(Label extensionLabel, String name) {
+      this.exported = new Exported(extensionLabel, name);
     }
 
     public boolean isExported() {
       return exported != null;
     }
 
-    private PackageIdentifier getExtensionFile() {
+    private Label getExtensionLabel() {
       Preconditions.checkArgument(isExported());
-      return exported.extensionFile;
+      return exported.extensionLabel;
     }
 
     private String getExportedName() {
@@ -626,16 +624,17 @@
 
     @Immutable
     private static class Exported {
-      private final PackageIdentifier extensionFile;
+      private final Label extensionLabel;
       private final String name;
 
-      public Exported(PackageIdentifier extensionFile, String name) {
-        this.extensionFile = extensionFile;
+      public Exported(Label extensionLabel, String name) {
+        this.extensionLabel = extensionLabel;
         this.name = name;
       }
 
+      @Override
       public String toString() {
-        return extensionFile.toString() + "%" + name;
+        return extensionLabel.toString() + "%" + name;
       }
     }
   }
@@ -646,7 +645,7 @@
   @Immutable
   public static final class SkylarkAspectClass implements AspectClass {
     private final AspectDefinition aspectDefinition;
-    private final PackageIdentifier extensionFile;
+    private final Label extensionLabel;
     private final String exportedName;
 
     public SkylarkAspectClass(SkylarkAspect skylarkAspect) {
@@ -657,7 +656,7 @@
       }
       this.aspectDefinition = builder.build();
 
-      this.extensionFile = skylarkAspect.getExtensionFile();
+      this.extensionLabel = skylarkAspect.getExtensionLabel();
       this.exportedName = skylarkAspect.getExportedName();
     }
 
@@ -671,18 +670,20 @@
       return aspectDefinition;
     }
 
-    public PackageIdentifier getExtensionFile() {
-      return extensionFile;
+    public Label getExtensionLabel() {
+      return extensionLabel;
     }
 
     public String getExportedName() {
       return exportedName;
     }
 
+    @Override
     public int hashCode() {
-      return Objects.hash(extensionFile, exportedName);
+      return Objects.hash(extensionLabel, exportedName);
     }
 
+    @Override
     public boolean equals(Object other) {
       if (this == other) {
         return true;
@@ -692,7 +693,7 @@
       }
 
       SkylarkAspectClass that = (SkylarkAspectClass) other;
-      return Objects.equals(this.extensionFile, that.extensionFile)
+      return Objects.equals(this.extensionLabel, that.extensionLabel)
           && Objects.equals(this.exportedName, that.exportedName);
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
index e5e4771..c030ccc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
@@ -14,10 +14,8 @@
 
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
-import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Runtime;
@@ -32,113 +30,79 @@
 import com.google.devtools.build.skyframe.SkyValue;
 
 import java.io.IOException;
-import java.util.List;
-import java.util.concurrent.atomic.AtomicReference;
 
 import javax.annotation.Nullable;
 
 /**
- * A SkyFunction for {@link ASTFileLookupValue}s. Tries to locate a file and load it as a
- * syntax tree and cache the resulting {@link BuildFileAST}. If the file doesn't exist
- * the function doesn't fail but returns a specific NO_FILE ASTLookupValue.
+ * A SkyFunction for {@link ASTFileLookupValue}s.
+ *
+ * <p> Given a {@link Label} referencing a Skylark file, loads it as a syntax tree
+ * ({@link BuildFileAST}). The Label must be absolute, and must not reference the special
+ * {@code external} package. If the file (or the package containing it) doesn't exist, the
+ * function doesn't fail, but instead returns a specific {@code NO_FILE} {@link ASTFileLookupValue}.
  */
 public class ASTFileLookupFunction implements SkyFunction {
 
-  private abstract static class FileLookupResult {
-    /** Returns whether the file lookup was successful. */
-    public abstract boolean lookupSuccessful();
-
-    /** If {@code lookupSuccessful()}, returns the {@link RootedPath} to the file. */
-    public abstract RootedPath rootedPath();
-
-    /** If {@code lookupSuccessful()}, returns the file's size, in bytes. */
-    public abstract long fileSize();
-
-    static FileLookupResult noFile() {
-      return UnsuccessfulFileResult.INSTANCE;
-    }
-
-    static FileLookupResult file(RootedPath rootedPath, long fileSize) {
-      return new SuccessfulFileResult(rootedPath, fileSize);
-    }
-
-    private static class SuccessfulFileResult extends FileLookupResult {
-      private final RootedPath rootedPath;
-      private final long fileSize;
-
-      private SuccessfulFileResult(RootedPath rootedPath, long fileSize) {
-        this.rootedPath = rootedPath;
-        this.fileSize = fileSize;
-      }
-
-      @Override
-      public boolean lookupSuccessful() {
-        return true;
-      }
-
-      @Override
-      public RootedPath rootedPath() {
-        return rootedPath;
-      }
-
-      @Override
-      public long fileSize() {
-        return fileSize;
-      }
-    }
-
-    private static class UnsuccessfulFileResult extends FileLookupResult {
-      private static final UnsuccessfulFileResult INSTANCE = new UnsuccessfulFileResult();
-      private UnsuccessfulFileResult() {
-      }
-
-      @Override
-      public boolean lookupSuccessful() {
-        return false;
-      }
-
-      @Override
-      public RootedPath rootedPath() {
-        throw new IllegalStateException("unsuccessful lookup");
-      }
-
-      @Override
-      public long fileSize() {
-        throw new IllegalStateException("unsuccessful lookup");
-      }
-    }
-  }
-
-  private final AtomicReference<PathPackageLocator> pkgLocator;
   private final RuleClassProvider ruleClassProvider;
 
-  public ASTFileLookupFunction(AtomicReference<PathPackageLocator> pkgLocator,
-      RuleClassProvider ruleClassProvider) {
-    this.pkgLocator = pkgLocator;
+  public ASTFileLookupFunction(RuleClassProvider ruleClassProvider) {
     this.ruleClassProvider = ruleClassProvider;
   }
 
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) throws SkyFunctionException,
       InterruptedException {
-    PackageIdentifier key = (PackageIdentifier) skyKey.argument();
-    PathFragment astFilePathFragment = key.getPackageFragment();
-    FileLookupResult lookupResult = getASTFile(env, key);
-    if (lookupResult == null) {
+    Label fileLabel = (Label) skyKey.argument();
+    PathFragment filePathFragment = fileLabel.toPathFragment();
+
+    //
+    // Determine whether the package designated by fileLabel exists.
+    //
+    SkyKey pkgSkyKey = PackageLookupValue.key(fileLabel.getPackageIdentifier());
+    PackageLookupValue pkgLookupValue = null;
+    pkgLookupValue = (PackageLookupValue) env.getValue(pkgSkyKey);
+    if (pkgLookupValue == null) {
       return null;
     }
-    if (!lookupResult.lookupSuccessful()) {
-      return ASTFileLookupValue.noFile();
+    if (!pkgLookupValue.packageExists()) {
+      return ASTFileLookupValue.forBadPackage(fileLabel, pkgLookupValue.getErrorMsg());
     }
-    BuildFileAST ast = null;
-    Path path = lookupResult.rootedPath().asPath();
-    long fileSize = lookupResult.fileSize();
-    // Skylark files end with bzl.
-    boolean parseAsSkylark = astFilePathFragment.getPathString().endsWith(".bzl");
+
+    //
+    // Determine whether the file designated by fileLabel exists.
+    //
+    Path packageRoot = pkgLookupValue.getRoot();
+    RootedPath rootedPath = RootedPath.toRootedPath(packageRoot, filePathFragment);
+    SkyKey fileSkyKey = FileValue.key(rootedPath);
+    FileValue fileValue = null;
     try {
+      fileValue = (FileValue) env.getValueOrThrow(fileSkyKey, IOException.class,
+          FileSymlinkException.class, InconsistentFilesystemException.class);
+    } catch (IOException | FileSymlinkException e) {
+      throw new ASTLookupFunctionException(new ErrorReadingSkylarkExtensionException(e),
+          Transience.PERSISTENT);
+    } catch (InconsistentFilesystemException e) {
+      throw new ASTLookupFunctionException(e, Transience.PERSISTENT);
+    }
+    if (fileValue == null) {
+      return null;
+    }
+    if (!fileValue.isFile()) {
+      return ASTFileLookupValue.forBadFile(fileLabel);
+    }
+
+    //
+    // Both the package and the file exist; load the file and parse it as an AST.
+    //
+    BuildFileAST ast = null;
+    Path path = rootedPath.asPath();
+    // Skylark files end with bzl
+    boolean parseAsSkylark = filePathFragment.getPathString().endsWith(".bzl");
+    try {
+      long astFileSize = fileValue.getSize();
       if (parseAsSkylark) {
         try (Mutability mutability = Mutability.create("validate")) {
-            ast = BuildFileAST.parseSkylarkFile(path, fileSize, env.getListener(),
+            ast = BuildFileAST.parseSkylarkFile(path, astFileSize, env.getListener(),
                 new ValidationEnvironment(
                     ruleClassProvider.createSkylarkRuleClassEnvironment(
                         mutability,
@@ -150,52 +114,16 @@
                     .setupDynamic(Runtime.REPOSITORY_NAME, Runtime.NONE)));
         }
       } else {
-        ast = BuildFileAST.parseBuildFile(path, fileSize, env.getListener(), false);
+        ast = BuildFileAST.parseBuildFile(path, astFileSize, env.getListener(), false);
       }
     } catch (IOException e) {
-        throw new ASTLookupFunctionException(new ErrorReadingSkylarkExtensionException(
-            e.getMessage()), Transience.TRANSIENT);
+      throw new ASTLookupFunctionException(new ErrorReadingSkylarkExtensionException(e),
+          Transience.TRANSIENT);
     }
+
     return ASTFileLookupValue.withFile(ast);
   }
 
-  private FileLookupResult getASTFile(Environment env, PackageIdentifier key)
-      throws ASTLookupFunctionException {
-    List<Path> candidateRoots;
-    if (!key.getRepository().isDefault()) {
-      RepositoryValue repository =
-          (RepositoryValue) env.getValue(RepositoryValue.key(key.getRepository()));
-      if (repository == null) {
-        return null;
-      }
-
-      candidateRoots = ImmutableList.of(repository.getPath());
-    } else {
-      candidateRoots = pkgLocator.get().getPathEntries();
-    }
-
-    for (Path root : candidateRoots) {
-      RootedPath rootedPath = RootedPath.toRootedPath(root, key.getPackageFragment());
-      FileValue fileValue;
-      try {
-        fileValue = (FileValue) env.getValueOrThrow(FileValue.key(rootedPath),
-            IOException.class, FileSymlinkException.class, InconsistentFilesystemException.class);
-      } catch (IOException | FileSymlinkException e) {
-        throw new ASTLookupFunctionException(new ErrorReadingSkylarkExtensionException(
-            e.getMessage()), Transience.PERSISTENT);
-      } catch (InconsistentFilesystemException e) {
-        throw new ASTLookupFunctionException(e, Transience.PERSISTENT);
-      }
-      if (fileValue == null) {
-        return null;
-      }
-      if (fileValue.isFile()) {
-        return FileLookupResult.file(rootedPath, fileValue.getSize());
-      }
-    }
-    return FileLookupResult.noFile();
-  }
-
   @Nullable
   @Override
   public String extractTag(SkyKey skyKey) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
index 99e4f18..4581cb2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
@@ -14,48 +14,87 @@
 
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
-import javax.annotation.Nullable;
-
 /**
- * A value that represents an AST file lookup result.
+ * A value that represents an AST file lookup result. There are two subclasses: one for the
+ * case where the file is found, and another for the case where the file is missing (but there
+ * are no other errors).
  */
-public class ASTFileLookupValue implements SkyValue {
+abstract class ASTFileLookupValue implements SkyValue {
+  public abstract boolean lookupSuccessful();
+  public abstract BuildFileAST getAST();
+  public abstract String getErrorMsg();
+  
+  /** If the file is found, this class encapsulates the parsed AST. */
+  private static class ASTLookupWithFile extends ASTFileLookupValue {
+    private final BuildFileAST ast;
 
-  private static final ASTFileLookupValue NO_FILE = new ASTFileLookupValue(null);
-
-  @Nullable private final BuildFileAST ast;
-
-  private ASTFileLookupValue(@Nullable BuildFileAST ast) {
-    this.ast = ast;
-  }
-
-  public static ASTFileLookupValue noFile() {
-    return NO_FILE;
-  }
-
-  public static ASTFileLookupValue withFile(BuildFileAST ast) {
-    return new ASTFileLookupValue(ast);
-  }
-
-  /**
-   * Returns the original AST file.
-   */
-  @Nullable public BuildFileAST getAST() {
-    return ast;
-  }
-
-  static SkyKey key(PackageIdentifier astFileIdentifier) {
-    return new SkyKey(SkyFunctions.AST_FILE_LOOKUP, astFileIdentifier);
-  }
-
-  static final class ASTLookupInputException extends Exception {
-    ASTLookupInputException(String msg) {
-      super(msg);
+    private ASTLookupWithFile(BuildFileAST ast) {
+      Preconditions.checkNotNull(ast);
+      this.ast = ast;
     }
+
+    @Override
+    public boolean lookupSuccessful() {
+      return true;
+    }
+
+    @Override
+    public BuildFileAST getAST() {
+      return this.ast;
+    }
+
+    @Override
+    public String getErrorMsg() {
+      throw new IllegalStateException(
+          "attempted to retrieve unsuccessful lookup reason for successful lookup");
+    }
+  }
+ 
+  /** If the file isn't found, this class encapsulates a message with the reason. */
+  private static class ASTLookupNoFile extends ASTFileLookupValue {
+    private final String errorMsg;
+
+    private ASTLookupNoFile(String errorMsg) {
+      this.errorMsg = Preconditions.checkNotNull(errorMsg);
+    }
+
+    @Override
+    public boolean lookupSuccessful() {
+      return false;
+    }
+
+    @Override
+    public BuildFileAST getAST() {
+      throw new IllegalStateException("attempted to retrieve AST from an unsuccessful lookup");
+    }
+
+    @Override
+    public String getErrorMsg() {
+      return this.errorMsg;
+    }
+  }
+
+  static ASTFileLookupValue forBadPackage(Label fileLabel, String reason) {
+    return new ASTLookupNoFile(
+        String.format("Unable to load package for '%s': %s", fileLabel, reason));
+  }
+  
+  static ASTFileLookupValue forBadFile(Label fileLabel) {
+    return new ASTLookupNoFile(
+        String.format("Unable to load file '%s': file doesn't exist or isn't a file", fileLabel));
+  }
+  
+  public static ASTFileLookupValue withFile(BuildFileAST ast) {
+    return new ASTLookupWithFile(ast);
+  }
+
+  static SkyKey key(Label astFileLabel) {
+    return new SkyKey(SkyFunctions.AST_FILE_LOOKUP, astFileLabel);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index bc7bc6a..d365738 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -25,7 +25,7 @@
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.Attribute;
@@ -38,7 +38,6 @@
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.rules.SkylarkRuleClassFunctions.SkylarkAspect;
 import com.google.devtools.build.lib.rules.SkylarkRuleClassFunctions.SkylarkAspectClass;
-import com.google.devtools.build.lib.skyframe.ASTFileLookupValue.ASTLookupInputException;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.DependencyEvaluationException;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
@@ -71,10 +70,10 @@
    */
   @Nullable
   public static SkylarkAspect loadSkylarkAspect(
-      Environment env, PackageIdentifier extensionFile, String skylarkValueName)
-      throws ASTLookupInputException, ConversionException {
-    SkyKey importFileKey;
-    importFileKey = SkylarkImportLookupValue.key(extensionFile);
+      Environment env, Label extensionLabel, String skylarkValueName)
+      throws ConversionException {
+    
+    SkyKey importFileKey = SkylarkImportLookupValue.key(extensionLabel);
     SkylarkImportLookupValue skylarkImportLookupValue =
         (SkylarkImportLookupValue) env.getValue(importFileKey);
     if (skylarkImportLookupValue == null) {
@@ -84,7 +83,7 @@
     Object skylarkValue = skylarkImportLookupValue.getEnvironmentExtension().get(skylarkValueName);
     if (!(skylarkValue instanceof SkylarkAspect)) {
       throw new ConversionException(
-          skylarkValueName + " from " + extensionFile.toString() + " is not an aspect");
+          skylarkValueName + " from " + extensionLabel.toString() + " is not an aspect");
     }
     return (SkylarkAspect) skylarkValue;
   }
@@ -106,8 +105,8 @@
       try {
         skylarkAspect =
             loadSkylarkAspect(
-                env, skylarkAspectClass.getExtensionFile(), skylarkAspectClass.getExportedName());
-      } catch (ASTLookupInputException | ConversionException e) {
+                env, skylarkAspectClass.getExtensionLabel(), skylarkAspectClass.getExportedName());
+      } catch (ConversionException e) {
         throw new AspectFunctionException(skyKey, e);
       }
       if (skylarkAspect == null) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
index 4d5e6c2..c2d6f2d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
@@ -19,13 +19,13 @@
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.Aspect;
 import com.google.devtools.build.lib.packages.AspectClass;
 import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 
@@ -86,6 +86,7 @@
       return aspect;
     }
 
+    @Override
     public String getDescription() {
       return String.format("%s of %s", aspect.getAspectClass().getName(), getLabel());
     }
@@ -134,13 +135,13 @@
 
     private final Label targetLabel;
     private final BuildConfiguration targetConfiguration;
-    private final PackageIdentifier extensionFile;
+    private final PathFragment extensionFile;
     private final String skylarkValueName;
 
     private SkylarkAspectLoadingKey(
         Label targetLabel,
         BuildConfiguration targetConfiguration,
-        PackageIdentifier extensionFile,
+        PathFragment extensionFile,
         String skylarkFunctionName) {
       this.targetLabel = targetLabel;
       this.targetConfiguration = targetConfiguration;
@@ -154,7 +155,7 @@
       return SkyFunctions.LOAD_SKYLARK_ASPECT;
     }
 
-    public PackageIdentifier getExtensionFile() {
+    public PathFragment getExtensionFile() {
       return extensionFile;
     }
 
@@ -170,6 +171,7 @@
       return targetConfiguration;
     }
 
+    @Override
     public String getDescription() {
       // Skylark aspects are referred to on command line with <file>%<value ame>
       return String.format("%s%%%s of %s", extensionFile.toString(), skylarkValueName, targetLabel);
@@ -240,7 +242,7 @@
   public static SkylarkAspectLoadingKey createSkylarkAspectKey(
       Label targetLabel,
       BuildConfiguration targetConfiguration,
-      PackageIdentifier skylarkFile,
+      PathFragment skylarkFile,
       String skylarkExportName) {
     return new SkylarkAspectLoadingKey(
         targetLabel, targetConfiguration, skylarkFile, skylarkExportName);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ErrorReadingSkylarkExtensionException.java b/src/main/java/com/google/devtools/build/lib/skyframe/ErrorReadingSkylarkExtensionException.java
index 6df0113..af4f039 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ErrorReadingSkylarkExtensionException.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ErrorReadingSkylarkExtensionException.java
@@ -15,7 +15,7 @@
 
 /** Indicates some sort of IO error while dealing with a Skylark extension. */
 public class ErrorReadingSkylarkExtensionException extends Exception {
-  public ErrorReadingSkylarkExtensionException(String message) {
-    super(message);
+  public ErrorReadingSkylarkExtensionException(Exception e) {
+    super(e.getMessage(), e);
   }
 }
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 3829c98..197d929 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
@@ -15,6 +15,7 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.cache.Cache;
+import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -23,8 +24,8 @@
 import com.google.common.collect.Maps;
 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.PackageIdentifier;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.events.StoredEventHandler;
@@ -43,12 +44,12 @@
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
-import com.google.devtools.build.lib.skyframe.ASTFileLookupValue.ASTLookupInputException;
 import com.google.devtools.build.lib.skyframe.GlobValue.InvalidGlobPatternException;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction.SkylarkImportFailedException;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.syntax.Environment.Extension;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.syntax.LoadStatement;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 import com.google.devtools.build.lib.syntax.Statement;
 import com.google.devtools.build.lib.util.Pair;
@@ -61,9 +62,9 @@
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.ValueOrException2;
 import com.google.devtools.build.skyframe.ValueOrException3;
 import com.google.devtools.build.skyframe.ValueOrException4;
-import com.google.devtools.build.skyframe.ValueOrExceptionUtils;
 
 import java.io.IOException;
 import java.util.Collection;
@@ -89,8 +90,7 @@
   private final AtomicBoolean showLoadingProgress;
   private final AtomicInteger numPackagesLoaded;
   private final Profiler profiler = Profiler.instance();
-
-  private final PathFragment preludePath;
+  private final Label preludeLabel;
 
   // Not final only for testing.
   @Nullable private SkylarkImportLookupFunction skylarkImportLookupFunctionForInlining;
@@ -107,9 +107,9 @@
       @Nullable SkylarkImportLookupFunction skylarkImportLookupFunctionForInlining) {
     this.skylarkImportLookupFunctionForInlining = skylarkImportLookupFunctionForInlining;
     // Can be null in tests.
-    this.preludePath = packageFactory == null
+    this.preludeLabel = packageFactory == null
         ? null
-        : packageFactory.getRuleClassProvider().getPreludePath();
+        : packageFactory.getRuleClassProvider().getPreludeLabel();
     this.packageFactory = packageFactory;
     this.packageLocator = pkgLocator;
     this.showLoadingProgress = showLoadingProgress;
@@ -433,21 +433,22 @@
       return null;
     }
 
+    SkyKey astLookupKey = ASTFileLookupValue.key(preludeLabel);
     ASTFileLookupValue astLookupValue = null;
-    SkyKey astLookupKey = ASTFileLookupValue.key(
-        PackageIdentifier.createInDefaultRepo(preludePath));
     try {
       astLookupValue = (ASTFileLookupValue) env.getValueOrThrow(astLookupKey,
           ErrorReadingSkylarkExtensionException.class, InconsistentFilesystemException.class);
     } catch (ErrorReadingSkylarkExtensionException | InconsistentFilesystemException e) {
-      throw new PackageFunctionException(new BadPreludeFileException(packageId, e.getMessage()),
-          Transience.PERSISTENT);
+      throw new PackageFunctionException(
+          new BadPreludeFileException(packageId, e.getMessage()), Transience.PERSISTENT);
     }
     if (astLookupValue == null) {
       return null;
     }
-    List<Statement> preludeStatements = astLookupValue.getAST() == null
-        ? ImmutableList.<Statement>of() : astLookupValue.getAST().getStatements();
+    // The prelude file doesn't have to exist. If not, we substitute an empty statement list.
+    List<Statement> preludeStatements =
+        astLookupValue.lookupSuccessful()
+            ? astLookupValue.getAST().getStatements() : ImmutableList.<Statement>of();
     Package.LegacyBuilder legacyPkgBuilder =
         loadPackage(
             externalPkg,
@@ -455,7 +456,6 @@
             packageId,
             buildFilePath,
             buildFileValue,
-            buildFileFragment,
             defaultVisibility,
             preludeStatements,
             env);
@@ -527,7 +527,6 @@
   @Nullable
   private SkylarkImportResult discoverSkylarkImports(
       Path buildFilePath,
-      PathFragment buildFileFragment,
       PackageIdentifier packageId,
       AstAfterPreprocessing astAfterPreprocessing,
       Environment env)
@@ -540,47 +539,12 @@
               ImmutableList.<Label>of());
     } else {
       importResult =
-          fetchImportsFromBuildFile(buildFilePath, buildFileFragment, packageId,
-              astAfterPreprocessing.ast, env);
+          fetchImportsFromBuildFile(buildFilePath, packageId, astAfterPreprocessing.ast, env);
     }
 
     return importResult;
   }
 
-  static SkyKey getImportKey(
-      Map.Entry<Location, PathFragment> entry,
-      PathFragment preludePath,
-      PathFragment buildFileFragment,
-      PackageIdentifier packageId)
-      throws ASTLookupInputException {
-    PathFragment importFile = entry.getValue();
-    // HACK: The prelude sometimes contains load() statements, which need to be resolved
-    // relative to the prelude file. However, we don't have a good way to tell "this should come
-    // from the main repository" in a load() statement, and we don't have a good way to tell if
-    // a load() statement comes from the prelude, since we just prepend those statements before
-    // the actual BUILD file. So we use this evil .endsWith() statement to figure it out.
-    RepositoryName repository =
-        entry.getKey().getPath().endsWith(preludePath)
-            ? PackageIdentifier.DEFAULT_REPOSITORY_NAME
-            : packageId.getRepository();
-    return SkylarkImportLookupValue.key(repository, buildFileFragment, importFile);
-  }
-
-  private static SkyKey getImportKeyAndMaybeThrowException(
-      Map.Entry<Location, PathFragment> entry,
-      PathFragment preludePath,
-      PathFragment buildFileFragment,
-      PackageIdentifier packageId)
-      throws PackageFunctionException {
-    try {
-      return getImportKey(entry, preludePath, buildFileFragment, packageId);
-    } catch (ASTLookupInputException e) {
-      // The load syntax is bad in the BUILD file so BuildFileContainsErrorsException is OK.
-      throw new PackageFunctionException(
-          new BuildFileContainsErrorsException(packageId, e.getMessage()), Transience.PERSISTENT);
-    }
-  }
-
   /**
    * Fetch the skylark loads for this BUILD file. If any of them haven't been computed yet,
    * returns null.
@@ -588,110 +552,105 @@
   @Nullable
   private SkylarkImportResult fetchImportsFromBuildFile(
       Path buildFilePath,
-      PathFragment buildFileFragment,
       PackageIdentifier packageId,
       BuildFileAST buildFileAST,
       Environment env)
       throws PackageFunctionException, InterruptedException {
-    ImmutableMap<Location, PathFragment> imports = buildFileAST.getImports();
-    Map<PathFragment, Extension> importMap = Maps.newHashMapWithExpectedSize(imports.size());
+    ImmutableList<LoadStatement> loadStmts = buildFileAST.getImports();
+    Map<PathFragment, Extension> importMap = Maps.newHashMapWithExpectedSize(loadStmts.size());
     ImmutableList.Builder<SkylarkFileDependency> fileDependencies = ImmutableList.builder();
-    Map<
-            SkyKey,
-            ValueOrException4<
-                SkylarkImportFailedException, InconsistentFilesystemException,
-                ASTLookupInputException, BuildFileNotFoundException>>
-        skylarkImportMap;
-    Map<SkyKey, PathFragment> skylarkImports = Maps.newHashMapWithExpectedSize(imports.size());
-    if (skylarkImportLookupFunctionForInlining != null) {
-      skylarkImportMap = Maps.newHashMapWithExpectedSize(imports.size());
-      for (Map.Entry<Location, PathFragment> entry : imports.entrySet()) {
-        SkyKey importKey =
-            getImportKeyAndMaybeThrowException(entry, preludePath, buildFileFragment, packageId);
-        skylarkImports.put(importKey, entry.getValue());
-        ValueOrException4<
-                SkylarkImportFailedException, InconsistentFilesystemException,
-                ASTLookupInputException, BuildFileNotFoundException>
-            lookupResult;
-        try {
-          SkyValue value =
-              skylarkImportLookupFunctionForInlining.computeWithInlineCalls(importKey, env);
-          if (value == null) {
-            Preconditions.checkState(env.valuesMissing(), importKey);
-            // Don't give up on computing. This is against the Skyframe contract, but we don't want
-            // to pay the price of serializing all these calls, since they are fundamentally
-            // independent.
-            lookupResult = ValueOrExceptionUtils.ofNullValue();
+    ImmutableMap<PathFragment, Label> importPathMap;
+    
+    // Find the labels corresponding to the load statements.
+    Label labelForCurrBuildFile;
+    try {
+      labelForCurrBuildFile = Label.create(packageId, "BUILD");
+    } catch (LabelSyntaxException e) {
+      // Shouldn't happen; the Label is well-formed by construction.
+      throw new IllegalStateException(e);
+    }
+    try {
+      importPathMap = SkylarkImportLookupFunction.findLabelsForLoadStatements(
+          loadStmts, labelForCurrBuildFile, env);
+      if (importPathMap == null) {
+        return null;
+      }
+    } catch (SkylarkImportFailedException e) {
+      env.getListener().handle(Event.error(Location.fromFile(buildFilePath), e.getMessage()));
+      throw new PackageFunctionException(
+          new BuildFileContainsErrorsException(packageId, e.getMessage()), Transience.PERSISTENT);
+    }
+
+    // Look up and load the imports.
+    ImmutableCollection<Label> importLabels = importPathMap.values();
+    List<SkyKey> importLookupKeys = Lists.newArrayListWithExpectedSize(importLabels.size());
+    for (Label importLabel : importLabels) {
+      importLookupKeys.add(SkylarkImportLookupValue.key(importLabel));
+    }
+    Map<SkyKey, SkyValue> skylarkImportMap = Maps.newHashMapWithExpectedSize(importPathMap.size());
+    boolean valuesMissing = false;
+
+    try {
+      if (skylarkImportLookupFunctionForInlining == null) {
+        // Not inlining
+        Map<SkyKey,
+            ValueOrException2<
+                SkylarkImportFailedException,
+                InconsistentFilesystemException>> skylarkLookupResults = env.getValuesOrThrow(
+                    importLookupKeys,
+                    SkylarkImportFailedException.class,
+                    InconsistentFilesystemException.class);
+        valuesMissing = env.valuesMissing();
+        for (Map.Entry<
+              SkyKey,
+              ValueOrException2<
+                  SkylarkImportFailedException,
+                  InconsistentFilesystemException>> entry : skylarkLookupResults.entrySet()) {
+          // Fetching the value will raise any deferred exceptions
+          skylarkImportMap.put(entry.getKey(), entry.getValue().get());
+        }
+      } else {
+        // Inlining calls to SkylarkImportLookupFunction
+        for (SkyKey importLookupKey : importLookupKeys) {
+          SkyValue skyValue = skylarkImportLookupFunctionForInlining.computeWithInlineCalls(
+              importLookupKey, env);
+          if (skyValue == null) {
+            Preconditions.checkState(
+                env.valuesMissing(), "no skylark import value for %s", importLookupKey);
+            // We continue making inline calls even if some requested values are missing, to
+            // maximize the number of dependent (non-inlined) SkyFunctions that are requested, thus
+            // avoiding a quadratic number of restarts.
+            valuesMissing = true;
           } else {
-            lookupResult = ValueOrExceptionUtils.ofValue(value);
-          }
-        } catch (SkyFunctionException e) {
-          Exception cause = e.getCause();
-          if (cause instanceof SkylarkImportFailedException) {
-            lookupResult = ValueOrExceptionUtils.ofExn1((SkylarkImportFailedException) cause);
-          } else if (cause instanceof InconsistentFilesystemException) {
-            lookupResult = ValueOrExceptionUtils.ofExn2((InconsistentFilesystemException) cause);
-          } else if (cause instanceof ASTLookupInputException) {
-            lookupResult = ValueOrExceptionUtils.ofExn3((ASTLookupInputException) cause);
-          } else if (cause instanceof BuildFileNotFoundException) {
-            lookupResult = ValueOrExceptionUtils.ofExn4((BuildFileNotFoundException) cause);
-          } else {
-            throw new IllegalStateException("Unexpected type for " + importKey, e);
+            skylarkImportMap.put(importLookupKey, skyValue);
           }
         }
-        skylarkImportMap.put(importKey, lookupResult);
       }
-    } else {
-      for (Map.Entry<Location, PathFragment> entry : imports.entrySet()) {
-        skylarkImports.put(
-            getImportKeyAndMaybeThrowException(entry, preludePath, buildFileFragment, packageId),
-            entry.getValue());
-      }
-      skylarkImportMap =
-          env.getValuesOrThrow(
-              skylarkImports.keySet(),
-              SkylarkImportFailedException.class,
-              InconsistentFilesystemException.class,
-              ASTLookupInputException.class,
-              BuildFileNotFoundException.class);
+    } catch (SkylarkImportFailedException e) {
+      env.getListener().handle(Event.error(Location.fromFile(buildFilePath), e.getMessage()));
+      throw new PackageFunctionException(
+          new BuildFileContainsErrorsException(packageId, e.getMessage()), Transience.PERSISTENT);
+    } catch (InconsistentFilesystemException e) {
+      throw new PackageFunctionException(
+          new InternalInconsistentFilesystemException(packageId, e), Transience.PERSISTENT);
     }
-
-    for (Map.Entry<
-            SkyKey,
-            ValueOrException4<
-                SkylarkImportFailedException, InconsistentFilesystemException,
-                ASTLookupInputException, BuildFileNotFoundException>>
-        entry : skylarkImportMap.entrySet()) {
-      SkylarkImportLookupValue importLookupValue;
-      try {
-        importLookupValue = (SkylarkImportLookupValue) entry.getValue().get();
-      } catch (SkylarkImportFailedException e) {
-        env.getListener().handle(Event.error(Location.fromFile(buildFilePath), e.getMessage()));
-        throw new PackageFunctionException(
-            new BuildFileContainsErrorsException(packageId, e.getMessage()), Transience.PERSISTENT);
-      } catch (InconsistentFilesystemException e) {
-        throw new PackageFunctionException(
-            new InternalInconsistentFilesystemException(packageId, e), Transience.PERSISTENT);
-      } catch (ASTLookupInputException e) {
-        // The load syntax is bad in the BUILD file so BuildFileContainsErrorsException is OK.
-        throw new PackageFunctionException(
-            new BuildFileContainsErrorsException(packageId, e.getMessage()), Transience.PERSISTENT);
-      } catch (BuildFileNotFoundException e) {
-        throw new PackageFunctionException(e, Transience.PERSISTENT);
-      }
-      if (importLookupValue == null) {
-        Preconditions.checkState(env.valuesMissing(), entry);
-      } else {
-        importMap.put(
-            skylarkImports.get(entry.getKey()), importLookupValue.getEnvironmentExtension());
-        fileDependencies.add(importLookupValue.getDependency());
-      }
-    }
-
-    if (env.valuesMissing()) {
-      // There are unavailable Skylark dependencies.
+    
+    if (valuesMissing) {
+      // Some imports are unavailable.
       return null;
     }
+    
+    // Process the loaded imports.
+    for (Entry<PathFragment, Label> importEntry : importPathMap.entrySet()) {
+      PathFragment importPath = importEntry.getKey();
+      Label importLabel = importEntry.getValue();
+      SkyKey keyForLabel = SkylarkImportLookupValue.key(importLabel);
+      SkylarkImportLookupValue importLookupValue =
+          (SkylarkImportLookupValue) skylarkImportMap.get(keyForLabel);
+      importMap.put(importPath, importLookupValue.getEnvironmentExtension());
+      fileDependencies.add(importLookupValue.getDependency());
+    }
+    
     return new SkylarkImportResult(importMap, transitiveClosureOfLabels(fileDependencies.build()));
   }
 
@@ -858,7 +817,6 @@
       PackageIdentifier packageId,
       Path buildFilePath,
       @Nullable FileValue buildFileValue,
-      PathFragment buildFileFragment,
       RuleVisibility defaultVisibility,
       List<Statement> preludeStatements,
       Environment env)
@@ -921,7 +879,6 @@
         try {
           importResult = discoverSkylarkImports(
               buildFilePath,
-              buildFileFragment,
               packageId,
               astAfterPreprocessing,
               env);
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 9c1dce2..b3e5b8e 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
@@ -333,7 +333,7 @@
     map.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
     map.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));
     map.put(SkyFunctions.CONTAINING_PACKAGE_LOOKUP, new ContainingPackageLookupFunction());
-    map.put(SkyFunctions.AST_FILE_LOOKUP, new ASTFileLookupFunction(pkgLocator, ruleClassProvider));
+    map.put(SkyFunctions.AST_FILE_LOOKUP, new ASTFileLookupFunction(ruleClassProvider));
     map.put(
         SkyFunctions.SKYLARK_IMPORTS_LOOKUP,
         newSkylarkImportLookupFunction(ruleClassProvider, pkgFactory));
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
index bba850b..603e832 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
@@ -15,22 +15,26 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.LinkedHashMultimap;
+import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
+import com.google.common.collect.Multimap;
 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.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
 import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.rules.SkylarkRuleClassFunctions;
-import com.google.devtools.build.lib.skyframe.ASTFileLookupValue.ASTLookupInputException;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.syntax.Environment.Extension;
+import com.google.devtools.build.lib.syntax.LoadStatement;
 import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
@@ -38,15 +42,25 @@
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.ValueOrException2;
 
 import java.util.LinkedHashSet;
+import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 
 import javax.annotation.Nullable;
 
 /**
  * A Skyframe function to look up and import a single Skylark extension.
+ *
+ * <p> Given a {@link Label} referencing a Skylark file, attempts to locate the file and load it.
+ * The Label must be absolute, and must not reference the special {@code external} package. If
+ * loading is successful, returns a {@link SkylarkImportLookupValue} that encapsulates
+ * the loaded {@link Extension} and {@link SkylarkFileDependency} information. If loading is
+ * unsuccessful, throws a {@link SkylarkImportLookupFunctionException} that encapsulates the
+ * cause of the failure.
  */
 public class SkylarkImportLookupFunction implements SkyFunction {
 
@@ -62,166 +76,273 @@
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) throws SkyFunctionException,
       InterruptedException {
-    return computeInternal((PackageIdentifier) skyKey.argument(), env, null);
+    Label fileLabel = (Label) skyKey.argument();
+    try {
+      return computeInternal(fileLabel, env, null);
+    } catch (InconsistentFilesystemException e) {
+      throw new SkylarkImportLookupFunctionException(e, Transience.PERSISTENT);
+    } catch (SkylarkImportFailedException e) {
+      throw new SkylarkImportLookupFunctionException(e);
+    }
   }
 
   SkyValue computeWithInlineCalls(SkyKey skyKey, Environment env)
-      throws SkyFunctionException, InterruptedException {
+      throws InconsistentFilesystemException,
+          SkylarkImportFailedException,
+          InterruptedException {
     return computeWithInlineCallsInternal(
-        (PackageIdentifier) skyKey.argument(), env, new LinkedHashSet<PackageIdentifier>());
+        (Label) skyKey.argument(), env, new LinkedHashSet<Label>());
   }
 
   private SkyValue computeWithInlineCallsInternal(
-      PackageIdentifier pkgId, Environment env, Set<PackageIdentifier> visited)
-          throws SkyFunctionException, InterruptedException {
-    return computeInternal(pkgId, env, Preconditions.checkNotNull(visited, pkgId));
+      Label fileLabel, Environment env, Set<Label> visited)
+          throws InconsistentFilesystemException,
+              SkylarkImportFailedException,
+              InterruptedException {
+    return computeInternal(fileLabel, env, Preconditions.checkNotNull(visited, fileLabel));
   }
 
-  SkyValue computeInternal(
-      PackageIdentifier pkgId, Environment env, @Nullable Set<PackageIdentifier> visited)
-          throws SkyFunctionException, InterruptedException {
-    PathFragment file = pkgId.getPackageFragment();
-    ASTFileLookupValue astLookupValue = null;
+  SkyValue computeInternal(Label fileLabel, Environment env, @Nullable Set<Label> visited)
+      throws InconsistentFilesystemException,
+          SkylarkImportFailedException,
+          InterruptedException {
+    PathFragment filePath = fileLabel.toPathFragment();
+    
+    // Load the AST corresponding to this file.
+    ASTFileLookupValue astLookupValue;
     try {
-      SkyKey astLookupKey = ASTFileLookupValue.key(pkgId);
+      SkyKey astLookupKey = ASTFileLookupValue.key(fileLabel);
       astLookupValue = (ASTFileLookupValue) env.getValueOrThrow(astLookupKey,
           ErrorReadingSkylarkExtensionException.class, InconsistentFilesystemException.class);
     } catch (ErrorReadingSkylarkExtensionException e) {
-      throw new SkylarkImportLookupFunctionException(SkylarkImportFailedException.errorReadingFile(
-          file, e.getMessage()));
-    } catch (InconsistentFilesystemException e) {
-      throw new SkylarkImportLookupFunctionException(e, Transience.PERSISTENT);
+      throw SkylarkImportFailedException.errorReadingFile(filePath, e.getMessage());
     }
     if (astLookupValue == null) {
       return null;
     }
-    if (astLookupValue.getAST() == null) {
+    if (!astLookupValue.lookupSuccessful()) {
       // Skylark import files have to exist.
-      throw new SkylarkImportLookupFunctionException(SkylarkImportFailedException.noFile(file));
+      throw SkylarkImportFailedException.noFile(astLookupValue.getErrorMsg());
     }
-
     BuildFileAST ast = astLookupValue.getAST();
     if (ast.containsErrors()) {
-      throw new SkylarkImportLookupFunctionException(
-          SkylarkImportFailedException.skylarkErrors(file));
+      throw SkylarkImportFailedException.skylarkErrors(filePath);
     }
 
-    Label label = pathFragmentToLabel(pkgId.getRepository(), file, env);
-    if (label == null) {
-      Preconditions.checkState(env.valuesMissing(), "null label with no missing %s", file);
+    // Process the load statements in the file.
+    ImmutableList<LoadStatement> loadStmts = ast.getImports();
+    Map<PathFragment, Extension> importMap = Maps.newHashMapWithExpectedSize(loadStmts.size());
+    ImmutableList.Builder<SkylarkFileDependency> fileDependencies = ImmutableList.builder();
+    ImmutableMap<PathFragment, Label> importPathMap;
+    
+    // Find the labels corresponding to the load statements.
+    importPathMap = findLabelsForLoadStatements(loadStmts, fileLabel, env);
+    if (importPathMap == null) {
       return null;
     }
 
-    Map<Location, PathFragment> astImports = ast.getImports();
-    Map<PathFragment, Extension> importMap = Maps.newHashMapWithExpectedSize(astImports.size());
-    ImmutableList.Builder<SkylarkFileDependency> fileDependencies = ImmutableList.builder();
-    Map<SkyKey, PathFragment> skylarkImports = Maps.newHashMapWithExpectedSize(astImports.size());
-    for (Map.Entry<Location, PathFragment> entry : ast.getImports().entrySet()) {
-      try {
-        skylarkImports.put(
-            PackageFunction.getImportKey(entry, ruleClassProvider.getPreludePath(), file, pkgId),
-            entry.getValue());
-      } catch (ASTLookupInputException e) {
-        throw new SkylarkImportLookupFunctionException(e, Transience.PERSISTENT);
-      }
+    // Look up and load the imports.
+    ImmutableCollection<Label> importLabels = importPathMap.values();
+    List<SkyKey> importLookupKeys =
+        Lists.newArrayListWithExpectedSize(importLabels.size());
+    for (Label importLabel : importLabels) {
+      importLookupKeys.add(SkylarkImportLookupValue.key(importLabel));
     }
-
     Map<SkyKey, SkyValue> skylarkImportMap;
     boolean valuesMissing = false;
     if (visited == null) {
       // Not inlining.
-      skylarkImportMap = env.getValues(skylarkImports.keySet());
+      skylarkImportMap = env.getValues(importLookupKeys);
       valuesMissing = env.valuesMissing();
     } else {
-      // inlining calls to SkylarkImportLookupFunction.
-      if (!visited.add(pkgId)) {
-        ImmutableList<PackageIdentifier> cycle =
-            CycleUtils.splitIntoPathAndChain(Predicates.equalTo(pkgId), visited)
+      // Inlining calls to SkylarkImportLookupFunction.
+      if (!visited.add(fileLabel)) {
+        ImmutableList<Label> cycle =
+            CycleUtils.splitIntoPathAndChain(Predicates.equalTo(fileLabel), visited)
                 .second;
         if (env.getValue(SkylarkImportUniqueCycleFunction.key(cycle)) == null) {
           return null;
         }
-        throw new SkylarkImportLookupFunctionException(
-            new SkylarkImportFailedException("Skylark import cycle"));
+        throw new SkylarkImportFailedException("Skylark import cycle");
       }
-      skylarkImportMap = Maps.newHashMapWithExpectedSize(astImports.size());
-      for (SkyKey skylarkImport : skylarkImports.keySet()) {
+      skylarkImportMap = Maps.newHashMapWithExpectedSize(loadStmts.size());
+      for (SkyKey importLookupKey : importLookupKeys) {
         SkyValue skyValue =
             this.computeWithInlineCallsInternal(
-                (PackageIdentifier) skylarkImport.argument(), env, visited);
+                (Label) importLookupKey.argument(), env, visited);
         if (skyValue == null) {
           Preconditions.checkState(
-              env.valuesMissing(), "no skylark import value for %s", skylarkImport);
-          // Don't give up on computing. This is against the Skyframe contract, but we don't want to
-          // pay the price of serializing all these calls, since they are fundamentally independent.
+              env.valuesMissing(), "no skylark import value for %s", importLookupKey);
+          // We continue making inline calls even if some requested values are missing, to maximize
+          // the number of dependent (non-inlined) SkyFunctions that are requested, thus avoiding a
+          // quadratic number of restarts.
           valuesMissing = true;
         } else {
-          skylarkImportMap.put(skylarkImport, skyValue);
+          skylarkImportMap.put(importLookupKey, skyValue);
         }
       }
       // All imports traversed, this key can no longer be part of a cycle.
-      visited.remove(pkgId);
+      visited.remove(fileLabel);
     }
-
     if (valuesMissing) {
       // This means some imports are unavailable.
       return null;
     }
 
-    for (Map.Entry<SkyKey, SkyValue> entry : skylarkImportMap.entrySet()) {
-      SkylarkImportLookupValue importLookupValue = (SkylarkImportLookupValue) entry.getValue();
-      importMap.put(
-          skylarkImports.get(entry.getKey()), importLookupValue.getEnvironmentExtension());
+    // Process the loaded imports.
+    for (Entry<PathFragment, Label> importEntry : importPathMap.entrySet()) {
+      PathFragment importPath = importEntry.getKey();
+      Label importLabel = importEntry.getValue();
+      SkyKey keyForLabel = SkylarkImportLookupValue.key(importLabel);
+      SkylarkImportLookupValue importLookupValue =
+          (SkylarkImportLookupValue) skylarkImportMap.get(keyForLabel);
+      importMap.put(importPath, importLookupValue.getEnvironmentExtension());
       fileDependencies.add(importLookupValue.getDependency());
     }
-
     // Skylark UserDefinedFunction-s in that file will share this function definition Environment,
     // which will be frozen by the time it is returned by createExtension.
-    Extension extension = createExtension(ast, pkgId, importMap, env);
+    Extension extension = createExtension(ast, fileLabel, importMap, env);
 
     return new SkylarkImportLookupValue(
-        extension, new SkylarkFileDependency(label, fileDependencies.build()));
+        extension, new SkylarkFileDependency(fileLabel, fileDependencies.build()));
+  }
+
+  /** Computes the Label corresponding to a relative import path. */
+  private static Label labelForRelativeImport(PathFragment importPath, Label containingFileLabel)
+      throws SkylarkImportFailedException {
+    PackageIdentifier pkgIdForImport = containingFileLabel.getPackageIdentifier();
+    PathFragment containingDir =
+        (new PathFragment(containingFileLabel.getName())).getParentDirectory();
+    String targetNameForImport = importPath.getRelative(containingDir).toString();
+    try {
+      return Label.create(pkgIdForImport, targetNameForImport);
+    } catch (LabelSyntaxException e) {
+      // While the Label is for the most part guaranteed to be well-formed by construction, an
+      // error is still possible if the filename itself is malformed, e.g., contains control
+      // characters. Since we expect this error to be very rare, for code simplicity, we allow the
+      // error message to refer to a Label even though the filename was specified via a simple path.
+     throw new SkylarkImportFailedException(e);
+    }
   }
 
   /**
-   * Converts the PathFragment of the Skylark file to a Label using the BUILD file closest to the
-   * Skylark file in its directory hierarchy - finds the package to which the Skylark file belongs.
-   * Throws an exception if no such BUILD file exists.
+   * Computes the set of Labels corresponding to a collection of PathFragments representing
+   * absolute import paths.
+   * 
+   * @return a map from the computed {@link Label}s to the corresponding {@link PathFragment}s;
+   *   {@code null} if any Skyframe dependencies are unavailable.
+   * @throws SkylarkImportFailedException
    */
-  private Label pathFragmentToLabel(RepositoryName repo, PathFragment file, Environment env)
-      throws SkylarkImportLookupFunctionException {
-    ContainingPackageLookupValue containingPackageLookupValue = null;
+  @Nullable
+  static ImmutableMap<PathFragment, Label> labelsForAbsoluteImports(
+      ImmutableSet<PathFragment> pathsToLookup, Environment env)
+          throws SkylarkImportFailedException {
+
+    // Import PathFragments are absolute, so there is a 1-1 mapping from corresponding Labels.
+    ImmutableMap.Builder<PathFragment, Label> outputMap = new ImmutableMap.Builder<>();
+ 
+    // The SkyKey here represents the directory containing an import PathFragment, hence there
+    // can in general be multiple imports per lookup.
+    Multimap<SkyKey, PathFragment> lookupMap = LinkedHashMultimap.create();
+    for (PathFragment importPath : pathsToLookup) {
+      PathFragment relativeImportPath = importPath.toRelative();
+      PackageIdentifier pkgToLookUp =
+          PackageIdentifier.createInDefaultRepo(relativeImportPath.getParentDirectory());
+      lookupMap.put(ContainingPackageLookupValue.key(pkgToLookUp), importPath);
+    }
+ 
+    // Attempt to find a package for every directory containing an import.
+    Map<SkyKey,
+        ValueOrException2<BuildFileNotFoundException,
+            InconsistentFilesystemException>> lookupResults =
+        env.getValuesOrThrow(
+            lookupMap.keySet(),
+            BuildFileNotFoundException.class,
+            InconsistentFilesystemException.class);
+    if (env.valuesMissing()) {
+     return null;
+    }
     try {
-      PackageIdentifier newPkgId = PackageIdentifier.create(repo, file.getParentDirectory());
-      containingPackageLookupValue = (ContainingPackageLookupValue) env.getValueOrThrow(
-          ContainingPackageLookupValue.key(newPkgId),
-          BuildFileNotFoundException.class, InconsistentFilesystemException.class);
+      // Process lookup results.
+      for (Entry<SkyKey,
+               ValueOrException2<BuildFileNotFoundException,
+                   InconsistentFilesystemException>> entry : lookupResults.entrySet()) {
+        ContainingPackageLookupValue lookupValue =
+            (ContainingPackageLookupValue) entry.getValue().get();
+        PackageIdentifier pkgIdForImport = lookupValue.getContainingPackageName();
+        if (!lookupValue.hasContainingPackage()) {
+          // Although multiple imports may be in the same package-less directory, we only
+          // report an error for the first one.
+          PackageIdentifier lookupKey = ((PackageIdentifier) entry.getKey().argument());
+          PathFragment importFile = lookupKey.getPackageFragment();
+          throw SkylarkImportFailedException.noBuildFile(importFile);
+        }
+        PathFragment containingPkgPath = pkgIdForImport.getPackageFragment();
+        for (PathFragment importPath : lookupMap.get(entry.getKey())) {
+         PathFragment relativeImportPath = importPath.toRelative();
+         String targetNameForImport = relativeImportPath.relativeTo(containingPkgPath).toString();
+         try {
+           outputMap.put(importPath, Label.create(pkgIdForImport, targetNameForImport));
+         } catch (LabelSyntaxException e) {
+           // While the Label is for the most part guaranteed to be well-formed by construction, an
+           // error is still possible if the filename itself is malformed, e.g., contains control
+           // characters. Since we expect this error to be very rare, for code simplicity, we allow
+           // the error message to refer to a Label even though the filename was specified via a
+           // simple path.
+           throw new SkylarkImportFailedException(e);
+         }         
+        }
+      }
     } catch (BuildFileNotFoundException e) {
       // Thrown when there are IO errors looking for BUILD files.
-      throw new SkylarkImportLookupFunctionException(e, Transience.PERSISTENT);
+      throw new SkylarkImportFailedException(e);
     } catch (InconsistentFilesystemException e) {
-      throw new SkylarkImportLookupFunctionException(e, Transience.PERSISTENT);
+      throw new SkylarkImportFailedException(e);
     }
 
-    if (containingPackageLookupValue == null) {
+  return outputMap.build();
+  }
+
+  /**
+   * Computes the set of {@link Label}s corresponding to a set of Skylark {@link LoadStatement}s.
+   * 
+   * @param loadStmts a collection of Skylark {@link LoadStatement}s
+   * @param containingFileLabel the {@link Label} of the file containing the load statements
+   * @return an {@link ImmutableMap} which maps a {@link PathFragment} corresponding
+   *     to one of the files to be loaded to the corresponding {@Label}. Returns {@code null} if any
+   *     Skyframe dependencies are unavailable. (attempt to retrieve an AST 
+   * @throws SkylarkImportFailedException if no package can be found that contains the
+   *     loaded file
+   */
+  @Nullable
+  static ImmutableMap<PathFragment, Label> findLabelsForLoadStatements(
+      Iterable<LoadStatement> loadStmts, Label containingFileLabel, Environment env)
+          throws SkylarkImportFailedException {
+    ImmutableSet.Builder<PathFragment> absolutePathsToLookup = new ImmutableSet.Builder<>();
+
+    ImmutableMap.Builder<PathFragment, Label> outputMap = new ImmutableMap.Builder<>();
+    for (LoadStatement loadStmt : loadStmts) {
+      PathFragment importPath = loadStmt.getImportPath();
+      if (loadStmt.isAbsolute()) {
+        absolutePathsToLookup.add(importPath);
+      } else {
+        // Relative paths don't require package lookups since they can only refer to files in the
+        // same directory as the file containing the load statement; i.e., they can't refer to
+        // subdirectories. We can therefore compute the corresponding label directly from the label
+        // of the containing file (whose package has already been validated).
+        outputMap.put(importPath, labelForRelativeImport(importPath, containingFileLabel));
+      }
+    }
+
+    // Compute labels for absolute paths 
+    ImmutableMap<PathFragment, Label> absoluteLabels =
+        labelsForAbsoluteImports(absolutePathsToLookup.build(), env);
+    if (absoluteLabels == null) {
       return null;
     }
-
-    if (!containingPackageLookupValue.hasContainingPackage()) {
-      throw new SkylarkImportLookupFunctionException(
-          SkylarkImportFailedException.noBuildFile(file));
-    }
-
-    PathFragment pkgName =
-        containingPackageLookupValue.getContainingPackageName().getPackageFragment();
-    PathFragment fileInPkg = file.relativeTo(pkgName);
-
-    try {
-      // This code relies on PackageIdentifier.RepositoryName.toString()
-      return Label.parseAbsolute(repo + "//" + pkgName.getPathString() + ":" + fileInPkg);
-    } catch (LabelSyntaxException e) {
-      throw new IllegalStateException(e);
-    }
+    outputMap.putAll(absoluteLabels);
+    
+    return outputMap.build();
   }
 
   /**
@@ -229,27 +350,27 @@
    */
   private Extension createExtension(
       BuildFileAST ast,
-      PackageIdentifier packageIdentifier,
+      Label extensionLabel,
       Map<PathFragment, Extension> importMap,
       Environment env)
-      throws InterruptedException, SkylarkImportLookupFunctionException {
+          throws SkylarkImportFailedException, InterruptedException {
     StoredEventHandler eventHandler = new StoredEventHandler();
     // TODO(bazel-team): this method overestimates the changes which can affect the
     // Skylark RuleClass. For example changes to comments or unused functions can modify the hash.
     // A more accurate - however much more complicated - way would be to calculate a hash based on
     // the transitive closure of the accessible AST nodes.
-    try (Mutability mutability = Mutability.create("importing %s", packageIdentifier)) {
+    PathFragment extensionFile = extensionLabel.toPathFragment();
+    try (Mutability mutability = Mutability.create("importing %s", extensionFile)) {
       com.google.devtools.build.lib.syntax.Environment extensionEnv =
           ruleClassProvider.createSkylarkRuleClassEnvironment(
               mutability, eventHandler, ast.getContentHashCode(), importMap)
           .setupOverride("native", packageFactory.getNativeModule());
       ast.exec(extensionEnv, eventHandler);
-      SkylarkRuleClassFunctions.exportRuleFunctionsAndAspects(extensionEnv, packageIdentifier);
+      SkylarkRuleClassFunctions.exportRuleFunctionsAndAspects(extensionEnv, extensionLabel);
 
       Event.replayEventsOn(env.getListener(), eventHandler.getEvents());
       if (eventHandler.hasErrors()) {
-        throw new SkylarkImportLookupFunctionException(
-            SkylarkImportFailedException.errors(packageIdentifier.getPackageFragment()));
+        throw SkylarkImportFailedException.errors(extensionFile);
       }
       return new Extension(extensionEnv);
     }
@@ -265,6 +386,18 @@
       super(errorMessage);
     }
 
+    private SkylarkImportFailedException(InconsistentFilesystemException e) {
+      super(e.getMessage());
+    }
+
+    private SkylarkImportFailedException(BuildFileNotFoundException e) {
+      super(e.getMessage());
+    }
+
+    private SkylarkImportFailedException(LabelSyntaxException e) {
+      super(e.getMessage());
+    }
+
     static SkylarkImportFailedException errors(PathFragment file) {
       return new SkylarkImportFailedException(
           String.format("Extension file '%s' has errors", file));
@@ -275,9 +408,9 @@
           String.format("Encountered error while reading extension file '%s': %s", file, error));
     }
 
-    static SkylarkImportFailedException noFile(PathFragment file) {
+    static SkylarkImportFailedException noFile(String reason) {
       return new SkylarkImportFailedException(
-          String.format("Extension file not found: '%s'", file));
+          String.format("Extension file not found. %s", reason));
     }
 
     static SkylarkImportFailedException noBuildFile(PathFragment file) {
@@ -302,11 +435,6 @@
       super(e, transience);
     }
 
-    private SkylarkImportLookupFunctionException(ASTLookupInputException e,
-        Transience transience) {
-      super(e, transience);
-    }
-
     private SkylarkImportLookupFunctionException(BuildFileNotFoundException e,
         Transience transience) {
       super(e, transience);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
index 8530884..c298977 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
@@ -13,20 +13,16 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
-import com.google.devtools.build.lib.skyframe.ASTFileLookupValue.ASTLookupInputException;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.syntax.Environment.Extension;
-import com.google.devtools.build.lib.syntax.LoadStatement;
-import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /**
  * A value that represents a Skylark import lookup result. The lookup value corresponds to
- * exactly one Skylark file, identified by the PathFragment SkyKey argument.
+ * exactly one Skylark file, identified by an absolute {@link Label} {@link SkyKey} argument. The
+ * Label should not reference the special {@code external} package.
  */
 public class SkylarkImportLookupValue implements SkyValue {
 
@@ -58,44 +54,11 @@
     return dependency;
   }
 
-  private static void checkInputArgument(PathFragment astFilePathFragment)
-      throws ASTLookupInputException {
-    if (astFilePathFragment.isAbsolute()) {
-      throw new ASTLookupInputException(String.format(
-          "Input file '%s' cannot be an absolute path.", astFilePathFragment));
-    }
-  }
-
-  @VisibleForTesting
-  public static SkyKey key(PackageIdentifier pkgIdentifier) throws ASTLookupInputException {
-    return key(pkgIdentifier.getRepository(), pkgIdentifier.getPackageFragment());
-  }
-
   /**
-   * Returns a SkyKey to get a SkylarkImportLookupValue. Note that SkylarkImportLookupValue
-   * computations may be inlined to avoid having them in the graph. Callers should confirm whether
-   * inlining is desired and either do the computation directly themselves (if inlined) or request
-   * this key's value from the environment (if not).
+   * Returns a SkyKey to look up {@link Label} {@code importLabel}, which must be an absolute
+   * label.
    */
-  static SkyKey key(RepositoryName repo, PathFragment fromFile, PathFragment fileToImport)
-      throws ASTLookupInputException {
-    PathFragment computedPath;
-    if (fileToImport.isAbsolute()) {
-      computedPath = fileToImport.toRelative();
-    } else if (fileToImport.segmentCount() == 1) {
-      computedPath = fromFile.getParentDirectory().getRelative(fileToImport);
-    } else {
-      throw new ASTLookupInputException(String.format(LoadStatement.PATH_ERROR_MSG, fileToImport));
-    }
-    return key(repo, computedPath);
-  }
-
-  private static SkyKey key(RepositoryName repo, PathFragment fileToImport)
-      throws ASTLookupInputException {
-    // Skylark import lookup keys need to be valid AST file lookup keys.
-    checkInputArgument(fileToImport);
-    return new SkyKey(
-        SkyFunctions.SKYLARK_IMPORTS_LOOKUP,
-        PackageIdentifier.create(repo, fileToImport));
+  static SkyKey key(Label importLabel) {
+    return new SkyKey(SkyFunctions.SKYLARK_IMPORTS_LOOKUP, importLabel);  
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportUniqueCycleFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportUniqueCycleFunction.java
index bffbf00..bb5ff30 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportUniqueCycleFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportUniqueCycleFunction.java
@@ -14,16 +14,16 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.skyframe.SkyKey;
 
 /**
  * Emits an error message exactly once when a Skylark import cycle is found when running inlined
  * {@link SkylarkImportLookupFunction}s.
  */
-class SkylarkImportUniqueCycleFunction extends AbstractChainUniquenessFunction<PackageIdentifier> {
+class SkylarkImportUniqueCycleFunction extends AbstractChainUniquenessFunction<Label> {
 
-  static SkyKey key(ImmutableList<PackageIdentifier> cycle) {
+  static SkyKey key(ImmutableList<Label> cycle) {
     return ChainUniquenessUtils.key(SkyFunctions.SKYLARK_IMPORT_CYCLE, cycle);
   }
 
@@ -43,7 +43,7 @@
   }
 
   @Override
-  protected String elementToString(PackageIdentifier pkgId) {
-    return pkgId.getPathFragment().getPathString();
+  protected String elementToString(Label importLabel) {
+    return importLabel.toString();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkModuleCycleReporter.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkModuleCycleReporter.java
index b6329a7..4da76f0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkModuleCycleReporter.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkModuleCycleReporter.java
@@ -18,7 +18,7 @@
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.skyframe.CycleInfo;
@@ -58,7 +58,7 @@
           new Function<SkyKey, String>() {
         @Override
         public String apply(SkyKey input) {
-          return ((PackageIdentifier) input.argument()).toString();
+          return ((Label) input.argument()).toString();
         }
       });
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
index fabb1bb..cecc689 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
@@ -14,13 +14,16 @@
 
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.rules.SkylarkRuleClassFunctions.SkylarkAspect;
 import com.google.devtools.build.lib.rules.SkylarkRuleClassFunctions.SkylarkAspectClass;
-import com.google.devtools.build.lib.skyframe.ASTFileLookupValue.ASTLookupInputException;
 import com.google.devtools.build.lib.skyframe.AspectValue.SkylarkAspectLoadingKey;
+import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction.SkylarkImportFailedException;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -33,7 +36,7 @@
  *
  * Used for loading top-level aspects. At top level, in
  * {@link com.google.devtools.build.lib.analysis.BuildView}, we cannot invoke two SkyFunctions
- * one aftre another, so BuildView call this function to do the work.
+ * one after another, so BuildView calls this function to do the work.
  */
 public class ToplevelSkylarkAspectFunction implements SkyFunction {
 
@@ -43,11 +46,25 @@
       throws LoadSkylarkAspectFunctionException, InterruptedException {
     SkylarkAspectLoadingKey aspectLoadingKey = (SkylarkAspectLoadingKey) skyKey.argument();
     String skylarkValueName = aspectLoadingKey.getSkylarkValueName();
-    PackageIdentifier extensionFile = aspectLoadingKey.getExtensionFile();
+    PathFragment extensionFile = aspectLoadingKey.getExtensionFile();
+    
+    // Find label corresponding to skylark file, if one exists.
+    ImmutableMap<PathFragment, Label> labelLookupMap;
+    try {
+      labelLookupMap =
+          SkylarkImportLookupFunction.labelsForAbsoluteImports(ImmutableSet.of(extensionFile), env);
+    } catch (SkylarkImportFailedException e) {
+      throw new LoadSkylarkAspectFunctionException(e, skyKey);
+    }
+    if (labelLookupMap == null) {
+      return null;
+    }
+
     SkylarkAspect skylarkAspect = null;
     try {
-      skylarkAspect = AspectFunction.loadSkylarkAspect(env, extensionFile, skylarkValueName);
-    } catch (ASTLookupInputException | ConversionException e) {
+      skylarkAspect = AspectFunction.loadSkylarkAspect(
+          env, labelLookupMap.get(extensionFile), skylarkValueName);
+    } catch (ConversionException e) {
       throw new LoadSkylarkAspectFunctionException(e, skyKey);
     }
     if (skylarkAspect == null) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java b/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java
index 39a86ce..d1fc8b7 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java
@@ -14,13 +14,11 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.hash.HashCode;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.vfs.Path;
-import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.io.IOException;
 import java.util.List;
@@ -36,7 +34,7 @@
 
   private final ImmutableList<Comment> comments;
 
-  private ImmutableMap<Location, PathFragment> loads;
+  private ImmutableList<LoadStatement> loads;
 
   /**
    * Whether any errors were encountered during scanning or parsing.
@@ -61,13 +59,13 @@
     setLocation(result.location);
   }
 
-  /** Collects paths from all load statements */
-  private ImmutableMap<Location, PathFragment> fetchLoads(List<Statement> stmts) {
-    ImmutableMap.Builder<Location, PathFragment> loads = ImmutableMap.builder();
+  /** Collects all load statements */
+  private ImmutableList<LoadStatement> fetchLoads(List<Statement> stmts) {
+    ImmutableList.Builder<LoadStatement> loads = new ImmutableList.Builder<>();
     for (Statement stmt : stmts) {
       if (stmt instanceof LoadStatement) {
         LoadStatement imp = (LoadStatement) stmt;
-        loads.put(imp.getLocation(), imp.getImportPath());
+        loads.add(imp);
       }
     }
     return loads.build();
@@ -97,9 +95,9 @@
   }
 
   /**
-   * Returns a set of loads in this BUILD file.
+   * Returns a list of loads in this BUILD file.
    */
-  public synchronized ImmutableMap<Location, PathFragment> getImports() {
+  public synchronized ImmutableList<LoadStatement> getImports() {
     if (loads == null) {
       loads = fetchLoads(stmts);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java
index 670380c..67ca431 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java
@@ -31,8 +31,6 @@
  */
 public final class LoadStatement extends Statement {
 
-  public static final String PATH_ERROR_MSG = "Path '%s' is not valid. "
-      + "It should either start with a slash or refer to a file in the current directory.";
   private final ImmutableMap<Identifier, String> symbols;
   private final ImmutableList<Identifier> cachedSymbols; // to save time
   private final PathFragment importPath;
@@ -41,10 +39,9 @@
   /**
    * Constructs an import statement.
    *
-   * <p>Symbols maps a symbol to its original name under which it was defined in
-   * the bzl file that should be loaded.
-   * If aliasing is used, the value differs from it's key's symbol#getName().
-   * Otherwise, both values are identical.
+   * <p>{@code symbols} maps a symbol to the original name under which it was defined in
+   * the bzl file that should be loaded. If aliasing is used, the value differs from its key's
+   * {@code symbol.getName()}. Otherwise, both values are identical.
    */
   LoadStatement(StringLiteral path, Map<Identifier, String> symbols) {
     this.symbols = ImmutableMap.copyOf(symbols);
@@ -77,7 +74,7 @@
               getLocation(), "symbol '" + current + "' is private and cannot be imported.");
         }
         // The key is the original name that was used to define the symbol
-        // in the loaded bzl file
+        // in the loaded bzl file.
         env.importSymbol(getImportPath(), current, entry.getValue());
       } catch (Environment.NoSuchVariableException | Environment.LoadFailedException e) {
         throw new EvalException(getLocation(), e.getMessage());
@@ -93,10 +90,6 @@
   @Override
   void validate(ValidationEnvironment env) throws EvalException {
     validatePath();
-
-    if (!importPath.isAbsolute() && importPath.segmentCount() > 1) {
-      throw new EvalException(getLocation(), String.format(PATH_ERROR_MSG, importPath));
-    }
     for (Identifier symbol : cachedSymbols) {
       env.declare(symbol.getName(), getLocation());
     }
@@ -119,6 +112,11 @@
       error =
           "First argument of load() is a path, not a label. "
           + "It should start with a single slash if it is an absolute path.";
+    } else if (!importPath.isAbsolute() && importPath.segmentCount() > 1) {
+      error = String.format(
+          "Path '%s' is not valid. "
+              + "It should either start with a slash or refer to a file in the current directory.",
+          importPath);
     }
 
     if (error != null) {
@@ -133,4 +131,8 @@
         "load statements should never appear in method bodies and"
             + " should never be compiled in general");
   }
+
+  public boolean isAbsolute() {
+    return getImportPath().isAbsolute();
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionException.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionException.java
index 883fc21..a1d5334 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionException.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionException.java
@@ -22,7 +22,7 @@
  * Base class of exceptions thrown by {@link SkyFunction#compute} on failure.
  *
  * SkyFunctions should declare a subclass {@code C} of {@link SkyFunctionException} whose
- * constructors forward fine-grained exception types (e.g. {@link IOException}) to
+ * constructors forward fine-grained exception types (e.g. {@code IOException}) to
  * {@link SkyFunctionException}'s constructor, and they should also declare
  * {@link SkyFunction#compute} to throw {@code C}. This way the type system checks that no
  * unexpected exceptions are thrown by the {@link SkyFunction}.
@@ -90,7 +90,7 @@
   }
 
   @Override
-  public Exception getCause() {
+  public synchronized Exception getCause() {
     return (Exception) super.getCause();
   }