From 9dbe48b678b0aa53456f6d44e2de1b4e15f6c634 Mon Sep 17 00:00:00 2001 From: gregce Date: Wed, 20 Sep 2017 00:35:36 +0200 Subject: Move ConfiguredTargetFunction dynamic config selection to its own class. Also clarify the interfaces *TransitionResolver* - which determines what transition to apply to an input configuration and *ConfigurationResolver* - which determines the output configuration from that transition. PiperOrigin-RevId: 169311986 --- .../build/lib/analysis/DependencyResolver.java | 18 +- .../lib/analysis/config/ConfigurationResolver.java | 595 ++++++++++++++++----- .../lib/analysis/config/TransitionResolver.java | 211 ++++++++ .../lib/skyframe/ConfiguredTargetFunction.java | 472 +--------------- .../lib/skyframe/PostConfiguredTargetFunction.java | 5 +- .../build/lib/skyframe/SkyframeExecutor.java | 5 +- .../build/lib/skyframe/TransitiveTargetValue.java | 2 +- 7 files changed, 683 insertions(+), 625 deletions(-) create mode 100644 src/main/java/com/google/devtools/build/lib/analysis/config/TransitionResolver.java (limited to 'src/main/java/com/google/devtools/build') diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java index 855c985486..41323b6892 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java @@ -22,11 +22,11 @@ import com.google.devtools.build.lib.analysis.AspectCollection.AspectCycleOnPath import com.google.devtools.build.lib.analysis.config.BuildConfiguration; import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider; -import com.google.devtools.build.lib.analysis.config.ConfigurationResolver; import com.google.devtools.build.lib.analysis.config.DynamicTransitionMapper; import com.google.devtools.build.lib.analysis.config.HostTransition; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; import com.google.devtools.build.lib.analysis.config.PatchTransition; +import com.google.devtools.build.lib.analysis.config.TransitionResolver; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; import com.google.devtools.build.lib.events.Location; @@ -62,10 +62,10 @@ import javax.annotation.Nullable; *

Includes logic to derive the right configurations depending on transition type. */ public abstract class DependencyResolver { - private final ConfigurationResolver configResolver; + private final TransitionResolver transitionResolver; protected DependencyResolver(DynamicTransitionMapper transitionMapper) { - this.configResolver = new ConfigurationResolver(transitionMapper); + this.transitionResolver = new TransitionResolver(transitionMapper); } /** @@ -374,11 +374,11 @@ public abstract class DependencyResolver { getSplitOptions(depResolver.rule, attribute, ruleConfig); if (!splitOptions.isEmpty() && !ruleConfig.isHostConfiguration()) { // Late-bound attribute with a split transition: - // Since we want to get the same results as ConfigurationResolver.evaluateTransition (but + // Since we want to get the same results as TransitionResolver.evaluateTransition (but // skip it since we've already applied the split), we want to make sure this logic - // doesn't do anything differently. ConfigurationResolver.evaluateTransition has additional + // doesn't do anything differently. TransitionResolver.evaluateTransition has additional // logic for host configs. So when we're in the host configuration we fall back to the - // non-split branch, which calls ConfigurationResolver.evaluateTransition, which returns its + // non-split branch, which calls TransitionResolver.evaluateTransition, which returns its // "host mode" result without ever looking at the split. Iterable splitConfigs = getConfigurations(ruleConfig.fragmentClasses(), splitOptions); @@ -714,7 +714,7 @@ public abstract class DependencyResolver { if (toTarget == null) { return; // Skip this round: we still need to Skyframe-evaluate the dep's target. } - Attribute.Transition transition = configResolver.evaluateTransition( + Attribute.Transition transition = transitionResolver.evaluateTransition( ruleConfig, rule, attributeAndOwner.attribute, toTarget); outgoingEdges.put( attributeAndOwner.attribute, @@ -728,7 +728,7 @@ public abstract class DependencyResolver { * Resolves the given dep for the given attribute using a pre-prepared configuration. * *

Use this method with care: it skips Bazel's standard config transition semantics ({@link - * ConfigurationResolver#evaluateTransition}). That means attributes passed through here won't + * TransitionResolver#evaluateTransition}). That means attributes passed through here won't * obey standard rules on which configurations apply to their deps. This should only be done for * special circumstances that really justify the difference. When in doubt, use {@link * #resolveDep(AttributeAndOwner, Label)}. @@ -741,7 +741,7 @@ public abstract class DependencyResolver { } outgoingEdges.put( attributeAndOwner.attribute, - configResolver.usesNullConfiguration(toTarget) + transitionResolver.usesNullConfiguration(toTarget) ? Dependency.withNullConfiguration(depLabel) : Dependency.withTransitionAndAspects(depLabel, new FixedTransition( config.getOptions()), requiredAspects(attributeAndOwner, toTarget))); diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java index 2da77b0129..02916941ef 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/config/ConfigurationResolver.java @@ -15,193 +15,502 @@ package com.google.devtools.build.lib.analysis.config; import com.google.common.annotations.VisibleForTesting; +import com.google.common.base.Joiner; +import com.google.common.base.Verify; +import com.google.common.base.VerifyException; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +import com.google.common.collect.LinkedHashMultimap; +import com.google.common.collect.LinkedListMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; +import com.google.devtools.build.lib.analysis.Dependency; +import com.google.devtools.build.lib.analysis.TargetAndConfiguration; +import com.google.devtools.build.lib.cmdline.Label; +import com.google.devtools.build.lib.concurrent.ThreadSafety; +import com.google.devtools.build.lib.events.Event; import com.google.devtools.build.lib.packages.Attribute; -import com.google.devtools.build.lib.packages.Attribute.ConfigurationTransition; -import com.google.devtools.build.lib.packages.Attribute.SplitTransition; -import com.google.devtools.build.lib.packages.Attribute.Transition; -import com.google.devtools.build.lib.packages.InputFile; -import com.google.devtools.build.lib.packages.PackageGroup; -import com.google.devtools.build.lib.packages.Rule; -import com.google.devtools.build.lib.packages.RuleTransitionFactory; -import com.google.devtools.build.lib.packages.Target; -import com.google.devtools.build.lib.util.Preconditions; +import com.google.devtools.build.lib.packages.RuleClassProvider; +import com.google.devtools.build.lib.skyframe.BuildConfigurationValue; +import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction; +import com.google.devtools.build.lib.skyframe.TransitiveTargetValue; +import com.google.devtools.build.lib.util.OrderedSetMultimap; +import com.google.devtools.build.skyframe.SkyFunction; +import com.google.devtools.build.skyframe.SkyKey; +import com.google.devtools.build.skyframe.ValueOrException; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.Iterator; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.Set; +import javax.annotation.Nullable; /** - * Determines which configurations targets should take. + * Turns configuration transition requests into actual configurations. + * + *

This involves: + *

    + *
  1. Patching a source configuration's options with the transition + *
  2. If {@link BuildConfiguration#trimConfigurations} is true, trimming configuration fragments + * to only those needed by the destination target and its transitive dependencies + *
  3. Getting the destination configuration from Skyframe + *
    4. + *
* - *

This is the "generic engine" for configuration selection. It doesn't know anything about - * specific rules or their requirements. Rule writers decide those with appropriately placed - * {@link PatchTransition} declarations. This class then processes those declarations to determine - * final configurations. + *

For the work of determining the transition requests themselves, see + * {@link TransitionResolver}. */ public final class ConfigurationResolver { - private final DynamicTransitionMapper transitionMapper; - /** - * Instantiates this resolver with a helper class that maps non-{@link PatchTransition}s to - * {@link PatchTransition}s. + * Translates a set of {@link Dependency} objects with configuration transition requests to the + * same objects with resolved configurations. + * + *

If {@link BuildConfiguration.Options#trimConfigurations()} is true, these configurations + * only contain the fragments needed by the dep and its transitive closure. Else they + * unconditionally include all fragments. + * + *

This method is heavily performance-optimized. Because {@link ConfiguredTargetFunction} calls + * it over every edge in the configured target graph, small inefficiencies can have observable + * impact on analysis time. Keep this in mind when making modifications and performance-test any + * changes you make. + * + * @param env Skyframe evaluation environment + * @param ctgValue the label and configuration of the source target + * @param originalDeps the transition requests for each dep under this target's attributes + * @param hostConfiguration the host configuration + * @param ruleClassProvider provider for determining the right configuration fragments for deps + * + * @return a mapping from each attribute in the source target to the {@link BuildConfiguration}s + * and {@link Label}s for the deps under that attribute. Returns null if not all Skyframe + * dependencies are available. */ - public ConfigurationResolver(DynamicTransitionMapper transitionMapper) { - this.transitionMapper = transitionMapper; + @Nullable + public static OrderedSetMultimap resolveConfigurations( + SkyFunction.Environment env, + TargetAndConfiguration ctgValue, + OrderedSetMultimap originalDeps, + BuildConfiguration hostConfiguration, + RuleClassProvider ruleClassProvider) + throws ConfiguredTargetFunction.DependencyEvaluationException, InterruptedException { + + // Maps each Skyframe-evaluated BuildConfiguration to the dependencies that need that + // configuration. For cases where Skyframe isn't needed to get the configuration (e.g. when + // we just re-used the original rule's configuration), we should skip this outright. + Multimap> keysToEntries = LinkedListMultimap.create(); + + // Stores the result of applying a transition to the current configuration using a + // particular subset of fragments. By caching this, we save from redundantly computing the + // same transition for every dependency edge that requests that transition. This can have + // real effect on analysis time for commonly triggered transitions. + // + // Split transitions may map to multiple values. All other transitions map to one. + Map> transitionsMap = new LinkedHashMap<>(); + + // The fragments used by the current target's configuration. + Set> ctgFragments = + ctgValue.getConfiguration().fragmentClasses(); + BuildOptions ctgOptions = ctgValue.getConfiguration().getOptions(); + + // Stores the configuration-resolved versions of each dependency. This method must preserve the + // original label ordering of each attribute. For example, if originalDeps.get("data") is + // [":a", ":b"], the resolved variant must also be [":a", ":b"] in the same order. Because we + // may not actualize the results in order (some results need Skyframe-evaluated configurations + // while others can be computed trivially), we dump them all into this map, then as a final step + // iterate through the original list and pluck out values from here for the final value. + // + // For split transitions, originaldeps.get("data") = [":a", ":b"] can produce the output + // [":a", ":a", ..., ":b", ":b", ...]. All instances of ":a" + // still appear before all instances of ":b". But the [":a", ":a""] subset may + // be in any (deterministic) order. In particular, this may not be the same order as + // SplitTransition.split. If needed, this code can be modified to use that order, but that + // involves more runtime in performance-critical code, so we won't make that change without a + // clear need. + // + // This map is used heavily by all builds. Inserts and gets should be as fast as possible. + Multimap resolvedDeps = LinkedHashMultimap.create(); + + // Performance optimization: This method iterates over originalDeps twice. By storing + // AttributeAndLabel instances in this list, we avoid having to recreate them the second time + // (particularly avoid recomputing their hash codes). Profiling shows this shaves 25% off this + // method's execution time (at the time of this comment). + ArrayList attributesAndLabels = new ArrayList<>(originalDeps.size()); + + for (Map.Entry depsEntry : originalDeps.entries()) { + Dependency dep = depsEntry.getValue(); + AttributeAndLabel attributeAndLabel = + new AttributeAndLabel(depsEntry.getKey(), dep.getLabel()); + attributesAndLabels.add(attributeAndLabel); + // Certain targets (like output files) trivially re-use their input configuration. Likewise, + // deps with null configurations (e.g. source files), can be trivially computed. So we skip + // all logic in this method for these cases and just reinsert their original configurations + // when preparing final results. Note that null-configured deps are received with + // NullConfigurationDependency instead of + // Dependency(label, transition=Attribute.Configuration.Transition.NULL)). + // + // A *lot* of targets have null deps, so this produces real savings. Profiling tests over a + // simple cc_binary show this saves ~1% of total analysis phase time. + if (dep.hasExplicitConfiguration()) { + continue; + } + + // Figure out the required fragments for this dep and its transitive closure. + Set> depFragments = + getTransitiveFragments(env, dep.getLabel(), ctgValue.getConfiguration()); + if (depFragments == null) { + return null; + } + // TODO(gregce): remove the below call once we have confidence trimmed configurations always + // provide needed fragments. This unnecessarily drags performance on the critical path (up + // to 0.5% of total analysis time as profiled over a simple cc_binary). + if (ctgValue.getConfiguration().trimConfigurations()) { + checkForMissingFragments(env, ctgValue, attributeAndLabel.attribute.getName(), dep, + depFragments); + } + + boolean sameFragments = depFragments.equals(ctgFragments); + Attribute.Transition transition = dep.getTransition(); + + if (sameFragments) { + if (transition == Attribute.ConfigurationTransition.NONE) { + // The dep uses the same exact configuration. + putOnlyEntry( + resolvedDeps, + attributeAndLabel, + Dependency.withConfigurationAndAspects( + dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects())); + continue; + } else if (transition == HostTransition.INSTANCE) { + // The current rule's host configuration can also be used for the dep. We short-circuit + // the standard transition logic for host transitions because these transitions are + // uniquely frequent. It's possible, e.g., for every node in the configured target graph + // to incur multiple host transitions. So we aggressively optimize to avoid hurting + // analysis time. + putOnlyEntry( + resolvedDeps, + attributeAndLabel, + Dependency.withConfigurationAndAspects( + dep.getLabel(), hostConfiguration, dep.getAspects())); + continue; + } + } + + // Apply the transition or use the cached result if it was already applied. + FragmentsAndTransition transitionKey = new FragmentsAndTransition(depFragments, transition); + List toOptions = transitionsMap.get(transitionKey); + if (toOptions == null) { + toOptions = applyTransition(ctgOptions, transition, depFragments, ruleClassProvider, + !sameFragments); + transitionsMap.put(transitionKey, toOptions); + } + + // If the transition doesn't change the configuration, trivially re-use the original + // configuration. + if (sameFragments && toOptions.size() == 1 + && Iterables.getOnlyElement(toOptions).equals(ctgOptions)) { + putOnlyEntry( + resolvedDeps, + attributeAndLabel, + Dependency.withConfigurationAndAspects( + dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects())); + continue; + } + + // If we get here, we have to get the configuration from Skyframe. + for (BuildOptions options : toOptions) { + keysToEntries.put(BuildConfigurationValue.key(depFragments, options), depsEntry); + } + } + + // Get all BuildConfigurations we need from Skyframe. While not every value might be available, + // we don't call env.valuesMissing() here because that could be true from the earlier + // resolver.dependentNodeMap call in computeDependencies, which also calls Skyframe. This method + // doesn't need those missing values, but it still has to be called after + // resolver.dependentNodeMap because it consumes that method's output. The reason the missing + // values don't matter is because resolver.dependentNodeMap still returns "partial" results + // and this method runs over whatever's available. + // + // While there would be no *correctness* harm in nulling out early, there's significant + // *performance* harm. Profiling shows that putting "if (env.valuesMissing()) { return null; }" + // here (or even after resolver.dependentNodeMap) produces a ~30% performance hit on the + // analysis phase. That's because resolveConfiguredTargetDependencies and + // resolveAspectDependencies don't get a chance to make their own Skyframe requests before + // bailing out of this ConfiguredTargetFunction call. Ideally we could batch all requests + // from all methods into a single Skyframe call, but there are enough subtle data flow + // dependencies in ConfiguredTargetFucntion to make that impractical. + Map> depConfigValues = + env.getValuesOrThrow(keysToEntries.keySet(), InvalidConfigurationException.class); + + // Now fill in the remaining unresolved deps with the now-resolved configurations. + try { + for (Map.Entry> entry : + depConfigValues.entrySet()) { + SkyKey key = entry.getKey(); + ValueOrException valueOrException = entry.getValue(); + if (valueOrException.get() == null) { + // Instead of env.missingValues(), check for missing values here. This guarantees we only + // null out on missing values from *this specific Skyframe request*. + return null; + } + BuildConfigurationValue trimmedConfig = (BuildConfigurationValue) valueOrException.get(); + for (Map.Entry info : keysToEntries.get(key)) { + Dependency originalDep = info.getValue(); + AttributeAndLabel attr = new AttributeAndLabel(info.getKey(), originalDep.getLabel()); + Dependency resolvedDep = Dependency.withConfigurationAndAspects(originalDep.getLabel(), + trimmedConfig.getConfiguration(), originalDep.getAspects()); + if (attr.attribute.hasSplitConfigurationTransition()) { + resolvedDeps.put(attr, resolvedDep); + } else { + putOnlyEntry(resolvedDeps, attr, resolvedDep); + } + } + } + } catch (InvalidConfigurationException e) { + throw new ConfiguredTargetFunction.DependencyEvaluationException(e); + } + + return sortResolvedDeps(originalDeps, resolvedDeps, attributesAndLabels); } /** - * Given a parent rule and configuration depending on a child through an attribute, determines - * the configuration the child should take. - * - * @param fromConfig the parent rule's configuration - * @param fromRule the parent rule - * @param attribute the attribute creating the dependency (e.g. "srcs") - * @param toTarget the child target (which may or may not be a rule) - * - * @return the child's configuration, expressed as a diff from the parent's configuration. This - * is usually a {@PatchTransition} but exceptions apply (e.g. - * {@link Attribute.ConfigurationTransition}). + * Encapsulates a set of config fragments and a config transition. This can be used to determine + * the exact build options needed to set a configuration. */ - public Transition evaluateTransition(BuildConfiguration fromConfig, final Rule fromRule, - final Attribute attribute, final Target toTarget) { + @ThreadSafety.Immutable + private static final class FragmentsAndTransition { + // Treat this as immutable. The only reason this isn't an ImmutableSet is because it + // gets bound to a NestedSet.toSet() reference, which returns a Set interface. + final Set> fragments; + final Attribute.Transition transition; + private final int hashCode; - // I. Input files and package groups have no configurations. We don't want to duplicate them. - if (usesNullConfiguration(toTarget)) { - return Attribute.ConfigurationTransition.NULL; + FragmentsAndTransition(Set> fragments, + Attribute.Transition transition) { + this.fragments = fragments; + this.transition = transition; + hashCode = Objects.hash(this.fragments, this.transition); } - // II. Host configurations never switch to another. All prerequisites of host targets have the - // same host configuration. - if (fromConfig.isHostConfiguration()) { - return Attribute.ConfigurationTransition.NONE; + @Override + public boolean equals(Object o) { + if (o == this) { + return true; + } else if (o == null) { + return false; + } else { + FragmentsAndTransition other = (FragmentsAndTransition) o; + return other.transition.equals(transition) && other.fragments.equals(fragments); + } } - // Make sure config_setting dependencies are resolved in the referencing rule's configuration, - // unconditionally. For example, given: - // - // genrule( - // name = 'myrule', - // tools = select({ '//a:condition': [':sometool'] }) - // - // all labels in "tools" get resolved in the host configuration (since the "tools" attribute - // declares a host configuration transition). We want to explicitly exclude configuration labels - // from these transitions, since their *purpose* is to do computation on the owning - // rule's configuration. - // TODO(bazel-team): don't require special casing here. This is far too hackish. - if (toTarget instanceof Rule && ((Rule) toTarget).getRuleClassObject().isConfigMatcher()) { - // TODO(gregce): see if this actually gets called - return Attribute.ConfigurationTransition.NONE; - } - - // The current transition to apply. When multiple transitions are requested, this is a - // ComposingSplitTransition, which encapsulates them into a single object so calling code - // doesn't need special logic for combinations. - Transition currentTransition = Attribute.ConfigurationTransition.NONE; - - // Apply the parent rule's outgoing transition if it has one. - RuleTransitionFactory transitionFactory = - fromRule.getRuleClassObject().getOutgoingTransitionFactory(); - if (transitionFactory != null) { - Transition transition = transitionFactory.buildTransitionFor(toTarget.getAssociatedRule()); - if (transition != null) { - currentTransition = composeTransitions(currentTransition, transition); + @Override + public int hashCode() { + return hashCode; + } + } + + /** + * Encapsulates an pair that can be used to map from an input dependency to a + * trimmed dependency. + */ + @ThreadSafety.Immutable + private static final class AttributeAndLabel { + final Attribute attribute; + final Label label; + Integer hashCode; + + AttributeAndLabel(Attribute attribute, Label label) { + this.attribute = attribute; + this.label = label; + } + + @Override + public boolean equals(Object o) { + if (!(o instanceof AttributeAndLabel)) { + return false; } + AttributeAndLabel other = (AttributeAndLabel) o; + return Objects.equals(other.attribute, attribute) && other.label.equals(label); } - // TODO(gregce): make the below transitions composable (i.e. take away the "else" clauses). - // The "else" is a legacy restriction from static configurations. - if (attribute.hasSplitConfigurationTransition()) { - currentTransition = split(currentTransition, - (SplitTransition) attribute.getSplitTransition(fromRule)); - } else { - // III. Attributes determine configurations. The configuration of a prerequisite is determined - // by the attribute. - currentTransition = composeTransitions(currentTransition, - attribute.getConfigurationTransition()); + @Override + public int hashCode() { + if (hashCode == null) { + // Not every pair gets hashed. So only evaluate for the instances that + // need it. This can significantly reduce the number of evaluations. + hashCode = Objects.hash(this.attribute, this.label); + } + return hashCode; } + } - return applyConfigurationHook(currentTransition, toTarget); + /** + * Variation of {@link Multimap#put} that triggers an exception if a value already exists. + */ + @VisibleForTesting + public static void putOnlyEntry(Multimap map, K key, V value) { + // Performance note: while "Verify.verify(!map.containsKey(key, value), String.format(...)))" + // is simpler code, profiling shows a substantial performance penalty to that approach + // (~10% extra analysis phase time on a simple cc_binary). Most of that is from the cost of + // evaluating value.toString() on every call. This approach essentially eliminates the overhead. + if (map.containsKey(key)) { + throw new VerifyException( + String.format("couldn't insert %s: map already has key %s", + value.toString(), key.toString())); + } + map.put(key, value); } + /** - * Returns true if the given target should have a null configuration. This method is the - * "source of truth" for this determination. + * Returns the configuration fragments required by a dep and its transitive closure. + * Returns null if Skyframe dependencies aren't yet available. + * + * @param env Skyframe evaluation environment + * @param dep label of the dep to check + * @param parentConfig configuration of the rule depending on the dep */ - public static boolean usesNullConfiguration(Target target) { - return target instanceof InputFile || target instanceof PackageGroup; + @Nullable + private static Set> getTransitiveFragments( + SkyFunction.Environment env, Label dep, BuildConfiguration parentConfig) + throws InterruptedException { + if (!parentConfig.trimConfigurations()) { + return parentConfig.getAllFragments().keySet(); + } + SkyKey fragmentsKey = TransitiveTargetValue.key(dep); + TransitiveTargetValue transitiveDepInfo = (TransitiveTargetValue) env.getValue(fragmentsKey); + if (transitiveDepInfo == null) { + // This should only be possible for tests. In actual runs, this was already called + // as a routine part of the loading phase. + // TODO(bazel-team): check this only occurs in a test context. + return null; + } + return transitiveDepInfo.getTransitiveConfigFragments().toSet(); } /** - * Composes two transitions together efficiently. + * Applies a configuration transition over a set of build options. + * + * @return the build options for the transitioned configuration. If trimResults is true, + * only options needed by the required fragments are included. Else the same options as the + * original input are included (with different possible values, of course). */ @VisibleForTesting - public Transition composeTransitions(Transition transition1, Transition transition2) { - if (isFinal(transition1)) { - return transition1; - } else if (transition2 == Attribute.ConfigurationTransition.NONE) { - return transition1; - } else if (transition2 == Attribute.ConfigurationTransition.NULL) { - // A NULL transition can just replace earlier transitions: no need to cfpose them. - return Attribute.ConfigurationTransition.NULL; - } else if (transition2 == Attribute.ConfigurationTransition.HOST) { - // A HOST transition can just replace earlier transitions: no need to compose them. - // But it also improves performance: host transitions are common, and - // ConfiguredTargetFunction has special optimized logic to handle them. If they were buried - // in the last segment of a ComposingSplitTransition, those optimizations wouldn't trigger. - return HostTransition.INSTANCE; - } - - // TODO(gregce): remove the below conversion when all transitions are patch transitions. - Transition dynamicTransition = transitionMapper.map(transition2); - return transition1 == Attribute.ConfigurationTransition.NONE - ? dynamicTransition - : new ComposingSplitTransition(transition1, dynamicTransition); + public static List applyTransition(BuildOptions fromOptions, + Attribute.Transition transition, + Iterable> requiredFragments, + RuleClassProvider ruleClassProvider, boolean trimResults) { + List result; + if (transition == Attribute.ConfigurationTransition.NONE) { + result = ImmutableList.of(fromOptions); + } else if (transition instanceof PatchTransition) { + // TODO(bazel-team): safety-check that this never mutates fromOptions. + result = ImmutableList.of(((PatchTransition) transition).apply(fromOptions)); + } else if (transition instanceof Attribute.SplitTransition) { + @SuppressWarnings("unchecked") // Attribute.java doesn't have the BuildOptions symbol. + List toOptions = + ((Attribute.SplitTransition) transition).split(fromOptions); + if (toOptions.isEmpty()) { + // When the split returns an empty list, it's signaling it doesn't apply to this instance. + // So return the original options. + result = ImmutableList.of(fromOptions); + } else { + result = toOptions; + } + } else { + throw new IllegalStateException(String.format( + "unsupported config transition type: %s", transition.getClass().getName())); + } + + if (!trimResults) { + return result; + } else { + ImmutableList.Builder trimmedOptions = ImmutableList.builder(); + for (BuildOptions toOptions : result) { + trimmedOptions.add(toOptions.trim( + BuildConfiguration.getOptionsClasses(requiredFragments, ruleClassProvider))); + } + return trimmedOptions.build(); + } } /** - * Returns true if once the given transition is applied to a dep no followup transitions should - * be composed after it. + * Checks the config fragments required by a dep against the fragments in its actual + * configuration. If any are missing, triggers a descriptive "missing fragments" error. */ - private static boolean isFinal(Transition transition) { - return (transition == Attribute.ConfigurationTransition.NULL - || transition == HostTransition.INSTANCE); + private static void checkForMissingFragments(SkyFunction.Environment env, + TargetAndConfiguration ctgValue, String attribute, Dependency dep, + Set> expectedDepFragments) + throws ConfiguredTargetFunction.DependencyEvaluationException { + Set ctgFragmentNames = new HashSet<>(); + for (BuildConfiguration.Fragment fragment : + ctgValue.getConfiguration().getAllFragments().values()) { + ctgFragmentNames.add(fragment.getClass().getSimpleName()); + } + Set depFragmentNames = new HashSet<>(); + for (Class fragmentClass : expectedDepFragments) { + depFragmentNames.add(fragmentClass.getSimpleName()); + } + Set missing = Sets.difference(depFragmentNames, ctgFragmentNames); + if (!missing.isEmpty()) { + String msg = String.format( + "%s: dependency %s from attribute \"%s\" is missing required config fragments: %s", + ctgValue.getLabel(), dep.getLabel(), attribute, Joiner.on(", ").join(missing)); + env.getListener().handle(Event.error(msg)); + throw new ConfiguredTargetFunction.DependencyEvaluationException( + new InvalidConfigurationException(msg)); + } } /** - * Applies the given split and composes it after an existing transition. + * Determines the output ordering of each -> + * [dep, dep, ...] collection produced by a split transition. */ - private static Transition split(Transition currentTransition, - SplitTransition split) { - Preconditions.checkState(currentTransition != Attribute.ConfigurationTransition.NULL, - "cannot apply splits after null transitions (null transitions are expected to be final)"); - Preconditions.checkState(currentTransition != HostTransition.INSTANCE, - "cannot apply splits after host transitions (host transitions are expected to be final)"); - return currentTransition == Attribute.ConfigurationTransition.NONE - ? split - : new ComposingSplitTransition(currentTransition, split); - } + @VisibleForTesting + public static final Comparator SPLIT_DEP_ORDERING = + new Comparator() { + @Override + public int compare(Dependency d1, Dependency d2) { + return d1.getConfiguration().getMnemonic().compareTo(d2.getConfiguration().getMnemonic()); + } + }; /** - * Applies any configuration hooks associated with the dep target, composes their transitions - * after an existing transition, and returns the composed result. + * Returns a copy of the output deps using the same key and value ordering as the input deps. + * + * @param originalDeps the input deps with the ordering to preserve + * @param resolvedDeps the unordered output deps + * @param attributesAndLabels collection of pairs guaranteed to match + * the ordering of originalDeps.entries(). This is a performance optimization: see + * {@link #resolveConfigurations#attributesAndLabels} for details. */ - private Transition applyConfigurationHook(Transition currentTransition, Target toTarget) { - if (isFinal(currentTransition)) { - return currentTransition; - } - Rule associatedRule = toTarget.getAssociatedRule(); - RuleTransitionFactory transitionFactory = - associatedRule.getRuleClassObject().getTransitionFactory(); - if (transitionFactory != null) { - // transitionMapper is only needed because of Attribute.ConfigurationTransition.DATA: this is - // C++-specific but non-C++ rules declare it. So they can't directly provide the C++-specific - // patch transition that implements it. - PatchTransition ruleClassTransition = (PatchTransition) - transitionMapper.map(transitionFactory.buildTransitionFor(associatedRule)); - if (ruleClassTransition != null) { - if (currentTransition == ConfigurationTransition.NONE) { - return ruleClassTransition; - } else { - return new ComposingSplitTransition(currentTransition, ruleClassTransition); + private static OrderedSetMultimap sortResolvedDeps( + OrderedSetMultimap originalDeps, + Multimap resolvedDeps, + ArrayList attributesAndLabels) { + Iterator iterator = attributesAndLabels.iterator(); + OrderedSetMultimap result = OrderedSetMultimap.create(); + for (Map.Entry depsEntry : originalDeps.entries()) { + AttributeAndLabel attrAndLabel = iterator.next(); + if (depsEntry.getValue().hasExplicitConfiguration()) { + result.put(attrAndLabel.attribute, depsEntry.getValue()); + } else { + Collection resolvedDepWithSplit = resolvedDeps.get(attrAndLabel); + Verify.verify(!resolvedDepWithSplit.isEmpty()); + if (resolvedDepWithSplit.size() > 1) { + List sortedSplitList = new ArrayList<>(resolvedDepWithSplit); + Collections.sort(sortedSplitList, SPLIT_DEP_ORDERING); + resolvedDepWithSplit = sortedSplitList; } + result.putAll(depsEntry.getKey(), resolvedDepWithSplit); } } - return currentTransition; + return result; } } diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/TransitionResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/config/TransitionResolver.java new file mode 100644 index 0000000000..ebcefb6eb2 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/analysis/config/TransitionResolver.java @@ -0,0 +1,211 @@ +// Copyright 2017 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.analysis.config; + +import com.google.common.annotations.VisibleForTesting; +import com.google.devtools.build.lib.packages.Attribute; +import com.google.devtools.build.lib.packages.Attribute.ConfigurationTransition; +import com.google.devtools.build.lib.packages.Attribute.SplitTransition; +import com.google.devtools.build.lib.packages.Attribute.Transition; +import com.google.devtools.build.lib.packages.InputFile; +import com.google.devtools.build.lib.packages.PackageGroup; +import com.google.devtools.build.lib.packages.Rule; +import com.google.devtools.build.lib.packages.RuleTransitionFactory; +import com.google.devtools.build.lib.packages.Target; +import com.google.devtools.build.lib.util.Preconditions; + +/** + * Determines the {@link Attribute.Transition}s dependencies should apply to their parents' + * configurations. + * + *

For the work of turning these transitions into actual configurations, see + * {@link ConfigurationResolver}. + * + *

This is the "generic engine" for configuration selection. It doesn't know anything about + * specific rules or their requirements. Rule writers decide those with appropriately placed + * {@link PatchTransition} declarations. This class then processes those declarations to determine + * final transitions. + */ +public final class TransitionResolver { + private final DynamicTransitionMapper transitionMapper; + + /** + * Instantiates this resolver with a helper class that maps non-{@link PatchTransition}s to + * {@link PatchTransition}s. + */ + public TransitionResolver(DynamicTransitionMapper transitionMapper) { + this.transitionMapper = transitionMapper; + } + + /** + * Given a parent rule and configuration depending on a child through an attribute, determines + * the configuration the child should take. + * + * @param fromConfig the parent rule's configuration + * @param fromRule the parent rule + * @param attribute the attribute creating the dependency (e.g. "srcs") + * @param toTarget the child target (which may or may not be a rule) + * + * @return the child's configuration, expressed as a diff from the parent's configuration. This + * is usually a {@PatchTransition} but exceptions apply (e.g. + * {@link Attribute.ConfigurationTransition}). + */ + public Transition evaluateTransition(BuildConfiguration fromConfig, final Rule fromRule, + final Attribute attribute, final Target toTarget) { + + // I. Input files and package groups have no configurations. We don't want to duplicate them. + if (usesNullConfiguration(toTarget)) { + return Attribute.ConfigurationTransition.NULL; + } + + // II. Host configurations never switch to another. All prerequisites of host targets have the + // same host configuration. + if (fromConfig.isHostConfiguration()) { + return Attribute.ConfigurationTransition.NONE; + } + + // Make sure config_setting dependencies are resolved in the referencing rule's configuration, + // unconditionally. For example, given: + // + // genrule( + // name = 'myrule', + // tools = select({ '//a:condition': [':sometool'] }) + // + // all labels in "tools" get resolved in the host configuration (since the "tools" attribute + // declares a host configuration transition). We want to explicitly exclude configuration labels + // from these transitions, since their *purpose* is to do computation on the owning + // rule's configuration. + // TODO(bazel-team): don't require special casing here. This is far too hackish. + if (toTarget instanceof Rule && ((Rule) toTarget).getRuleClassObject().isConfigMatcher()) { + // TODO(gregce): see if this actually gets called + return Attribute.ConfigurationTransition.NONE; + } + + // The current transition to apply. When multiple transitions are requested, this is a + // ComposingSplitTransition, which encapsulates them into a single object so calling code + // doesn't need special logic for combinations. + Transition currentTransition = Attribute.ConfigurationTransition.NONE; + + // Apply the parent rule's outgoing transition if it has one. + RuleTransitionFactory transitionFactory = + fromRule.getRuleClassObject().getOutgoingTransitionFactory(); + if (transitionFactory != null) { + Transition transition = transitionFactory.buildTransitionFor(toTarget.getAssociatedRule()); + if (transition != null) { + currentTransition = composeTransitions(currentTransition, transition); + } + } + + // TODO(gregce): make the below transitions composable (i.e. take away the "else" clauses). + // The "else" is a legacy restriction from static configurations. + if (attribute.hasSplitConfigurationTransition()) { + currentTransition = split(currentTransition, + (SplitTransition) attribute.getSplitTransition(fromRule)); + } else { + // III. Attributes determine configurations. The configuration of a prerequisite is determined + // by the attribute. + currentTransition = composeTransitions(currentTransition, + attribute.getConfigurationTransition()); + } + + return applyConfigurationHook(currentTransition, toTarget); + } + + /** + * Returns true if the given target should have a null configuration. This method is the + * "source of truth" for this determination. + */ + public static boolean usesNullConfiguration(Target target) { + return target instanceof InputFile || target instanceof PackageGroup; + } + + /** + * Composes two transitions together efficiently. + */ + @VisibleForTesting + public Transition composeTransitions(Transition transition1, Transition transition2) { + if (isFinal(transition1)) { + return transition1; + } else if (transition2 == Attribute.ConfigurationTransition.NONE) { + return transition1; + } else if (transition2 == Attribute.ConfigurationTransition.NULL) { + // A NULL transition can just replace earlier transitions: no need to compose them. + return Attribute.ConfigurationTransition.NULL; + } else if (transition2 == Attribute.ConfigurationTransition.HOST) { + // A HOST transition can just replace earlier transitions: no need to compose them. + // But it also improves performance: host transitions are common, and + // ConfiguredTargetFunction has special optimized logic to handle them. If they were buried + // in the last segment of a ComposingSplitTransition, those optimizations wouldn't trigger. + return HostTransition.INSTANCE; + } + + // TODO(gregce): remove the below conversion when all transitions are patch transitions. + Transition dynamicTransition = transitionMapper.map(transition2); + return transition1 == Attribute.ConfigurationTransition.NONE + ? dynamicTransition + : new ComposingSplitTransition(transition1, dynamicTransition); + } + + /** + * Returns true if once the given transition is applied to a dep no followup transitions should + * be composed after it. + */ + private static boolean isFinal(Transition transition) { + return (transition == Attribute.ConfigurationTransition.NULL + || transition == HostTransition.INSTANCE); + } + + /** + * Applies the given split and composes it after an existing transition. + */ + private static Transition split(Transition currentTransition, + SplitTransition split) { + Preconditions.checkState(currentTransition != Attribute.ConfigurationTransition.NULL, + "cannot apply splits after null transitions (null transitions are expected to be final)"); + Preconditions.checkState(currentTransition != HostTransition.INSTANCE, + "cannot apply splits after host transitions (host transitions are expected to be final)"); + return currentTransition == Attribute.ConfigurationTransition.NONE + ? split + : new ComposingSplitTransition(currentTransition, split); + } + + /** + * Applies any configuration hooks associated with the dep target, composes their transitions + * after an existing transition, and returns the composed result. + */ + private Transition applyConfigurationHook(Transition currentTransition, Target toTarget) { + if (isFinal(currentTransition)) { + return currentTransition; + } + Rule associatedRule = toTarget.getAssociatedRule(); + RuleTransitionFactory transitionFactory = + associatedRule.getRuleClassObject().getTransitionFactory(); + if (transitionFactory != null) { + // transitionMapper is only needed because of Attribute.ConfigurationTransition.DATA: this is + // C++-specific but non-C++ rules declare it. So they can't directly provide the C++-specific + // patch transition that implements it. + PatchTransition ruleClassTransition = (PatchTransition) + transitionMapper.map(transitionFactory.buildTransitionFor(associatedRule)); + if (ruleClassTransition != null) { + if (currentTransition == ConfigurationTransition.NONE) { + return ruleClassTransition; + } else { + return new ComposingSplitTransition(currentTransition, ruleClassTransition); + } + } + } + return currentTransition; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java index 715ecf23d9..c157351ba2 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java @@ -13,20 +13,12 @@ // limitations under the License. package com.google.devtools.build.lib.skyframe; -import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.Joiner; import com.google.common.base.Supplier; -import com.google.common.base.Verify; -import com.google.common.base.VerifyException; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; -import com.google.common.collect.LinkedHashMultimap; -import com.google.common.collect.LinkedListMultimap; import com.google.common.collect.Maps; -import com.google.common.collect.Multimap; -import com.google.common.collect.Sets; import com.google.devtools.build.lib.actions.Actions; import com.google.devtools.build.lib.actions.Actions.GeneratingActions; import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException; @@ -42,18 +34,15 @@ import com.google.devtools.build.lib.analysis.LabelAndConfiguration; import com.google.devtools.build.lib.analysis.TargetAndConfiguration; import com.google.devtools.build.lib.analysis.ToolchainContext; import com.google.devtools.build.lib.analysis.config.BuildConfiguration; -import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider; -import com.google.devtools.build.lib.analysis.config.HostTransition; +import com.google.devtools.build.lib.analysis.config.ConfigurationResolver; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; -import com.google.devtools.build.lib.analysis.config.PatchTransition; import com.google.devtools.build.lib.analysis.configuredtargets.MergedConfiguredTarget; import com.google.devtools.build.lib.analysis.configuredtargets.MergedConfiguredTarget.DuplicateException; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.collect.nestedset.NestedSet; import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; import com.google.devtools.build.lib.collect.nestedset.Order; -import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable; import com.google.devtools.build.lib.events.Event; import com.google.devtools.build.lib.events.StoredEventHandler; import com.google.devtools.build.lib.packages.Aspect; @@ -81,17 +70,12 @@ import com.google.devtools.build.skyframe.SkyKey; import com.google.devtools.build.skyframe.SkyValue; import com.google.devtools.build.skyframe.ValueOrException; import com.google.devtools.build.skyframe.ValueOrException2; -import java.util.ArrayList; + import java.util.Collection; -import java.util.Collections; -import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; -import java.util.Iterator; import java.util.LinkedHashMap; -import java.util.List; import java.util.Map; -import java.util.Objects; import java.util.Set; import java.util.concurrent.Semaphore; import javax.annotation.Nullable; @@ -401,8 +385,8 @@ public final class ConfiguredTargetFunction implements SkyFunction { // Trim each dep's configuration so it only includes the fragments needed by its transitive // closure. if (ctgValue.getConfiguration() != null) { - depValueNames = getDynamicConfigurations(env, ctgValue, depValueNames, hostConfiguration, - ruleClassProvider); + depValueNames = ConfigurationResolver.resolveConfigurations(env, ctgValue, depValueNames, + hostConfiguration, ruleClassProvider); // It's important that we don't use "if (env.missingValues()) { return null }" here (or // in the following lines). See the comments in getDynamicConfigurations' Skyframe call // for explanation. @@ -437,454 +421,6 @@ public final class ConfiguredTargetFunction implements SkyFunction { } } - /** - * Helper class for {@link #getDynamicConfigurations} - encapsulates a set of config fragments and - * a dynamic transition. This can be used to determine the exact build options needed to - * set a dynamic configuration. - */ - @Immutable - private static final class FragmentsAndTransition { - // Treat this as immutable. The only reason this isn't an ImmutableSet is because it - // gets bound to a NestedSet.toSet() reference, which returns a Set interface. - final Set> fragments; - final Attribute.Transition transition; - private final int hashCode; - - FragmentsAndTransition(Set> fragments, - Attribute.Transition transition) { - this.fragments = fragments; - this.transition = transition; - hashCode = Objects.hash(this.fragments, this.transition); - } - - @Override - public boolean equals(Object o) { - if (o == this) { - return true; - } else if (o == null) { - return false; - } else { - FragmentsAndTransition other = (FragmentsAndTransition) o; - return other.transition.equals(transition) && other.fragments.equals(fragments); - } - } - - @Override - public int hashCode() { - return hashCode; - } - } - - /** - * Helper class for {@link #getDynamicConfigurations} - encapsulates an pair - * that can be used to map from an input dependency to a trimmed dependency. - */ - @Immutable - private static final class AttributeAndLabel { - final Attribute attribute; - final Label label; - Integer hashCode; - - AttributeAndLabel(Attribute attribute, Label label) { - this.attribute = attribute; - this.label = label; - } - - @Override - public boolean equals(Object o) { - if (!(o instanceof AttributeAndLabel)) { - return false; - } - AttributeAndLabel other = (AttributeAndLabel) o; - return Objects.equals(other.attribute, attribute) && other.label.equals(label); - } - - @Override - public int hashCode() { - if (hashCode == null) { - // Not every pair gets hashed. So only evaluate for the instances that - // need it. This can significantly reduce the number of evaluations. - hashCode = Objects.hash(this.attribute, this.label); - } - return hashCode; - } - } - - /** - * Variation of {@link Multimap#put} that triggers an exception if a value already exists. - */ - @VisibleForTesting - static void putOnlyEntry(Multimap map, K key, V value) { - // Performance note: while "Verify.verify(!map.containsKey(key, value), String.format(...)))" - // is simpler code, profiling shows a substantial performance penalty to that approach - // (~10% extra analysis phase time on a simple cc_binary). Most of that is from the cost of - // evaluating value.toString() on every call. This approach essentially eliminates the overhead. - if (map.containsKey(key)) { - throw new VerifyException( - String.format("couldn't insert %s: map already has key %s", - value.toString(), key.toString())); - } - map.put(key, value); - } - - /** - * Creates a dynamic configuration for each dep that's custom-fitted specifically for that dep. - * - *

More specifically: given a set of {@link Dependency} instances holding dynamic config - * transition requests (e.g. {@link Dependency#hasExplicitConfiguration()} == false}), returns - * equivalent dependencies containing dynamically created configurations applying those - * transitions. If {@link BuildConfiguration.Options#trimConfigurations()} is true, these - * configurations only contain the fragments needed by the dep and its transitive closure. Else - * the configurations unconditionally include all fragments. - * - *

This method is heavily performance-optimized. Because it, in aggregate, reads over every - * edge in the configured target graph, small inefficiencies can have observable impact on - * analysis time. Keep this in mind when making modifications and performance-test any changes you - * make. - * - * @param env Skyframe evaluation environment - * @param ctgValue the label and the configuration of the node - * @param originalDeps the set of configuration transition requests for this target's attributes - * @param hostConfiguration the host configuration - * @param ruleClassProvider the rule class provider for determining the right configuration - * fragments to apply to deps - * - * @return a mapping from each attribute to the {@link BuildConfiguration}s and {@link Label}s - * to use for that attribute's deps. Returns null if not all Skyframe dependencies are - * available yet. - */ - @Nullable - static OrderedSetMultimap getDynamicConfigurations( - Environment env, - TargetAndConfiguration ctgValue, - OrderedSetMultimap originalDeps, - BuildConfiguration hostConfiguration, - RuleClassProvider ruleClassProvider) - throws DependencyEvaluationException, InterruptedException { - - // Maps each Skyframe-evaluated BuildConfiguration to the dependencies that need that - // configuration. For cases where Skyframe isn't needed to get the configuration (e.g. when - // we just re-used the original rule's configuration), we should skip this outright. - Multimap> keysToEntries = LinkedListMultimap.create(); - - // Stores the result of applying a dynamic transition to the current configuration using a - // particular subset of fragments. By caching this, we save from redundantly computing the - // same transition for every dependency edge that requests that transition. This can have - // real effect on analysis time for commonly triggered transitions. - // - // Split transitions may map to multiple values. All other transitions map to one. - Map> transitionsMap = new LinkedHashMap<>(); - - // The fragments used by the current target's configuration. - Set> ctgFragments = - ctgValue.getConfiguration().fragmentClasses(); - BuildOptions ctgOptions = ctgValue.getConfiguration().getOptions(); - - // Stores the dynamically configured versions of each dependency. This method must preserve the - // original label ordering of each attribute. For example, if originalDeps.get("data") is - // [":a", ":b"], the dynamic variant must also be [":a", ":b"] in the same order. Because we may - // not actualize the results in order (some results need Skyframe-evaluated configurations while - // others can be computed trivially), we dump them all into this map, then as a final step - // iterate through the original list and pluck out values from here for the final value. - // - // For split transitions, originaldeps.get("data") = [":a", ":b"] can produce the output - // [":a", ":a", ..., ":b", ":b", ...]. All instances of ":a" - // still appear before all instances of ":b". But the [":a", ":a""] subset may - // be in any (deterministic) order. In particular, this may not be the same order as - // SplitTransition.split. If needed, this code can be modified to use that order, but that - // involves more runtime in performance-critical code, so we won't make that change without a - // clear need. - // - // This map is used heavily by all builds. Inserts and gets should be as fast as possible. - Multimap dynamicDeps = LinkedHashMultimap.create(); - - // Performance optimization: This method iterates over originalDeps twice. By storing - // AttributeAndLabel instances in this list, we avoid having to recreate them the second time - // (particularly avoid recomputing their hash codes). Profiling shows this shaves 25% off this - // method's execution time (at the time of this comment). - ArrayList attributesAndLabels = new ArrayList<>(originalDeps.size()); - - for (Map.Entry depsEntry : originalDeps.entries()) { - Dependency dep = depsEntry.getValue(); - AttributeAndLabel attributeAndLabel = - new AttributeAndLabel(depsEntry.getKey(), dep.getLabel()); - attributesAndLabels.add(attributeAndLabel); - // Certain targets (like output files) trivially re-use their input configuration. Likewise, - // deps with null configurations (e.g. source files), can be trivially computed. So we skip - // all logic in this method for these cases and just reinsert their original configurations - // back at the end (note that null-configured targets will have a static - // NullConfigurationDependency instead of dynamic - // Dependency(label, transition=Attribute.Configuration.Transition.NULL)). - // - // A *lot* of targets have null deps, so this produces real savings. Profiling tests over a - // simple cc_binary show this saves ~1% of total analysis phase time. - if (dep.hasExplicitConfiguration()) { - continue; - } - - // Figure out the required fragments for this dep and its transitive closure. - Set> depFragments = - getTransitiveFragments(env, dep.getLabel(), ctgValue.getConfiguration()); - if (depFragments == null) { - return null; - } - // TODO(gregce): remove the below call once we have confidence dynamic configurations always - // provide needed fragments. This unnecessarily drags performance on the critical path (up - // to 0.5% of total analysis time as profiled over a simple cc_binary). - if (ctgValue.getConfiguration().trimConfigurations()) { - checkForMissingFragments(env, ctgValue, attributeAndLabel.attribute.getName(), dep, - depFragments); - } - - boolean sameFragments = depFragments.equals(ctgFragments); - Attribute.Transition transition = dep.getTransition(); - - if (sameFragments) { - if (transition == Attribute.ConfigurationTransition.NONE) { - // The dep uses the same exact configuration. - putOnlyEntry( - dynamicDeps, - attributeAndLabel, - Dependency.withConfigurationAndAspects( - dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects())); - continue; - } else if (transition == HostTransition.INSTANCE) { - // The current rule's host configuration can also be used for the dep. We short-circuit - // the standard transition logic for host transitions because these transitions are - // uniquely frequent. It's possible, e.g., for every node in the configured target graph - // to incur multiple host transitions. So we aggressively optimize to avoid hurting - // analysis time. - putOnlyEntry( - dynamicDeps, - attributeAndLabel, - Dependency.withConfigurationAndAspects( - dep.getLabel(), hostConfiguration, dep.getAspects())); - continue; - } - } - - // Apply the transition or use the cached result if it was already applied. - FragmentsAndTransition transitionKey = new FragmentsAndTransition(depFragments, transition); - List toOptions = transitionsMap.get(transitionKey); - if (toOptions == null) { - toOptions = getDynamicTransitionOptions(ctgOptions, transition, depFragments, - ruleClassProvider, !sameFragments); - transitionsMap.put(transitionKey, toOptions); - } - - // If the transition doesn't change the configuration, trivially re-use the original - // configuration. - if (sameFragments && toOptions.size() == 1 - && Iterables.getOnlyElement(toOptions).equals(ctgOptions)) { - putOnlyEntry( - dynamicDeps, - attributeAndLabel, - Dependency.withConfigurationAndAspects( - dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects())); - continue; - } - - // If we get here, we have to get the configuration from Skyframe. - for (BuildOptions options : toOptions) { - keysToEntries.put(BuildConfigurationValue.key(depFragments, options), depsEntry); - } - } - - // Get all BuildConfigurations we need from Skyframe. While not every value might be available, - // we don't call env.valuesMissing() here because that could be true from the earlier - // resolver.dependentNodeMap call in computeDependencies, which also calls Skyframe. This method - // doesn't need those missing values, but it still has to be called after - // resolver.dependentNodeMap because it consumes that method's output. The reason the missing - // values don't matter is because resolver.dependentNodeMap still returns "partial" results - // and this method runs over whatever's available. - // - // While there would be no *correctness* harm in nulling out early, there's significant - // *performance* harm. Profiling shows that putting "if (env.valuesMissing()) { return null; }" - // here (or even after resolver.dependentNodeMap) produces a ~30% performance hit on the - // analysis phase. That's because resolveConfiguredTargetDependencies and - // resolveAspectDependencies don't get a chance to make their own Skyframe requests before - // bailing out of this ConfiguredTargetFunction call. Ideally we could batch all requests - // from all methods into a single Skyframe call, but there are enough subtle data flow - // dependencies in ConfiguredTargetFucntion to make that impractical. - Map> depConfigValues = - env.getValuesOrThrow(keysToEntries.keySet(), InvalidConfigurationException.class); - - // Now fill in the remaining unresolved deps with the now-resolved configurations. - try { - for (Map.Entry> entry : - depConfigValues.entrySet()) { - SkyKey key = entry.getKey(); - ValueOrException valueOrException = entry.getValue(); - if (valueOrException.get() == null) { - // Instead of env.missingValues(), check for missing values here. This guarantees we only - // null out on missing values from *this specific Skyframe request*. - return null; - } - BuildConfigurationValue trimmedConfig = (BuildConfigurationValue) valueOrException.get(); - for (Map.Entry info : keysToEntries.get(key)) { - Dependency originalDep = info.getValue(); - AttributeAndLabel attr = new AttributeAndLabel(info.getKey(), originalDep.getLabel()); - Dependency resolvedDep = Dependency.withConfigurationAndAspects(originalDep.getLabel(), - trimmedConfig.getConfiguration(), originalDep.getAspects()); - if (attr.attribute.hasSplitConfigurationTransition()) { - dynamicDeps.put(attr, resolvedDep); - } else { - putOnlyEntry(dynamicDeps, attr, resolvedDep); - } - } - } - } catch (InvalidConfigurationException e) { - throw new DependencyEvaluationException(e); - } - - return sortDynamicallyConfiguredDeps(originalDeps, dynamicDeps, attributesAndLabels); - } - - /** - * Returns the configuration fragments required by a dep and its transitive closure. - * Returns null if Skyframe dependencies aren't yet available. - * - * @param env Skyframe evaluation environment - * @param dep label of the dep to check - * @param parentConfig configuration of the rule depending on the dep - */ - @Nullable - private static Set> getTransitiveFragments( - Environment env, Label dep, BuildConfiguration parentConfig) throws InterruptedException { - if (!parentConfig.trimConfigurations()) { - return parentConfig.getAllFragments().keySet(); - } - SkyKey fragmentsKey = TransitiveTargetValue.key(dep); - TransitiveTargetValue transitiveDepInfo = (TransitiveTargetValue) env.getValue(fragmentsKey); - if (transitiveDepInfo == null) { - // This should only be possible for tests. In actual runs, this was already called - // as a routine part of the loading phase. - // TODO(bazel-team): check this only occurs in a test context. - return null; - } - return transitiveDepInfo.getTransitiveConfigFragments().toSet(); - } - - /** - * Applies a dynamic configuration transition over a set of build options. - * - * @return the build options for the transitioned configuration. If trimResults is true, - * only options needed by the required fragments are included. Else the same options as the - * original input are included (with different possible values, of course). - */ - static List getDynamicTransitionOptions(BuildOptions fromOptions, - Attribute.Transition transition, - Iterable> requiredFragments, - RuleClassProvider ruleClassProvider, boolean trimResults) { - List result; - if (transition == Attribute.ConfigurationTransition.NONE) { - result = ImmutableList.of(fromOptions); - } else if (transition instanceof PatchTransition) { - // TODO(bazel-team): safety-check that this never mutates fromOptions. - result = ImmutableList.of(((PatchTransition) transition).apply(fromOptions)); - } else if (transition instanceof Attribute.SplitTransition) { - @SuppressWarnings("unchecked") // Attribute.java doesn't have the BuildOptions symbol. - List toOptions = - ((Attribute.SplitTransition) transition).split(fromOptions); - if (toOptions.isEmpty()) { - // When the split returns an empty list, it's signaling it doesn't apply to this instance. - // So return the original options. - result = ImmutableList.of(fromOptions); - } else { - result = toOptions; - } - } else { - throw new IllegalStateException(String.format( - "unsupported dynamic transition type: %s", transition.getClass().getName())); - } - - if (!trimResults) { - return result; - } else { - ImmutableList.Builder trimmedOptions = ImmutableList.builder(); - for (BuildOptions toOptions : result) { - trimmedOptions.add(toOptions.trim( - BuildConfiguration.getOptionsClasses(requiredFragments, ruleClassProvider))); - } - return trimmedOptions.build(); - } - } - - /** - * Diagnostic helper method for dynamic configurations: checks the config fragments required by - * a dep against the fragments in its actual configuration. If any are missing, triggers a - * descriptive "missing fragments" error. - */ - private static void checkForMissingFragments(Environment env, TargetAndConfiguration ctgValue, - String attribute, Dependency dep, - Set> expectedDepFragments) - throws DependencyEvaluationException { - Set ctgFragmentNames = new HashSet<>(); - for (BuildConfiguration.Fragment fragment : - ctgValue.getConfiguration().getAllFragments().values()) { - ctgFragmentNames.add(fragment.getClass().getSimpleName()); - } - Set depFragmentNames = new HashSet<>(); - for (Class fragmentClass : expectedDepFragments) { - depFragmentNames.add(fragmentClass.getSimpleName()); - } - Set missing = Sets.difference(depFragmentNames, ctgFragmentNames); - if (!missing.isEmpty()) { - String msg = String.format( - "%s: dependency %s from attribute \"%s\" is missing required config fragments: %s", - ctgValue.getLabel(), dep.getLabel(), attribute, Joiner.on(", ").join(missing)); - env.getListener().handle(Event.error(msg)); - throw new DependencyEvaluationException(new InvalidConfigurationException(msg)); - } - } - - /** - * Determines the output ordering of each -> - * [dep, dep, ...] collection produced by a split transition. - */ - @VisibleForTesting - static final Comparator DYNAMIC_SPLIT_DEP_ORDERING = - new Comparator() { - @Override - public int compare(Dependency d1, Dependency d2) { - return d1.getConfiguration().getMnemonic().compareTo(d2.getConfiguration().getMnemonic()); - } - }; - - /** - * Helper method for {@link #getDynamicConfigurations}: returns a copy of the output deps - * using the same key and value ordering as the input deps. - * - * @param originalDeps the input deps with the ordering to preserve - * @param dynamicDeps the unordered output deps - * @param attributesAndLabels collection of pairs guaranteed to match - * the ordering of originalDeps.entries(). This is a performance optimization: see - * {@link #getDynamicConfigurations#attributesAndLabels} for details. - */ - private static OrderedSetMultimap sortDynamicallyConfiguredDeps( - OrderedSetMultimap originalDeps, - Multimap dynamicDeps, - ArrayList attributesAndLabels) { - Iterator iterator = attributesAndLabels.iterator(); - OrderedSetMultimap result = OrderedSetMultimap.create(); - for (Map.Entry depsEntry : originalDeps.entries()) { - AttributeAndLabel attrAndLabel = iterator.next(); - if (depsEntry.getValue().hasExplicitConfiguration()) { - result.put(attrAndLabel.attribute, depsEntry.getValue()); - } else { - Collection dynamicAttrDeps = dynamicDeps.get(attrAndLabel); - Verify.verify(!dynamicAttrDeps.isEmpty()); - if (dynamicAttrDeps.size() > 1) { - List sortedSplitList = new ArrayList<>(dynamicAttrDeps); - Collections.sort(sortedSplitList, DYNAMIC_SPLIT_DEP_ORDERING); - dynamicAttrDeps = sortedSplitList; - } - result.putAll(depsEntry.getKey(), dynamicAttrDeps); - } - } - return result; - } - /** * Merges the each direct dependency configured target with the aspects associated with it. * diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java index 0a6d6af9c8..897c0fc177 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java @@ -24,6 +24,7 @@ import com.google.devtools.build.lib.analysis.LabelAndConfiguration; import com.google.devtools.build.lib.analysis.TargetAndConfiguration; import com.google.devtools.build.lib.analysis.config.BuildConfiguration; import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider; +import com.google.devtools.build.lib.analysis.config.ConfigurationResolver; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.packages.Attribute; @@ -113,8 +114,8 @@ public class PostConfiguredTargetFunction implements SkyFunction { configConditions, /*toolchainContext=*/ null); if (ct.getConfiguration() != null) { - deps = ConfiguredTargetFunction.getDynamicConfigurations(env, ctgValue, deps, - hostConfiguration, ruleClassProvider); + deps = ConfigurationResolver.resolveConfigurations(env, ctgValue, deps, hostConfiguration, + ruleClassProvider); } } catch (EvalException | ConfiguredTargetFunction.DependencyEvaluationException | InvalidConfigurationException | InconsistentAspectOrderException e) { diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java index 42709cc8d8..1cbb82743b 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java @@ -68,6 +68,7 @@ import com.google.devtools.build.lib.analysis.config.BuildConfiguration; import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection; import com.google.devtools.build.lib.analysis.config.BuildOptions; import com.google.devtools.build.lib.analysis.config.ConfigurationFragmentFactory; +import com.google.devtools.build.lib.analysis.config.ConfigurationResolver; import com.google.devtools.build.lib.analysis.config.HostTransition; import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException; import com.google.devtools.build.lib.analysis.config.PatchTransition; @@ -1454,7 +1455,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory { Set> depFragments = fragmentsMap.get(key.getLabel()); if (depFragments != null) { - for (BuildOptions toOptions : ConfiguredTargetFunction.getDynamicTransitionOptions( + for (BuildOptions toOptions : ConfigurationResolver.applyTransition( fromOptions, key.getTransition(), depFragments, ruleClassProvider, true)) { configSkyKeys.add(BuildConfigurationValue.key(depFragments, toOptions)); } @@ -1469,7 +1470,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory { Set> depFragments = fragmentsMap.get(key.getLabel()); if (depFragments != null) { - for (BuildOptions toOptions : ConfiguredTargetFunction.getDynamicTransitionOptions( + for (BuildOptions toOptions : ConfigurationResolver.applyTransition( fromOptions, key.getTransition(), depFragments, ruleClassProvider, true)) { SkyKey configKey = BuildConfigurationValue.key(depFragments, toOptions); BuildConfigurationValue configValue = diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java index 843c531b3d..531d2152f0 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetValue.java @@ -126,7 +126,7 @@ public class TransitiveTargetValue implements SkyValue { *

See * {@link com.google.devtools.build.lib.packages.RuleClass.Builder#requiresConfigurationFragments} */ - NestedSet> getTransitiveConfigFragments() { + public NestedSet> getTransitiveConfigFragments() { return transitiveConfigFragments; } -- cgit v1.2.3