Make selector list construction n^2 -> n efficient.

On the subject of simpler toString output (i.e. "selector" vs.
"selector({dictionary contents here})", I'm not changing that here
because there are consistency concerns. BuildType.SelectorList.toString
is defined to match lib.syntax.SelectorList's Skylark serialization.
That follows a standard pattern defined here:

https://github.com/bazelbuild/bazel/blob/67bd6fc6354f2abbbc149fcd0120228b538842d3/src/main/java/com/google/devtools/build/lib/skylarkinterface/SkylarkValue.java#L37

which has concerns about deserialization. If you want to take this further
we can discuss with the Skylark devs.

PiperOrigin-RevId: 164311511

2 files changed, 36 insertions, 30 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/packages/BuildType.java b/src/main/java/com/google/devtools/build/lib/packages/BuildType.java
index 4d21b53525..c2f191ce16 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/BuildType.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/BuildType.java
@@ -539,7 +539,7 @@ public final class BuildType {
         selectorValueList.add(new SelectorValue(element.getEntries(), element.getNoMatchError()));
       }
       try {
-        printer.repr(com.google.devtools.build.lib.syntax.SelectorList.of(selectorValueList));
+        printer.repr(com.google.devtools.build.lib.syntax.SelectorList.of(null, selectorValueList));
       } catch (EvalException e) {
         throw new IllegalStateException("this list should have been validated on creation");
       }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java b/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
index 098e7d9ae7..7ec367cb89 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
@@ -14,13 +14,14 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 import com.google.devtools.build.lib.util.Preconditions;
 import java.util.ArrayList;
-import java.util.Iterator;
+import java.util.Arrays;
 import java.util.List;
 
 /**
@@ -78,54 +79,59 @@ public final class SelectorList implements SkylarkValue {
   }
 
   /**
-   * Creates a list that concatenates two values, where each value may be either a native
-   * type or a select over that type.
+   * Creates a list that concatenates two values, where each value may be a native
+   * type, a select over that type, or a selector list over that type.
    *
    * @throws EvalException if the values don't have the same underlying type
    */
   public static SelectorList concat(Location location, Object value1, Object value2)
       throws EvalException {
-    ImmutableList.Builder<Object> builder = ImmutableList.builder();
-    Class<?> type1 = addValue(value1, builder);
-    Class<?> type2 = addValue(value2, builder);
-    if (!canConcatenate(type1, type2)) {
-      throw new EvalException(
-          location,
-          String.format(
-              "'+' operator applied to incompatible types (%s, %s)",
-              EvalUtils.getDataTypeName(value1, true),
-              EvalUtils.getDataTypeName(value2, true)));
-    }
-    return new SelectorList(type1, builder.build());
+    return of(location, Arrays.asList(value1, value2));
   }
 
   /**
-   * Creates a list consisting of the given selects.
+   * Creates a list from the given sequence of values, which must be non-empty. Each value may be
+   * a native type, a select over that type, or a selector list over that type.
+   *
+   * @throws EvalException if all values don't have the same underlying type
    */
-  public static SelectorList of(List<SelectorValue> selectors) throws EvalException {
-    Preconditions.checkArgument(!selectors.isEmpty());
-    Iterator<SelectorValue> it = selectors.iterator();
-    SelectorList list = SelectorList.of(it.next());
-    while (it.hasNext()) {
-      list = SelectorList.concat(null, list, it.next());
+  public static SelectorList of(Location location, Iterable<?> values) throws EvalException {
+    Preconditions.checkArgument(!Iterables.isEmpty(values));
+    ImmutableList.Builder<Object> elements = ImmutableList.builder();
+    Object firstValue = null;
+
+    for (Object value : values) {
+      if (value instanceof SelectorList) {
+        elements.addAll(((SelectorList) value).getElements());
+      } else {
+        elements.add(value);
+      }
+      if (firstValue == null) {
+        firstValue = value;
+      }
+      if (!canConcatenate(getNativeType(firstValue), getNativeType(value))) {
+        throw new EvalException(
+            location,
+            String.format(
+                "'+' operator applied to incompatible types (%s, %s)",
+                EvalUtils.getDataTypeName(firstValue, true),
+                EvalUtils.getDataTypeName(value, true)));
+      }
     }
-    return list;
+
+    return new SelectorList(getNativeType(firstValue), elements.build());
   }
 
   // TODO(bazel-team): match on the List interface, not the actual implementation. For now,
   // we verify this is the right class through test coverage.
   private static final Class<?> NATIVE_LIST_TYPE = ArrayList.class;
 
-  private static Class<?> addValue(Object value, ImmutableList.Builder<Object> builder) {
+  private static Class<?> getNativeType(Object value) {
     if (value instanceof SelectorList) {
-      SelectorList selectorList = (SelectorList) value;
-      builder.addAll(selectorList.getElements());
-      return selectorList.getType();
+      return ((SelectorList) value).getType();
     } else if (value instanceof SelectorValue) {
-      builder.add(value);
       return ((SelectorValue) value).getType();
     } else {
-      builder.add(value);
       return value.getClass();
     }
   }