diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
index cef2a10..9ac363d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
@@ -54,11 +54,6 @@
     }
 
     @Override
-    protected CollectPackagesUnderDirectoryValue getEmptyReturn() {
-      return CollectPackagesUnderDirectoryValue.EMPTY;
-    }
-
-    @Override
     protected MyVisitor getInitialVisitor() {
       return new MyVisitor();
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageFunction.java
new file mode 100644
index 0000000..7a085c4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageFunction.java
@@ -0,0 +1,77 @@
+// 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.Function;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.pkgcache.TargetPatternResolverUtil;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionException;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import javax.annotation.Nullable;
+
+/**
+ * Declares a dependency on all targets in a package, to ensure those targets are in the graph. Does
+ * no error-checking on the package id provided, so callers should have already verified that there
+ * is a package with this id.
+ */
+class CollectTargetsInPackageFunction implements SkyFunction {
+  @Nullable
+  @Override
+  public SkyValue compute(SkyKey skyKey, Environment env)
+      throws SkyFunctionException, InterruptedException {
+    CollectTargetsInPackageValue.CollectTargetsInPackageKey argument =
+        (CollectTargetsInPackageValue.CollectTargetsInPackageKey) skyKey.argument();
+    PackageIdentifier packageId = argument.getPackageId();
+    PackageValue packageValue = (PackageValue) env.getValue(PackageValue.key(packageId));
+    if (env.valuesMissing()) {
+      return null;
+    }
+    Package pkg = packageValue.getPackage();
+    if (pkg.containsErrors()) {
+      env.getListener()
+          .handle(
+              Event.error(
+                  "package contains errors: " + packageId.getPackageFragment().getPathString()));
+    }
+    env.getValues(
+        Iterables.transform(
+            TargetPatternResolverUtil.resolvePackageTargets(pkg, argument.getFilteringPolicy())
+                .getTargets(),
+            TO_TRANSITIVE_TRAVERSAL_KEY));
+    if (env.valuesMissing()) {
+      return null;
+    }
+    return CollectTargetsInPackageValue.INSTANCE;
+  }
+
+  private static final Function<Target, SkyKey> TO_TRANSITIVE_TRAVERSAL_KEY =
+      new Function<Target, SkyKey>() {
+        @Override
+        public SkyKey apply(Target target) {
+          return TransitiveTraversalValue.key(target.getLabel());
+        }
+      };
+
+  @Nullable
+  @Override
+  public String extractTag(SkyKey skyKey) {
+    return null;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageValue.java
new file mode 100644
index 0000000..4809ae1
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageValue.java
@@ -0,0 +1,51 @@
+// 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.auto.value.AutoValue;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+/** Singleton result of {@link CollectTargetsInPackageFunction}. */
+public class CollectTargetsInPackageValue implements SkyValue {
+  public static final CollectTargetsInPackageValue INSTANCE = new CollectTargetsInPackageValue();
+
+  private CollectTargetsInPackageValue() {}
+
+  /**
+   * Creates a key for evaluation of {@link CollectTargetsInPackageFunction}. See that class's
+   * comment for what callers should have done beforehand.
+   */
+  static SkyKey key(PackageIdentifier packageId, FilteringPolicy filteringPolicy) {
+    return SkyKey.create(
+        SkyFunctions.COLLECT_TARGETS_IN_PACKAGE,
+        CollectTargetsInPackageKey.create(packageId, filteringPolicy));
+  }
+
+  /** {@link SkyKey} argument. */
+  @AutoValue
+  public abstract static class CollectTargetsInPackageKey {
+    public static CollectTargetsInPackageKey create(
+        PackageIdentifier packageId, FilteringPolicy filteringPolicy) {
+      return new AutoValue_CollectTargetsInPackageValue_CollectTargetsInPackageKey(
+          packageId, filteringPolicy);
+    }
+
+    public abstract PackageIdentifier getPackageId();
+
+    public abstract FilteringPolicy getFilteringPolicy();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
index 568b623..780254b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
@@ -15,24 +15,19 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
-import com.google.devtools.build.lib.packages.NoSuchTargetException;
-import com.google.devtools.build.lib.packages.Package;
-import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
-import com.google.devtools.build.lib.pkgcache.TargetPatternResolverUtil;
 import com.google.devtools.build.lib.skyframe.PrepareDepsOfTargetsUnderDirectoryValue.PrepareDepsOfTargetsUnderDirectoryKey;
 import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
-import com.google.devtools.build.lib.util.Preconditions;
 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.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.util.Map;
 import javax.annotation.Nullable;
 
 /**
@@ -43,7 +38,7 @@
 public class PrepareDepsOfTargetsUnderDirectoryFunction implements SkyFunction {
   private final BlazeDirectories directories;
 
-  public PrepareDepsOfTargetsUnderDirectoryFunction(BlazeDirectories directories) {
+  PrepareDepsOfTargetsUnderDirectoryFunction(BlazeDirectories directories) {
     this.directories = directories;
   }
 
@@ -51,70 +46,50 @@
   public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
     PrepareDepsOfTargetsUnderDirectoryKey argument =
         (PrepareDepsOfTargetsUnderDirectoryKey) skyKey.argument();
-    FilteringPolicy filteringPolicy = argument.getFilteringPolicy();
+    final FilteringPolicy filteringPolicy = argument.getFilteringPolicy();
     RecursivePkgKey recursivePkgKey = argument.getRecursivePkgKey();
-    return new MyTraversalFunction(filteringPolicy).visitDirectory(recursivePkgKey, env);
-  }
-
-  private class MyTraversalFunction
-      extends RecursiveDirectoryTraversalFunction<
-          MyVisitor, PrepareDepsOfTargetsUnderDirectoryValue> {
-    private final FilteringPolicy filteringPolicy;
-
-    private MyTraversalFunction(FilteringPolicy filteringPolicy) {
-      super(directories);
-      this.filteringPolicy = filteringPolicy;
+    ProcessPackageDirectory processPackageDirectory =
+        new ProcessPackageDirectory(
+            directories,
+            new ProcessPackageDirectory.SkyKeyTransformer() {
+              @Override
+              public SkyKey makeSkyKey(
+                  RepositoryName repository,
+                  RootedPath subdirectory,
+                  ImmutableSet<PathFragment> excludedSubdirectoriesBeneathSubdirectory) {
+                return PrepareDepsOfTargetsUnderDirectoryValue.key(
+                    repository,
+                    subdirectory,
+                    excludedSubdirectoriesBeneathSubdirectory,
+                    filteringPolicy);
+              }
+            });
+    ProcessPackageDirectoryResult packageExistenceAndSubdirDeps =
+        processPackageDirectory.getPackageExistenceAndSubdirDeps(
+            recursivePkgKey.getRootedPath(),
+            recursivePkgKey.getRepository(),
+            env,
+            recursivePkgKey.getExcludedPaths());
+    if (env.valuesMissing()) {
+      return null;
     }
-
-    @Override
-    protected PrepareDepsOfTargetsUnderDirectoryValue getEmptyReturn() {
-      return PrepareDepsOfTargetsUnderDirectoryValue.INSTANCE;
+    Iterable<SkyKey> keysToRequest = packageExistenceAndSubdirDeps.getChildDeps();
+    if (packageExistenceAndSubdirDeps.packageExists()) {
+      keysToRequest =
+          Iterables.concat(
+              ImmutableList.of(
+                  CollectTargetsInPackageValue.key(
+                      PackageIdentifier.create(
+                          recursivePkgKey.getRepository(),
+                          recursivePkgKey.getRootedPath().getRelativePath()),
+                      filteringPolicy)),
+              keysToRequest);
     }
-
-    @Override
-    protected MyVisitor getInitialVisitor() {
-      return new MyVisitor(filteringPolicy);
+    env.getValuesOrThrow(keysToRequest, NoSuchPackageException.class);
+    if (env.valuesMissing()) {
+      return null;
     }
-
-    @Override
-    protected SkyKey getSkyKeyForSubdirectory(
-        RepositoryName repository,
-        RootedPath subdirectory,
-        ImmutableSet<PathFragment> excludedSubdirectoriesBeneathSubdirectory) {
-      return PrepareDepsOfTargetsUnderDirectoryValue.key(
-          repository, subdirectory, excludedSubdirectoriesBeneathSubdirectory, filteringPolicy);
-    }
-
-    @Override
-    protected PrepareDepsOfTargetsUnderDirectoryValue aggregateWithSubdirectorySkyValues(
-        MyVisitor visitor, Map<SkyKey, SkyValue> subdirectorySkyValues) {
-      return PrepareDepsOfTargetsUnderDirectoryValue.INSTANCE;
-    }
-  }
-
-  private static class MyVisitor implements RecursiveDirectoryTraversalFunction.Visitor {
-    private final FilteringPolicy filteringPolicy;
-
-    private MyVisitor(FilteringPolicy filteringPolicy) {
-      this.filteringPolicy = Preconditions.checkNotNull(filteringPolicy);
-    }
-
-    @Override
-    public void visitPackageValue(Package pkg, Environment env) throws InterruptedException {
-      loadTransitiveTargets(env, pkg, filteringPolicy);
-    }
-  }
-
-  private static void loadTransitiveTargets(
-      Environment env, Package pkg, FilteringPolicy filteringPolicy) throws InterruptedException {
-    ResolvedTargets<Target> packageTargets =
-        TargetPatternResolverUtil.resolvePackageTargets(pkg, filteringPolicy);
-    ImmutableList.Builder<SkyKey> builder = ImmutableList.builder();
-    for (Target target : packageTargets.getTargets()) {
-      builder.add(TransitiveTraversalValue.key(target.getLabel()));
-    }
-    ImmutableList<SkyKey> skyKeys = builder.build();
-    env.getValuesOrThrow(skyKeys, NoSuchPackageException.class, NoSuchTargetException.class);
+    return PrepareDepsOfTargetsUnderDirectoryValue.INSTANCE;
   }
 
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ProcessPackageDirectory.java b/src/main/java/com/google/devtools/build/lib/skyframe/ProcessPackageDirectory.java
new file mode 100644
index 0000000..d6c5ff0
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ProcessPackageDirectory.java
@@ -0,0 +1,252 @@
+// 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.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.Dirent;
+import com.google.devtools.build.lib.vfs.Dirent.Type;
+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.SkyFunction;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.ValueOrException4;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import javax.annotation.Nullable;
+
+/**
+ * Processes a directory that may contain a package and subdirectories for the benefit of processes
+ * that traverse directories recursively, looking for packages.
+ */
+public class ProcessPackageDirectory {
+  private static final String SENTINEL_FILE_NAME_FOR_NOT_TRAVERSING_SYMLINKS =
+      "DONT_FOLLOW_SYMLINKS_WHEN_TRAVERSING_THIS_DIRECTORY_VIA_A_RECURSIVE_TARGET_PATTERN";
+
+  interface SkyKeyTransformer {
+    SkyKey makeSkyKey(
+        RepositoryName repository,
+        RootedPath subdirectory,
+        ImmutableSet<PathFragment> excludedSubdirectoriesBeneathSubdirectory);
+  }
+
+  private final BlazeDirectories directories;
+  private final SkyKeyTransformer skyKeyTransformer;
+
+  ProcessPackageDirectory(BlazeDirectories directories, SkyKeyTransformer skyKeyTransformer) {
+    this.directories = directories;
+    this.skyKeyTransformer = skyKeyTransformer;
+  }
+
+  /**
+   * Examines {@code rootedPath} to see if it is the location of a package, and to see if it has any
+   * subdirectory children that should also be examined. Returns a {@link
+   * ProcessPackageDirectoryResult}, or {@code null} if required dependencies were missing.
+   */
+  @Nullable
+  ProcessPackageDirectoryResult getPackageExistenceAndSubdirDeps(
+      RootedPath rootedPath,
+      RepositoryName repositoryName,
+      SkyFunction.Environment env,
+      Set<PathFragment> excludedPaths)
+      throws InterruptedException {
+    PathFragment rootRelativePath = rootedPath.getRelativePath();
+
+    SkyKey fileKey = FileValue.key(rootedPath);
+    FileValue fileValue;
+    try {
+      fileValue =
+          (FileValue)
+              env.getValueOrThrow(
+                  fileKey,
+                  InconsistentFilesystemException.class,
+                  FileSymlinkException.class,
+                  IOException.class);
+    } catch (InconsistentFilesystemException | FileSymlinkException | IOException e) {
+      return reportErrorAndReturn(
+          "Failed to get information about path", e, rootRelativePath, env.getListener());
+    }
+    if (env.valuesMissing()) {
+      return null;
+    }
+
+    if (!fileValue.isDirectory()) {
+      return ProcessPackageDirectoryResult.EMPTY_RESULT;
+    }
+
+    PackageIdentifier packageId = PackageIdentifier.create(repositoryName, rootRelativePath);
+
+    if ((packageId.getRepository().isDefault() || packageId.getRepository().isMain())
+        && fileValue.isSymlink()
+        && fileValue
+            .getUnresolvedLinkTarget()
+            .startsWith(directories.getOutputBase().asFragment())) {
+      // Symlinks back to the output base are not traversed so that we avoid convenience symlinks.
+      // Note that it's not enough to just check for the convenience symlinks themselves, because
+      // if the value of --symlink_prefix changes, the old symlinks are left in place. This
+      // algorithm also covers more creative use cases where people create convenience symlinks
+      // somewhere in the directory tree manually.
+      return ProcessPackageDirectoryResult.EMPTY_RESULT;
+    }
+
+    SkyKey pkgLookupKey = PackageLookupValue.key(packageId);
+    SkyKey dirListingKey = DirectoryListingValue.key(rootedPath);
+    Map<
+            SkyKey,
+            ValueOrException4<
+                NoSuchPackageException, InconsistentFilesystemException, FileSymlinkException,
+                IOException>>
+        pkgLookupAndDirectoryListingDeps =
+            env.getValuesOrThrow(
+                ImmutableList.of(pkgLookupKey, dirListingKey),
+                NoSuchPackageException.class,
+                InconsistentFilesystemException.class,
+                FileSymlinkException.class,
+                IOException.class);
+    if (env.valuesMissing()) {
+      return null;
+    }
+    PackageLookupValue pkgLookupValue;
+    try {
+      pkgLookupValue =
+          (PackageLookupValue)
+              Preconditions.checkNotNull(
+                  pkgLookupAndDirectoryListingDeps.get(pkgLookupKey).get(),
+                  "%s %s %s",
+                  rootedPath,
+                  repositoryName,
+                  pkgLookupKey);
+    } catch (NoSuchPackageException | InconsistentFilesystemException e) {
+      return reportErrorAndReturn("Failed to load package", e, rootRelativePath, env.getListener());
+    } catch (IOException | FileSymlinkException e) {
+      throw new IllegalStateException(e);
+    }
+    DirectoryListingValue dirListingValue;
+    try {
+      dirListingValue =
+          (DirectoryListingValue)
+              Preconditions.checkNotNull(
+                  pkgLookupAndDirectoryListingDeps.get(dirListingKey).get(),
+                  "%s %s %s",
+                  rootedPath,
+                  repositoryName,
+                  dirListingKey);
+    } catch (InconsistentFilesystemException | IOException e) {
+      return reportErrorAndReturn(
+          "Failed to list directory contents", e, rootRelativePath, env.getListener());
+    } catch (FileSymlinkException e) {
+      // DirectoryListingFunction only throws FileSymlinkCycleException when FileFunction throws it,
+      // but FileFunction was evaluated for rootedPath above, and didn't throw there. It shouldn't
+      // be able to avoid throwing there but throw here.
+      throw new IllegalStateException(
+          "Symlink cycle found after not being found for \"" + rootedPath + "\"");
+    } catch (NoSuchPackageException e) {
+      throw new IllegalStateException(e);
+    }
+    return new ProcessPackageDirectoryResult(
+        pkgLookupValue.packageExists() && pkgLookupValue.getRoot().equals(rootedPath.getRoot()),
+        getSubdirDeps(dirListingValue, rootedPath, repositoryName, excludedPaths));
+  }
+
+  private Iterable<SkyKey> getSubdirDeps(
+      DirectoryListingValue dirListingValue,
+      RootedPath rootedPath,
+      RepositoryName repositoryName,
+      Set<PathFragment> excludedPaths) {
+    Path root = rootedPath.getRoot();
+    PathFragment rootRelativePath = rootedPath.getRelativePath();
+    boolean followSymlinks = shouldFollowSymlinksWhenTraversing(dirListingValue.getDirents());
+    List<SkyKey> childDeps = new ArrayList<>();
+    for (Dirent dirent : dirListingValue.getDirents()) {
+      Type type = dirent.getType();
+      if (type != Type.DIRECTORY && (type != Type.SYMLINK || !followSymlinks)) {
+        // Non-directories can never host packages. Symlinks to non-directories are weeded out at
+        // the next level of recursion when we check if its FileValue is a directory. This is slower
+        // if there are a lot of symlinks in the tree, but faster if there are only a few, which is
+        // the case most of the time.
+        //
+        // We are not afraid of weird symlink structure here: both cyclical ones and ones that give
+        // rise to infinite directory trees are diagnosed by FileValue.
+        continue;
+      }
+      String basename = dirent.getName();
+      if (rootRelativePath.equals(PathFragment.EMPTY_FRAGMENT)
+          && PathPackageLocator.DEFAULT_TOP_LEVEL_EXCLUDES.contains(basename)) {
+        continue;
+      }
+      PathFragment subdirectory = rootRelativePath.getRelative(basename);
+
+      // If this subdirectory is one of the excluded paths, don't recurse into it.
+      if (excludedPaths.contains(subdirectory)) {
+        continue;
+      }
+
+      // If we have an excluded path that isn't below this subdirectory, we shouldn't pass that
+      // excluded path to our evaluation of the subdirectory, because the exclusion can't
+      // possibly match anything beneath the subdirectory.
+      //
+      // For example, if we're currently evaluating directory "a", are looking at its subdirectory
+      // "a/b", and we have an excluded path "a/c/d", there's no need to pass the excluded path
+      // "a/c/d" to our evaluation of "a/b".
+      //
+      // This strategy should help to get more skyframe sharing. Consider the example above. A
+      // subsequent request of "a/b/...", without any excluded paths, will be a cache hit.
+      //
+      // TODO(bazel-team): Replace the excludedPaths set with a trie or a SortedSet for better
+      // efficiency.
+      ImmutableSet<PathFragment> excludedSubdirectoriesBeneathThisSubdirectory =
+          PathFragment.filterPathsStartingWith(excludedPaths, subdirectory);
+      RootedPath subdirectoryRootedPath = RootedPath.toRootedPath(root, subdirectory);
+      childDeps.add(
+          skyKeyTransformer.makeSkyKey(
+              repositoryName,
+              subdirectoryRootedPath,
+              excludedSubdirectoriesBeneathThisSubdirectory));
+    }
+    return childDeps;
+  }
+
+  private static ProcessPackageDirectoryResult reportErrorAndReturn(
+      String errorPrefix, Exception e, PathFragment rootRelativePath, EventHandler handler) {
+    handler.handle(
+        Event.warn(errorPrefix + ", for " + rootRelativePath + ", skipping: " + e.getMessage()));
+    return ProcessPackageDirectoryResult.EMPTY_RESULT;
+  }
+
+  private static boolean shouldFollowSymlinksWhenTraversing(Dirents dirents) {
+    for (Dirent dirent : dirents) {
+      // This is a special sentinel file whose existence tells Blaze not to follow symlinks when
+      // recursively traversing through this directory.
+      //
+      // This admittedly ugly feature is used to support workspaces with directories with weird
+      // symlink structures that aren't intended to be consumed by Blaze.
+      if (dirent.getName().equals(SENTINEL_FILE_NAME_FOR_NOT_TRAVERSING_SYMLINKS)) {
+        return false;
+      }
+    }
+    return true;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ProcessPackageDirectoryResult.java b/src/main/java/com/google/devtools/build/lib/skyframe/ProcessPackageDirectoryResult.java
new file mode 100644
index 0000000..3f0fb54
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ProcessPackageDirectoryResult.java
@@ -0,0 +1,38 @@
+// 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.collect.ImmutableList;
+import com.google.devtools.build.skyframe.SkyKey;
+
+/** Result of {@link ProcessPackageDirectory#getPackageExistenceAndSubdirDeps}. */
+class ProcessPackageDirectoryResult {
+  static final ProcessPackageDirectoryResult EMPTY_RESULT =
+      new ProcessPackageDirectoryResult(false, ImmutableList.<SkyKey>of());
+  private final boolean packageExists;
+  private final Iterable<SkyKey> childDeps;
+
+  ProcessPackageDirectoryResult(boolean packageExists, Iterable<SkyKey> childDeps) {
+    this.packageExists = packageExists;
+    this.childDeps = childDeps;
+  }
+
+  boolean packageExists() {
+    return packageExists;
+  }
+
+  Iterable<SkyKey> getChildDeps() {
+    return childDeps;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
index 4c66e8f..a7491d5f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
@@ -23,25 +23,15 @@
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.Package;
-import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
-import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.lib.vfs.Dirent;
-import com.google.devtools.build.lib.vfs.Dirent.Type;
-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.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.ValueOrException;
-import com.google.devtools.build.skyframe.ValueOrException4;
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.List;
 import java.util.Map;
 
 /**
@@ -54,19 +44,25 @@
   private static final String SENTINEL_FILE_NAME_FOR_NOT_TRAVERSING_SYMLINKS =
       "DONT_FOLLOW_SYMLINKS_WHEN_TRAVERSING_THIS_DIRECTORY_VIA_A_RECURSIVE_TARGET_PATTERN";
 
-  private final BlazeDirectories directories;
+  private final ProcessPackageDirectory processPackageDirectory;
 
   protected RecursiveDirectoryTraversalFunction(BlazeDirectories directories) {
-    this.directories = directories;
+    this.processPackageDirectory =
+        new ProcessPackageDirectory(
+            directories,
+            new ProcessPackageDirectory.SkyKeyTransformer() {
+              @Override
+              public SkyKey makeSkyKey(
+                  RepositoryName repository,
+                  RootedPath subdirectory,
+                  ImmutableSet<PathFragment> excludedSubdirectoriesBeneathSubdirectory) {
+                return getSkyKeyForSubdirectory(
+                    repository, subdirectory, excludedSubdirectoriesBeneathSubdirectory);
+              }
+            });
   }
 
   /**
-   * Returned from {@link #visitDirectory} if its {@code recursivePkgKey} is a symlink or not a
-   * directory, or if a dependency value lookup returns an error.
-   */
-  protected abstract TReturn getEmptyReturn();
-
-  /**
    * Called by {@link #visitDirectory}, which will next call {@link Visitor#visitPackageValue} if
    * the {@code recursivePkgKey} specifies a directory with a package, and which will lastly be
    * provided to {@link #aggregateWithSubdirectorySkyValues} to compute the {@code TReturn} value
@@ -125,139 +121,23 @@
   TReturn visitDirectory(RecursivePkgKey recursivePkgKey, Environment env)
       throws InterruptedException {
     RootedPath rootedPath = recursivePkgKey.getRootedPath();
-    ImmutableSet<PathFragment> excludedPaths = recursivePkgKey.getExcludedPaths();
-    Path root = rootedPath.getRoot();
-    PathFragment rootRelativePath = rootedPath.getRelativePath();
-
-    SkyKey fileKey = FileValue.key(rootedPath);
-    FileValue fileValue;
-    try {
-      fileValue = (FileValue) env.getValueOrThrow(fileKey, InconsistentFilesystemException.class,
-          FileSymlinkException.class, IOException.class);
-    } catch (InconsistentFilesystemException | FileSymlinkException | IOException e) {
-      return reportErrorAndReturn("Failed to get information about path", e, rootRelativePath,
-          env.getListener());
-    }
-    if (fileValue == null) {
-      return null;
-    }
-
-    if (!fileValue.isDirectory()) {
-      return getEmptyReturn();
-    }
-
-    PackageIdentifier packageId = PackageIdentifier.create(
-        recursivePkgKey.getRepository(), rootRelativePath);
-
-    if ((packageId.getRepository().isDefault() || packageId.getRepository().isMain())
-      && fileValue.isSymlink()
-      && fileValue.getUnresolvedLinkTarget().startsWith(directories.getOutputBase().asFragment())) {
-      // Symlinks back to the output base are not traversed so that we avoid convenience symlinks.
-      // Note that it's not enough to just check for the convenience symlinks themselves, because
-      // if the value of --symlink_prefix changes, the old symlinks are left in place. This
-      // algorithm also covers more creative use cases where people create convenience symlinks
-      // somewhere in the directory tree manually.
-      return getEmptyReturn();
-    }
-
-    SkyKey pkgLookupKey = PackageLookupValue.key(packageId);
-    SkyKey dirListingKey = DirectoryListingValue.key(rootedPath);
-    Map<SkyKey,
-        ValueOrException4<
-            NoSuchPackageException,
-            InconsistentFilesystemException,
-            FileSymlinkException,
-            IOException>> pkgLookupAndDirectoryListingDeps = env.getValuesOrThrow(
-                ImmutableList.of(pkgLookupKey, dirListingKey),
-                NoSuchPackageException.class,
-                InconsistentFilesystemException.class,
-                FileSymlinkException.class,
-                IOException.class);
+    ProcessPackageDirectoryResult packageExistenceAndSubdirDeps =
+        processPackageDirectory.getPackageExistenceAndSubdirDeps(
+            rootedPath, recursivePkgKey.getRepository(), env, recursivePkgKey.getExcludedPaths());
     if (env.valuesMissing()) {
       return null;
     }
-    PackageLookupValue pkgLookupValue;
-    try {
-      pkgLookupValue = (PackageLookupValue) Preconditions.checkNotNull(
-          pkgLookupAndDirectoryListingDeps.get(pkgLookupKey).get(), "%s %s", recursivePkgKey,
-          pkgLookupKey);
-    } catch (NoSuchPackageException | InconsistentFilesystemException e) {
-      return reportErrorAndReturn("Failed to load package", e, rootRelativePath,
-          env.getListener());
-    } catch (IOException | FileSymlinkException e) {
-      throw new IllegalStateException(e);
-    }
+
+    Iterable<SkyKey> childDeps = packageExistenceAndSubdirDeps.getChildDeps();
 
     TVisitor visitor = getInitialVisitor();
 
-    DirectoryListingValue dirListingValue;
-    try {
-      dirListingValue = (DirectoryListingValue) Preconditions.checkNotNull(
-          pkgLookupAndDirectoryListingDeps.get(dirListingKey).get(), "%s %s", recursivePkgKey,
-          dirListingKey);
-    } catch (InconsistentFilesystemException | IOException e) {
-      return reportErrorAndReturn("Failed to list directory contents", e, rootRelativePath,
-          env.getListener());
-    } catch (FileSymlinkException e) {
-      // DirectoryListingFunction only throws FileSymlinkCycleException when FileFunction throws it,
-      // but FileFunction was evaluated for rootedPath above, and didn't throw there. It shouldn't
-      // be able to avoid throwing there but throw here.
-      throw new IllegalStateException("Symlink cycle found after not being found for \""
-          + rootedPath + "\"");
-    } catch (NoSuchPackageException e) {
-      throw new IllegalStateException(e);
-    }
-
-    boolean followSymlinks = shouldFollowSymlinksWhenTraversing(dirListingValue.getDirents());
-    List<SkyKey> childDeps = new ArrayList<>();
-    for (Dirent dirent : dirListingValue.getDirents()) {
-      Type type = dirent.getType();
-      if (type != Type.DIRECTORY
-          && (type != Type.SYMLINK || (type == Type.SYMLINK && !followSymlinks))) {
-        // Non-directories can never host packages. Symlinks to non-directories are weeded out at
-        // the next level of recursion when we check if its FileValue is a directory. This is slower
-        // if there are a lot of symlinks in the tree, but faster if there are only a few, which is
-        // the case most of the time.
-        //
-        // We are not afraid of weird symlink structure here: both cyclical ones and ones that give
-        // rise to infinite directory trees are diagnosed by FileValue.
-        continue;
-      }
-      String basename = dirent.getName();
-      if (rootRelativePath.equals(PathFragment.EMPTY_FRAGMENT)
-          && PathPackageLocator.DEFAULT_TOP_LEVEL_EXCLUDES.contains(basename)) {
-        continue;
-      }
-      PathFragment subdirectory = rootRelativePath.getRelative(basename);
-
-      // If this subdirectory is one of the excluded paths, don't recurse into it.
-      if (excludedPaths.contains(subdirectory)) {
-        continue;
-      }
-
-      // If we have an excluded path that isn't below this subdirectory, we shouldn't pass that
-      // excluded path to our evaluation of the subdirectory, because the exclusion can't
-      // possibly match anything beneath the subdirectory.
-      //
-      // For example, if we're currently evaluating directory "a", are looking at its subdirectory
-      // "a/b", and we have an excluded path "a/c/d", there's no need to pass the excluded path
-      // "a/c/d" to our evaluation of "a/b".
-      //
-      // This strategy should help to get more skyframe sharing. Consider the example above. A
-      // subsequent request of "a/b/...", without any excluded paths, will be a cache hit.
-      //
-      // TODO(bazel-team): Replace the excludedPaths set with a trie or a SortedSet for better
-      // efficiency.
-      ImmutableSet<PathFragment> excludedSubdirectoriesBeneathThisSubdirectory =
-          PathFragment.filterPathsStartingWith(excludedPaths, subdirectory);
-      RootedPath subdirectoryRootedPath = RootedPath.toRootedPath(root, subdirectory);
-      childDeps.add(getSkyKeyForSubdirectory(recursivePkgKey.getRepository(),
-          subdirectoryRootedPath, excludedSubdirectoriesBeneathThisSubdirectory));
-    }
-
     Map<SkyKey, SkyValue> subdirectorySkyValues;
-    if (pkgLookupValue.packageExists() && pkgLookupValue.getRoot().equals(root)) {
-      SkyKey packageKey = PackageValue.key(packageId);
+    if (packageExistenceAndSubdirDeps.packageExists()) {
+      PathFragment rootRelativePath = rootedPath.getRelativePath();
+      SkyKey packageKey =
+          PackageValue.key(
+              PackageIdentifier.create(recursivePkgKey.getRepository(), rootRelativePath));
       Map<SkyKey, ValueOrException<NoSuchPackageException>> dependentSkyValues =
           env.getValuesOrThrow(
               Iterables.concat(childDeps, ImmutableList.of(packageKey)),
@@ -307,26 +187,4 @@
     }
     return aggregateWithSubdirectorySkyValues(visitor, subdirectorySkyValues);
   }
-
-  private static boolean shouldFollowSymlinksWhenTraversing(Dirents dirents) {
-    for (Dirent dirent : dirents) {
-      // This is a special sentinel file whose existence tells Blaze not to follow symlinks when
-      // recursively traversing through this directory.
-      //
-      // This admittedly ugly feature is used to support workspaces with directories with weird
-      // symlink structures that aren't intended to be consumed by Blaze.
-      if (dirent.getName().equals(SENTINEL_FILE_NAME_FOR_NOT_TRAVERSING_SYMLINKS)) {
-        return false;
-      }
-    }
-    return true;
-  }
-
-  // Ignore all errors in traversal and return an empty value.
-  private TReturn reportErrorAndReturn(String errorPrefix, Exception e,
-      PathFragment rootRelativePath, EventHandler handler) {
-    handler.handle(Event.warn(errorPrefix + ", for " + rootRelativePath
-        + ", skipping: " + e.getMessage()));
-    return getEmptyReturn();
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
index 9b97b4b..95cc59b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
@@ -58,11 +58,6 @@
     }
 
     @Override
-    protected RecursivePkgValue getEmptyReturn() {
-      return RecursivePkgValue.EMPTY;
-    }
-
-    @Override
     protected MyVisitor getInitialVisitor() {
       return new MyVisitor();
     }
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 a7b7224..09dc01b 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
@@ -40,8 +40,6 @@
   public static final SkyFunctionName AST_FILE_LOOKUP = SkyFunctionName.create("AST_FILE_LOOKUP");
   public static final SkyFunctionName SKYLARK_IMPORTS_LOOKUP =
       SkyFunctionName.create("SKYLARK_IMPORTS_LOOKUP");
-  public static final SkyFunctionName SKYLARK_IMPORT_CYCLE =
-      SkyFunctionName.create("SKYLARK_IMPORT_CYCLE");
   public static final SkyFunctionName GLOB = SkyFunctionName.create("GLOB");
   public static final SkyFunctionName PACKAGE = SkyFunctionName.create("PACKAGE");
   public static final SkyFunctionName PACKAGE_ERROR = SkyFunctionName.create("PACKAGE_ERROR");
@@ -53,6 +51,8 @@
       SkyFunctionName.create("PREPARE_DEPS_OF_PATTERN");
   public static final SkyFunctionName PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY =
       SkyFunctionName.create("PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY");
+  public static final SkyFunctionName COLLECT_TARGETS_IN_PACKAGE =
+      SkyFunctionName.create("COLLECT_TARGETS_IN_PACKAGE");
   public static final SkyFunctionName COLLECT_PACKAGES_UNDER_DIRECTORY =
       SkyFunctionName.create("COLLECT_PACKAGES_UNDER_DIRECTORY");
   public static final SkyFunctionName BLACKLISTED_PACKAGE_PREFIXES =
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 90f28ea..93e3323 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
@@ -346,7 +346,6 @@
     map.put(
         SkyFunctions.SKYLARK_IMPORTS_LOOKUP,
         newSkylarkImportLookupFunction(ruleClassProvider, pkgFactory));
-    map.put(SkyFunctions.SKYLARK_IMPORT_CYCLE, new SkylarkImportUniqueCycleFunction());
     map.put(SkyFunctions.GLOB, newGlobFunction());
     map.put(SkyFunctions.TARGET_PATTERN, new TargetPatternFunction());
     map.put(SkyFunctions.PREPARE_DEPS_OF_PATTERNS, new PrepareDepsOfPatternsFunction());
@@ -354,6 +353,7 @@
     map.put(
         SkyFunctions.PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY,
         new PrepareDepsOfTargetsUnderDirectoryFunction(directories));
+    map.put(SkyFunctions.COLLECT_TARGETS_IN_PACKAGE, new CollectTargetsInPackageFunction());
     map.put(
         SkyFunctions.COLLECT_PACKAGES_UNDER_DIRECTORY,
         new CollectPackagesUnderDirectoryFunction(directories));
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 8e64132..fb68cb2 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
@@ -168,10 +168,7 @@
         ImmutableList<Label> cycle =
             CycleUtils.splitIntoPathAndChain(Predicates.equalTo(fileLabel), alreadyVisited.keySet())
                 .second;
-        if (env.getValue(SkylarkImportUniqueCycleFunction.key(cycle)) == null) {
-          return null;
-        }
-        throw new SkylarkImportFailedException("Skylark import cycle");
+        throw new SkylarkImportFailedException("Skylark import cycle: " + cycle);
       }
       alreadyVisited.put(fileLabel, null);
       skylarkImportMap = Maps.newHashMapWithExpectedSize(imports.size());
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
deleted file mode 100644
index bb5ff30..0000000
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportUniqueCycleFunction.java
+++ /dev/null
@@ -1,49 +0,0 @@
-// Copyright 2015 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.collect.ImmutableList;
-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<Label> {
-
-  static SkyKey key(ImmutableList<Label> cycle) {
-    return ChainUniquenessUtils.key(SkyFunctions.SKYLARK_IMPORT_CYCLE, cycle);
-  }
-
-  @Override
-  protected String getConciseDescription() {
-    return "cycle in referenced extension files";
-  }
-
-  @Override
-  protected String getHeaderMessage() {
-    return "";
-  }
-
-  @Override
-  protected String getFooterMessage() {
-    return "";
-  }
-
-  @Override
-  protected String elementToString(Label importLabel) {
-    return importLabel.toString();
-  }
-}
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
index dc08c01..f8c326f 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
@@ -1116,12 +1116,11 @@
       } catch (BuildFileContainsErrorsException e) {
         // This is expected
       }
-      assertContainsEvent("cycle in referenced extension files");
       assertContainsEvent("test/skylark:ext1.bzl");
       assertContainsEvent("test/skylark:ext2.bzl");
       assertContainsEvent("Skylark import cycle");
       assertContainsEvent("Loading of target '//test/skylark:rule' failed; build aborted");
-      assertThat(eventCollector).hasSize(2);
+      assertThat(eventCollector).hasSize(1);
     }
   }
 }