Add new skyframe function to lookup the repository given a path, and use that
to report invalid package references. Fixes #1592.

--
MOS_MIGRATED_REVID=137164164
diff --git a/src/main/java/com/google/devtools/build/lib/packages/ErrorDeterminingRepositoryException.java b/src/main/java/com/google/devtools/build/lib/packages/ErrorDeterminingRepositoryException.java
new file mode 100644
index 0000000..f8659ae
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/packages/ErrorDeterminingRepositoryException.java
@@ -0,0 +1,27 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.packages;
+
+/** Exception indicating an attempt to access a repository which is not found or does not exist. */
+public class ErrorDeterminingRepositoryException extends NoSuchThingException {
+
+  public ErrorDeterminingRepositoryException(String message) {
+    super(message);
+  }
+
+  public ErrorDeterminingRepositoryException(String message, Throwable cause) {
+    super(message, cause);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index 54ccc3e..7e1fca4 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -475,11 +476,23 @@
     return (Rule) targets.get(targetName);
   }
 
+  /** Returns all rules in the package that match the given rule class. */
+  public Iterable<Rule> getRulesMatchingRuleClass(final String ruleClass) {
+    Iterable<Rule> targets = getTargets(Rule.class);
+    return Iterables.filter(
+        targets,
+        new Predicate<Rule>() {
+          @Override
+          public boolean apply(@Nullable Rule rule) {
+            return rule.getRuleClass().equals(ruleClass);
+          }
+        });
+  }
+
   /**
    * Returns this package's workspace name.
    *
-   * <p>Package-private to encourage callers to get their workspace name from a rule, not a
-   * package.</p>
+   * <p>Package-private to encourage callers to get their workspace name from a rule, not a package.
    */
   public String getWorkspaceName() {
     return workspaceName;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunction.java
new file mode 100644
index 0000000..4c97875
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunction.java
@@ -0,0 +1,246 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import com.google.common.base.Optional;
+import com.google.common.base.Predicate;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
+import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
+import com.google.devtools.build.lib.packages.ErrorDeterminingRepositoryException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.Package.NameConflictException;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.rules.repository.LocalRepositoryRule;
+import com.google.devtools.build.lib.skyframe.PackageFunction.PackageFunctionException;
+import com.google.devtools.build.lib.syntax.Type;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionException;
+import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import java.io.IOException;
+import javax.annotation.Nullable;
+
+/** SkyFunction for {@link LocalRepositoryLookupValue}s. */
+public class LocalRepositoryLookupFunction implements SkyFunction {
+
+  @Override
+  @Nullable
+  public String extractTag(SkyKey skyKey) {
+    return null;
+  }
+
+  // Implementation note: Although LocalRepositoryLookupValue.NOT_FOUND exists, it should never be
+  // returned from this method.
+  @Override
+  public SkyValue compute(SkyKey skyKey, Environment env)
+      throws SkyFunctionException, InterruptedException {
+    RootedPath directory = (RootedPath) skyKey.argument();
+
+    // Is this the root directory? If so, we're in the MAIN repository. This assumes that the main
+    // repository has a WORKSPACE in the root directory, but Bazel will have failed with an error
+    // before this can be called if that is incorrect.
+    if (directory.getRelativePath().equals(PathFragment.EMPTY_FRAGMENT)) {
+      return LocalRepositoryLookupValue.mainRepository();
+    }
+
+    // Does this directory contain a WORKSPACE file?
+    Optional<Boolean> maybeWorkspaceFileExists = maybeGetWorkspaceFileExistence(env, directory);
+    if (!maybeWorkspaceFileExists.isPresent()) {
+      return null;
+    } else if (maybeWorkspaceFileExists.get()) {
+      Optional<LocalRepositoryLookupValue> maybeRepository =
+          maybeCheckWorkspaceForRepository(env, directory);
+      if (!maybeRepository.isPresent()) {
+        return null;
+      }
+      LocalRepositoryLookupValue repository = maybeRepository.get();
+      // If the repository that was discovered doesn't exist, continue recursing.
+      if (repository.exists()) {
+        return repository;
+      }
+    }
+
+    // If we haven't found a repository yet, check the parent directory.
+    RootedPath parentDirectory =
+        RootedPath.toRootedPath(
+            directory.getRoot(), directory.getRelativePath().getParentDirectory());
+    return env.getValue(LocalRepositoryLookupValue.key(parentDirectory));
+  }
+
+  private Optional<Boolean> maybeGetWorkspaceFileExistence(Environment env, RootedPath directory)
+      throws InterruptedException, LocalRepositoryLookupFunctionException {
+    try {
+      RootedPath workspaceRootedFile =
+          RootedPath.toRootedPath(
+              directory.getRoot(),
+              directory
+                  .getRelativePath()
+                  .getChild(PackageLookupValue.BuildFileName.WORKSPACE.getFilename()));
+      FileValue workspaceFileValue =
+          (FileValue)
+              env.getValueOrThrow(
+                  FileValue.key(workspaceRootedFile),
+                  IOException.class,
+                  FileSymlinkException.class,
+                  InconsistentFilesystemException.class);
+      if (workspaceFileValue == null) {
+        return Optional.absent();
+      }
+      return Optional.of(workspaceFileValue.exists());
+    } catch (IOException e) {
+      throw new LocalRepositoryLookupFunctionException(
+          new ErrorDeterminingRepositoryException(
+              "IOException while checking if there is a WORKSPACE file in "
+                  + directory.asPath().getPathString(),
+              e),
+          Transience.PERSISTENT);
+    } catch (FileSymlinkException e) {
+      throw new LocalRepositoryLookupFunctionException(
+          new ErrorDeterminingRepositoryException(
+              "FileSymlinkException while checking if there is a WORKSPACE file in "
+                  + directory.asPath().getPathString(),
+              e),
+          Transience.PERSISTENT);
+    } catch (InconsistentFilesystemException e) {
+      throw new LocalRepositoryLookupFunctionException(
+          new ErrorDeterminingRepositoryException(
+              "InconsistentFilesystemException while checking if there is a WORKSPACE file in "
+                  + directory.asPath().getPathString(),
+              e),
+          Transience.PERSISTENT);
+    }
+  }
+
+  /**
+   * Checks whether the directory exists and is a workspace root. Returns {@link Optional#absent()}
+   * if Skyframe needs to re-run, {@link Optional#of(LocalRepositoryLookupValue)} otherwise.
+   */
+  private Optional<LocalRepositoryLookupValue> maybeCheckWorkspaceForRepository(
+      Environment env, RootedPath directory)
+      throws InterruptedException, LocalRepositoryLookupFunctionException {
+    // Look up the main WORKSPACE file by the external package, to find all repositories.
+    PackageLookupValue externalPackageLookupValue;
+    try {
+      externalPackageLookupValue =
+          (PackageLookupValue)
+              env.getValueOrThrow(
+                  PackageLookupValue.key(Label.EXTERNAL_PACKAGE_IDENTIFIER),
+                  BuildFileNotFoundException.class,
+                  InconsistentFilesystemException.class);
+      if (externalPackageLookupValue == null) {
+        return Optional.absent();
+      }
+    } catch (BuildFileNotFoundException e) {
+      throw new LocalRepositoryLookupFunctionException(
+          new ErrorDeterminingRepositoryException(
+              "BuildFileNotFoundException while loading the //external package", e),
+          Transience.PERSISTENT);
+    } catch (InconsistentFilesystemException e) {
+      throw new LocalRepositoryLookupFunctionException(
+          new ErrorDeterminingRepositoryException(
+              "InconsistentFilesystemException while loading the //external package", e),
+          Transience.PERSISTENT);
+    }
+
+    RootedPath workspacePath =
+        externalPackageLookupValue.getRootedPath(Label.EXTERNAL_PACKAGE_IDENTIFIER);
+
+    SkyKey workspaceKey = WorkspaceFileValue.key(workspacePath);
+    do {
+      WorkspaceFileValue value;
+      try {
+        value =
+            (WorkspaceFileValue)
+                env.getValueOrThrow(
+                    workspaceKey, PackageFunctionException.class, NameConflictException.class);
+        if (value == null) {
+          return Optional.absent();
+        }
+      } catch (PackageFunctionException e) {
+        // TODO(jcater): When WFF is rewritten to not throw a PFE, update this.
+        throw new LocalRepositoryLookupFunctionException(
+            new ErrorDeterminingRepositoryException(
+                "PackageFunctionException while loading the root WORKSPACE file", e),
+            Transience.PERSISTENT);
+      } catch (NameConflictException e) {
+        throw new LocalRepositoryLookupFunctionException(
+            new ErrorDeterminingRepositoryException(
+                "NameConflictException while loading the root WORKSPACE file", e),
+            Transience.PERSISTENT);
+      }
+
+      Package externalPackage = value.getPackage();
+      if (externalPackage.containsErrors()) {
+        Event.replayEventsOn(env.getListener(), externalPackage.getEvents());
+      }
+
+      // Find all local_repository rules in the WORKSPACE, and check if any have a "path" attribute
+      // the same as the requested directory.
+      Iterable<Rule> localRepositories =
+          externalPackage.getRulesMatchingRuleClass(LocalRepositoryRule.NAME);
+      Rule rule =
+          Iterables.find(
+              localRepositories,
+              new Predicate<Rule>() {
+                @Override
+                public boolean apply(@Nullable Rule rule) {
+                  AggregatingAttributeMapper mapper = AggregatingAttributeMapper.of(rule);
+                  PathFragment pathAttr = new PathFragment(mapper.get("path", Type.STRING));
+                  return directory.getRelativePath().equals(pathAttr);
+                }
+              },
+              null);
+      if (rule != null) {
+        try {
+          return Optional.of(
+              LocalRepositoryLookupValue.success(RepositoryName.create("@" + rule.getName())));
+        } catch (LabelSyntaxException e) {
+          // This shouldn't be possible if the rule name is valid, and it should already have been
+          // validated.
+          throw new LocalRepositoryLookupFunctionException(
+              new ErrorDeterminingRepositoryException(
+                  "LabelSyntaxException while creating the repository name from the rule "
+                      + rule.getName(),
+                  e),
+              Transience.PERSISTENT);
+        }
+      }
+      workspaceKey = value.next();
+
+      // TODO(bazel-team): This loop can be quadratic in the number of load() statements, consider
+      // rewriting or unrolling.
+    } while (workspaceKey != null);
+
+    return Optional.of(LocalRepositoryLookupValue.notFound());
+  }
+
+  /**
+   * Used to declare all the exception types that can be wrapped in the exception thrown by {@link
+   * LocalRepositoryLookupFunction#compute}.
+   */
+  private static final class LocalRepositoryLookupFunctionException extends SkyFunctionException {
+    public LocalRepositoryLookupFunctionException(
+        ErrorDeterminingRepositoryException e, Transience transience) {
+      super(e, transience);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupValue.java
new file mode 100644
index 0000000..794dcc3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupValue.java
@@ -0,0 +1,166 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+/**
+ * A value that represents a local repository lookup result.
+ *
+ * <p>Local repository lookups will always produce a value. The {@code #getRepository} method
+ * returns the name of the repository that the directory resides in.
+ */
+public abstract class LocalRepositoryLookupValue implements SkyValue {
+
+  static SkyKey key(RootedPath directory) {
+    return SkyKey.create(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, directory);
+  }
+
+  private static final LocalRepositoryLookupValue MAIN_REPO_VALUE = new MainRepositoryLookupValue();
+  private static final LocalRepositoryLookupValue NOT_FOUND_VALUE =
+      new NotFoundLocalRepositoryLookupValue();
+
+  public static LocalRepositoryLookupValue mainRepository() {
+    return MAIN_REPO_VALUE;
+  }
+
+  public static LocalRepositoryLookupValue success(RepositoryName repositoryName) {
+    return new SuccessfulLocalRepositoryLookupValue(repositoryName);
+  }
+
+  public static LocalRepositoryLookupValue notFound() {
+    return NOT_FOUND_VALUE;
+  }
+
+  /**
+   * Returns {@code true} if the local repository lookup succeeded and the {@link #getRepository}
+   * method will return a useful result.
+   */
+  public abstract boolean exists();
+
+  /**
+   * Returns the {@link RepositoryName} of the local repository contained in the directory which was
+   * looked up, {@link RepositoryName#MAIN} if the directory is part of the main repository, or
+   * throws a {@link IllegalStateException} if there was no repository found.
+   */
+  public abstract RepositoryName getRepository();
+
+  /** Represents a successful lookup of the main repository. */
+  public static final class MainRepositoryLookupValue extends LocalRepositoryLookupValue {
+
+    // This should be a singleton value.
+    private MainRepositoryLookupValue() {}
+
+    @Override
+    public boolean exists() {
+      return true;
+    }
+
+    @Override
+    public RepositoryName getRepository() {
+      return RepositoryName.MAIN;
+    }
+
+    @Override
+    public String toString() {
+      return "MainRepositoryLookupValue";
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      // All MainRepositoryLookupValue instances are equivalent.
+      return obj instanceof MainRepositoryLookupValue;
+    }
+
+    @Override
+    public int hashCode() {
+      return MainRepositoryLookupValue.class.getSimpleName().hashCode();
+    }
+  }
+
+  /** Represents a successful lookup of a local repository. */
+  public static final class SuccessfulLocalRepositoryLookupValue
+      extends LocalRepositoryLookupValue {
+    private final RepositoryName repositoryName;
+
+    public SuccessfulLocalRepositoryLookupValue(RepositoryName repositoryName) {
+      this.repositoryName = repositoryName;
+    }
+
+    @Override
+    public boolean exists() {
+      return true;
+    }
+
+    @Override
+    public RepositoryName getRepository() {
+      return repositoryName;
+    }
+
+    @Override
+    public String toString() {
+      return "SuccessfulLocalRepositoryLookupValue(" + repositoryName + ")";
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (!(obj instanceof SuccessfulLocalRepositoryLookupValue)) {
+        return false;
+      }
+      SuccessfulLocalRepositoryLookupValue other = (SuccessfulLocalRepositoryLookupValue) obj;
+      return repositoryName.equals(other.repositoryName);
+    }
+
+    @Override
+    public int hashCode() {
+      return repositoryName.hashCode();
+    }
+  }
+
+  /** Represents the state where no repository was found, either local or the main repository. */
+  public static final class NotFoundLocalRepositoryLookupValue extends LocalRepositoryLookupValue {
+
+    // This should be a singleton value.
+    private NotFoundLocalRepositoryLookupValue() {}
+
+    @Override
+    public boolean exists() {
+      return false;
+    }
+
+    @Override
+    public RepositoryName getRepository() {
+      throw new IllegalStateException("Repository was not found");
+    }
+
+    @Override
+    public String toString() {
+      return "NotFoundLocalRepositoryLookupValue";
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      // All NotFoundLocalRepositoryLookupValue instances are equivalent.
+      return obj instanceof NotFoundLocalRepositoryLookupValue;
+    }
+
+    @Override
+    public int hashCode() {
+      return NotFoundLocalRepositoryLookupValue.class.getSimpleName().hashCode();
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
index 86545011..331a081 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
@@ -19,10 +19,12 @@
 import com.google.devtools.build.lib.cmdline.LabelValidator;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
+import com.google.devtools.build.lib.packages.ErrorDeterminingRepositoryException;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.skyframe.PackageLookupValue.BuildFileName;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -61,6 +63,7 @@
   public SkyValue compute(SkyKey skyKey, Environment env)
       throws PackageLookupFunctionException, InterruptedException {
     PathPackageLocator pkgLocator = PrecomputedValue.PATH_PACKAGE_LOCATOR.get(env);
+
     PackageIdentifier packageKey = (PackageIdentifier) skyKey.argument();
     if (PackageFunction.isDefaultsPackage(packageKey)) {
       return PackageLookupValue.success(pkgLocator.getPathEntries().get(0), BuildFileName.BUILD);
@@ -149,10 +152,50 @@
       RootedPath buildFileRootedPath = RootedPath.toRootedPath(packagePathEntry,
           buildFileFragment);
 
-      if (crossRepositoryLabelViolationStrategy != CrossRepositoryLabelViolationStrategy.IGNORE) {
-        // TODO(jcater): Check for cross repository package label violations.
+      if (crossRepositoryLabelViolationStrategy == CrossRepositoryLabelViolationStrategy.ERROR) {
+        // Is this path part of a local repository?
+        RootedPath currentPath =
+            RootedPath.toRootedPath(packagePathEntry, buildFileFragment.getParentDirectory());
+        SkyKey repositoryLookupKey = LocalRepositoryLookupValue.key(currentPath);
+
+        // TODO(jcater): Consider parallelizing these lookups.
+        LocalRepositoryLookupValue localRepository;
+        try {
+          localRepository =
+              (LocalRepositoryLookupValue)
+                  env.getValueOrThrow(
+                      repositoryLookupKey, ErrorDeterminingRepositoryException.class);
+          if (localRepository == null) {
+            return null;
+          }
+        } catch (ErrorDeterminingRepositoryException e) {
+          // If the directory selected isn't part of a repository, that's an error.
+          // TODO(katre): Improve the error message given here.
+          throw new PackageLookupFunctionException(
+              new BuildFileNotFoundException(
+                  packageIdentifier,
+                  "Unable to determine the local repository for directory "
+                      + currentPath.asPath().getPathString()),
+              Transience.PERSISTENT);
+        }
+
+        if (localRepository.exists()
+            && !localRepository.getRepository().equals(packageIdentifier.getRepository())) {
+          // There is a repository mismatch, this is an error.
+          // TODO(jcater): Work out the correct package name for this error message.
+          return PackageLookupValue.invalidPackageName(
+              "Package crosses into repository " + localRepository.getRepository().getName());
+        }
+
+        // There's no local repository, keep going.
+      } else {
+        // Future-proof against adding future values to CrossRepositoryLabelViolationStrategy.
+        Preconditions.checkState(
+            crossRepositoryLabelViolationStrategy == CrossRepositoryLabelViolationStrategy.IGNORE,
+            crossRepositoryLabelViolationStrategy);
       }
 
+      // Check for the existence of the build file.
       FileValue fileValue = getFileValue(buildFileRootedPath, env, packageIdentifier);
       if (fileValue == null) {
         return null;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
index a9861b7..8ad5ae0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
@@ -15,7 +15,6 @@
 
 import com.google.common.base.Objects;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.skyframe.PackageLookupValue.BuildFileName;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
index 09dc01b..3e138ad 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
@@ -104,6 +104,8 @@
   public static final SkyFunctionName EXTERNAL_PACKAGE = SkyFunctionName.create("EXTERNAL_PACKAGE");
   public static final SkyFunctionName ACTION_TEMPLATE_EXPANSION =
       SkyFunctionName.create("ACTION_TEMPLATE_EXPANSION");
+  public static final SkyFunctionName LOCAL_REPOSITORY_LOOKUP =
+      SkyFunctionName.create("LOCAL_REPOSITORY_LOOKUP");
 
   public static Predicate<SkyKey> isSkyFunction(final SkyFunctionName functionName) {
     return new Predicate<SkyKey>() {
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 146c468..39cf8c8 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
@@ -417,6 +417,7 @@
         new RecursiveFilesystemTraversalFunction());
     map.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction());
     map.put(SkyFunctions.ACTION_TEMPLATE_EXPANSION, new ActionTemplateExpansionFunction());
+    map.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
     map.putAll(extraSkyFunctions);
     return map.build();
   }
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 201e8fc..d97c034 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
@@ -19,7 +19,6 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-
 import java.io.Serializable;
 import java.util.Objects;
 
@@ -75,6 +74,11 @@
     }
 
     @Override
+    public String toString() {
+      return importLabel + (inWorkspace ? " (in workspace)" : "");
+    }
+
+    @Override
     public boolean equals(Object obj) {
       if (this == obj) {
         return true;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
index 87ec20c..faacb3c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileFunction.java
@@ -110,7 +110,11 @@
         return null;
       }
       parser.execute(ast, importResult.importMap);
-    } catch (PackageFunctionException | NameConflictException e) {
+    } catch (PackageFunctionException e) {
+      // TODO(jcater): Unwrap the PackageFunctionException and handle the underlying error.
+      // PFE shouldn't be exposed to callers.
+      throw new WorkspaceFileFunctionException(e, Transience.PERSISTENT);
+    } catch (NameConflictException e) {
       throw new WorkspaceFileFunctionException(e, Transience.PERSISTENT);
     }
 
@@ -129,12 +133,12 @@
   }
 
   private static final class WorkspaceFileFunctionException extends SkyFunctionException {
-    public WorkspaceFileFunctionException(Exception e, Transience transience) {
+    public WorkspaceFileFunctionException(PackageFunctionException e, Transience transience) {
       super(e, transience);
     }
 
-    public WorkspaceFileFunctionException(Exception e) {
-      super(e, Transience.PERSISTENT);
+    public WorkspaceFileFunctionException(NameConflictException e, Transience transience) {
+      super(e, transience);
     }
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
index ea1fc81..fa5f891 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupFunctionTest.java
@@ -77,6 +77,11 @@
     skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(
         new AtomicReference<TimestampGranularityMonitor>(), externalFilesHelper));
     skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
+    skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
+    skyFunctions.put(
+        SkyFunctions.DIRECTORY_LISTING_STATE,
+        new DirectoryListingStateFunction(externalFilesHelper));
+    skyFunctions.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
     RecordingDifferencer differencer = new RecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
index 131dbbb..6de849a 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileFunctionTest.java
@@ -157,6 +157,7 @@
                             TestRuleClassProvider.getRuleClassProvider(), fs),
                         directories))
                 .put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction())
+                .put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction())
                 .build(),
             differencer);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
index 3b66ae1..e030cef 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunctionTest.java
@@ -105,6 +105,7 @@
     skyFunctions.put(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES,
         new BlacklistedPackagePrefixesFunction());
     skyFunctions.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction());
+    skyFunctions.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
 
     differencer = new RecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
index 0209343..4ee3a8e 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
@@ -144,6 +144,11 @@
         new FileStateFunction(
             new AtomicReference<TimestampGranularityMonitor>(), externalFilesHelper));
     skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
+    skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
+    skyFunctions.put(
+        SkyFunctions.DIRECTORY_LISTING_STATE,
+        new DirectoryListingStateFunction(externalFilesHelper));
+    skyFunctions.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
     return skyFunctions;
   }
 
@@ -692,7 +697,7 @@
     assertGlobMatches("symlinks/*.txt", "symlinks/existing.txt");
   }
 
-  private class CustomInMemoryFs extends InMemoryFileSystem {
+  private static final class CustomInMemoryFs extends InMemoryFileSystem {
 
     private Map<Path, FileStatus> stubbedStats = Maps.newHashMap();
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
new file mode 100644
index 0000000..d4b51bb
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupFunctionTest.java
@@ -0,0 +1,235 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.skyframe;
+
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.skyframe.EvaluationResultSubjectFactory.assertThatEvaluationResult;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.analysis.util.AnalysisMock;
+import com.google.devtools.build.lib.bazel.rules.BazelRulesModule;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.packages.RuleClassProvider;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.skyframe.ExternalFilesHelper.ExternalFileAction;
+import com.google.devtools.build.lib.skyframe.PackageLookupFunction.CrossRepositoryLabelViolationStrategy;
+import com.google.devtools.build.lib.testutil.FoundationTestCase;
+import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.EvaluationResult;
+import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
+import com.google.devtools.build.skyframe.MemoizingEvaluator;
+import com.google.devtools.build.skyframe.RecordingDifferencer;
+import com.google.devtools.build.skyframe.SequentialBuildDriver;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicReference;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link LocalRepositoryLookupFunction}. */
+@RunWith(JUnit4.class)
+public class LocalRepositoryLookupFunctionTest extends FoundationTestCase {
+  private AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages;
+  private MemoizingEvaluator evaluator;
+  private SequentialBuildDriver driver;
+  private RecordingDifferencer differencer;
+
+  @Before
+  public final void setUp() throws Exception {
+    AnalysisMock analysisMock = AnalysisMock.get();
+    AtomicReference<PathPackageLocator> pkgLocator =
+        new AtomicReference<>(new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)));
+    deletedPackages = new AtomicReference<>(ImmutableSet.<PackageIdentifier>of());
+    BlazeDirectories directories =
+        new BlazeDirectories(
+            rootDirectory, outputBase, rootDirectory, analysisMock.getProductName());
+    ExternalFilesHelper externalFilesHelper = new ExternalFilesHelper(
+        pkgLocator, ExternalFileAction.DEPEND_ON_EXTERNAL_PKG_FOR_EXTERNAL_REPO_PATHS, directories);
+
+    Map<SkyFunctionName, SkyFunction> skyFunctions = new HashMap<>();
+    skyFunctions.put(
+        SkyFunctions.PACKAGE_LOOKUP,
+        new PackageLookupFunction(deletedPackages, CrossRepositoryLabelViolationStrategy.ERROR));
+    skyFunctions.put(
+        SkyFunctions.FILE_STATE,
+        new FileStateFunction(
+            new AtomicReference<TimestampGranularityMonitor>(), externalFilesHelper));
+    skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
+    skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
+    skyFunctions.put(
+        SkyFunctions.DIRECTORY_LISTING_STATE,
+        new DirectoryListingStateFunction(externalFilesHelper));
+    RuleClassProvider ruleClassProvider = analysisMock.createRuleClassProvider();
+    skyFunctions.put(SkyFunctions.WORKSPACE_AST, new WorkspaceASTFunction(ruleClassProvider));
+    skyFunctions.put(
+        SkyFunctions.WORKSPACE_FILE,
+        new WorkspaceFileFunction(
+            ruleClassProvider,
+            analysisMock
+                .getPackageFactoryForTesting()
+                .create(
+                    ruleClassProvider,
+                    new BazelRulesModule().getPackageEnvironmentExtension(),
+                    scratch.getFileSystem()),
+            directories));
+    skyFunctions.put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction());
+    skyFunctions.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
+    skyFunctions.put(
+        SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, new FileSymlinkCycleUniquenessFunction());
+
+    differencer = new RecordingDifferencer();
+    evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
+    driver = new SequentialBuildDriver(evaluator);
+    PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
+  }
+
+  private SkyKey createKey(RootedPath directory) {
+    return LocalRepositoryLookupValue.key(directory);
+  }
+
+  private LocalRepositoryLookupValue lookupDirectory(RootedPath directory)
+      throws InterruptedException {
+    SkyKey key = createKey(directory);
+    return lookupDirectory(key).get(key);
+  }
+
+  private EvaluationResult<LocalRepositoryLookupValue> lookupDirectory(SkyKey directoryKey)
+      throws InterruptedException {
+    return driver.<LocalRepositoryLookupValue>evaluate(
+        ImmutableList.of(directoryKey),
+        false,
+        SkyframeExecutor.DEFAULT_THREAD_COUNT,
+        NullEventHandler.INSTANCE);
+  }
+
+  @Test
+  public void testNoPath() throws Exception {
+    LocalRepositoryLookupValue repositoryLookupValue =
+        lookupDirectory(RootedPath.toRootedPath(rootDirectory, PathFragment.EMPTY_FRAGMENT));
+    assertThat(repositoryLookupValue).isNotNull();
+    assertThat(repositoryLookupValue.getRepository()).isEqualTo(RepositoryName.MAIN);
+  }
+
+  @Test
+  public void testActualPackage() throws Exception {
+    scratch.file("some/path/BUILD");
+
+    LocalRepositoryLookupValue repositoryLookupValue =
+        lookupDirectory(RootedPath.toRootedPath(rootDirectory, new PathFragment("some/path")));
+    assertThat(repositoryLookupValue).isNotNull();
+    assertThat(repositoryLookupValue.getRepository()).isEqualTo(RepositoryName.MAIN);
+  }
+
+  @Test
+  public void testLocalRepository() throws Exception {
+    scratch.overwriteFile("WORKSPACE", "local_repository(name='local', path='local/repo')");
+    scratch.file("local/repo/WORKSPACE");
+    scratch.file("local/repo/BUILD");
+
+    LocalRepositoryLookupValue repositoryLookupValue =
+        lookupDirectory(RootedPath.toRootedPath(rootDirectory, new PathFragment("local/repo")));
+    assertThat(repositoryLookupValue).isNotNull();
+    assertThat(repositoryLookupValue.getRepository().getName()).isEqualTo("@local");
+  }
+
+  @Test
+  public void testLocalRepositorySubPackage() throws Exception {
+    scratch.overwriteFile("WORKSPACE", "local_repository(name='local', path='local/repo')");
+    scratch.file("local/repo/WORKSPACE");
+    scratch.file("local/repo/BUILD");
+    scratch.file("local/repo/sub/package/BUILD");
+
+    LocalRepositoryLookupValue repositoryLookupValue =
+        lookupDirectory(
+            RootedPath.toRootedPath(rootDirectory, new PathFragment("local/repo/sub/package")));
+    assertThat(repositoryLookupValue).isNotNull();
+    assertThat(repositoryLookupValue.getRepository().getName()).isEqualTo("@local");
+  }
+
+  @Test
+  public void testWorkspaceButNoLocalRepository() throws Exception {
+    scratch.overwriteFile("WORKSPACE", "");
+    scratch.file("local/repo/WORKSPACE");
+    scratch.file("local/repo/BUILD");
+
+    LocalRepositoryLookupValue repositoryLookupValue =
+        lookupDirectory(RootedPath.toRootedPath(rootDirectory, new PathFragment("local/repo")));
+    assertThat(repositoryLookupValue).isNotNull();
+    assertThat(repositoryLookupValue.getRepository()).isEqualTo(RepositoryName.MAIN);
+  }
+
+  @Test
+  public void testLocalRepository_LocalWorkspace_SymlinkCycle() throws Exception {
+    scratch.overwriteFile("WORKSPACE", "local_repository(name='local', path='local/repo')");
+    Path localRepoWorkspace = scratch.resolve("local/repo/WORKSPACE");
+    Path localRepoWorkspaceLink = scratch.resolve("local/repo/WORKSPACE.link");
+    FileSystemUtils.createDirectoryAndParents(localRepoWorkspace.getParentDirectory());
+    FileSystemUtils.createDirectoryAndParents(localRepoWorkspaceLink.getParentDirectory());
+    localRepoWorkspace.createSymbolicLink(localRepoWorkspaceLink);
+    localRepoWorkspaceLink.createSymbolicLink(localRepoWorkspace);
+    scratch.file("local/repo/BUILD");
+
+    SkyKey localRepositoryKey =
+        createKey(RootedPath.toRootedPath(rootDirectory, new PathFragment("local/repo")));
+    EvaluationResult<LocalRepositoryLookupValue> result = lookupDirectory(localRepositoryKey);
+
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(localRepositoryKey)
+        .hasExceptionThat()
+        .hasMessage(
+            "FileSymlinkException while checking if there is a WORKSPACE file in "
+                + "/workspace/local/repo");
+  }
+
+  @Test
+  public void testLocalRepository_MainWorkspace_NotFound() throws Exception {
+    // Do not add a local_repository to WORKSPACE.
+    scratch.overwriteFile("WORKSPACE", "");
+    scratch.deleteFile("WORKSPACE");
+    scratch.file("local/repo/WORKSPACE");
+    scratch.file("local/repo/BUILD");
+
+    LocalRepositoryLookupValue repositoryLookupValue =
+        lookupDirectory(RootedPath.toRootedPath(rootDirectory, new PathFragment("local/repo")));
+    assertThat(repositoryLookupValue).isNotNull();
+    // In this case, the repository should be MAIN as we can't find any local_repository rules.
+    assertThat(repositoryLookupValue.getRepository()).isEqualTo(RepositoryName.MAIN);
+  }
+
+  // TODO(katre): Add tests for the following exceptions
+  // While reading dir/WORKSPACE:
+  // - IOException
+  // - FileSymlinkException
+  // - InconsistentFilesystemException
+  // While loading //external
+  // - BuildFileNotFoundException
+  // - InconsistentFilesystemException
+  // While reading //external:WORKSPACE
+  // - PackageFunctionException
+  // - NameConflictException
+  // - WorkspaceFileException
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
index 40bebb7..a8ead28 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageLookupFunctionTest.java
@@ -14,12 +14,14 @@
 
 package com.google.devtools.build.lib.skyframe;
 
+import static com.google.devtools.build.skyframe.EvaluationResultSubjectFactory.assertThatEvaluationResult;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
@@ -27,17 +29,25 @@
 import com.google.devtools.build.lib.bazel.rules.BazelRulesModule;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.events.NullEventHandler;
+import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.rules.repository.LocalRepositoryFunction;
+import com.google.devtools.build.lib.rules.repository.LocalRepositoryRule;
+import com.google.devtools.build.lib.rules.repository.RepositoryDelegatorFunction;
+import com.google.devtools.build.lib.rules.repository.RepositoryFunction;
+import com.google.devtools.build.lib.rules.repository.RepositoryLoaderFunction;
 import com.google.devtools.build.lib.skyframe.ExternalFilesHelper.ExternalFileAction;
 import com.google.devtools.build.lib.skyframe.PackageLookupFunction.CrossRepositoryLabelViolationStrategy;
 import com.google.devtools.build.lib.skyframe.PackageLookupValue.BuildFileName;
 import com.google.devtools.build.lib.skyframe.PackageLookupValue.ErrorReason;
 import com.google.devtools.build.lib.testutil.FoundationTestCase;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
@@ -48,6 +58,7 @@
 import java.util.HashMap;
 import java.util.Map;
 import java.util.UUID;
+import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicReference;
 import org.junit.Before;
 import org.junit.Test;
@@ -88,6 +99,10 @@
     skyFunctions.put(SkyFunctions.FILE_STATE, new FileStateFunction(
         new AtomicReference<TimestampGranularityMonitor>(), externalFilesHelper));
     skyFunctions.put(SkyFunctions.FILE, new FileFunction(pkgLocator));
+    skyFunctions.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
+    skyFunctions.put(
+        SkyFunctions.DIRECTORY_LISTING_STATE,
+        new DirectoryListingStateFunction(externalFilesHelper));
     skyFunctions.put(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES,
         new BlacklistedPackagePrefixesFunction());
     RuleClassProvider ruleClassProvider = analysisMock.createRuleClassProvider();
@@ -104,6 +119,17 @@
                     scratch.getFileSystem()),
             directories));
     skyFunctions.put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction());
+    skyFunctions.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
+    skyFunctions.put(
+        SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, new FileSymlinkCycleUniquenessFunction());
+
+    ImmutableMap<String, RepositoryFunction> repositoryHandlers =
+        ImmutableMap.of(LocalRepositoryRule.NAME, new LocalRepositoryFunction());
+    skyFunctions.put(
+        SkyFunctions.REPOSITORY_DIRECTORY,
+        new RepositoryDelegatorFunction(repositoryHandlers, null, new AtomicBoolean(true)));
+    skyFunctions.put(SkyFunctions.REPOSITORY, new RepositoryLoaderFunction());
+
     differencer = new RecordingDifferencer();
     evaluator = new InMemoryMemoizingEvaluator(skyFunctions, differencer);
     driver = new SequentialBuildDriver(evaluator);
@@ -111,18 +137,26 @@
     PrecomputedValue.PATH_PACKAGE_LOCATOR.set(differencer, pkgLocator.get());
     PrecomputedValue.BLACKLISTED_PACKAGE_PREFIXES_FILE.set(
         differencer, PathFragment.EMPTY_FRAGMENT);
+    PrecomputedValue.BLAZE_DIRECTORIES.set(differencer, directories);
   }
 
-  private PackageLookupValue lookupPackage(String packageName) throws InterruptedException {
+  protected PackageLookupValue lookupPackage(String packageName) throws InterruptedException {
     return lookupPackage(PackageIdentifier.createInMainRepo(packageName));
   }
 
-  private PackageLookupValue lookupPackage(PackageIdentifier packageId)
+  protected PackageLookupValue lookupPackage(PackageIdentifier packageId)
       throws InterruptedException {
     SkyKey key = PackageLookupValue.key(packageId);
+    return lookupPackage(key).get(key);
+  }
+
+  protected EvaluationResult<PackageLookupValue> lookupPackage(SkyKey packageIdentifierSkyKey)
+      throws InterruptedException {
     return driver.<PackageLookupValue>evaluate(
-        ImmutableList.of(key), false, SkyframeExecutor.DEFAULT_THREAD_COUNT,
-        NullEventHandler.INSTANCE).get(key);
+        ImmutableList.of(packageIdentifierSkyKey),
+        false,
+        SkyframeExecutor.DEFAULT_THREAD_COUNT,
+        NullEventHandler.INSTANCE);
   }
 
   @Test
@@ -256,35 +290,83 @@
         .testEquals();
   }
 
+  protected void createAndCheckInvalidPackageLabel(boolean expectedPackageExists) throws Exception {
+    scratch.overwriteFile("WORKSPACE", "local_repository(name='local', path='local/repo')");
+    scratch.file("local/repo/WORKSPACE");
+    scratch.file("local/repo/BUILD");
+
+    // First, use the correct label.
+    PackageLookupValue packageLookupValue =
+        lookupPackage(PackageIdentifier.create("@local", PathFragment.EMPTY_FRAGMENT));
+    assertTrue(packageLookupValue.packageExists());
+
+    // Then, use the incorrect label.
+    packageLookupValue = lookupPackage(PackageIdentifier.createInMainRepo("local/repo"));
+    assertEquals(expectedPackageExists, packageLookupValue.packageExists());
+  }
+
   /**
-   * Runs all tests in the base {@link PackageLookupFunctionTest} class with the
-   * {@link CrossRepositoryLabelViolationStrategy#IGNORE} enum set, and also additional tests
-   * specific to that setting.
+   * Runs all tests in the base {@link PackageLookupFunctionTest} class with the {@link
+   * CrossRepositoryLabelViolationStrategy#IGNORE} enum set, and also additional tests specific to
+   * that setting.
    */
   @RunWith(JUnit4.class)
-  public static class IgnoreLabelViolationsTest
-      extends PackageLookupFunctionTest {
+  public static class IgnoreLabelViolationsTest extends PackageLookupFunctionTest {
     @Override
     protected CrossRepositoryLabelViolationStrategy crossRepositoryLabelViolationStrategy() {
       return CrossRepositoryLabelViolationStrategy.IGNORE;
     }
 
     // Add any ignore-specific tests here.
+
+    @Test
+    public void testInvalidPackageLabelIsIgnored() throws Exception {
+      createAndCheckInvalidPackageLabel(true);
+    }
   }
 
   /**
-   * Runs all tests in the base {@link PackageLookupFunctionTest} class with the
-   * {@link CrossRepositoryLabelViolationStrategy#ERROR} enum set, and also additional tests
-   * specific to that setting.
+   * Runs all tests in the base {@link PackageLookupFunctionTest} class with the {@link
+   * CrossRepositoryLabelViolationStrategy#ERROR} enum set, and also additional tests specific to
+   * that setting.
    */
   @RunWith(JUnit4.class)
-  public static class ErrorLabelViolationsTest
-      extends PackageLookupFunctionTest {
+  public static class ErrorLabelViolationsTest extends PackageLookupFunctionTest {
     @Override
     protected CrossRepositoryLabelViolationStrategy crossRepositoryLabelViolationStrategy() {
       return CrossRepositoryLabelViolationStrategy.ERROR;
     }
 
     // Add any error-specific tests here.
+
+    @Test
+    public void testInvalidPackageLabelIsError() throws Exception {
+      createAndCheckInvalidPackageLabel(false);
+    }
+
+    @Test
+    public void testSymlinkCycleInWorkspace() throws Exception {
+      scratch.overwriteFile("WORKSPACE", "local_repository(name='local', path='local/repo')");
+      Path localRepoWorkspace = scratch.resolve("local/repo/WORKSPACE");
+      Path localRepoWorkspaceLink = scratch.resolve("local/repo/WORKSPACE.link");
+      FileSystemUtils.createDirectoryAndParents(localRepoWorkspace.getParentDirectory());
+      FileSystemUtils.createDirectoryAndParents(localRepoWorkspaceLink.getParentDirectory());
+      localRepoWorkspace.createSymbolicLink(localRepoWorkspaceLink);
+      localRepoWorkspaceLink.createSymbolicLink(localRepoWorkspace);
+      scratch.file("local/repo/BUILD");
+
+      SkyKey skyKey = PackageLookupValue.key(PackageIdentifier.createInMainRepo("local/repo"));
+      EvaluationResult<PackageLookupValue> result = lookupPackage(skyKey);
+      assertThatEvaluationResult(result)
+          .hasErrorEntryForKeyThat(skyKey)
+          .hasExceptionThat()
+          .isInstanceOf(BuildFileNotFoundException.class);
+      assertThatEvaluationResult(result)
+          .hasErrorEntryForKeyThat(skyKey)
+          .hasExceptionThat()
+          .hasMessage(
+              "no such package 'local/repo': Unable to determine the local repository for "
+                  + "directory /workspace/local/repo");
+    }
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
index b769b6d..58b31e7 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
@@ -120,6 +120,7 @@
                 .create(ruleClassProvider, scratch.getFileSystem()),
             directories));
     skyFunctions.put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction());
+    skyFunctions.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
 
     progressReceiver = new RecordingEvaluationProgressReceiver();
     differencer = new RecordingDifferencer();
diff --git a/src/test/shell/bazel/BUILD b/src/test/shell/bazel/BUILD
index 241577a..9ffd05d 100644
--- a/src/test/shell/bazel/BUILD
+++ b/src/test/shell/bazel/BUILD
@@ -202,6 +202,13 @@
 )
 
 sh_test(
+    name = "cross_repository_test",
+    size = "large",
+    srcs = ["cross_repository_test.sh"],
+    data = [":test-deps"],
+)
+
+sh_test(
     name = "external_skylark_load_test",
     size = "large",
     srcs = ["external_skylark_load_test.sh"],
diff --git a/src/test/shell/bazel/cross_repository_test.sh b/src/test/shell/bazel/cross_repository_test.sh
new file mode 100755
index 0000000..b484437
--- /dev/null
+++ b/src/test/shell/bazel/cross_repository_test.sh
@@ -0,0 +1,241 @@
+#!/bin/bash
+#
+# Copyright 2016 The Bazel Authors. All rights reserved.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#    http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+# Tests for package labels that cross repository boundaries
+# Includes regression tests for #1592.
+#
+
+# Load the test setup defined in the parent directory
+CURRENT_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
+source "${CURRENT_DIR}/../integration_test_setup.sh" \
+  || { echo "integration_test_setup.sh not found!" >&2; exit 1; }
+
+function write_rule {
+  name=$1
+  shift
+  srcs=""
+  for src in "$@"; do
+    srcs="\"$src\", $srcs"
+  done
+
+  cat <<EOF
+genrule(
+  name = "$name",
+  srcs = [
+    $srcs
+  ],
+  outs = ["$name.out"],
+  cmd = "echo $name > \$@",
+  visibility = ["//visibility:public"],
+)
+EOF
+}
+
+# Basic use case: Define a repository nested in the main repository, check
+# correct targets are visible
+function test_basic_cross_repo_targets {
+  cat > WORKSPACE <<EOF
+local_repository(
+    name = "bar",
+    path = "bar",
+)
+EOF
+
+  write_rule depend_via_repo "@bar//:bar" >> BUILD
+  write_rule depend_via_repo_subdir "@bar//subbar:subbar" >> BUILD
+  write_rule depend_directly "//bar:bar" >> BUILD
+  write_rule depend_directly_subdir "//bar/subbar:subbar" >> BUILD
+
+  mkdir -p bar
+  touch bar/WORKSPACE
+  write_rule bar >> bar/BUILD
+  mkdir -p bar/subbar
+  write_rule subbar >> bar/subbar/BUILD
+
+  # These should succeed, they use the correct label.
+  bazel build //:depend_via_repo || fail "build should succeed"
+  bazel build //:depend_via_repo_subdir || fail "build should succeed"
+
+  # These should fail, they is using the wrong label that crosses the
+  # repository boundary.
+  bazel build //:depend_directly >& $TEST_log && fail "build should fail"
+  expect_log "no such package 'bar': Package crosses into repository @bar"
+  bazel build //:depend_directly_subdir >& $TEST_log && fail "build should fail"
+  expect_log "no such package 'bar/subbar': Package crosses into repository @bar"
+}
+
+function test_top_level_local_repository {
+  cat > WORKSPACE <<EOF
+local_repository(
+    name = "loc",
+    path = ".",
+)
+EOF
+
+  write_rule foo >> BUILD
+
+  # These should succeed, they use the correct label.
+  bazel build //:foo || fail "build should succeed"
+  bazel build @loc//:foo || fail "build should succeed"
+}
+
+# Loading rules.
+function test_workspace_loads_rules {
+  cat > WORKSPACE <<EOF
+load("//baz:rules.bzl", "baz_rule")
+local_repository(
+    name = "bar",
+    path = "bar",
+)
+EOF
+
+  write_rule depend_via_repo "@bar//:bar" >> BUILD
+  write_rule depend_directly "//bar:bar" >> BUILD
+
+  mkdir -p bar
+  touch bar/WORKSPACE
+  write_rule bar >> bar/BUILD
+
+  mkdir -p baz
+  touch baz/BUILD
+  cat > baz/rules.bzl <<EOF
+baz_rule = 'baz_rule'
+EOF
+
+  # This should succeed, it uses the correct label.
+  bazel build //:depend_via_repo || fail "build should succeed"
+
+  # This should fail, it is using the wrong label that crosses the repository
+  # boundary.
+  bazel build //:depend_directly >& $TEST_log && fail "build should fail"
+  expect_log "no such package 'bar': Package crosses into repository @bar"
+}
+
+# Load rules via an invalid label.
+function test_workspace_loads_rules_failure {
+  cat > WORKSPACE <<EOF
+load("//bar:rules.bzl", "bar_rule")
+local_repository(
+    name = "bar",
+    path = "bar",
+)
+EOF
+
+  write_rule depend_via_repo "@bar//:bar" >> BUILD
+
+  mkdir -p bar
+  touch bar/WORKSPACE
+  write_rule bar >> bar/BUILD
+  cat > bar/rules.bzl <<EOF
+bar_rule = 'bar_rule'
+EOF
+
+  # This should fail in workspace parsing.
+  bazel build //:depend_via_repo >& $TEST_log && fail "build should fail"
+  # TODO(jcater): Show a better error when this occurs
+  #expect_log "no such package 'bar': Package crosses into repository @bar"
+  # This is the current error shown.
+  expect_log "cycles detected"
+}
+
+function test_top_level_local_repository {
+  cat > WORKSPACE <<EOF
+local_repository(
+    name = "loc",
+    path = ".",
+)
+EOF
+
+  write_rule foo >> BUILD
+
+  # These should succeed, they use the correct label.
+  bazel build //:foo || fail "build should succeed"
+  bazel build @loc//:foo || fail "build should succeed"
+}
+
+function test_incremental_add_repository {
+  # Empty workspace, defines no local_repository.
+  cat > WORKSPACE
+
+  mkdir -p bar
+  write_rule bar >> bar/BUILD
+  mkdir -p bar/subbar
+  write_rule subbar >> bar/subbar/BUILD
+
+  bazel query //bar/... >& $TEST_log || fail "query should succeed"
+
+  # Now add the local_repository and WORKSPACE.
+  cat > WORKSPACE <<EOF
+local_repository(
+    name = "bar",
+    path = "bar",
+)
+EOF
+  touch bar/WORKSPACE
+
+  # These should now fail, using the incorrect label.
+  bazel query //bar:bar >& $TEST_log && fail "build should fail"
+  expect_log "no such package 'bar': Package crosses into repository @bar"
+  bazel query //bar/subbar:subbar >& $TEST_log && fail "build should fail"
+  expect_log "no such package 'bar/subbar': Package crosses into repository @bar"
+
+  # These should succeed.
+  echo "about to test @bar//"
+  bazel query @bar//:bar || fail "query should succeed"
+  bazel query @bar//subbar:subbar || fail "query should succeed"
+}
+
+function test_incremental_remove_repository {
+  # Add the local_repository and WORKSPACE.
+  cat > WORKSPACE <<EOF
+local_repository(
+    name = "bar",
+    path = "bar",
+)
+EOF
+  mkdir -p bar
+  touch bar/WORKSPACE
+  write_rule bar >> bar/BUILD
+  mkdir -p bar/subbar
+  write_rule subbar >> bar/subbar/BUILD
+
+  # These should succeed.
+  echo "about to test @bar//"
+  bazel query @bar//:bar || fail "query should succeed"
+  bazel query @bar//subbar:subbar || fail "query should succeed"
+
+  # Now remove the workspace and the local_repository.
+  cat > WORKSPACE
+  rm bar/WORKSPACE
+
+  # These should now succeed.
+  bazel query //bar:bar || fail "query should succeed"
+  bazel query //bar/subbar:subbar || fail "query should succeed"
+
+
+  # These should now fail.
+  bazel query @bar//:bar >& $TEST_log && fail "build should fail"
+  expect_log "no such package '@bar//':.*The repository named 'bar' could not be resolved"
+  bazel query @bar//subbar:subbar >& $TEST_log && fail "build should fail"
+  expect_log "no such package '@bar//subbar':.*The repository named 'bar' could not be resolved"
+}
+
+# TODO(katre): Add tests to verify incremental package reloads are necessary and correct.
+# - /WORKSPACE edited, rule not changed - no reload
+# - /WORKSPACE not edited, /dir/WORKSPACE added or removed - only packages in
+#   /dir invalidated and re-loaded
+
+run_suite "cross-repository tests"