Configurable attributes: support embeddable selects. With this

change, the following syntax:

  deps = [':always'] + select({':a': [':adep'], ':b': [':bdep']})

or

  deps = select({':a': [':adep'], ':b': [':bdep']})
       + select({':c': [':cdep'], ':d': [':ddep']})

works.

--
MOS_MIGRATED_REVID=91016337

12 files changed, 327 insertions, 72 deletions

diff --git a/src/main/java/com/google/devtools/build/docgen/templates/be-footer.html b/src/main/java/com/google/devtools/build/docgen/templates/be-footer.html
index 5c5cef1295..94b7a1cfba 100644
--- a/src/main/java/com/google/devtools/build/docgen/templates/be-footer.html
+++ b/src/main/java/com/google/devtools/build/docgen/templates/be-footer.html
@@ -550,10 +550,11 @@ sh_binary(
     considered to match if no other condition matches. If this condition
     is left out, some other rule must match to avoid an error.
   </li>
-  <li><code>select</code> cannot currently be embedded <i>within</i> an
-    attribute assignment. In other words, <code>srcs = ["common.sh"]
-    + select({ "conditionA": ["myrule_a.sh"], ...})</code> does not
-    currently work.
+  <li><code>select</code> can be embedded <i>inside</i> a larger
+    attribute assignment. So <code>srcs = ["common.sh"]
+    + select({ ":conditionA": ["myrule_a.sh"], ...})</code> and <code>
+    srcs = select({ ":conditionA": ["a.sh"]}) + select({ ":conditionB":
+    ["b.sh"]})</code> are valid expressions.
   </li>
   <li><code>select</code> works with most, but not all, attributes.
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java
index 67ff7a23c7..bd0fd68d57 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java
@@ -25,6 +25,8 @@ import com.google.devtools.build.lib.packages.Type;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Label;
 
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
@@ -97,12 +99,21 @@ public class ConfiguredAttributeMapper extends AbstractAttributeMapper {
    * can't be resolved due to intrinsic contradictions in the configuration.
    */
   private <T> T getAndValidate(String attributeName, Type<T> type) throws EvalException  {
-    Type.Selector<T> selector = getSelector(attributeName, type);
-    if (selector == null) {
+    Type.SelectorList<T> selectorList = getSelectorList(attributeName, type);
+    if (selectorList == null) {
       // This is a normal attribute.
       return super.get(attributeName, type);
     }
 
+    List<T> resolvedList = new ArrayList<>();
+    for (Type.Selector<T> selector : selectorList.getSelectors()) {
+      resolvedList.add(resolveSelector(attributeName, selector));
+    }
+    return resolvedList.size() == 1 ? resolvedList.get(0) : type.concat(resolvedList);
+  }
+
+  private <T> T resolveSelector(String attributeName, Type.Selector<T> selector)
+      throws EvalException {
     ConfigMatchingProvider matchingCondition = null;
     T matchingValue = null;
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java b/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java
index 108a577311..2c0b98a254 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java
@@ -53,7 +53,7 @@ public final class RedirectChaser {
      */
     public <T> T getAndValidate(String attributeName, Type<T> type)
         throws InvalidConfigurationException {
-      if (getSelector(attributeName, type) != null) {
+      if (getSelectorList(attributeName, type) != null) {
         throw new InvalidConfigurationException
             ("The value of '" + attributeName + "' cannot be configuration-dependent");
       }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java
index f3875b65a9..544435afd4 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java
@@ -161,29 +161,30 @@ public abstract class AbstractAttributeMapper implements AttributeMap {
   protected abstract <T> Iterable<T> visitAttribute(String attributeName, Type<T> type);
 
   /**
-   * Returns a {@link Type.Selector} for the given attribute if the attribute is configurable
+   * Returns a {@link Type.SelectorList} for the given attribute if the attribute is configurable
    * for this rule, null otherwise.
    *
-   * @return a {@link Type.Selector} if the attribute takes the form
+   * @return a {@link Type.SelectorList} if the attribute takes the form
    *     "attrName = { 'a': value1_of_type_T, 'b': value2_of_type_T }") for this rule, null
    *     if it takes the form "attrName = value_of_type_T", null if it doesn't exist
    * @throws IllegalArgumentException if the attribute is configurable but of the wrong type
    */
   @Nullable
-  protected <T> Type.Selector<T> getSelector(String attributeName, Type<T> type) {
+  @SuppressWarnings("unchecked")
+  protected <T> Type.SelectorList<T> getSelectorList(String attributeName, Type<T> type) {
     Integer index = ruleClass.getAttributeIndex(attributeName);
     if (index == null) {
       return null;
     }
     Object attrValue = attributes.getAttributeValue(index);
-    if (!(attrValue instanceof Type.Selector<?>)) {
+    if (!(attrValue instanceof Type.SelectorList)) {
       return null;
     }
-    if (((Type.Selector<?>) attrValue).getOriginalType() != type) {
+    if (((Type.SelectorList) attrValue).getOriginalType() != type) {
       throw new IllegalArgumentException("Attribute " + attributeName
           + " is not of type " + type + " in rule " + ruleLabel);
     }
-    return (Type.Selector<T>) attrValue;
+    return (Type.SelectorList<T>) attrValue;
   }
 
   /**
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 682d2dd698..b51b195ebc 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
@@ -65,12 +65,10 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper {
     super.visitLabels(observer);
     for (String attrName : getAttributeNames()) {
       Attribute attribute = getAttributeDefinition(attrName);
-      Type.Selector<?> selector = getSelector(attrName, attribute.getType());
-      if (selector != null) {
-        for (Label configLabel : selector.getEntries().keySet()) {
-          if (!Type.Selector.isReservedLabel(configLabel)) {
-            observer.acceptLabelAttribute(configLabel, attribute);
-          }
+      Type.SelectorList<?> selectorList = getSelectorList(attrName, attribute.getType());
+      if (selectorList != null) {
+        for (Label configLabel : selectorList.getKeyLabels()) {
+          observer.acceptLabelAttribute(configLabel, attribute);
         }
       }
     }
@@ -82,12 +80,10 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper {
   @Override
   public <T> Iterable<T> visitAttribute(String attributeName, Type<T> type) {
     // If this attribute value is configurable, visit all possible values.
-    Type.Selector<T> selector = getSelector(attributeName, type);
-    if (selector != null) {
+    Type.SelectorList<T> selectorList = getSelectorList(attributeName, type);
+    if (selectorList != null) {
       ImmutableList.Builder<T> builder = ImmutableList.builder();
-      for (Map.Entry<Label, T> entry : selector.getEntries().entrySet()) {
-        builder.add(entry.getValue());
-      }
+      visitConfigurableAttribute(selectorList.getSelectors(), type, null, builder);
       return builder.build();
     }
 
@@ -116,6 +112,33 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper {
   }
 
   /**
+   * Determines all possible values a configurable attribute can take and places each one into
+   * valuesBuilder.
+   */
+  private <T> void visitConfigurableAttribute(List<Type.Selector<T>> selectors, Type<T> type,
+      T currentValueSoFar, ImmutableList.Builder<T> valuesBuilder) {
+
+    // TODO(bazel-team): minimize or eliminate uses of this interface. It necessarily grows
+    // exponentially with the number of selects in the attribute. Is that always necessary?
+    // For example, dependency resolution just needs to know every possible label an attribute
+    // might reference, but it doesn't need to know the exact combination of labels that make
+    // up a value.
+    if (selectors.isEmpty()) {
+      valuesBuilder.add(Preconditions.checkNotNull(currentValueSoFar));
+    } else {
+      Type.Selector<T> firstSelector = selectors.get(0);
+      List<Type.Selector<T>> remainingSelectors = selectors.subList(1, selectors.size());
+      for (T branchedValue : firstSelector.getEntries().values()) {
+        visitConfigurableAttribute(remainingSelectors, type,
+            currentValueSoFar == null
+                ? branchedValue
+                : type.concat(ImmutableList.of(currentValueSoFar, branchedValue)),
+            valuesBuilder);
+      }
+    }
+  }
+
+  /**
    * Given (possibly configurable) attributes that a computed default depends on, creates an
    * {attrName -> attrValue} map for every possible combination of those attribute values and
    * returns a list of all the maps. This defines the complete dependency space that can affect
diff --git a/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java
index 57d986596b..63ada93705 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/MethodLibrary.java
@@ -37,6 +37,7 @@ import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Function;
 import com.google.devtools.build.lib.syntax.MixedModeFunction;
+import com.google.devtools.build.lib.syntax.SelectorList;
 import com.google.devtools.build.lib.syntax.SelectorValue;
 import com.google.devtools.build.lib.syntax.SkylarkBuiltin;
 import com.google.devtools.build.lib.syntax.SkylarkBuiltin.Param;
@@ -829,7 +830,7 @@ public class MethodLibrary {
           throw new EvalException(ast.getLocation(),
               "select({...}) argument isn't a dictionary");
         }
-        return new SelectorValue((Map<?, ?>) dict);
+        return SelectorList.of(new SelectorValue((Map<?, ?>) dict));
       }
     };
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RawAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/RawAttributeMapper.java
index 7de23d7c19..64c22bf35d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RawAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RawAttributeMapper.java
@@ -71,10 +71,11 @@ public class RawAttributeMapper extends AbstractAttributeMapper {
       return get(attributeName, type);
     }
 
-    Type.Selector<List<T>> selector = getSelector(attributeName, type);
     ImmutableSet.Builder<T> mergedValues = ImmutableSet.builder();
-    for (List<T> configuredList : selector.getEntries().values()) {
-      mergedValues.addAll(configuredList);
+    for (Type.Selector<List<T>> selector : getSelectorList(attributeName, type).getSelectors()) {
+      for (List<T> configuredList : selector.getEntries().values()) {
+        mergedValues.addAll(configuredList);
+      }
     }
     return mergedValues.build();
   }
@@ -84,7 +85,7 @@ public class RawAttributeMapper extends AbstractAttributeMapper {
    * otherwise.
    */
   public <T> boolean isConfigurable(String attributeName, Type<T> type) {
-    return getSelector(attributeName, type) != null;
+    return getSelectorList(attributeName, type) != null;
   }
 
   /**
@@ -92,7 +93,14 @@ public class RawAttributeMapper extends AbstractAttributeMapper {
    * keys. Else returns an empty list.
    */
   public <T> Iterable<Label> getConfigurabilityKeys(String attributeName, Type<T> type) {
-    Type.Selector<T> selector = getSelector(attributeName, type);
-    return selector == null ? ImmutableList.<Label>of() : selector.getEntries().keySet();
+    Type.SelectorList<T> selectorList = getSelectorList(attributeName, type);
+    if (selectorList == null) {
+      return ImmutableList.of();
+    }
+    ImmutableList.Builder<Label> builder = ImmutableList.builder();
+    for (Type.Selector<T> selector : selectorList.getSelectors()) {
+      builder.addAll(selector.getEntries().keySet());
+    }
+    return builder.build();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index d265a44a6a..4521b3304c 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -1278,13 +1278,9 @@ public final class RuleClass {
 
     Set<Label> configLabels = new LinkedHashSet<>();
     for (Attribute attr : rule.getAttributes()) {
-      Type.Selector<?> selector = attributes.getSelector(attr.getName(), attr.getType());
-      if (selector != null) {
-        for (Label label : selector.getEntries().keySet()) {
-          if (!Type.Selector.isReservedLabel(label)) {
-            configLabels.add(label);
-          }
-        }
+      Type.SelectorList<?> selectors = attributes.getSelectorList(attr.getName(), attr.getType());
+      if (selectors != null) {
+        configLabels.addAll(selectors.getKeyLabels());
       }
     }
 
@@ -1444,7 +1440,7 @@ public final class RuleClass {
       String what = "attribute '" + attrName + "' in '" + name + "' rule";
       converted = attr.getType().selectableConvert(attrVal, what, rule.getLabel());
 
-      if ((converted instanceof Type.Selector<?>) && !attr.isConfigurable()) {
+      if ((converted instanceof Type.SelectorList<?>) && !attr.isConfigurable()) {
         rule.reportError(rule.getLabel() + ": attribute \"" + attr.getName()
             + "\" is not configurable", eventHandler);
         return null;
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 e869096e95..e197bb5464 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
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -131,10 +132,13 @@ public abstract class Type<T> {
    */
   public Object selectableConvert(Object x, String what, @Nullable Label currentRule)
       throws ConversionException {
-    if (x instanceof SelectorValue) {
-      return new Selector<T>(((SelectorValue) x).getDictionary(), what, currentRule, this);
+    if (x instanceof com.google.devtools.build.lib.syntax.SelectorList) {
+      return new SelectorList<T>(
+          ((com.google.devtools.build.lib.syntax.SelectorList) x).getElements(),
+          what, currentRule, this);
+    } else {
+      return convert(x, what, currentRule);
     }
-    return convert(x, what, currentRule);
   }
 
   public abstract T cast(Object value);
@@ -167,6 +171,14 @@ public abstract class Type<T> {
   private static final Iterable<Label> NO_LABELS_HERE = ImmutableList.of();
 
   /**
+   * Implementation of concatenation for this type (e.g. "val1 + val2"). Returns null to
+   * designate concatenation isn't supported.
+   */
+  public T concat(Iterable<T> elements) {
+    return null;
+  }
+
+  /**
    * Converts an initialized Type object into a tag set representation.
    * This operation is only valid for certain sub-Types which are guaranteed
    * to be properly initialized.
@@ -426,6 +438,15 @@ public abstract class Type<T> {
       }
       return (Integer) x;
     }
+
+    @Override
+    public Integer concat(Iterable<Integer> elements) {
+      int ans = 0;
+      for (Integer elem : elements) {
+        ans += elem;
+      }
+      return Integer.valueOf(ans);
+    }
   }
 
   private static class BooleanType extends Type<Boolean> {
@@ -560,6 +581,11 @@ public abstract class Type<T> {
       return StringCanonicalizer.intern((String) x);
     }
 
+    @Override
+    public String concat(Iterable<String> elements) {
+      return Joiner.on("").join(elements);
+    }
+
     /**
      * A String is representable as a set containing its value.
      */
@@ -771,35 +797,35 @@ public abstract class Type<T> {
   /**
    * A type to support dictionary attributes.
    */
-  public static class DictType<KEY, VALUE> extends Type<Map<KEY, VALUE>> {
+  public static class DictType<KeyT, ValueT> extends Type<Map<KeyT, ValueT>> {
 
-    private final Type<KEY> keyType;
-    private final Type<VALUE> valueType;
+    private final Type<KeyT> keyType;
+    private final Type<ValueT> valueType;
 
-    private final Map<KEY, VALUE> empty = ImmutableMap.of();
+    private final Map<KeyT, ValueT> empty = ImmutableMap.of();
 
     private static <KEY, VALUE> DictType<KEY, VALUE> create(
         Type<KEY> keyType, Type<VALUE> valueType) {
       return new DictType<>(keyType, valueType);
     }
 
-    private DictType(Type<KEY> keyType, Type<VALUE> valueType) {
+    private DictType(Type<KeyT> keyType, Type<ValueT> valueType) {
       this.keyType = keyType;
       this.valueType = valueType;
     }
 
-    public Type<KEY> getKeyType() {
+    public Type<KeyT> getKeyType() {
       return keyType;
     }
 
-    public Type<VALUE> getValueType() {
+    public Type<ValueT> getValueType() {
       return valueType;
     }
 
     @SuppressWarnings("unchecked")
     @Override
-    public Map<KEY, VALUE> cast(Object value) {
-      return (Map<KEY, VALUE>) value;
+    public Map<KeyT, ValueT> cast(Object value) {
+      return (Map<KeyT, ValueT>) value;
     }
 
     @Override
@@ -808,13 +834,13 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Map<KEY, VALUE> convert(Object x, String what, Label currentRule)
+    public Map<KeyT, ValueT> convert(Object x, String what, Label currentRule)
         throws ConversionException {
       if (!(x instanceof Map<?, ?>)) {
         throw new ConversionException(String.format(
             "Expected a map for dictionary but got a %s", x.getClass().getName())); 
       }
-      ImmutableMap.Builder<KEY, VALUE> result = ImmutableMap.builder();
+      ImmutableMap.Builder<KeyT, ValueT> result = ImmutableMap.builder();
       Map<?, ?> o = (Map<?, ?>) x;
       for (Entry<?, ?> elem : o.entrySet()) {
         result.put(
@@ -825,14 +851,14 @@ public abstract class Type<T> {
     }
 
     @Override
-    public Map<KEY, VALUE> getDefaultValue() {
+    public Map<KeyT, ValueT> getDefaultValue() {
       return empty;
     }
 
     @Override
     public Iterable<Label> getLabels(Object value) {
       ImmutableList.Builder<Label> labels = ImmutableList.builder();
-      for (Map.Entry<KEY, VALUE> entry : cast(value).entrySet()) {
+      for (Map.Entry<KeyT, ValueT> entry : cast(value).entrySet()) {
         labels.addAll(keyType.getLabels(entry.getKey()));
         labels.addAll(valueType.getLabels(entry.getValue()));
       }
@@ -841,40 +867,40 @@ public abstract class Type<T> {
   }
 
   /** A type for lists of a given element type */
-  public static class ListType<ELEM> extends Type<List<ELEM>> {
+  public static class ListType<ElemT> extends Type<List<ElemT>> {
 
-    private final Type<ELEM> elemType;
+    private final Type<ElemT> elemType;
 
-    private final List<ELEM> empty = ImmutableList.of();
+    private final List<ElemT> empty = ImmutableList.of();
 
     private static <ELEM> ListType<ELEM> create(Type<ELEM> elemType) {
       return new ListType<>(elemType);
     }
 
-    private ListType(Type<ELEM> elemType) {
+    private ListType(Type<ElemT> elemType) {
       this.elemType = elemType;
     }
 
     @SuppressWarnings("unchecked")
     @Override
-    public List<ELEM> cast(Object value) {
-      return (List<ELEM>) value;
+    public List<ElemT> cast(Object value) {
+      return (List<ElemT>) value;
     }
 
     @Override
-    public Type<ELEM> getListElementType() {
+    public Type<ElemT> getListElementType() {
       return elemType;
     }
 
     @Override
-    public List<ELEM> getDefaultValue() {
+    public List<ElemT> getDefaultValue() {
       return empty;
     }
 
     @Override
     public Iterable<Label> getLabels(Object value) {
       ImmutableList.Builder<Label> labels = ImmutableList.builder();
-      for (ELEM entry : cast(value)) {
+      for (ElemT entry : cast(value)) {
         labels.addAll(elemType.getLabels(entry));
       }
       return labels.build();
@@ -886,15 +912,15 @@ public abstract class Type<T> {
     }
 
     @Override
-    public List<ELEM> convert(Object x, String what, Label currentRule)
+    public List<ElemT> convert(Object x, String what, Label currentRule)
         throws ConversionException {
       if (!(x instanceof Iterable<?>)) {
         throw new ConversionException(this, x, what);
       }
-      List<ELEM> result = new ArrayList<>();
+      List<ElemT> result = new ArrayList<>();
       int index = 0;
       for (Object elem : (Iterable<?>) x) {
-        ELEM converted = elemType.convert(elem, "element " + index + " of " + what, currentRule);
+        ElemT converted = elemType.convert(elem, "element " + index + " of " + what, currentRule);
         if (converted != null) {
           result.add(converted);
         } else {
@@ -913,6 +939,15 @@ public abstract class Type<T> {
       }
     }
 
+    @Override
+    public List<ElemT> concat(Iterable<List<ElemT>> elements) {
+      ImmutableList.Builder<ElemT> builder = ImmutableList.builder();
+      for (List<ElemT> list : elements) {
+        builder.addAll(list);
+      }
+      return builder.build();
+    }
+
     /**
      * A list is representable as a tag set as the contents of itself expressed
      * as Strings. So a {@code List<String>} is effectively converted to a {@code Set<String>}.
@@ -925,8 +960,8 @@ public abstract class Type<T> {
       }
       Set<String> tags = new LinkedHashSet<>();
       @SuppressWarnings("unchecked")
-      List<ELEM> itemsAsListofElem = (List<ELEM>) items;
-      for (ELEM element : itemsAsListofElem) {
+      List<ElemT> itemsAsListofElem = (List<ElemT>) items;
+      for (ElemT element : itemsAsListofElem) {
         tags.add(element.toString());
       }
       return tags;
@@ -978,7 +1013,6 @@ public abstract class Type<T> {
    * objects of the attribute's native Type.
    */
   public static final class Selector<T> {
-
     private final Type<T> originalType;
     private final Map<Label, T> map;
     private final Label defaultConditionLabel;
@@ -1001,7 +1035,6 @@ public abstract class Type<T> {
         throw new IllegalStateException(DEFAULT_CONDITION_KEY + " is not a valid label");
       }
 
-
       this.originalType = originalType;
       Map<Label, T> result = Maps.newLinkedHashMap();
       boolean foundDefaultCondition = false;
@@ -1053,4 +1086,67 @@ public abstract class Type<T> {
       return label.toString().equals(DEFAULT_CONDITION_KEY);
     }
   }
+
+  /**
+   * Holds an ordered collection of {@link Selector}s. This is used to support
+   * {@code attr = rawValue + select(...) + select(...) + ..."} syntax. For consistency's
+   * sake, raw values are stored as selects with only a default condition.
+   */
+  public static final class SelectorList<T> {
+    private final Type<T> originalType;
+    private final List<Selector<T>> elements;
+
+    @VisibleForTesting
+    SelectorList(List<Object> x, String what, @Nullable Label currentRule,
+        Type<T> originalType) throws ConversionException {
+      if (x.size() > 1 && originalType.concat(ImmutableList.<T>of()) == null) {
+        throw new ConversionException(
+            String.format("type '%s' doesn't support select concatenation", originalType));
+      }
+
+      ImmutableList.Builder<Selector<T>> builder = ImmutableList.builder();
+      for (Object elem : x) {
+        if (elem instanceof SelectorValue) {
+          builder.add(new Selector<T>(((SelectorValue) elem).getDictionary(), what,
+              currentRule, originalType));
+        } else {
+          T directValue = originalType.convert(elem, what, currentRule);
+          builder.add(new Selector<T>(ImmutableMap.of(Selector.DEFAULT_CONDITION_KEY, directValue),
+              what, currentRule, originalType));
+        }
+      }
+      this.originalType = originalType;
+      this.elements = builder.build();
+    }
+
+    /**
+     * Returns a syntactically order-preserved list of all values and selectors for this attribute.
+     */
+    public List<Selector<T>> getSelectors() {
+      return elements;
+    }
+
+    /**
+     * Returns the native Type for this attribute (i.e. what this would be if it wasn't a
+     * selector list).
+     */
+    public Type<T> getOriginalType() {
+      return originalType;
+    }
+
+    /**
+     * Returns the labels of all configurability keys across all selects in this expression.
+     */
+    public Set<Label> getKeyLabels() {
+      ImmutableSet.Builder<Label> keys = ImmutableSet.builder();
+      for (Selector<T> selector : getSelectors()) {
+         for (Label label : selector.getEntries().keySet()) {
+           if (!Selector.isReservedLabel(label)) {
+             keys.add(label);
+           }
+         }
+      }
+      return keys.build();
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
index 5624ba76ec..dc97212cef 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
@@ -130,6 +130,11 @@ public final class BinaryOperatorExpression extends Expression {
           }
         }
 
+        if (lval instanceof SelectorValue || rval instanceof SelectorValue
+            || lval instanceof SelectorList || rval instanceof SelectorList) {
+          return SelectorList.concat(getLocation(), lval, rval);
+        }
+
         if (lval instanceof SkylarkList && rval instanceof SkylarkList) {
           return SkylarkList.concat((SkylarkList) lval, (SkylarkList) rval, getLocation());
         }
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
new file mode 100644
index 0000000000..f923e830ac
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
@@ -0,0 +1,105 @@
+// Copyright 2015 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.syntax;
+
+import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.events.Location;
+
+import java.util.List;
+
+/**
+ * An attribute value consisting of a concatenation of native types and selects, e.g:
+ *
+ * <pre>
+ *   rule(
+ *       name = 'myrule',
+ *       deps =
+ *           [':defaultdep']
+ *           + select({
+ *               'a': [':adep'],
+ *               'b': [':bdep'],})
+ *           + select({
+ *               'c': [':cdep'],
+ *               'd': [':ddep'],})
+ *   )
+ * </pre>
+ */
+public final class SelectorList {
+  private final Class<?> type;
+  private final List<Object> elements;
+
+  private SelectorList(Class<?> type, List<Object> elements) {
+    this.type = type;
+    this.elements = elements;
+  }
+
+  /**
+   * Returns an ordered list of the elements in this expression. Each element may be a
+   * native type or a select.
+   */
+  public List<Object> getElements() {
+    return elements;
+  }
+
+  /**
+   * Returns the native type contained by this expression.
+   */
+  private Class<?> getType() {
+    return type;
+  }
+
+  /**
+   * Creates a "wrapper" list that consists of a single select.
+   */
+  public static SelectorList of(SelectorValue selector) {
+    return new SelectorList(selector.getType(), ImmutableList.<Object>of(selector));
+  }
+
+  /**
+   * Creates a list that concatenates two values, where each value may be either a native
+   * type or a select 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 (type1 != type2) {
+      throw new EvalException(location, "'+' operator applied to incompatible types");
+    }
+    return new SelectorList(type1, builder.build());
+  }
+  
+  private static Class<?> addValue(Object value, ImmutableList.Builder<Object> builder) {
+    if (value instanceof SelectorList) {
+      SelectorList selectorList = (SelectorList) value;
+      builder.addAll(selectorList.getElements());
+      return selectorList.getType();
+    } else if (value instanceof SelectorValue) {
+      builder.add(value);
+      return ((SelectorValue) value).getType();
+    } else {
+      builder.add(value);
+      return value.getClass();
+    }
+  }
+
+  @Override
+  public String toString() {
+    return Joiner.on(" + ").join(elements);
+  }
+}
\ No newline at end of file
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java b/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
index 4fb3bdb4b5..5cdbb0b16b 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.collect.Iterables;
+
 import java.util.Map;
 
 /**
@@ -28,16 +30,22 @@ import java.util.Map;
  * </pre>
  */
 public final class SelectorValue {
-  Map<?, ?> dictionary;
+  private final Map<?, ?> dictionary;
+  private final Class<?> type;
 
   public SelectorValue(Map<?, ?> dictionary) {
     this.dictionary = dictionary;
+    this.type = dictionary.isEmpty() ? null : Iterables.get(dictionary.values(), 0).getClass();
   }
 
   public Map<?, ?> getDictionary() {
     return dictionary;
   }
 
+  Class<?> getType() {
+    return type;
+  }
+
   @Override
   public String toString() {
     return "selector({...})";