path: root/src/main/java/com/google/devtools/build/lib/rules/cpp/FeatureSelection.java

// Copyright 2015 The Bazel Authors. 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.rules.cpp;

import com.google.common.base.Joiner;
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.rules.cpp.CcToolchainFeatures.ActionConfig;
import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.CollidingProvidesException;
import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.CrosstoolSelectable;
import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Feature;
import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * Implements the feature selection algorithm.
 *
 * <p>Feature selection is done by first enabling all features reachable by an 'implies' edge, and
 * then iteratively pruning features that have unmet requirements.
 */
class FeatureSelection {

  /**
   * The selectables Bazel would like to enable; either because they are supported and generally
   * useful, or because the user required them (for example through the command line).
   */
  private final ImmutableSet<CrosstoolSelectable> requestedSelectables;
  /**
   * The currently enabled selectable; during feature selection, we first put all selectables
   * reachable via an 'implies' edge into the enabled selectable set, and than prune that set from
   * selectables that have unmet requirements.
   */
  private final Set<CrosstoolSelectable> enabled = new HashSet<>();
  /**
   * 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<CrosstoolSelectable> selectables;

  /**
   * Maps an action's name to the ActionConfig.
   */
  private final ImmutableMap<String, ActionConfig> actionConfigsByActionName;

  /**
   * Maps from a selectable to a set of all the selectables it has a direct 'implies' edge to.
   */
  private final ImmutableMultimap<CrosstoolSelectable, CrosstoolSelectable> implies;

  /**
   * 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 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<CrosstoolSelectable, ImmutableSet<CrosstoolSelectable>>
      requires;

  /**
   * Maps from a string to the set of selectables that 'provide' it.
   */
  private final ImmutableMultimap<String, CrosstoolSelectable> provides;

  /**
   * 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<CrosstoolSelectable, CrosstoolSelectable> requiredBy;

  FeatureSelection(
      ImmutableSet<String> requestedFeatures,
      ImmutableMap<String, CrosstoolSelectable> selectablesByName,
      ImmutableList<CrosstoolSelectable> selectables,
      ImmutableMultimap<String, CrosstoolSelectable> provides,
      ImmutableMultimap<CrosstoolSelectable, CrosstoolSelectable> implies,
      ImmutableMultimap<CrosstoolSelectable, CrosstoolSelectable> impliedBy,
      ImmutableMultimap<CrosstoolSelectable, ImmutableSet<CrosstoolSelectable>> requires,
      ImmutableMultimap<CrosstoolSelectable, CrosstoolSelectable> requiredBy,
      ImmutableMap<String, ActionConfig> actionConfigsByActionName) {
    ImmutableSet.Builder<CrosstoolSelectable> builder = ImmutableSet.builder();
    for (String name : requestedFeatures) {
      if (selectablesByName.containsKey(name)) {
        builder.add(selectablesByName.get(name));
      }
    }
    this.requestedSelectables = builder.build();
    this.selectables = selectables;
    this.provides = provides;
    this.implies = implies;
    this.impliedBy = impliedBy;
    this.requires = requires;
    this.requiredBy = requiredBy;
    this.actionConfigsByActionName = actionConfigsByActionName;
  }

  /**
   * @return a {@link FeatureConfiguration} that reflects the set of activated features and action
   *     configs.
   */
  FeatureConfiguration run() throws CollidingProvidesException {
    for (CrosstoolSelectable selectable : requestedSelectables) {
      enableAllImpliedBy(selectable);
    }

    disableUnsupportedActivatables();
    ImmutableList.Builder<CrosstoolSelectable> enabledActivatablesInOrderBuilder =
        ImmutableList.builder();
    for (CrosstoolSelectable selectable : selectables) {
      if (enabled.contains(selectable)) {
        enabledActivatablesInOrderBuilder.add(selectable);
      }
    }

    ImmutableList<CrosstoolSelectable> enabledActivatablesInOrder =
        enabledActivatablesInOrderBuilder.build();
    ImmutableList<Feature> enabledFeaturesInOrder =
        enabledActivatablesInOrder
            .stream()
            .filter(a -> a instanceof Feature)
            .map(f -> (Feature) f)
            .collect(ImmutableList.toImmutableList());
    Iterable<ActionConfig> enabledActionConfigsInOrder =
        Iterables.filter(enabledActivatablesInOrder, ActionConfig.class);

    for (String provided : provides.keys()) {
      List<String> conflicts = new ArrayList<>();
      for (CrosstoolSelectable selectableProvidingString : provides.get(provided)) {
        if (enabledActivatablesInOrder.contains(selectableProvidingString)) {
          conflicts.add(selectableProvidingString.getName());
        }
      }

      if (conflicts.size() > 1) {
        throw new CollidingProvidesException(
            String.format(
                CcToolchainFeatures.COLLIDING_PROVIDES_ERROR,
                provided,
                Joiner.on(" ").join(conflicts)));
      }
    }

    ImmutableSet.Builder<String> enabledActionConfigNames = ImmutableSet.builder();
    for (ActionConfig actionConfig : enabledActionConfigsInOrder) {
      enabledActionConfigNames.add(actionConfig.getActionName());
    }

    return new FeatureConfiguration(
        enabledFeaturesInOrder, enabledActionConfigNames.build(), actionConfigsByActionName);
  }

  /**
   * Transitively and unconditionally enable all selectables implied by the given selectable and the
   * selectable itself to the enabled selectable set.
   */
  private void enableAllImpliedBy(CrosstoolSelectable selectable) {
    if (enabled.contains(selectable)) {
      return;
    }
    enabled.add(selectable);
    for (CrosstoolSelectable implied : implies.get(selectable)) {
      enableAllImpliedBy(implied);
    }
  }

  /** Remove all unsupported features from the enabled feature set. */
  private void disableUnsupportedActivatables() {
    Queue<CrosstoolSelectable> check = new ArrayDeque<>(enabled);
    while (!check.isEmpty()) {
      checkActivatable(check.poll());
    }
  }

  /**
   * 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 checkActivatable(CrosstoolSelectable selectable) {
    if (!enabled.contains(selectable) || isSatisfied(selectable)) {
      return;
    }
    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);
    }
  }

  /**
   * @return whether all requirements of the selectable are met in the set of currently enabled
   *     selectables.
   */
  private boolean isSatisfied(CrosstoolSelectable selectable) {
    return (requestedSelectables.contains(selectable) || isImpliedByEnabledActivatable(selectable))
        && allImplicationsEnabled(selectable)
        && allRequirementsMet(selectable);
  }

  /** @return whether a currently enabled selectable implies the given selectable. */
  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(CrosstoolSelectable selectable) {
    for (CrosstoolSelectable implied : implies.get(selectable)) {
      if (!enabled.contains(implied)) {
        return false;
      }
    }
    return true;
  }

  /**
   * @return whether all requirements are enabled.
   *     <p>This implies that for any of the selectable sets all of the specified selectable are
   *     enabled.
   */
  private boolean allRequirementsMet(CrosstoolSelectable feature) {
    if (!requires.containsKey(feature)) {
      return true;
    }
    for (ImmutableSet<CrosstoolSelectable> requiresAllOf : requires.get(feature)) {
      boolean requirementMet = true;
      for (CrosstoolSelectable required : requiresAllOf) {
        if (!enabled.contains(required)) {
          requirementMet = false;
          break;
        }
      }
      if (requirementMet) {
        return true;
      }
    }
    return false;
  }
}