Generalize some of methods in TargetPattern, PrepareDepsOfPatternValue, and RecursivePackageProvider dealing with the concept of "excluded directories".

RELNOTES: None
PiperOrigin-RevId: 163074794

13 files changed, 377 insertions, 193 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
index be3bcaa55f..43f77c8089 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
@@ -143,19 +143,32 @@ public abstract class TargetPattern implements Serializable {
   }
 
   /**
-   * Evaluates the current target pattern, excluding targets under directories in
-   * {@code excludedSubdirectories}, and returns the result.
+   * Evaluates the current target pattern, excluding targets under directories in both
+   * {@code blacklistedSubdirectories} and {@code excludedSubdirectories}, and returns the result.
    *
-   * @throws IllegalArgumentException if {@code excludedSubdirectories} is nonempty and this
-   *      pattern does not have type {@code Type.TARGETS_BELOW_DIRECTORY}.
+   * @throws IllegalArgumentException if either {@code blacklistedSubdirectories} or
+   *      {@code excludedSubdirectories} is nonempty and this pattern does not have type
+   *      {@code Type.TARGETS_BELOW_DIRECTORY}.
    */
   public abstract <T, E extends Exception> void eval(
       TargetPatternResolver<T> resolver,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       BatchCallback<T, E> callback,
       Class<E> exceptionClass)
       throws TargetParsingException, E, InterruptedException;
 
+  protected void assertBlacklistedAndExcludedSubdirectoriesEmpty(
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories) {
+    Preconditions.checkArgument(blacklistedSubdirectories.isEmpty(),
+        "Target pattern %s of type %s cannot be evaluated with blacklisted subdirectories: %s.",
+        getOriginalPattern(), getType(), blacklistedSubdirectories);
+    Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
+        "Target pattern %s of type %s cannot be evaluated with excluded subdirectories: %s.",
+        getOriginalPattern(), getType(), excludedSubdirectories);
+  }
+
   /**
    * Evaluates this {@link TargetPattern} synchronously, feeding the result to the given
    * {@code callback}, and then returns an appropriate immediate {@link ListenableFuture}.
@@ -166,11 +179,12 @@ public abstract class TargetPattern implements Serializable {
    */
   public final <T, E extends Exception> ListenableFuture<Void> evalAdaptedForAsync(
       TargetPatternResolver<T> resolver,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       ThreadSafeBatchCallback<T, E> callback,
       Class<E> exceptionClass) {
     try {
-      eval(resolver, excludedSubdirectories, callback, exceptionClass);
+      eval(resolver, blacklistedSubdirectories, excludedSubdirectories, callback, exceptionClass);
       return Futures.immediateFuture(null);
     } catch (TargetParsingException e) {
       return Futures.immediateFailedFuture(e);
@@ -194,11 +208,13 @@ public abstract class TargetPattern implements Serializable {
    */
   public <T, E extends Exception> ListenableFuture<Void> evalAsync(
       TargetPatternResolver<T> resolver,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       ThreadSafeBatchCallback<T, E> callback,
       Class<E> exceptionClass,
       ListeningExecutorService executor) {
-    return evalAdaptedForAsync(resolver, excludedSubdirectories, callback, exceptionClass);
+    return evalAdaptedForAsync(
+        resolver, blacklistedSubdirectories, excludedSubdirectories, callback, exceptionClass);
   }
 
   /**
@@ -210,19 +226,45 @@ public abstract class TargetPattern implements Serializable {
    */
   public abstract boolean containsAllTransitiveSubdirectoriesForTBD(PackageIdentifier directory);
 
+  /** A tristate return value for {@link #containsTBDForTBD}. */
+  public enum ContainsTBDForTBDResult {
+    /**
+     * Evaluating this TBD pattern with a directory exclusion of the other TBD pattern's directory
+     * would result in exactly the same set of targets as evaluating the subtraction of the other
+     * TBD pattern from this one.
+     */
+    DIRECTORY_EXCLUSION_WOULD_BE_EXACT,
+    /**
+     * A directory exclusion of the other TBD pattern's directory would be too broad because this
+     * TBD pattern is not "rules only" and the other one is, meaning that this TBD pattern
+     * potentially matches more targets underneath the directory in question than the other one
+     * does. Thus, a directory exclusion would incorrectly exclude non-rule targets.
+     */
+    DIRECTORY_EXCLUSION_WOULD_BE_TOO_BROAD,
+    /**
+     * None of the above. Perhaps the other pattern isn't a TBD pattern or perhaps it's not
+     * contained by this pattern.
+     */
+    OTHER,
+  }
+
   /**
-   * Returns {@code true} iff both this pattern and {@code containedPattern} have type
-   * {@code Type.TARGETS_BELOW_DIRECTORY} and the directory in question for {@code containedPattern}
-   * is underneath the directory in question for this pattern.
-   *
-   * <p>That is, when this method returns {@code true} it means every target matched by
-   * {@code containedPattern} is also matched by this pattern.
+   * Determines how, if it all, the evaluation of this TBD pattern with a directory exclusion of the
+   * given TBD {@containedPattern}'s directory relates to the evaluation of the subtraction of the
+   * given {@link containedPattern} from this one.
    */
-  public boolean containsDirectoryOfTBDForTBD(TargetPattern containedPattern) {
-    return containedPattern.getType() != Type.TARGETS_BELOW_DIRECTORY
-      ? false
-      : containsAllTransitiveSubdirectoriesForTBD(
-          containedPattern.getDirectoryForTargetsUnderDirectory());
+  public ContainsTBDForTBDResult containsTBDForTBD(TargetPattern containedPattern) {
+    if (containedPattern.getType() != Type.TARGETS_BELOW_DIRECTORY) {
+      return ContainsTBDForTBDResult.OTHER;
+    } else if (containsAllTransitiveSubdirectoriesForTBD(
+        containedPattern.getDirectoryForTargetsUnderDirectory())) {
+      return !getRulesOnly() && containedPattern.getRulesOnly()
+          ? ContainsTBDForTBDResult.DIRECTORY_EXCLUSION_WOULD_BE_TOO_BROAD
+          : ContainsTBDForTBDResult.DIRECTORY_EXCLUSION_WOULD_BE_EXACT;
+    } else {
+      return ContainsTBDForTBDResult.OTHER;
+    }
+
   }
 
   /**
@@ -282,12 +324,12 @@ public abstract class TargetPattern implements Serializable {
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback,
         Class<E> exceptionClass) throws TargetParsingException, E, InterruptedException {
-      Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
-          "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
-          getOriginalPattern(), getType(), excludedSubdirectories);
+      assertBlacklistedAndExcludedSubdirectoriesEmpty(
+          blacklistedSubdirectories, excludedSubdirectories);
       callback.process(resolver.getExplicitTarget(label(targetName)).getTargets());
     }
 
@@ -336,12 +378,12 @@ public abstract class TargetPattern implements Serializable {
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback, Class<E> exceptionClass)
         throws TargetParsingException, E, InterruptedException {
-      Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
-          "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
-          getOriginalPattern(), getType(), excludedSubdirectories);
+      assertBlacklistedAndExcludedSubdirectoriesEmpty(
+          blacklistedSubdirectories, excludedSubdirectories);
       if (resolver.isPackage(PackageIdentifier.createInMainRepo(path))) {
         // User has specified a package name. lookout for default target.
         callback.process(resolver.getExplicitTarget(label("//" + path)).getTargets());
@@ -423,12 +465,12 @@ public abstract class TargetPattern implements Serializable {
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback, Class<E> exceptionClass)
         throws TargetParsingException, E, InterruptedException {
-      Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
-          "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
-          getOriginalPattern(), getType(), excludedSubdirectories);
+      assertBlacklistedAndExcludedSubdirectoriesEmpty(
+          blacklistedSubdirectories, excludedSubdirectories);
       if (checkWildcardConflict) {
         ResolvedTargets<T> targets = getWildcardConflict(resolver);
         if (targets != null) {
@@ -534,6 +576,7 @@ public abstract class TargetPattern implements Serializable {
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback,
         Class<E> exceptionClass)
@@ -543,6 +586,7 @@ public abstract class TargetPattern implements Serializable {
           getOriginalPattern(),
           directory.getPackageFragment().getPathString(),
           rulesOnly,
+          blacklistedSubdirectories,
           excludedSubdirectories,
           callback,
           exceptionClass);
@@ -551,6 +595,7 @@ public abstract class TargetPattern implements Serializable {
     @Override
     public <T, E extends Exception> ListenableFuture<Void> evalAsync(
         TargetPatternResolver<T> resolver,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
         ThreadSafeBatchCallback<T, E> callback,
         Class<E> exceptionClass,
@@ -560,6 +605,7 @@ public abstract class TargetPattern implements Serializable {
           getOriginalPattern(),
           directory.getPackageFragment().getPathString(),
           rulesOnly,
+          blacklistedSubdirectories,
           excludedSubdirectories,
           callback,
           exceptionClass,
@@ -667,6 +713,10 @@ public abstract class TargetPattern implements Serializable {
       this.relativeDirectory = relativeDirectory;
     }
 
+    public String getRelativeDirectory() {
+      return relativeDirectory;
+    }
+
     /**
      * Parses the given pattern, and throws an exception if the pattern is invalid.
      *
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
index 38b866b68e..b3e14659b8 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
@@ -81,8 +81,10 @@ public abstract class TargetPatternResolver<T> {
    * @param originalPattern the original target pattern for error reporting purposes
    * @param directory the directory in which to look for packages
    * @param rulesOnly whether to return rules only
-   * @param excludedSubdirectories a set of transitive subdirectories beneath {@code directory}
+   * @param blacklistedSubdirectories a set of transitive subdirectories beneath {@code directory}
    *    to ignore
+   * @param excludedSubdirectories another set of transitive subdirectories beneath
+   *    {@code directory} to ignore
    * @param callback the callback to receive the result, possibly in multiple batches.
    * @param exceptionClass The class type of the parameterized exception.
    * @throws TargetParsingException under implementation-specific failure conditions
@@ -92,6 +94,7 @@ public abstract class TargetPatternResolver<T> {
       String originalPattern,
       String directory,
       boolean rulesOnly,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       BatchCallback<T, E> callback,
       Class<E> exceptionClass)
@@ -106,6 +109,7 @@ public abstract class TargetPatternResolver<T> {
       String originalPattern,
       String directory,
       boolean rulesOnly,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       ThreadSafeBatchCallback<T, E> callback,
       Class<E> exceptionClass,
@@ -116,6 +120,7 @@ public abstract class TargetPatternResolver<T> {
             originalPattern,
             directory,
             rulesOnly,
+            blacklistedSubdirectories,
             excludedSubdirectories,
             callback,
             exceptionClass);
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
index 9b857d9108..1a16b6c84c 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
@@ -37,6 +37,8 @@ public interface RecursivePackageProvider extends PackageProvider {
    * @param eventHandler any errors emitted during package lookup and loading for {@code directory}
    *     and non-excluded directories beneath it will be reported here
    * @param directory a {@link RootedPath} specifying the directory to search
+   * @param blacklistedSubdirectories a set of {@link PathFragment}s, all of which are beneath
+   *     {@code directory}, specifying transitive subdirectories to that have been blacklisted
    * @param excludedSubdirectories a set of {@link PathFragment}s, all of which are beneath {@code
    *     directory}, specifying transitive subdirectories to exclude
    */
@@ -44,6 +46,7 @@ public interface RecursivePackageProvider extends PackageProvider {
       ExtendedEventHandler eventHandler,
       RepositoryName repository,
       PathFragment directory,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories)
       throws InterruptedException;
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index 6cc8fd1585..80551587c3 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -685,24 +685,19 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     return new UniquifierImpl<>(ReverseDepSkyKeyKeyExtractor.INSTANCE, DEFAULT_THREAD_COUNT);
   }
 
-  private Pair<TargetPattern, ImmutableSet<PathFragment>> getPatternAndExcludes(String pattern)
-      throws TargetParsingException, InterruptedException {
-    TargetPatternKey targetPatternKey =
-        TargetPatternValue.key(
-            pattern, TargetPatternEvaluator.DEFAULT_FILTERING_POLICY, parserPrefix);
-    ImmutableSet<PathFragment> subdirectoriesToExclude =
-        targetPatternKey.getAllSubdirectoriesToExclude(blacklistPatternsSupplier);
-    return Pair.of(targetPatternKey.getParsedPattern(), subdirectoriesToExclude);
+  private ImmutableSet<PathFragment> getBlacklistedExcludes(TargetPatternKey targetPatternKey)
+  throws InterruptedException {
+    return targetPatternKey.getAllBlacklistedSubdirectoriesToExclude(blacklistPatternsSupplier);
   }
 
   @ThreadSafe
   @Override
   public QueryTaskFuture<Void> getTargetsMatchingPattern(
-      final QueryExpression owner, String pattern, Callback<Target> callback) {
-    // Directly evaluate the target pattern, making use of packages in the graph.
-    Pair<TargetPattern, ImmutableSet<PathFragment>> patternToEvalAndSubdirectoriesToExclude;
+      QueryExpression owner, String pattern, Callback<Target> callback) {
+    TargetPatternKey targetPatternKey;
     try {
-      patternToEvalAndSubdirectoriesToExclude = getPatternAndExcludes(pattern);
+      targetPatternKey = TargetPatternValue.key(
+          pattern, TargetPatternEvaluator.DEFAULT_FILTERING_POLICY, parserPrefix);
     } catch (TargetParsingException tpe) {
       try {
         reportBuildFileError(owner, tpe.getMessage());
@@ -710,12 +705,22 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
         return immediateFailedFuture(qe);
       }
       return immediateSuccessfulFuture(null);
+    }
+    return evalTargetPatternKey(owner, targetPatternKey, callback);
+  }
+
+  @ThreadSafe
+  public QueryTaskFuture<Void> evalTargetPatternKey(
+      QueryExpression owner, TargetPatternKey targetPatternKey, Callback<Target> callback) {
+    ImmutableSet<PathFragment> blacklistedSubdirectoriesToExclude;
+    try {
+      blacklistedSubdirectoriesToExclude = getBlacklistedExcludes(targetPatternKey);
     } catch (InterruptedException ie) {
       return immediateCancelledFuture();
     }
-    TargetPattern patternToEval = patternToEvalAndSubdirectoriesToExclude.getFirst();
-    ImmutableSet<PathFragment> subdirectoriesToExclude =
-        patternToEvalAndSubdirectoriesToExclude.getSecond();
+    TargetPattern patternToEval = targetPatternKey.getParsedPattern();
+    ImmutableSet<PathFragment> additionalSubdirectoriesToExclude =
+        targetPatternKey.getExcludedSubdirectories();
     AsyncFunction<TargetParsingException, Void> reportBuildFileErrorAsyncFunction =
         exn -> {
           reportBuildFileError(owner, exn.getMessage());
@@ -723,7 +728,8 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
         };
     ListenableFuture<Void> evalFuture = patternToEval.evalAsync(
         resolver,
-        subdirectoriesToExclude,
+        blacklistedSubdirectoriesToExclude,
+        additionalSubdirectoriesToExclude,
         callback,
         QueryException.class,
         executor);
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
index e1eadf3aa5..57db015f9e 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
@@ -38,11 +38,11 @@ import java.util.List;
  *
  * <pre>expr ::= SET '(' WORD * ')'</pre>
  */
-class SetExpression extends QueryExpression {
+public class SetExpression extends QueryExpression {
 
   private final List<TargetLiteral> words;
 
-  SetExpression(List<TargetLiteral> words) {
+  public SetExpression(List<TargetLiteral> words) {
     this.words = words;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
index 4baa59dbeb..e070b659b4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
@@ -19,7 +19,6 @@ import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
@@ -37,6 +36,7 @@ import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyKey;
 import java.util.ArrayList;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 
@@ -115,6 +115,7 @@ public final class EnvironmentBackedRecursivePackageProvider implements Recursiv
       ExtendedEventHandler eventHandler,
       RepositoryName repository,
       PathFragment directory,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories)
       throws MissingDepException, InterruptedException {
     PathPackageLocator packageLocator = PrecomputedValue.PATH_PACKAGE_LOCATOR.get(env);
@@ -140,11 +141,11 @@ public final class EnvironmentBackedRecursivePackageProvider implements Recursiv
       roots.add(repositoryValue.getPath());
     }
 
-    NestedSetBuilder<String> packageNames = NestedSetBuilder.stableOrder();
+    LinkedHashSet<PathFragment> packageNames = new LinkedHashSet<>();
     for (Path root : roots) {
-      PathFragment.checkAllPathsAreUnder(excludedSubdirectories, directory);
+      PathFragment.checkAllPathsAreUnder(blacklistedSubdirectories, directory);
       RecursivePkgValue lookup = (RecursivePkgValue) env.getValue(RecursivePkgValue.key(
-          repository, RootedPath.toRootedPath(root, directory), excludedSubdirectories));
+          repository, RootedPath.toRootedPath(root, directory), blacklistedSubdirectories));
       if (lookup == null) {
         // Typically a null value from Environment.getValue(k) means that either the key k is
         // missing a dependency or an exception was thrown during evaluation of k. Here, if this
@@ -156,11 +157,19 @@ public final class EnvironmentBackedRecursivePackageProvider implements Recursiv
         throw new MissingDepException();
       }
 
-      packageNames.addTransitive(lookup.getPackages());
+      for (String packageName : lookup.getPackages()) {
+        // TODO(bazel-team): Make RecursivePkgValue return NestedSet<PathFragment> so this transform
+        // is unnecessary.
+        PathFragment packageNamePathFragment = PathFragment.create(packageName);
+        if (!Iterables.any(
+            excludedSubdirectories,
+            excludedSubdirectory -> packageNamePathFragment.startsWith(excludedSubdirectory))) {
+          packageNames.add(packageNamePathFragment);
+        }
+      }
     }
-    // TODO(bazel-team): Make RecursivePkgValue return NestedSet<PathFragment> so this transform is
-    // unnecessary.
-    return Iterables.transform(packageNames.build(), PathFragment::create);
+
+    return packageNames;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
index b5ba1da184..0cc2097bf0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
@@ -166,10 +166,16 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
       ExtendedEventHandler eventHandler,
       RepositoryName repository,
       PathFragment directory,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories)
       throws InterruptedException {
+    PathFragment.checkAllPathsAreUnder(blacklistedSubdirectories, directory);
     PathFragment.checkAllPathsAreUnder(excludedSubdirectories, directory);
 
+    if (excludedSubdirectories.contains(directory)) {
+      return ImmutableList.of();
+    }
+
     // Check that this package is covered by at least one of our universe patterns.
     boolean inUniverse = false;
     for (TargetPatternKey patternKey : universeTargetPatternKeys) {
@@ -206,7 +212,8 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
     ImmutableList.Builder<PathFragment> builder = ImmutableList.builder();
     for (Path root : roots) {
       RootedPath rootedDir = RootedPath.toRootedPath(root, directory);
-      TraversalInfo info = new TraversalInfo(rootedDir, excludedSubdirectories);
+      TraversalInfo info =
+          new TraversalInfo(rootedDir, blacklistedSubdirectories, excludedSubdirectories);
       collectPackagesUnder(eventHandler, repository, ImmutableSet.of(info), builder);
     }
     return builder.build();
@@ -225,7 +232,7 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
               @Override
               public SkyKey apply(TraversalInfo traversalInfo) {
                 return CollectPackagesUnderDirectoryValue.key(
-                    repository, traversalInfo.rootedDir, traversalInfo.excludedSubdirectories);
+                    repository, traversalInfo.rootedDir, traversalInfo.blacklistedSubdirectories);
               }
             });
     Map<SkyKey, SkyValue> values = graph.getSuccessfulValues(traversalToKeyMap.values());
@@ -251,11 +258,19 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
         for (RootedPath subdirectory : subdirectoryTransitivelyContainsPackages.keySet()) {
           if (subdirectoryTransitivelyContainsPackages.get(subdirectory)) {
             PathFragment subdirectoryRelativePath = subdirectory.getRelativePath();
+            ImmutableSet<PathFragment> blacklistedSubdirectoriesBeneathThisSubdirectory =
+                PathFragment.filterPathsStartingWith(
+                    info.blacklistedSubdirectories, subdirectoryRelativePath);
             ImmutableSet<PathFragment> excludedSubdirectoriesBeneathThisSubdirectory =
                 PathFragment.filterPathsStartingWith(
                     info.excludedSubdirectories, subdirectoryRelativePath);
-            subdirTraversalBuilder.add(
-                new TraversalInfo(subdirectory, excludedSubdirectoriesBeneathThisSubdirectory));
+            if (!excludedSubdirectoriesBeneathThisSubdirectory.contains(subdirectoryRelativePath)) {
+              subdirTraversalBuilder.add(
+                  new TraversalInfo(
+                      subdirectory,
+                      blacklistedSubdirectoriesBeneathThisSubdirectory,
+                      excludedSubdirectoriesBeneathThisSubdirectory));
+            }
           }
         }
       }
@@ -275,16 +290,28 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
 
   private static final class TraversalInfo {
     private final RootedPath rootedDir;
+    // Set of blacklisted directories. The graph is assumed to be prepopulated with
+    // CollectPackagesUnderDirectoryValue nodes whose keys have blacklisted packages embedded in
+    // them. Therefore, we need to be careful to request and use the same sort of keys here in our
+    // traversal.
+    private final ImmutableSet<PathFragment> blacklistedSubdirectories;
+    // Set of directories, targets under which should be excluded from the traversal results.
+    // Excluded directory information isn't part of the graph keys in the prepopulated graph, so we
+    // need to perform the filtering ourselves.
     private final ImmutableSet<PathFragment> excludedSubdirectories;
 
-    private TraversalInfo(RootedPath rootedDir, ImmutableSet<PathFragment> excludedSubdirectories) {
+    private TraversalInfo(
+        RootedPath rootedDir,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
+        ImmutableSet<PathFragment> excludedSubdirectories) {
       this.rootedDir = rootedDir;
+      this.blacklistedSubdirectories = blacklistedSubdirectories;
       this.excludedSubdirectories = excludedSubdirectories;
     }
 
     @Override
     public int hashCode() {
-      return Objects.hashCode(rootedDir, excludedSubdirectories);
+      return Objects.hashCode(rootedDir, blacklistedSubdirectories, excludedSubdirectories);
     }
 
     @Override
@@ -295,6 +322,7 @@ public final class GraphBackedRecursivePackageProvider implements RecursivePacka
       if (obj instanceof TraversalInfo) {
         TraversalInfo otherTraversal = (TraversalInfo) obj;
         return Objects.equal(rootedDir, otherTraversal.rootedDir)
+            && Objects.equal(blacklistedSubdirectories, otherTraversal.blacklistedSubdirectories)
             && Objects.equal(excludedSubdirectories, otherTraversal.excludedSubdirectories);
       }
       return false;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
index a4a3b1bda8..b2ce5b6469 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
@@ -84,15 +84,22 @@ public class PrepareDepsOfPatternFunction implements SkyFunction {
     if (blacklist == null) {
       return null;
     }
-    ImmutableSet<PathFragment> subdirectoriesToExclude =
+    // This SkyFunction is used to load the universe, so we want both the blacklisted directories
+    // from the global blacklist and the excluded directories from the TargetPatternKey itself to be
+    // embedded in the SkyKeys created and used by the DepsOfPatternPreparer. The
+    // DepsOfPatternPreparer ignores excludedSubdirectories and embeds blacklistedSubdirectories in
+    // the SkyKeys it creates and uses.
+    ImmutableSet<PathFragment> blacklistedSubdirectories =
         patternKey.getAllSubdirectoriesToExclude(blacklist.getPatterns());
+    ImmutableSet<PathFragment> excludedSubdirectories = ImmutableSet.of();
 
     DepsOfPatternPreparer preparer = new DepsOfPatternPreparer(env, pkgPath.get());
 
     try {
       parsedPattern.eval(
           preparer,
-          subdirectoriesToExclude,
+          blacklistedSubdirectories,
+          excludedSubdirectories,
           NullCallback.<Void>instance(),
           RuntimeException.class);
     } catch (TargetParsingException e) {
@@ -227,10 +234,12 @@ public class PrepareDepsOfPatternFunction implements SkyFunction {
         String originalPattern,
         String directory,
         boolean rulesOnly,
+        ImmutableSet<PathFragment> blacklistedSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<Void, E> callback,
         Class<E> exceptionClass)
         throws TargetParsingException, E, InterruptedException {
+      Preconditions.checkArgument(excludedSubdirectories.isEmpty(), excludedSubdirectories);
       FilteringPolicy policy =
           rulesOnly ? FilteringPolicies.RULES_ONLY : FilteringPolicies.NO_FILTER;
       PathFragment pathFragment = TargetPatternResolverUtil.getPathFragment(directory);
@@ -257,9 +266,9 @@ public class PrepareDepsOfPatternFunction implements SkyFunction {
         env.getValues(
             ImmutableList.of(
                 PrepareDepsOfTargetsUnderDirectoryValue.key(
-                    repository, rootedPath, excludedSubdirectories, policy),
+                    repository, rootedPath, blacklistedSubdirectories, policy),
                 CollectPackagesUnderDirectoryValue.key(
-                    repository, rootedPath, excludedSubdirectories)));
+                    repository, rootedPath, blacklistedSubdirectories)));
         if (env.valuesMissing()) {
           throw new MissingDepException();
         }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
index f54604d536..1dc932d6e6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
@@ -14,15 +14,12 @@
 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.cmdline.TargetParsingException;
-import com.google.devtools.build.lib.cmdline.TargetPattern;
 import com.google.devtools.build.lib.cmdline.TargetPattern.Type;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternSkyKeyOrException;
-import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
@@ -58,123 +55,97 @@ public class PrepareDepsOfPatternValue implements SkyValue {
     return 42;
   }
 
+
   /**
-   * Returns an iterable of {@link PrepareDepsOfPatternSkyKeyOrException}, with {@link
-   * TargetPatternKey} arguments. Negative target patterns of type other than {@link
-   * Type#TARGETS_BELOW_DIRECTORY} are not permitted. If a provided pattern fails to parse or is
-   * negative but not a {@link Type#TARGETS_BELOW_DIRECTORY}, an element in the returned iterable
-   * will throw when its {@link PrepareDepsOfPatternSkyKeyOrException#getSkyKey} method is called
-   * and will return the failing pattern when its {@link
-   * PrepareDepsOfPatternSkyKeyOrException#getOriginalPattern} method is called.
+   * Returns a {@link PrepareDepsOfPatternSkyKeysAndExceptions}, containing
+   * {@link PrepareDepsOfPatternSkyKeyValue} and {@link PrepareDepsOfPatternSkyKeyException}
+   * instances that have {@link TargetPatternKey} arguments. Negative target patterns of type other
+   * than {@link Type#TARGETS_BELOW_DIRECTORY} are not permitted. If a provided pattern fails to
+   * parse or is negative but not a {@link Type#TARGETS_BELOW_DIRECTORY}, there will be a
+   * corresponding {@link PrepareDepsOfPatternSkyKeyException} in the iterable returned by
+   * {@link PrepareDepsOfPatternSkyKeysAndExceptions#getExceptions} whose
+   * {@link PrepareDepsOfPatternSkyKeyException#getException} and
+   * {@link PrepareDepsOfPatternSkyKeyException#getOriginalPattern} methods return the
+   * {@link TargetParsingException} and original pattern, respectively.
    *
-   * <p>There may be fewer returned elements than patterns provided as input. This function will
-   * combine negative {@link Type#TARGETS_BELOW_DIRECTORY} patterns with preceding patterns to
-   * return an iterable of SkyKeys that avoids loading excluded directories during evaluation.
+   * <p>There may be fewer returned elements in
+   * {@link PrepareDepsOfPatternSkyKeysAndExceptions#getValues} than patterns provided as input.
+   * This function will combine negative {@link Type#TARGETS_BELOW_DIRECTORY} patterns with
+   * preceding patterns to return an iterable of SkyKeys that avoids loading excluded directories
+   * during evaluation.
    *
    * @param patterns The list of patterns, e.g. [//foo/..., -//foo/biz/...]. If a pattern's first
    *     character is "-", it is treated as a negative pattern.
    * @param offset The offset to apply to relative target patterns.
    */
   @ThreadSafe
-  public static Iterable<PrepareDepsOfPatternSkyKeyOrException> keys(List<String> patterns,
-      String offset) {
-    List<TargetPatternSkyKeyOrException> keysMaybe =
-        ImmutableList.copyOf(TargetPatternValue.keys(patterns, FilteringPolicies.NO_FILTER,
-            offset));
-
+  public static PrepareDepsOfPatternSkyKeysAndExceptions keys(
+      List<String> patterns, String offset) {
+    ImmutableList.Builder<PrepareDepsOfPatternSkyKeyValue> resultValuesBuilder =
+        ImmutableList.builder();
+    ImmutableList.Builder<PrepareDepsOfPatternSkyKeyException> resultExceptionsBuilder =
+        ImmutableList.builder();
+    Iterable<TargetPatternSkyKeyOrException> keysMaybe =
+        TargetPatternValue.keys(patterns, FilteringPolicies.NO_FILTER, offset);
+    ImmutableList.Builder<TargetPatternKey> targetPatternKeysBuilder = ImmutableList.builder();
+    for (TargetPatternSkyKeyOrException keyMaybe : keysMaybe) {
+      try {
+        SkyKey key = keyMaybe.getSkyKey();
+        targetPatternKeysBuilder.add((TargetPatternKey) key.argument());
+      } catch (TargetParsingException e) {
+        resultExceptionsBuilder.add(
+            new PrepareDepsOfPatternSkyKeyException(e, keyMaybe.getOriginalPattern()));
+      }
+    }
     // This code path is evaluated only for query universe preloading, and the quadratic cost of
     // the code below (i.e. for each pattern, consider each later pattern as a candidate for
     // subdirectory exclusion) is only acceptable because all the use cases for query universe
     // preloading involve short (<10 items) pattern sequences.
-    ImmutableList.Builder<PrepareDepsOfPatternSkyKeyOrException> builder = ImmutableList.builder();
-    for (int i = 0; i < keysMaybe.size(); i++) {
-      TargetPatternSkyKeyOrException keyMaybe = keysMaybe.get(i);
-      TargetPatternKey targetPatternKey;
-      try {
-        targetPatternKey = keyMaybe.getSkyKey();
-      } catch (TargetParsingException e) {
-        // keyMaybe.getSkyKey() may throw TargetParsingException if its corresponding pattern
-        // failed to parse. If so, wrap the exception and return it, so that our caller can
-        // deal with it.
-        targetPatternKey = null;
-        builder.add(new PrepareDepsOfPatternSkyKeyException(e, keyMaybe.getOriginalPattern()));
-      }
-      if (targetPatternKey != null) {
-        if (targetPatternKey.isNegative()) {
-          if (!targetPatternKey.getParsedPattern().getType().equals(Type.TARGETS_BELOW_DIRECTORY)) {
-            builder.add(
-                new PrepareDepsOfPatternSkyKeyException(
-                    new TargetParsingException(
-                        "Negative target patterns of types other than \"targets below directory\""
-                            + " are not permitted."), targetPatternKey.toString()));
-          }
-          // Otherwise it's a negative TBD pattern which was combined with previous patterns as an
-          // excluded directory. These can be skipped because there's no PrepareDepsOfPattern work
-          // to be done for them.
-        } else {
-          builder.add(new PrepareDepsOfPatternSkyKeyValue(setExcludedDirectories(targetPatternKey,
-              excludedDirectoriesBeneath(targetPatternKey, i, keysMaybe))));
-        }
+    Iterable<TargetPatternKey> combinedTargetPatternKeys =
+        TargetPatternValue.combineNegativeTargetsBelowDirectoryPatterns(
+            targetPatternKeysBuilder.build());
+    for (TargetPatternKey targetPatternKey : combinedTargetPatternKeys) {
+      if (targetPatternKey.isNegative()
+          && !targetPatternKey.getParsedPattern().getType().equals(Type.TARGETS_BELOW_DIRECTORY)) {
+        resultExceptionsBuilder.add(
+            new PrepareDepsOfPatternSkyKeyException(
+                new TargetParsingException(
+                    "Negative target patterns of types other than \"targets below directory\""
+                        + " are not permitted."), targetPatternKey.toString()));
+      } else {
+        resultValuesBuilder.add(new PrepareDepsOfPatternSkyKeyValue(targetPatternKey));
       }
     }
-    return builder.build();
+    return new PrepareDepsOfPatternSkyKeysAndExceptions(
+        resultValuesBuilder.build(), resultExceptionsBuilder.build());
   }
 
-  private static TargetPatternKey setExcludedDirectories(
-      TargetPatternKey original, ImmutableSet<PathFragment> excludedSubdirectories) {
-    return new TargetPatternKey(original.getParsedPattern(), original.getPolicy(),
-        original.isNegative(), original.getOffset(), excludedSubdirectories);
-  }
+  /**
+   * A pair of {@link Iterable<PrepareDepsOfPatternSkyKeyValue>} and
+   * {@link Iterable<PrepareDepsOfPatternSkyKeyException>}.
+   */
+  public static class PrepareDepsOfPatternSkyKeysAndExceptions {
+    private final Iterable<PrepareDepsOfPatternSkyKeyValue> values;
+    private final Iterable<PrepareDepsOfPatternSkyKeyException> exceptions;
+
+    public PrepareDepsOfPatternSkyKeysAndExceptions(
+        Iterable<PrepareDepsOfPatternSkyKeyValue> values,
+        Iterable<PrepareDepsOfPatternSkyKeyException> exceptions) {
+      this.values = values;
+      this.exceptions = exceptions;
+    }
 
-  private static ImmutableSet<PathFragment> excludedDirectoriesBeneath(
-      TargetPatternKey targetPatternKey,
-      int position,
-      List<TargetPatternSkyKeyOrException> keysMaybe) {
-    ImmutableSet.Builder<PathFragment> excludedDirectoriesBuilder = ImmutableSet.builder();
-    for (int j = position + 1; j < keysMaybe.size(); j++) {
-      TargetPatternSkyKeyOrException laterPatternMaybe = keysMaybe.get(j);
-      TargetPatternKey laterTargetPatternKey;
-      try {
-        laterTargetPatternKey = laterPatternMaybe.getSkyKey();
-      } catch (TargetParsingException ignored) {
-        laterTargetPatternKey = null;
-      }
-      if (laterTargetPatternKey != null) {
-        TargetPattern laterParsedPattern = laterTargetPatternKey.getParsedPattern();
-        if (laterTargetPatternKey.isNegative()
-            && laterParsedPattern.getType() == Type.TARGETS_BELOW_DIRECTORY
-            && targetPatternKey.getParsedPattern().containsDirectoryOfTBDForTBD(
-                laterParsedPattern)) {
-          excludedDirectoriesBuilder.add(
-              laterParsedPattern.getDirectoryForTargetsUnderDirectory().getPackageFragment());
-        }
-      }
+    public Iterable<PrepareDepsOfPatternSkyKeyValue> getValues() {
+      return values;
     }
-    return excludedDirectoriesBuilder.build();
-  }
 
-  /**
-   * Wrapper for a prepare deps of pattern {@link SkyKey} or the {@link TargetParsingException}
-   * thrown when trying to create it.
-   */
-  public interface PrepareDepsOfPatternSkyKeyOrException {
-
-    /**
-     * Returns the stored {@link SkyKey} or throws {@link TargetParsingException} if one was thrown
-     * when creating the key.
-     */
-    SkyKey getSkyKey() throws TargetParsingException;
-
-    /**
-     * Returns the pattern that resulted in the stored {@link SkyKey} or {@link
-     * TargetParsingException}.
-     */
-    String getOriginalPattern();
+    public Iterable<PrepareDepsOfPatternSkyKeyException> getExceptions() {
+      return exceptions;
+    }
   }
 
-
-  private static class PrepareDepsOfPatternSkyKeyException implements
-      PrepareDepsOfPatternSkyKeyOrException {
+  /** Represents a {@link TargetParsingException} when parsing a target pattern string. */
+  public static class PrepareDepsOfPatternSkyKeyException {
 
     private final TargetParsingException exception;
     private final String originalPattern;
@@ -185,19 +156,19 @@ public class PrepareDepsOfPatternValue implements SkyValue {
       this.originalPattern = originalPattern;
     }
 
-    @Override
-    public SkyKey getSkyKey() throws TargetParsingException {
-      throw exception;
+    public TargetParsingException getException() {
+      return exception;
     }
 
-    @Override
     public String getOriginalPattern() {
       return originalPattern;
     }
   }
 
-  private static class PrepareDepsOfPatternSkyKeyValue implements
-      PrepareDepsOfPatternSkyKeyOrException {
+  /**
+   * Represents the successful parsing of a target pattern string into a {@link TargetPatternKey}.
+   */
+  public static class PrepareDepsOfPatternSkyKeyValue {
 
     private final TargetPatternKey targetPatternKey;
 
@@ -205,12 +176,10 @@ public class PrepareDepsOfPatternValue implements SkyValue {
       this.targetPatternKey = targetPatternKey;
     }
 
-    @Override
-    public SkyKey getSkyKey() throws TargetParsingException {
+    public SkyKey getSkyKey() {
       return LegacySkyKey.create(SkyFunctions.PREPARE_DEPS_OF_PATTERN, targetPatternKey);
     }
 
-    @Override
     public String getOriginalPattern() {
       return targetPatternKey.getPattern();
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java
index 422462e723..3e48fab046 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java
@@ -20,7 +20,9 @@ import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.pkgcache.ParsingFailedEvent;
-import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternValue.PrepareDepsOfPatternSkyKeyOrException;
+import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternValue.PrepareDepsOfPatternSkyKeyException;
+import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternValue.PrepareDepsOfPatternSkyKeyValue;
+import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternValue.PrepareDepsOfPatternSkyKeysAndExceptions;
 import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternsValue.TargetPatternSequence;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -39,22 +41,24 @@ public class PrepareDepsOfPatternsFunction implements SkyFunction {
 
   public static ImmutableList<SkyKey> getSkyKeys(SkyKey skyKey, ExtendedEventHandler eventHandler) {
     TargetPatternSequence targetPatternSequence = (TargetPatternSequence) skyKey.argument();
-    Iterable<PrepareDepsOfPatternSkyKeyOrException> keysMaybe =
+    PrepareDepsOfPatternSkyKeysAndExceptions prepareDepsOfPatternSkyKeysAndExceptions =
         PrepareDepsOfPatternValue.keys(targetPatternSequence.getPatterns(),
             targetPatternSequence.getOffset());
 
     ImmutableList.Builder<SkyKey> skyKeyBuilder = ImmutableList.builder();
-    for (PrepareDepsOfPatternSkyKeyOrException skyKeyOrException : keysMaybe) {
-      try {
-        skyKeyBuilder.add(skyKeyOrException.getSkyKey());
-      } catch (TargetParsingException e) {
-        // We post an event here rather than in handleTargetParsingException because the
-        // TargetPatternFunction already posts an event unless the pattern cannot be parsed, in
-        // which case the caller (i.e., us) needs to post an event.
-        eventHandler.post(
-            new ParsingFailedEvent(skyKeyOrException.getOriginalPattern(), e.getMessage()));
-        handleTargetParsingException(eventHandler, skyKeyOrException.getOriginalPattern(), e);
-      }
+    for (PrepareDepsOfPatternSkyKeyValue skyKeyValue
+        : prepareDepsOfPatternSkyKeysAndExceptions.getValues()) {
+      skyKeyBuilder.add(skyKeyValue.getSkyKey());
+    }
+    for (PrepareDepsOfPatternSkyKeyException skyKeyException
+        : prepareDepsOfPatternSkyKeysAndExceptions.getExceptions()) {
+      TargetParsingException e = skyKeyException.getException();
+      // We post an event here rather than in handleTargetParsingException because the
+      // TargetPatternFunction already posts an event unless the pattern cannot be parsed, in
+      // which case the caller (i.e., us) needs to post an event.
+      eventHandler.post(
+          new ParsingFailedEvent(skyKeyException.getOriginalPattern(), e.getMessage()));
+      handleTargetParsingException(eventHandler, skyKeyException.getOriginalPattern(), e);
     }
 
     return skyKeyBuilder.build();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
index 2fb74861a2..4ba21224a2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
@@ -216,6 +216,7 @@ public class RecursivePackageProviderBackedTargetPatternResolver
       final String originalPattern,
       String directory,
       boolean rulesOnly,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       BatchCallback<Target, E> callback,
       Class<E> exceptionClass)
@@ -226,6 +227,7 @@ public class RecursivePackageProviderBackedTargetPatternResolver
           originalPattern,
           directory,
           rulesOnly,
+          blacklistedSubdirectories,
           excludedSubdirectories,
           new SynchronizedBatchCallback<Target, E>(callback),
           MoreExecutors.newDirectExecutorService()).get();
@@ -242,6 +244,7 @@ public class RecursivePackageProviderBackedTargetPatternResolver
       String originalPattern,
       String directory,
       boolean rulesOnly,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       ThreadSafeBatchCallback<Target, E> callback,
       Class<E> exceptionClass,
@@ -251,6 +254,7 @@ public class RecursivePackageProviderBackedTargetPatternResolver
         originalPattern,
         directory,
         rulesOnly,
+        blacklistedSubdirectories,
         excludedSubdirectories,
         callback,
         executor);
@@ -261,6 +265,7 @@ public class RecursivePackageProviderBackedTargetPatternResolver
       final String originalPattern,
       String directory,
       boolean rulesOnly,
+      ImmutableSet<PathFragment> blacklistedSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
       final ThreadSafeBatchCallback<Target, E> callback,
       ListeningExecutorService executor) {
@@ -273,7 +278,11 @@ public class RecursivePackageProviderBackedTargetPatternResolver
       pathFragment = TargetPatternResolverUtil.getPathFragment(directory);
       packagesUnderDirectory =
           recursivePackageProvider.getPackagesUnderDirectory(
-              eventHandler, repository, pathFragment, excludedSubdirectories);
+              eventHandler,
+              repository,
+              pathFragment,
+              blacklistedSubdirectories,
+              excludedSubdirectories);
     } catch (TargetParsingException e) {
       return Futures.immediateFailedFuture(e);
     } catch (InterruptedException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
index 62b537c146..197e0f7ffd 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
@@ -69,7 +69,12 @@ public class TargetPatternFunction implements SkyFunction {
               Iterables.addAll(results, partialResult);
             }
           };
-      parsedPattern.eval(resolver, excludedSubdirectories, callback, RuntimeException.class);
+      parsedPattern.eval(
+          resolver,
+          /*blacklistedSubdirectories=*/ ImmutableSet.of(),
+          excludedSubdirectories,
+          callback,
+          RuntimeException.class);
       resolvedTargets = ResolvedTargets.<Target>builder().addAll(results).build();
     } catch (TargetParsingException e) {
       env.getListener().post(new ParsingFailedEvent(patternKey.getPattern(),  e.getMessage()));
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
index f36a4396d2..f28cdfd9cc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
@@ -23,6 +23,7 @@ import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets.Builder;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
+import com.google.devtools.build.lib.cmdline.TargetPattern.ContainsTBDForTBDResult;
 import com.google.devtools.build.lib.cmdline.TargetPattern.Type;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
@@ -39,8 +40,10 @@ import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Objects;
+import java.util.Optional;
 
 /**
  * A value referring to a computed set of resolved targets. This is used for the results of target
@@ -152,6 +155,88 @@ public final class TargetPatternValue implements SkyValue {
     return builder.build();
   }
 
+  @ThreadSafe
+  public static ImmutableList<TargetPatternKey> combineNegativeTargetsBelowDirectoryPatterns(
+      List<TargetPatternKey> keys) {
+    ImmutableList.Builder<TargetPatternKey> builder = ImmutableList.builder();
+    HashSet<Integer> indicesOfNegativePatternsThatNeedToBeIncluded = new HashSet<>();
+    for (int i = 0; i < keys.size(); i++) {
+      TargetPatternKey targetPatternKey = keys.get(i);
+      if (targetPatternKey.isNegative()) {
+        if (!targetPatternKey.getParsedPattern().getType().equals(Type.TARGETS_BELOW_DIRECTORY)
+            || indicesOfNegativePatternsThatNeedToBeIncluded.contains(i)) {
+          builder.add(targetPatternKey);
+        }
+        // Otherwise it's a negative TBD pattern which was combined with previous patterns as an
+        // excluded directory.
+      } else {
+        TargetPatternKeyWithExclusionsResult result =
+            computeTargetPatternKeyWithExclusions(targetPatternKey, i, keys);
+        result.targetPatternKeyMaybe.ifPresent(builder::add);
+        indicesOfNegativePatternsThatNeedToBeIncluded.addAll(
+            result.indicesOfNegativePatternsThatNeedToBeIncluded);
+      }
+    }
+    return builder.build();
+  }
+
+  private static TargetPatternKey setExcludedDirectories(
+      TargetPatternKey original, ImmutableSet<PathFragment> excludedSubdirectories) {
+    return new TargetPatternKey(original.getParsedPattern(), original.getPolicy(),
+        original.isNegative(), original.getOffset(), excludedSubdirectories);
+  }
+
+  private static class TargetPatternKeyWithExclusionsResult {
+    private final Optional<TargetPatternKey> targetPatternKeyMaybe;
+    private final ImmutableList<Integer> indicesOfNegativePatternsThatNeedToBeIncluded;
+
+    private TargetPatternKeyWithExclusionsResult(
+        Optional<TargetPatternKey> targetPatternKeyMaybe,
+        ImmutableList<Integer> indicesOfNegativePatternsThatNeedToBeIncluded) {
+      this.targetPatternKeyMaybe = targetPatternKeyMaybe;
+      this.indicesOfNegativePatternsThatNeedToBeIncluded =
+          indicesOfNegativePatternsThatNeedToBeIncluded;
+    }
+  }
+
+  private static TargetPatternKeyWithExclusionsResult computeTargetPatternKeyWithExclusions(
+      TargetPatternKey targetPatternKey,
+      int position,
+      List<TargetPatternKey> keys) {
+    TargetPattern targetPattern = targetPatternKey.getParsedPattern();
+    ImmutableSet.Builder<PathFragment> excludedDirectoriesBuilder = ImmutableSet.builder();
+    ImmutableList.Builder<Integer> indicesOfNegativePatternsThatNeedToBeIncludedBuilder =
+        ImmutableList.builder();
+    for (int j = position + 1; j < keys.size(); j++) {
+      TargetPatternKey laterTargetPatternKey = keys.get(j);
+      TargetPattern laterParsedPattern = laterTargetPatternKey.getParsedPattern();
+      if (laterTargetPatternKey.isNegative()
+          && laterParsedPattern.getType() == Type.TARGETS_BELOW_DIRECTORY) {
+        if (laterParsedPattern.containsTBDForTBD(targetPattern)
+            == ContainsTBDForTBDResult.DIRECTORY_EXCLUSION_WOULD_BE_EXACT) {
+          return new TargetPatternKeyWithExclusionsResult(Optional.empty(), ImmutableList.of());
+        } else {
+          switch (targetPattern.containsTBDForTBD(laterParsedPattern)) {
+            case DIRECTORY_EXCLUSION_WOULD_BE_EXACT:
+              excludedDirectoriesBuilder.add(
+                  laterParsedPattern.getDirectoryForTargetsUnderDirectory().getPackageFragment());
+              break;
+            case DIRECTORY_EXCLUSION_WOULD_BE_TOO_BROAD:
+              indicesOfNegativePatternsThatNeedToBeIncludedBuilder.add(j);
+              break;
+            case OTHER:
+            default:
+              // Nothing to do with this pattern.
+          }
+
+        }
+      }
+    }
+    return new TargetPatternKeyWithExclusionsResult(
+        Optional.of(setExcludedDirectories(targetPatternKey, excludedDirectoriesBuilder.build())),
+        indicesOfNegativePatternsThatNeedToBeIncludedBuilder.build());
+  }
+
   public ResolvedTargets<Label> getTargets() {
     return targets;
   }
@@ -214,15 +299,17 @@ public final class TargetPatternValue implements SkyValue {
 
     ImmutableSet<PathFragment> getAllSubdirectoriesToExclude(
         Iterable<PathFragment> blacklistedPackagePrefixes) throws InterruptedException {
-      return getAllSubdirectoriesToExclude(
-          new InterruptibleSupplier.Instance<>(blacklistedPackagePrefixes));
+      ImmutableSet.Builder<PathFragment> excludedPathsBuilder = ImmutableSet.builder();
+      excludedPathsBuilder.addAll(getExcludedSubdirectories());
+      excludedPathsBuilder.addAll(getAllBlacklistedSubdirectoriesToExclude(
+          new InterruptibleSupplier.Instance<>(blacklistedPackagePrefixes)));
+      return excludedPathsBuilder.build();
     }
 
-    public ImmutableSet<PathFragment> getAllSubdirectoriesToExclude(
+    public ImmutableSet<PathFragment> getAllBlacklistedSubdirectoriesToExclude(
         InterruptibleSupplier<? extends Iterable<PathFragment>> blacklistedPackagePrefixes)
         throws InterruptedException {
-      ImmutableSet.Builder<PathFragment> excludedPathsBuilder = ImmutableSet.builder();
-      excludedPathsBuilder.addAll(getExcludedSubdirectories());
+      ImmutableSet.Builder<PathFragment> blacklistedPathsBuilder = ImmutableSet.builder();
       if (parsedPattern.getType() == Type.TARGETS_BELOW_DIRECTORY) {
         for (PathFragment blacklistedPackagePrefix : blacklistedPackagePrefixes.get()) {
           PackageIdentifier pkgIdForBlacklistedDirectorPrefix = PackageIdentifier.create(
@@ -230,11 +317,11 @@ public final class TargetPatternValue implements SkyValue {
               blacklistedPackagePrefix);
           if (parsedPattern.containsAllTransitiveSubdirectoriesForTBD(
               pkgIdForBlacklistedDirectorPrefix)) {
-            excludedPathsBuilder.add(blacklistedPackagePrefix);
+            blacklistedPathsBuilder.add(blacklistedPackagePrefix);
           }
         }
       }
-      return excludedPathsBuilder.build();
+      return blacklistedPathsBuilder.build();
     }
 
     @Override