Introduces action_config. Does this by:

1) Introducing the action_config message in the crosstool protobuf definition.  The only part of that definition that are implemented in this CL is the "tool" section, other parts will be implemented in future CLs.  The proto fields are here now to avoid being delayed by release cycles at each step of the implementation.

2) Refactoring the implementation of the "feature algebra" that computes the enabled features for a given toolchain.  An interface called "CrosstoolActivatable" is used to represent any participant int the feature algebra, and can be either a feature or an action_config.

--
MOS_MIGRATED_REVID=118943663

3 files changed, 570 insertions, 144 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
index f50e80663b..b7bf3f48cc 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
@@ -15,6 +15,9 @@
 package com.google.devtools.build.lib.rules.cpp;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Optional;
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicate;
 import com.google.common.cache.CacheBuilder;
 import com.google.common.cache.CacheLoader;
 import com.google.common.cache.LoadingCache;
@@ -22,9 +25,12 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.view.config.crosstool.CrosstoolConfig.CToolchain;
+import com.google.devtools.build.lib.view.config.crosstool.CrosstoolConfig.CToolchain.Tool;
 
 import java.io.IOException;
 import java.io.ObjectInputStream;
@@ -485,10 +491,24 @@ public class CcToolchainFeatures implements Serializable {
   }
 
   /**
+   * An interface for classes representing crosstool messages that can activate eachother
+   * using 'requires' and 'implies' semantics.
+   *
+   * <p>Currently there are two types of CrosstoolActivatable: Feature and ActionConfig.
+   */
+  private interface CrosstoolSelectable {
+
+    /**
+     * Returns the name of this selectable.
+     */
+    String getName();
+  }
+
+  /**
    * Contains flags for a specific feature.
    */
   @Immutable
-  private static class Feature implements Serializable {
+  private static class Feature implements Serializable, CrosstoolSelectable {
     private final String name;
     private final ImmutableList<FlagSet> flagSets;
     private final ImmutableList<EnvSet> envSets;
@@ -507,10 +527,8 @@ public class CcToolchainFeatures implements Serializable {
       this.envSets = envSetBuilder.build();
     }
 
-    /**
-     * @return the features's name.
-     */
-    private String getName() {
+    @Override
+    public String getName() {
       return name;
     }
 
@@ -531,6 +549,79 @@ public class CcToolchainFeatures implements Serializable {
       }
     }
   }
+
+  /**
+   * A container for information on a particular blaze action. 
+   * 
+   * <p>An ActionConfig can select a tool for its blaze action based on the set of active
+   * features.  Internally, an ActionConfig maintains an ordered list (the order being that of the
+   * list of tools in the crosstool action_config message) of such tools and the feature sets for 
+   * which they are valid.  For a given feature configuration, the ActionConfig will consider the
+   * first tool in that list with a feature set that matches the configuration to be the tool for
+   * its blaze action.
+   * 
+   * <p>ActionConfigs can be activated by features.  That is, a particular feature can cause an
+   * ActionConfig to be applied in its "implies" field.  Blaze may include certain actions in 
+   * the action graph only if a corresponding ActionConfig is activated in the toolchain - this 
+   * provides the crosstool with a mechanism for adding certain actions to the action graph based 
+   * on feature configuration.
+   * 
+   * <p>It is invalid for a toolchain to contain two action configs for the same blaze action.  In
+   * that case, blaze will throw an error when it consumes the crosstool.
+   */
+  @Immutable
+  private static class ActionConfig implements Serializable, CrosstoolSelectable {
+    private final String configName;
+    private final String actionName;
+    private final List<CToolchain.Tool> tools;
+
+    private ActionConfig(CToolchain.ActionConfig actionConfig) {
+      this.configName = actionConfig.getConfigName();
+      this.actionName = actionConfig.getActionName();
+      this.tools = actionConfig.getToolList();
+    }
+
+    @Override
+    public String getName() {
+      return configName;
+    }
+
+    /**
+     * Returns the name of the blaze action this action config applies to.
+     */
+    private String getActionName() {
+      return actionName;
+    }
+
+    /**
+     * Returns the path to this action's tool relative to the provided crosstool path given a set
+     * of enabled features.
+     */
+    private PathFragment getTool(
+        PathFragment crosstoolTopPathFragment, final Set<String> enabledFeatureNames) {
+      Optional<Tool> tool =
+          Iterables.tryFind(
+              tools,
+              new Predicate<CToolchain.Tool>() {
+                // We select the first listed tool for which all specified features are activated
+                // in this configuration
+                @Override
+                public boolean apply(CToolchain.Tool input) {
+                  Collection<String> featureNamesForTool = input.getWithFeature().getFeatureList();
+                  return enabledFeatureNames.containsAll(featureNamesForTool);
+                }
+              });
+      if (tool.isPresent()) {
+        return crosstoolTopPathFragment.getRelative(tool.get().getToolPath());
+      } else {
+        throw new IllegalArgumentException(
+            "Matching tool for action "
+                + getActionName()
+                + " not "
+                + "found for given feature configuration");
+      }
+    }
+  }
   
   /**
    * Configured build variables usable by the toolchain configuration.
@@ -871,25 +962,38 @@ public class CcToolchainFeatures implements Serializable {
   }
   
   /**
-   * Captures the set of enabled features for a rule.
+   * Captures the set of enabled features and action configs for a rule.
    */
   @Immutable
   public static class FeatureConfiguration {
     private final ImmutableSet<String> enabledFeatureNames;
-    private final ImmutableList<Feature> enabledFeatures;
+    private final Iterable<Feature> enabledFeatures;
+
+    private final ImmutableMap<String, ActionConfig> actionConfigByActionName;
     
     public FeatureConfiguration() {
-      enabledFeatureNames = ImmutableSet.of();
-      enabledFeatures = ImmutableList.of();
+      this(
+          ImmutableList.<Feature>of(),
+          ImmutableList.<ActionConfig>of(),
+          ImmutableMap.<String, ActionConfig>of());
     }
-    
-    private FeatureConfiguration(ImmutableList<Feature> enabledFeatures) {
+
+    private FeatureConfiguration(
+        Iterable<Feature> enabledFeatures,
+        Iterable<ActionConfig> enabledActionConfigs,
+        ImmutableMap<String, ActionConfig> actionConfigByActionName) {
       this.enabledFeatures = enabledFeatures;
-      ImmutableSet.Builder<String> builder = ImmutableSet.builder();
+      this.actionConfigByActionName = actionConfigByActionName;
+      ImmutableSet.Builder<String> featureBuilder = ImmutableSet.builder();
       for (Feature feature : enabledFeatures) {
-        builder.add(feature.getName());
+        featureBuilder.add(feature.getName());
+      }
+      this.enabledFeatureNames = featureBuilder.build();
+
+      ImmutableSet.Builder<String> actionConfigBuilder = ImmutableSet.builder();
+      for (ActionConfig actionConfig : enabledActionConfigs) {
+        actionConfigBuilder.add(actionConfig.getName());
       }
-      this.enabledFeatureNames = builder.build();
     }
     
     /**
@@ -920,112 +1024,182 @@ public class CcToolchainFeatures implements Serializable {
       }
       return envBuilder.build();
     }
+    
+    /**
+     * Returns the path to the given action's tool under this FeatureConfiguration relative to the
+     * crosstool.
+     */
+    PathFragment getToolPathFragmentForAction(
+        final String actionName, PathFragment crosstoolTopPathFragment) {
+      Preconditions.checkArgument(
+          actionConfigByActionName.containsKey(actionName),
+          "Action %s does not have an enabled configuration in the toolchain.",
+          actionName);
+      ActionConfig actionConfig = actionConfigByActionName.get(actionName);
+      return actionConfig.getTool(crosstoolTopPathFragment, enabledFeatureNames);
+    }
   }
   
   /**
-   * All features in the order in which they were specified in the configuration.
+   * All features and action configs in the order in which they were specified in the configuration.
    *
    * <p>We guarantee the command line to be in the order in which the flags were specified in the
    * configuration.
    */
-  private final ImmutableList<Feature> features;
-  
+  private final ImmutableList<CrosstoolSelectable> selectables;
+
   /**
-   * Maps from the feature's name to the feature.
+   * Maps the selectables's name to the selectable.
    */
-  private final ImmutableMap<String, Feature> featuresByName;
-  
+  private final ImmutableMap<String, CrosstoolSelectable> selectablesByName;
+
   /**
-   * Maps from a feature to a set of all the features it has a direct 'implies' edge to.
+   * Maps an action's name to the ActionConfig.
    */
-  private final ImmutableMultimap<Feature, Feature> implies;
-  
+  private final ImmutableMap<String, ActionConfig> actionConfigsByActionName;
+
   /**
-   * Maps from a feature to all features that have an direct 'implies' edge to this feature. 
+   * Maps from a selectable to a set of all the selectables it has a direct 'implies' edge to.
    */
-  private final ImmutableMultimap<Feature, Feature> impliedBy;
-  
+  private final ImmutableMultimap<CrosstoolSelectable, CrosstoolSelectable> implies;
+
   /**
-   * Maps from a feature to a set of feature sets, where:
+   * Maps from a selectable to all features that have an direct 'implies' edge to this
+   * selectable.
+   */
+  private final ImmutableMultimap<CrosstoolSelectable, CrosstoolSelectable> impliedBy;
+
+  /**
+   * Maps from a selectable to a set of selecatable sets, where:
    * <ul>
-   * <li>a feature set satisfies the 'requires' condition, if all features in the feature set are
-   *     enabled</li>
-   * <li>the 'requires' condition is satisfied, if at least one of the feature sets satisfies the
-   *     'requires' condition.</li>
-   * </ul> 
+   * <li>a selectable set satisfies the 'requires' condition, if all selectables in the
+   *        selectable set are enabled</li>
+   * <li>the 'requires' condition is satisfied, if at least one of the selectable sets satisfies
+   *        the 'requires' condition.</li>
+   * </ul>
    */
-  private final ImmutableMultimap<Feature, ImmutableSet<Feature>> requires;
-  
+  private final ImmutableMultimap<CrosstoolSelectable, ImmutableSet<CrosstoolSelectable>>
+      requires;
+
   /**
-   * Maps from a feature to all features that have a requirement referencing it.
-   * 
-   * <p>This will be used to determine which features need to be re-checked after a feature was
-   * disabled.
+   * Maps from a selectable to all selectables that have a requirement referencing it.
+   *
+   * <p>This will be used to determine which selectables need to be re-checked after a selectable
+   * was disabled.
    */
-  private final ImmutableMultimap<Feature, Feature> requiredBy;
-  
+  private final ImmutableMultimap<CrosstoolSelectable, CrosstoolSelectable> requiredBy;
+ 
   /**
    * A cache of feature selection results, so we do not recalculate the feature selection for
    * all actions.
    */
   private transient LoadingCache<Collection<String>, FeatureConfiguration>
       configurationCache = buildConfigurationCache();
-  
+
   /**
    * Constructs the feature configuration from a {@code CToolchain} protocol buffer.
-   * 
+   *
    * @param toolchain the toolchain configuration as specified by the user.
    * @throws InvalidConfigurationException if the configuration has logical errors.
    */
   @VisibleForTesting
   public CcToolchainFeatures(CToolchain toolchain) throws InvalidConfigurationException {
-    // Build up the feature graph.
-    // First, we build up the map of name -> features in one pass, so that earlier features can
-    // reference later features in their configuration.
-    ImmutableList.Builder<Feature> features = ImmutableList.builder();
-    HashMap<String, Feature> featuresByName = new HashMap<>();
+    // Build up the feature/action config graph.  We refer to features/action configs as
+    // 'selectables'.
+    // First, we build up the map of name -> selectables in one pass, so that earlier selectables
+    // can reference later features in their configuration.
+    ImmutableList.Builder<CrosstoolSelectable> selectablesBuilder = ImmutableList.builder();
+    HashMap<String, CrosstoolSelectable> selectablesByName = new HashMap<>();
+
+    // Also build a map from action -> action_config, for use in tool lookups
+    ImmutableMap.Builder<String, ActionConfig> actionConfigsByActionName = ImmutableMap.builder();
+ 
     for (CToolchain.Feature toolchainFeature : toolchain.getFeatureList()) {
       Feature feature = new Feature(toolchainFeature);
-      features.add(feature);
-      if (featuresByName.put(feature.getName(), feature) != null) {
-        throw new InvalidConfigurationException("Invalid toolchain configuration: feature '"
-            + feature.getName() + "' was specified multiple times.");
-      }
+      selectablesBuilder.add(feature);
+      selectablesByName.put(feature.getName(), feature);
     }
-    this.features = features.build();
-    this.featuresByName = ImmutableMap.copyOf(featuresByName);
     
+    for (CToolchain.ActionConfig toolchainActionConfig : toolchain.getActionConfigList()) {
+      ActionConfig actionConfig = new ActionConfig(toolchainActionConfig);
+      selectablesBuilder.add(actionConfig);
+      selectablesByName.put(actionConfig.getName(), actionConfig);
+      actionConfigsByActionName.put(actionConfig.getActionName(), actionConfig);
+    }
+
+    this.selectables = selectablesBuilder.build();
+    this.selectablesByName = ImmutableMap.copyOf(selectablesByName);
+
+    checkForActionNameDups(toolchain.getActionConfigList());
+    checkForActivatableDups(this.selectables);
+
+    this.actionConfigsByActionName = actionConfigsByActionName.build();
+
     // Next, we build up all forward references for 'implies' and 'requires' edges.
-    ImmutableMultimap.Builder<Feature, Feature> implies = ImmutableMultimap.builder();
-    ImmutableMultimap.Builder<Feature, ImmutableSet<Feature>> requires =
+    ImmutableMultimap.Builder<CrosstoolSelectable, CrosstoolSelectable> implies =
         ImmutableMultimap.builder();
-    // We also store the reverse 'implied by' and 'required by' edges during this pass. 
-    ImmutableMultimap.Builder<Feature, Feature> impliedBy = ImmutableMultimap.builder();
-    ImmutableMultimap.Builder<Feature, Feature> requiredBy = ImmutableMultimap.builder();
+    ImmutableMultimap.Builder<CrosstoolSelectable, ImmutableSet<CrosstoolSelectable>> requires =
+        ImmutableMultimap.builder();
+    // We also store the reverse 'implied by' and 'required by' edges during this pass.
+    ImmutableMultimap.Builder<CrosstoolSelectable, CrosstoolSelectable> impliedBy =
+        ImmutableMultimap.builder();
+    ImmutableMultimap.Builder<CrosstoolSelectable, CrosstoolSelectable> requiredBy =
+        ImmutableMultimap.builder();
+    
     for (CToolchain.Feature toolchainFeature : toolchain.getFeatureList()) {
       String name = toolchainFeature.getName();
-      Feature feature = featuresByName.get(name);
+      CrosstoolSelectable selectable = selectablesByName.get(name);
       for (CToolchain.FeatureSet requiredFeatures : toolchainFeature.getRequiresList()) {
-        ImmutableSet.Builder<Feature> allOf = ImmutableSet.builder(); 
+        ImmutableSet.Builder<CrosstoolSelectable> allOf = ImmutableSet.builder();
         for (String requiredName : requiredFeatures.getFeatureList()) {
-          Feature required = getFeatureOrFail(requiredName, name);
+          CrosstoolSelectable required = getActivatableOrFail(requiredName, name);
           allOf.add(required);
-          requiredBy.put(required, feature);
+          requiredBy.put(required, selectable);
         }
-        requires.put(feature, allOf.build());
+        requires.put(selectable, allOf.build());
       }
       for (String impliedName : toolchainFeature.getImpliesList()) {
-        Feature implied = getFeatureOrFail(impliedName, name);
-        impliedBy.put(implied, feature);
-        implies.put(feature, implied);
+        CrosstoolSelectable implied = getActivatableOrFail(impliedName, name);
+        impliedBy.put(implied, selectable);
+        implies.put(selectable, implied);
       }
     }
+    
+    
     this.implies = implies.build();
     this.requires = requires.build();
     this.impliedBy = impliedBy.build();
     this.requiredBy = requiredBy.build();
   }
-  
+
+  private static void checkForActivatableDups(Iterable<CrosstoolSelectable> selectables)
+      throws InvalidConfigurationException {
+    Collection<String> names = new HashSet<>();
+    for (CrosstoolSelectable selectable : selectables) {
+      if (!names.add(selectable.getName())) {
+        throw new InvalidConfigurationException(
+            "Invalid toolcahin configuration: feature or "
+                + "action config '"
+                + selectable.getName()
+                + "' was specified multiple times.");
+      }
+    }
+  }
+
+  private static void checkForActionNameDups(Iterable<CToolchain.ActionConfig> actionConfigs)
+      throws InvalidConfigurationException {
+    Collection<String> actionNames = new HashSet<>();
+    for (CToolchain.ActionConfig actionConfig : actionConfigs) {
+      if (!actionNames.add(actionConfig.getActionName())) {
+        throw new InvalidConfigurationException(
+            "Invalid toolchain configuration: multiple action "
+                + "configs for action '"
+                + actionConfig.getActionName()
+                + "'");
+      }
+    }
+  }
+ 
   /**
    * Assign an empty cache after default-deserializing all non-transient members.
    */
@@ -1077,24 +1251,24 @@ public class CcToolchainFeatures implements Serializable {
   }
 
   /**
-   * @return the feature with the given {@code name}.
-   * 
-   * @throws InvalidConfigurationException if no feature with the given name was configured.
+   * @return the selectable with the given {@code name}.
+   *
+   * @throws InvalidConfigurationException if no selectable with the given name was configured.
    */
-  private Feature getFeatureOrFail(String name, String reference)
+  private CrosstoolSelectable getActivatableOrFail(String name, String reference)
       throws InvalidConfigurationException {
-    if (!featuresByName.containsKey(name)) {
+    if (!selectablesByName.containsKey(name)) {
       throw new InvalidConfigurationException("Invalid toolchain configuration: feature '" + name
           + "', which is referenced from feature '" + reference + "', is not defined.");
     }
-    return featuresByName.get(name);
+    return selectablesByName.get(name);
   }
   
   @VisibleForTesting
-  Collection<String> getFeatureNames() {
+  Collection<String> getActivatableNames() {
     Collection<String> featureNames = new HashSet<>();
-    for (Feature feature : features) {
-      featureNames.add(feature.getName());
+    for (CrosstoolSelectable selectable : selectables) {
+      featureNames.add(selectable.getName());
     }
     return featureNames;
   }
@@ -1114,49 +1288,62 @@ public class CcToolchainFeatures implements Serializable {
     private final ImmutableSet<Feature> requestedFeatures;
     
     /**
-     * The currently enabled feature; during feature selection, we first put all features reachable
-     * via an 'implies' edge into the enabled feature set, and than prune that set from features
-     * that have unmet requirements.
+     * The currently enabled selectable; during feature selection, we first put all features
+     * reachable via an 'implies' edge into the enabled feature set, and than prune that set
+     * from features that have unmet requirements.
      */
-    private Set<Feature> enabled = new HashSet<>();
+    private final Set<CrosstoolSelectable> enabled = new HashSet<>();
     
     private FeatureSelection(Collection<String> requestedFeatures) {
       ImmutableSet.Builder<Feature> builder = ImmutableSet.builder();
       for (String name : requestedFeatures) {
-        if (featuresByName.containsKey(name)) {
-          builder.add(featuresByName.get(name));
+        if (selectablesByName.containsKey(name)) {
+          if (selectablesByName.get(name) instanceof Feature) {
+            builder.add((Feature) selectablesByName.get(name));
+          }
         }
       }
       this.requestedFeatures = builder.build();
     }
 
     /**
-     * @return all enabled features in the order in which they were specified in the configuration.
+     * @return a {@code FeatureConfiguration} that reflects the set of activated features and
+     * action configs.
      */
     private FeatureConfiguration run() {
       for (Feature feature : requestedFeatures) {
         enableAllImpliedBy(feature);
       }
-      disableUnsupportedFeatures();
-      ImmutableList.Builder<Feature> enabledFeaturesInOrder = ImmutableList.builder(); 
-      for (Feature feature : features) {
-        if (enabled.contains(feature)) {
-          enabledFeaturesInOrder.add(feature);
+      disableUnsupportedActivatables();
+      ImmutableList.Builder<CrosstoolSelectable> enabledActivatablesInOrderBuilder =
+          ImmutableList.builder();
+      for (CrosstoolSelectable selectable : selectables) {
+        if (enabled.contains(selectable)) {
+          enabledActivatablesInOrderBuilder.add(selectable);
         }
       }
-      return new FeatureConfiguration(enabledFeaturesInOrder.build());
+      
+      ImmutableList<CrosstoolSelectable> enabledActivatablesInOrder =
+          enabledActivatablesInOrderBuilder.build();
+      Iterable<Feature> enabledFeaturesInOrder =
+          Iterables.filter(enabledActivatablesInOrder, Feature.class);
+      Iterable<ActionConfig> enabledActionConfigsInOrder =
+          Iterables.filter(enabledActivatablesInOrder, ActionConfig.class);
+
+      return new FeatureConfiguration(
+          enabledFeaturesInOrder, enabledActionConfigsInOrder, actionConfigsByActionName);
     }
     
     /**
-     * Transitively and unconditionally enable all features implied by the given feature and the
-     * feature itself to the enabled feature set.
+     * Transitively and unconditionally enable all selectables implied by the given selectable
+     * and the selectable itself to the enabled selectable set.
      */
-    private void enableAllImpliedBy(Feature feature) {
-      if (enabled.contains(feature)) {
+    private void enableAllImpliedBy(CrosstoolSelectable selectable) {
+      if (enabled.contains(selectable)) {
         return;
       }
-      enabled.add(feature);
-      for (Feature implied : implies.get(feature)) {
+      enabled.add(selectable);
+      for (CrosstoolSelectable implied : implies.get(selectable)) {
         enableAllImpliedBy(implied);
       }
     }
@@ -1164,40 +1351,41 @@ public class CcToolchainFeatures implements Serializable {
     /**
      * Remove all unsupported features from the enabled feature set.
      */
-    private void disableUnsupportedFeatures() {
-      Queue<Feature> check = new ArrayDeque<>(enabled);
+    private void disableUnsupportedActivatables() {
+      Queue<CrosstoolSelectable> check = new ArrayDeque<>(enabled);
       while (!check.isEmpty()) {
-        checkFeature(check.poll());
+        checkActivatable(check.poll());
       }
     }
     
     /**
-     * Check if the given feature is still satisfied within the set of currently enabled features.
-     * 
-     * <p>If it is not, remove the feature from the set of enabled features, and re-check all
-     * features that may now also become disabled.
+     * Check if the given selectable is still satisfied within the set of currently enabled
+     * selectables.
+     *
+     * <p>If it is not, remove the selectable from the set of enabled selectables, and re-check
+     * all selectables that may now also become disabled.
      */
-    private void checkFeature(Feature feature) {
-      if (!enabled.contains(feature) || isSatisfied(feature)) {
+    private void checkActivatable(CrosstoolSelectable selectable) {
+      if (!enabled.contains(selectable) || isSatisfied(selectable)) {
         return;
       }
-      enabled.remove(feature);
-      
-      // Once we disable a feature, we have to re-check all features that can be affected by
-      // that removal.
-      // 1. A feature that implied the current feature is now going to be disabled.
-      for (Feature impliesCurrent : impliedBy.get(feature)) {
-        checkFeature(impliesCurrent);
-      }
-      // 2. A feature that required the current feature may now be disabled, depending on whether
-      //    the requirement was optional.
-      for (Feature requiresCurrent : requiredBy.get(feature)) {
-        checkFeature(requiresCurrent);
-      }
-      // 3. A feature that this feature implied may now be disabled if no other feature also implies
-      //    it.
-      for (Feature implied : implies.get(feature)) {
-        checkFeature(implied);
+      enabled.remove(selectable);
+
+      // Once we disable a selectable, we have to re-check all selectables that can be affected
+      // by that removal.
+      // 1. A selectable that implied the current selectable is now going to be disabled.
+      for (CrosstoolSelectable impliesCurrent : impliedBy.get(selectable)) {
+        checkActivatable(impliesCurrent);
+      }
+      // 2. A selectable that required the current selectable may now be disabled, depending on
+      // whether the requirement was optional.
+      for (CrosstoolSelectable requiresCurrent : requiredBy.get(selectable)) {
+        checkActivatable(requiresCurrent);
+      }
+      // 3. A selectable that this selectable implied may now be disabled if no other selectables
+      // also implies it.
+      for (CrosstoolSelectable implied : implies.get(selectable)) {
+        checkActivatable(implied);
       }
     }
 
@@ -1205,23 +1393,24 @@ public class CcToolchainFeatures implements Serializable {
      * @return whether all requirements of the feature are met in the set of currently enabled
      * features.
      */
-    private boolean isSatisfied(Feature feature) {
-      return (requestedFeatures.contains(feature) || isImpliedByEnabledFeature(feature))
-          && allImplicationsEnabled(feature) && allRequirementsMet(feature);
+    private boolean isSatisfied(CrosstoolSelectable selectable) {
+      return (requestedFeatures.contains(selectable) || isImpliedByEnabledActivatable(selectable))
+          && allImplicationsEnabled(selectable)
+          && allRequirementsMet(selectable);
     }
     
     /**
      * @return whether a currently enabled feature implies the given feature.
      */
-    private boolean isImpliedByEnabledFeature(Feature feature) {
-      return !Collections.disjoint(impliedBy.get(feature), enabled);
+    private boolean isImpliedByEnabledActivatable(CrosstoolSelectable selectable) {
+      return !Collections.disjoint(impliedBy.get(selectable), enabled);
     }
         
     /**
      * @return whether all implications of the given feature are enabled.
      */
-    private boolean allImplicationsEnabled(Feature feature) {
-      for (Feature implied : implies.get(feature)) {
+    private boolean allImplicationsEnabled(CrosstoolSelectable selectable) {
+      for (CrosstoolSelectable implied : implies.get(selectable)) {
         if (!enabled.contains(implied)) {
           return false;
         }
@@ -1231,16 +1420,17 @@ public class CcToolchainFeatures implements Serializable {
     
     /**
      * @return whether all requirements are enabled.
-     * 
-     * <p>This implies that for any of the feature sets all of the specified features are enabled.
+     *
+     * <p>This implies that for any of the selectable sets all of the specified selectable
+     *   are enabled.
      */
-    private boolean allRequirementsMet(Feature feature) {
+    private boolean allRequirementsMet(CrosstoolSelectable feature) {
       if (!requires.containsKey(feature)) {
         return true;
       }
-      for (ImmutableSet<Feature> requiresAllOf : requires.get(feature)) {
+      for (ImmutableSet<CrosstoolSelectable> requiresAllOf : requires.get(feature)) {
         boolean requirementMet = true;
-        for (Feature required : requiresAllOf) {
+        for (CrosstoolSelectable required : requiresAllOf) {
           if (!enabled.contains(required)) {
             requirementMet = false;
             break;
diff --git a/src/main/protobuf/crosstool_config.proto b/src/main/protobuf/crosstool_config.proto
index 1b824466de..ced4635c99 100644
--- a/src/main/protobuf/crosstool_config.proto
+++ b/src/main/protobuf/crosstool_config.proto
@@ -170,21 +170,21 @@ message CToolchain {
     // If 'requires' is omitted, the feature is supported independently of which
     // other features are enabled.
     //
-    // Use this for example to filter flags depending on the build mode enabled
-    // (opt / fastbuild / dbg).
+    // Use this for example to filter flags depending on the build mode
+    // enabled (opt / fastbuild / dbg).
     repeated FeatureSet requires = 3;
 
-    // A list of features that are automatically enabled when this feature is
-    // enabled. If any of the implied features cannot be enabled, this feature
-    // will (silently) not be enabled either.
+    // A list of features or action configs that are automatically enabled when
+    // this feature is enabled. If any of the implied features or action configs
+    // cannot be enabled, this feature will (silently) not be enabled either.
     repeated string implies = 4;
 
     // A list of names this feature conflicts with.
     // A feature cannot be enabled if:
-    // - 'provides' contains the name of a different feature that we want to
-    //   enable.
+    // - 'provides' contains the name of a different feature or action config
+    //  that we want to enable.
     // - 'provides' contains the same value as a 'provides' in a different
-    //   feature that we want to enable.
+    //   feature or action config that we want to enable.
     //
     // Use this in order to ensure that incompatible features cannot be
     // accidentally activated at the same time, leading to hard to diagnose
@@ -192,7 +192,75 @@ message CToolchain {
     repeated string provides = 5;
   }
 
+  // Describes a tool associated with a crosstool action config.
+  message Tool {
+    // Path to the tool, relative to the location of the crosstool.
+    required string tool_path = 1;
+
+    // A feature set defining when this tool is applicable.  If this attribute
+    // is left out, the Tool will be assumed to apply for any feature
+    // configuration.
+    optional FeatureSet with_feature = 2;
+
+    // Requirements on the execution environment for the execution of this tool,
+    // to be passed as out-of-band "hints" to the execution backend.
+    // Ex. "requires-darwin"
+    repeated string execution_requirement = 3;
+  }
+
+  // An action config corresponds to a blaze action, and allows selection of
+  // a tool based on activated features.  Action configs come in two varieties:
+  // automatic (the blaze action will exist whether or not the action config
+  // is activated) and attachable (the blaze action will be added to the
+  // action graph only if the action config is activated).
+  //
+  // Action config activation occurs by the same semantics as features: a
+  // feature can 'require' or 'imply' an action config in the same way that it
+  // would another feature.
+  message ActionConfig {
+    // The name other features will use to activate this action config.  Can
+    // be the same as action_name.
+    required string config_name = 1;
+
+    // The name of the blaze action that this config applies to, ex. 'c-compile'
+    // or 'c-module-compile'.
+    required string action_name = 2;
+
+    // The tool applied to the action will be the first Tool with a feature
+    // set that matches the feature configuration.  An error will be thrown
+    // if no tool matches a provided feature configuration - for that reason,
+    // it's a good idea to provide a default tool with an empty feature set.
+    repeated Tool tool = 3;
+
+    // If the given action config is enabled, the flag sets will be applied
+    // to the corresponding action.
+    repeated FlagSet flag_set = 4;
+
+    // If the given action config is enabled, the env sets will be applied
+    // to the corresponding action.
+    repeated EnvSet env_set = 5;
+
+    // A list of feature sets defining when this action config
+    // is supported by the toolchain. The action config is supported if any of
+    // the feature sets fully apply, that is, when all features of a
+    // feature set are enabled.
+    //
+    // If 'requires' is omitted, the action config is supported independently
+    // of which other features are enabled.
+    //
+    // Use this for example to filter actions depending on the build
+    // mode enabled (opt / fastbuild / dbg).
+    repeated FeatureSet requires = 6;
+
+    // A list of features or action configs that are automatically enabled when
+    // this action config is enabled. If any of the implied features or action
+    // configs cannot be enabled, this action config will (silently)
+    // not be enabled either.
+    repeated string implies = 7;
+  }
+
   repeated Feature feature = 50;
+  repeated ActionConfig action_config = 53;
 
   // The unique identifier of the toolchain within the crosstool release. It
   // must be possible to use this as a directory name in a path.
@@ -211,6 +279,9 @@ message CToolchain {
 
   // Tool locations. Relative paths are resolved relative to the configuration
   // file directory.
+  // NOTE: DEPRECATED. Prefer specifying an ActionConfig for the action that
+  // needs the tool.
+  // TODO(b/27903698) migrate to ActionConfig.
   repeated ToolPath tool_path = 9;
 
   // Feature flags.
@@ -333,7 +404,7 @@ message CToolchain {
   // why they are recorded here.
   repeated string debian_extra_requires = 33;
 
-  // Next free id: 53
+  // Next free id: 54
 }
 
 message ToolPath {
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
index 79b99ba2c3..4b3526bc5c 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
@@ -29,6 +29,7 @@ import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.testutil.Suite;
 import com.google.devtools.build.lib.testutil.TestSpec;
 import com.google.devtools.build.lib.testutil.TestUtils;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.view.config.crosstool.CrosstoolConfig.CToolchain;
 import com.google.protobuf.TextFormat;
 
@@ -87,7 +88,7 @@ public class CcToolchainFeaturesTest {
     FeatureConfiguration configuration =
         features.getFeatureConfiguration(Arrays.asList(requestedFeatures));
     ImmutableSet.Builder<String> enabledFeatures = ImmutableSet.builder();
-    for (String feature : features.getFeatureNames()) {
+    for (String feature : features.getActivatableNames()) {
       if (configuration.isEnabled(feature)) {
         enabledFeatures.add(feature);
       }
@@ -584,4 +585,168 @@ public class CcToolchainFeaturesTest {
     assertThat(features.getFeatureConfiguration("b").getCommandLine(CppCompileAction.CPP_COMPILE,
         createVariables("v", "1"))).containsExactly("-f", "1");
   }
+  
+  @Test
+  public void testSimpleActionTool() throws Exception {
+    FeatureConfiguration configuration =
+        buildFeatures(
+                "action_config {",
+                "  config_name: 'action-a'",
+                "  action_name: 'action-a'",
+                "  tool {",
+                "    tool_path: 'toolchain/a'",
+                "  }",
+                "}",
+                "feature {",
+                "   name: 'activates-action-a'",
+                "   implies: 'action-a'",
+                "}")
+            .getFeatureConfiguration("activates-action-a");
+    PathFragment crosstoolPath = new PathFragment("crosstool/");
+    PathFragment toolPath = configuration.getToolPathFragmentForAction("action-a", crosstoolPath);
+    assertThat(toolPath.toString()).isEqualTo("crosstool/toolchain/a");
+  }
+
+  @Test
+  public void testActionToolFromFeatureSet() throws Exception {
+    CcToolchainFeatures toolchainFeatures =
+        buildFeatures(
+            "action_config {",
+            "  config_name: 'action-a'",
+            "  action_name: 'action-a'",
+            "  tool {",
+            "    tool_path: 'toolchain/features-a-and-b'",
+            "    with_feature: {",
+            "      feature: 'feature-a'",
+            "      feature: 'feature-b'",
+            "     }",
+            "  }",
+            "  tool {",
+            "    tool_path: 'toolchain/feature-a'",
+            "    with_feature: { feature: 'feature-a' }",
+            "  }",
+            "  tool {",
+            "    tool_path: 'toolchain/feature-b'",
+            "    with_feature: { feature: 'feature-b' }",
+            "  }",
+            "  tool {",
+            "    tool_path: 'toolchain/default'",
+            "  }",
+            "}",
+            "feature {",
+            "  name: 'feature-a'",
+            "}",
+            "feature {",
+            "  name: 'feature-b'",
+            "}",
+            "feature {",
+            "  name: 'activates-action-a'",
+            "  implies: 'action-a'",
+            "}");
+
+    PathFragment crosstoolPath = new PathFragment("crosstool/");
+
+    FeatureConfiguration featureAConfiguration =
+        toolchainFeatures.getFeatureConfiguration("feature-a", "activates-action-a");
+    assertThat(
+            featureAConfiguration
+                .getToolPathFragmentForAction("action-a", crosstoolPath)
+                .toString())
+        .isEqualTo("crosstool/toolchain/feature-a");
+
+    FeatureConfiguration featureBConfiguration =
+        toolchainFeatures.getFeatureConfiguration("feature-b", "activates-action-a");
+    assertThat(
+            featureBConfiguration
+                .getToolPathFragmentForAction("action-a", crosstoolPath)
+                .toString())
+        .isEqualTo("crosstool/toolchain/feature-b");
+
+    FeatureConfiguration featureAAndBConfiguration =
+        toolchainFeatures.getFeatureConfiguration("feature-a", "feature-b", "activates-action-a");
+    assertThat(
+            featureAAndBConfiguration
+                .getToolPathFragmentForAction("action-a", crosstoolPath)
+                .toString())
+        .isEqualTo("crosstool/toolchain/features-a-and-b");
+
+    FeatureConfiguration noFeaturesConfiguration =
+        toolchainFeatures.getFeatureConfiguration("activates-action-a");
+    assertThat(
+            noFeaturesConfiguration
+                .getToolPathFragmentForAction("action-a", crosstoolPath)
+                .toString())
+        .isEqualTo("crosstool/toolchain/default");
+  }
+
+  @Test
+  public void testErrorForNoMatchingTool() throws Exception {
+    CcToolchainFeatures toolchainFeatures =
+        buildFeatures(
+            "action_config {",
+            "  config_name: 'action-a'",
+            "  action_name: 'action-a'",
+            "  tool {",
+            "    tool_path: 'toolchain/feature-a'",
+            "    with_feature: { feature: 'feature-a' }",
+            "  }",
+            "}",
+            "feature {",
+            "  name: 'feature-a'",
+            "}",
+            "feature {",
+            "  name: 'activates-action-a'",
+            "  implies: 'action-a'",
+            "}");
+
+    PathFragment crosstoolPath = new PathFragment("crosstool/");
+
+    FeatureConfiguration noFeaturesConfiguration =
+        toolchainFeatures.getFeatureConfiguration("activates-action-a");
+
+    try {
+      noFeaturesConfiguration.getToolPathFragmentForAction("action-a", crosstoolPath);
+      fail("Expected IllegalArgumentException");
+    } catch (IllegalArgumentException e) {
+      assertThat(e.getMessage())
+          .contains("Matching tool for action action-a not found for given feature configuration");
+    }
+  }
+
+  @Test
+  public void testInvalidActionConfigurationDuplicateActionConfigs() throws Exception {
+    try {
+      buildFeatures(
+          "action_config {",
+          "  config_name: 'action-a'",
+          "  action_name: 'action-1'",
+          "}",
+          "action_config {",
+          "  config_name: 'action-a'",
+          "  action_name: 'action-2'",
+          "}");
+      fail("Expected InvalidConfigurationException");
+    } catch (InvalidConfigurationException e) {
+      assertThat(e.getMessage())
+          .contains("feature or action config 'action-a' was specified multiple times.");
+    }
+  }
+
+  @Test
+  public void testInvalidActionConfigurationMultipleActionConfigsForAction() throws Exception {
+    try {
+      buildFeatures(
+          "action_config {",
+          "  config_name: 'name-a'",
+          "  action_name: 'action-a'",
+          "}",
+          "action_config {",
+          "  config_name: 'name-b'",
+          "  action_name: 'action-a'",
+          "}");
+      fail("Expected InvalidConfigurationException");
+    } catch (InvalidConfigurationException e) {
+      assertThat(e.getMessage()).contains("multiple action configs for action 'action-a'");
+    }
+  }
 }