Implement smart negation for target pattern sequences

This change uses the types of target patterns, and the order they
appear in the sequence, to construct a more efficiently processable
sequence of target pattern keys. Redundant patterns are eliminated and
negated TargetsBelowDirectory patterns are excluded from higher-up
positive patterns.

--
MOS_MIGRATED_REVID=94909360

1 files changed, 17 insertions, 12 deletions

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 1f665e0152..1f1b369396 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,7 +23,6 @@ import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
-import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
@@ -112,9 +111,14 @@ public final class TargetPatternValue implements SkyValue {
 
   /**
    * Returns an iterable of {@link TargetPatternSkyKeyOrException}, with {@link TargetPatternKey}
-   * arguments, in the same order as the list of patterns provided as input. If a provided pattern
-   * fails to parse, the element in the returned iterable corresponding to it will throw when its
-   * {@link TargetPatternSkyKeyOrException#getSkyKey} method is called.
+   * arguments. If a provided pattern fails to parse, an element in the returned iterable will
+   * throw when its {@link TargetPatternSkyKeyOrException#getSkyKey} method is called and will
+   * return the failing pattern when its {@link
+   * TargetPatternSkyKeyOrException#getOriginalPattern} method is called.
+   *
+   * <p>There may be fewer returned elements than patterns provided as input. This function may
+   * combine patterns to return an iterable of SkyKeys that is equivalent but more efficient to
+   * evaluate.
    *
    * @param patterns The list of patterns, eg "-foo/biz...". If a pattern's first character is "-",
    *     it is treated as a negative pattern.
@@ -125,23 +129,24 @@ public final class TargetPatternValue implements SkyValue {
   public static Iterable<TargetPatternSkyKeyOrException> keys(List<String> patterns,
       FilteringPolicy policy, String offset) {
     TargetPattern.Parser parser = new TargetPattern.Parser(offset);
+    AggregatedPatterns aggregatedPatterns = new AggregatedPatterns(policy, offset);
     ImmutableList.Builder<TargetPatternSkyKeyOrException> builder = ImmutableList.builder();
     for (String pattern : patterns) {
       boolean positive = !pattern.startsWith("-");
       String absoluteValueOfPattern = positive ? pattern : pattern.substring(1);
-      TargetPattern targetPattern;
       try {
-        targetPattern = parser.parse(absoluteValueOfPattern);
+        aggregatedPatterns.addPattern(
+            new SignedPattern(positive, parser.parse(absoluteValueOfPattern)));
       } catch (TargetParsingException e) {
         builder.add(new TargetPatternSkyKeyException(e, absoluteValueOfPattern));
-        continue;
       }
-      TargetPatternKey targetPatternKey = new TargetPatternKey(targetPattern,
-          positive ? policy : FilteringPolicies.NO_FILTER, /*isNegative=*/!positive, offset,
-          ImmutableSet.<String>of());
-      SkyKey skyKey = new SkyKey(SkyFunctions.TARGET_PATTERN, targetPatternKey);
-      builder.add(new TargetPatternSkyKeyValue(skyKey));
     }
+
+    for (TargetPatternKey patternKey : aggregatedPatterns.build()) {
+      builder.add(
+          new TargetPatternSkyKeyValue(new SkyKey(SkyFunctions.TARGET_PATTERN, patternKey)));
+    }
+
     return builder.build();
   }