Do not take all possible values of an attribute for selector lists of list types when running query output. Instead, simply return a list of list types, each list type being the concatenation of each of the possible outputs in each select.

RELNOTES:
Make querying attributes formed by selector lists of list types more efficient by no longer listing every possible combination of attribute value but by more compactly storing the possible values of the list.
PiperOrigin-RevId: 160326041

2 files changed, 36 insertions, 1 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 73d786bf5a..256cf93e6b 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
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.packages;
 
-
 import com.google.common.base.Verify;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -26,6 +25,7 @@ import com.google.devtools.build.lib.packages.BuildType.Selector;
 import com.google.devtools.build.lib.packages.BuildType.SelectorList;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.syntax.Type.LabelVisitor;
+import com.google.devtools.build.lib.syntax.Type.ListType;
 import com.google.devtools.build.lib.util.Preconditions;
 import java.util.ArrayList;
 import java.util.HashMap;
@@ -209,6 +209,33 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper {
   }
 
   /**
+   * If the attribute is a selector list of list type, then this method returns a list with number
+   * of elements equal to the number of select statements in the selector list. Each element of this
+   * list is equal to concatenating every possible attribute value in a single select statement.
+   * The conditions themselves in the select statements are completely ignored. Returns {@code null}
+   * if the attribute isn't of the desired format.
+   *
+   * As an example, if we have select({a: ["a"], b: ["a", "b"]}) + select({a: ["c", "d"], c: ["e"])
+   * The output will be [["a", "a", "b"], ["c", "d", "e"]]. The idea behind this structure is that
+   * at least some of the structure in the original selector list is preserved and we know any
+   * possible attribute value is the result of concatenating some sublist of each element.
+   */
+  @Nullable
+  public <T> Iterable<T> getConcatenatedSelectorListsOfListType(
+      String attributeName, Type<T> type) {
+    SelectorList<T> selectorList = getSelectorList(attributeName, type);
+    if (selectorList != null && type instanceof ListType) {
+      List<T> selectList = new ArrayList<>();
+
+      for (Selector<T> selector : selectorList.getSelectors()) {
+        selectList.add(type.concat(selector.getEntries().values()));
+      }
+      return ImmutableList.copyOf(selectList);
+    }
+    return null;
+  }
+
+  /**
    * Returns a list of all possible values an attribute can take for this rule.
    *
    * <p>Note that when an attribute uses multiple selects, or is a {@link Attribute.ComputedDefault}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
index 48923a3e83..4b732e1c15 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
@@ -18,6 +18,7 @@ import com.google.common.base.Function;
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.CompactHashSet;
@@ -809,6 +810,7 @@ public abstract class OutputFormatter implements Serializable {
     }
 
     AggregatingAttributeMapper attributeMap = AggregatingAttributeMapper.of(rule);
+    Iterable<?> list;
     if (attr.getType().equals(BuildType.LABEL_LIST)
         && attributeMap.isConfigurable(attr.getName())) {
       // TODO(gregce): Expand this to all collection types (we don't do this for scalars because
@@ -819,7 +821,13 @@ public abstract class OutputFormatter implements Serializable {
           ImmutableList.<Object>of(
               attributeMap.getReachableLabels(attr.getName(), /*includeSelectKeys=*/false)),
           source);
+    } else if ((list =
+            attributeMap.getConcatenatedSelectorListsOfListType(
+                attr.getName(), attr.getType()))
+        != null) {
+      return new PossibleAttributeValues(Lists.newArrayList(list), source);
     } else {
+      // The call to getPossibleAttributeValues below is especially slow with selector lists.
       return new PossibleAttributeValues(attributeMap.getPossibleAttributeValues(rule, attr),
           source);
     }