diff options
author | rosica <rosica@google.com> | 2018-05-04 09:19:16 -0700 |
---|---|---|
committer | Copybara-Service <copybara-piper@google.com> | 2018-05-04 09:20:31 -0700 |
commit | f7b5ce6d0cc7d2034245d15c533ac1c122c6852e (patch) | |
tree | 8fe958a426dcc2948fd297677e69ea0c3996ba94 /src/main/java/com/google/devtools/build | |
parent | ba6a7d45755a2552ebcb4bf5915b4c44a4405275 (diff) |
Move CcToolchainFeatures.FeatureSelection to a separate CcToolchainFeatureSelection class
RELNOTES: None.
PiperOrigin-RevId: 195425336
Diffstat (limited to 'src/main/java/com/google/devtools/build')
-rw-r--r-- | src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java | 220 | ||||
-rw-r--r-- | src/main/java/com/google/devtools/build/lib/rules/cpp/FeatureSelection.java | 286 |
2 files changed, 302 insertions, 204 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 6a50a56753..2e215f5131 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,7 +15,6 @@ package com.google.devtools.build.lib.rules.cpp; import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.Joiner; import com.google.common.base.Preconditions; import com.google.common.base.Strings; import com.google.common.base.Supplier; @@ -47,10 +46,8 @@ import com.google.devtools.build.lib.view.config.crosstool.CrosstoolConfig.CTool import java.io.IOException; import java.io.ObjectInputStream; import java.io.Serializable; -import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collection; -import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashMap; @@ -58,7 +55,6 @@ import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Optional; -import java.util.Queue; import java.util.Set; import java.util.Stack; import java.util.concurrent.ExecutionException; @@ -107,7 +103,7 @@ public class CcToolchainFeatures implements Serializable { "Toolchain must provide artifact_name_pattern for category %s"; /** Error message thrown when a toolchain enables two features that provide the same string. */ - @VisibleForTesting static final String COLLIDING_PROVIDES_ERROR = + public static final String COLLIDING_PROVIDES_ERROR = "Symbol %s is provided by all of the following features: %s"; /** @@ -890,12 +886,12 @@ public class CcToolchainFeatures implements Serializable { } /** - * An interface for classes representing crosstool messages that can activate eachother - * using 'requires' and 'implies' semantics. + * An interface for classes representing crosstool messages that can activate each other using + * 'requires' and 'implies' semantics. * * <p>Currently there are two types of CrosstoolActivatable: Feature and ActionConfig. */ - private interface CrosstoolSelectable { + interface CrosstoolSelectable { /** * Returns the name of this selectable. @@ -1117,7 +1113,7 @@ public class CcToolchainFeatures implements Serializable { /** * Returns the name of the blaze action this action config applies to. */ - private String getActionName() { + String getActionName() { return actionName; } @@ -2537,7 +2533,17 @@ public class CcToolchainFeatures implements Serializable { throws CollidingProvidesException { // Command line flags will be output in the order in which they are specified in the toolchain // configuration. - return new FeatureSelection(requestedSelectables).run(); + return new FeatureSelection( + requestedSelectables, + selectablesByName, + selectables, + provides, + implies, + impliedBy, + requires, + requiredBy, + actionConfigsByActionName) + .run(); } public ImmutableList<String> getDefaultFeaturesAndActionConfigs() { @@ -2603,198 +2609,4 @@ public class CcToolchainFeatures implements Serializable { } return false; } - - /** - * 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. - */ - private 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<>(); - - private FeatureSelection(ImmutableSet<String> requestedFeatures) { - ImmutableSet.Builder<CrosstoolSelectable> builder = ImmutableSet.builder(); - for (String name : requestedFeatures) { - if (selectablesByName.containsKey(name)) { - builder.add(selectablesByName.get(name)); - } - } - this.requestedSelectables = builder.build(); - } - - /** - * @return a {@code FeatureConfiguration} that reflects the set of activated features and action - * configs. - */ - private 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(COLLIDING_PROVIDES_ERROR, - provided, Joiner.on(" ").join(conflicts))); - } - } - - ImmutableSet.Builder<String> enabledActionConfigNames = ImmutableSet.builder(); - for (ActionConfig actionConfig : enabledActionConfigsInOrder) { - enabledActionConfigNames.add(actionConfig.actionName); - } - - 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; - } - } } diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FeatureSelection.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FeatureSelection.java new file mode 100644 index 0000000000..774042b6fb --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FeatureSelection.java @@ -0,0 +1,286 @@ +// 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; + } +} |