Refine duplicate label checking for embedded selects. Before, we were

coarsely checking for duplicates *anywhere*, e.g.:

select({':a': ['a.cc'], ':b': ['a.cc']}) + select({':a': ['b.cc'], ':b': ['b.cc']})

would fail. But this case is okay because these duplicates are in mutually
exclusive select paths (so they could never appear together anyway).

The new checking logic is:
 - Duplicates can appear in different paths of the same select.
 - Duplicates can *not* appear within the same path of a select.
 - Duplicates can *not* appear across multiple selects (no matter what path -
   this is still stricter than we need to be, but there's no strong case
   for refining this case now).

--
MOS_MIGRATED_REVID=93447979

2 files changed, 35 insertions, 18 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
index 61c4f3871b..a0e740c743 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
@@ -22,7 +22,9 @@ import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.syntax.Label;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashMap;
+import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
@@ -131,6 +133,7 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper {
   public Set<Label> checkForDuplicateLabels(Attribute attribute) {
     String attrName = attribute.getName();
     Type<?> attrType = attribute.getType();
+    ImmutableSet.Builder<Label> duplicates = ImmutableSet.builder();
 
     Type.SelectorList<?> selectorList = getSelectorList(attribute.getName(), attrType);
     if (selectorList == null || selectorList.getSelectors().size() == 1) {
@@ -140,22 +143,35 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper {
       //     visitAttribute might be inefficient. But we have no choice but to iterate over all
       //     possible values (since we have to compute them), so we take the efficiency hit.
       //  3) "attr = select({...})". With just a single select, visitAttribute runs efficiently.
-      ImmutableSet.Builder<Label> duplicates = ImmutableSet.builder();
       for (Object value : visitAttribute(attrName, attrType)) {
         if (value != null) {
           duplicates.addAll(CollectionUtils.duplicatedElementsOf(
               ImmutableList.copyOf(attrType.getLabels(value))));
         }
       }
-      return duplicates.build();
     } else {
       // Multiple selects concatenated together. It's expensive to iterate over every possible
       // value, so instead collect all labels across all the selects and check for duplicates.
       // This is overly strict, since this counts duplicates across values. We can presumably
       // relax this if necessary, but doing so would incur the value iteration expense this
       // code path avoids.
-      return CollectionUtils.duplicatedElementsOf(getReachableLabels(attrName, false));
+      List<Label> combinedLabels = new LinkedList<>(); // Labels that appear across all selectors.
+      for (Type.Selector<?> selector : selectorList.getSelectors()) {
+        // Labels within a single selector. It's okay for there to be duplicates as long as
+        // they're in different selector paths (since only one path can actually get chosen).
+        Set<Label> selectorLabels = new LinkedHashSet<>();
+        for (Object selectorValue : selector.getEntries().values()) {
+          Collection<Label> labelsInSelectorValue = attrType.getLabels(selectorValue);
+          // Duplicates within a single path are not okay.
+          duplicates.addAll(CollectionUtils.duplicatedElementsOf(labelsInSelectorValue));
+          selectorLabels.addAll(labelsInSelectorValue);
+        }
+        combinedLabels.addAll(selectorLabels);
+      }
+      duplicates.addAll(CollectionUtils.duplicatedElementsOf(combinedLabels));
     }
+
+    return duplicates.build();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Type.java b/src/main/java/com/google/devtools/build/lib/packages/Type.java
index e197bb5464..b1ca03e8a0 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Type.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Type.java
@@ -33,6 +33,7 @@ import com.google.devtools.build.lib.util.LoggingUtil;
 import com.google.devtools.build.lib.util.StringCanonicalizer;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -163,12 +164,12 @@ public abstract class Type<T> {
    * be careful about defining default instances in base types that get auto-inherited
    * by their children. Keep all definitions as explicit as possible.
    */
-  public abstract Iterable<Label> getLabels(Object value);
+  public abstract Collection<Label> getLabels(Object value);
 
   /**
    * {@link #getLabels} return value for types that don't contain labels.
    */
-  private static final Iterable<Label> NO_LABELS_HERE = ImmutableList.of();
+  private static final Collection<Label> NO_LABELS_HERE = ImmutableList.of();
 
   /**
    * Implementation of concatenation for this type (e.g. "val1 + val2"). Returns null to
@@ -254,7 +255,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return NO_LABELS_HERE;
     }
 
@@ -394,7 +395,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return NO_LABELS_HERE;
     }
 
@@ -421,7 +422,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return NO_LABELS_HERE;
     }
 
@@ -461,7 +462,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return NO_LABELS_HERE;
     }
 
@@ -520,7 +521,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return NO_LABELS_HERE;
     }
 
@@ -563,7 +564,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return NO_LABELS_HERE;
     }
 
@@ -625,7 +626,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return cast(value).getLabels();
     }
   }
@@ -642,7 +643,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return ImmutableList.of(cast(value));
     }
 
@@ -694,7 +695,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return NO_LABELS_HERE;
     }
 
@@ -733,7 +734,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object what) {
+    public Collection<Label> getLabels(Object what) {
       return NO_LABELS_HERE;
     }
 
@@ -760,7 +761,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       return ImmutableList.of(cast(value));
     }
 
@@ -856,7 +857,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       ImmutableList.Builder<Label> labels = ImmutableList.builder();
       for (Map.Entry<KeyT, ValueT> entry : cast(value).entrySet()) {
         labels.addAll(keyType.getLabels(entry.getKey()));
@@ -898,7 +899,7 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Iterable<Label> getLabels(Object value) {
+    public Collection<Label> getLabels(Object value) {
       ImmutableList.Builder<Label> labels = ImmutableList.builder();
       for (ElemT entry : cast(value)) {
         labels.addAll(elemType.getLabels(entry));