Implement the core structure for dynamic configurations.

This is a big change, so let me walk you through the key pieces:

1) This cl provides an alternative mechanism for creating configurations and doing configuration transitions that's "dynamic" in that the configurations can be created on the fly and the transitions are arbitrary mappings from BuildOptions --> BuildOptions that can also be created on the fly. It also integrates this with ConfiguredTargetFunction, so the configured target graph automatically uses this framework.

2) It does *not* replace old-style (which we'll call "static") configurations. For a number of important reasons: It's not yet at feature parity (particularly: no LIPO). It's not remotely tested across real projects enough to have confidence that it's battle-ready. It doesn't yet handle certain "special" functions like BuildConfiguration.prepareToBuild() and BuildConfiguration.getRoots(). It still relies on the old static transition logic to determine what transitions to apply (eventually we'll distribute that logic out, but that's too much for a single cl). We need the option to toggle it on and off until we have enough confidence in it. So with this cl, builds can be done in either mode.

3) The new flag --experimental_dynamic_configs toggles use of dynamic configurations.

4) Dynamic configurations are created with the Skyframe function BuildConfigurationFunction (this was already created in an earlier change). This consumes a BuildOptions and a set of configuration fragments to produce a BuildConfiguration.

5) Dynamic transitions are instances of the new class PatchTransition, which simply maps an input BuildOptions to an output BuildOptions.

6) Since static and dynamic configurations have to co-exist (for now), this cl tries hard to keep today's transition logic defined in a single place (vs. forking a dedicated copy for each configuration style). This is done via the new interface BuildConfiguration.TransitionApplier. BuildConfiguration.evaluateTransition is modified to feed its transition logic into TransitionApplier's common API. Both dynamic and static configurations have their own implementations that "do the right thing" with the results.

7) The transition applier for dynamic configurations basically stores the Transition, then allows DependencyResolver (which calls BuildConfiguration.evaluateTransition) to return Dependency instances containing that Transition (vs. a BuildConfiguration, which they traditionally contain).

7.5) An earlier variation of the dynamic transition applier retained BuildOptions (e.g. when it got a Transition it immediately applied it to get its output BuildOptions, then stored that). This had the advantage of making composing of transitions easier, especially within BuildConfiguration.evaluateTransition (which can theoretically apply multiple transitions to the input configuration). But it turns out that applying transitions has a cost, and it's simply more performant to pass them through until they're really needed.

8) In dynamic configuration mode, after ConfiguredTargetFunction gets its deps (e.g. an <Attribute, Dependency> multimap), it "trims" the configurations for its dependencies by a) only including config fragments required by the deps' subtrees and b) applying the transitions that came from 7). This all happens in the new method ConfiguredTargetFunction.trimConfigurations.

9) trimConfigurations is heavily performance-optimized based on a lot of experience running this through a large project within Google. As it turns out, the cost of host transitions can be atrocious (because there are a lot of them). Also, BuildOptions.clone() is expensive. And just creating BuildConfiguration SkyKeys also has a cost (largely because of BuildOptions cloning), so that shouldn't be done except when really necessary. My experience with this convinced me it's worth making this method complicated for the sake of making it fast. Since it basically visits every edge in the configured target graph (at least), it really needs to be slick.

10) Since host transitions in particular are problematic w.r.t. speed, I compute the host *once* in ConfigurationCollectionFunction.getHostConfiguration() and expose that reference to ConfiguredTargetFunction and other Skyframe functions. This limits recomputation to just when the fragments are trimmed.

11) Since options cloning is expensive, I'm doing something scary: exposing a BuildConfiguration.getOptions() method that returns a direct reference. Since BuildOptions is mutable, this is dangerous in the wrong hands. I can experiment with going back to cloning (with the caching of host transitions it may not matter as much), but we may ultimately have to put up with this risk for the sake of performant analysis time. What would be *really* awesome would be to make BuildOptions immutable. But that's not going to happen in this cl.

So in short, the key abstractions in this cl are:
 - PatchTransition
 - BuildConfiguration.TransitionApplier
 - ConfiguredTargetFunction.trimConfigurations

The current implementation imposes no analysis time penalty

--
MOS_MIGRATED_REVID=101474620

9 files changed, 790 insertions, 123 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index a64e031e5f..289cabcfa1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -20,12 +20,12 @@ import com.google.common.base.Preconditions;
 import com.google.common.base.Predicate;
 import com.google.common.cache.LoadingCache;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableListMultimap;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
-import com.google.common.collect.Multimaps;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.Action;
@@ -269,8 +269,9 @@ public class BuildView {
               public void run() {
                 clear();
               }
-        },
-        binTools);
+            },
+            binTools,
+            ruleClassProvider);
     skyframeExecutor.setSkyframeBuildView(skyframeBuildView);
   }
 
@@ -298,6 +299,7 @@ public class BuildView {
   @VisibleForTesting
   public void setConfigurationsForTesting(BuildConfigurationCollection configurations) {
     this.configurations = configurations;
+    skyframeBuildView.setTopLevelHostConfiguration(configurations.getHostConfiguration());
   }
 
   public BuildConfigurationCollection getConfigurationCollection() {
@@ -352,8 +354,8 @@ public class BuildView {
 
   public Iterable<ConfiguredTarget> getDirectPrerequisites(
       ConfiguredTarget ct, @Nullable final LoadingCache<Label, Target> targetCache) {
-    return skyframeExecutor.getConfiguredTargets(
-        getDirectPrerequisiteDependencies(ct, targetCache));
+    return skyframeExecutor.getConfiguredTargets(ct.getConfiguration(),
+        getDirectPrerequisiteDependencies(ct, targetCache), false);
   }
 
   public Iterable<Dependency> getDirectPrerequisiteDependencies(
@@ -391,7 +393,8 @@ public class BuildView {
     DependencyResolver dependencyResolver = new SilentDependencyResolver();
     TargetAndConfiguration ctgNode =
         new TargetAndConfiguration(ct.getTarget(), ct.getConfiguration());
-    return dependencyResolver.dependentNodes(ctgNode, getConfigurableAttributeKeys(ctgNode));
+    return dependencyResolver.dependentNodes(ctgNode, configurations.getHostConfiguration(),
+        getConfigurableAttributeKeys(ctgNode));
   }
 
   /**
@@ -603,6 +606,7 @@ public class BuildView {
     skyframeAnalysisWasDiscarded = false;
     ImmutableMap<PackageIdentifier, Path> packageRoots = loadingResult.getPackageRoots();
     this.configurations = configurations;
+    skyframeBuildView.setTopLevelHostConfiguration(this.configurations.getHostConfiguration());
     setArtifactRoots(packageRoots);
     // Determine the configurations.
     List<TargetAndConfiguration> nodes = nodesForTargets(targets);
@@ -633,7 +637,7 @@ public class BuildView {
     }
 
     prepareToBuild(new SkyframePackageRootResolver(skyframeExecutor));
-    skyframeExecutor.injectWorkspaceStatusData();
+    skyframeExecutor.injectWorkspaceStatusData(configurations);
     SkyframeAnalysisResult skyframeAnalysisResult;
     try {
       skyframeAnalysisResult =
@@ -843,7 +847,7 @@ public class BuildView {
       Label label, BuildConfiguration configuration) {
     return Iterables.getFirst(
         skyframeExecutor.getConfiguredTargets(
-            ImmutableList.of(new Dependency(label, configuration))),
+            configuration, ImmutableList.of(new Dependency(label, configuration)), true),
         null);
   }
 
@@ -868,23 +872,21 @@ public class BuildView {
     TargetAndConfiguration ctNode = new TargetAndConfiguration(target);
     ListMultimap<Attribute, Dependency> depNodeNames;
     try {
-      depNodeNames = resolver.dependentNodeMap(ctNode, null, getConfigurableAttributeKeys(ctNode));
+      depNodeNames = resolver.dependentNodeMap(ctNode, configurations.getHostConfiguration(), null,
+          getConfigurableAttributeKeys(ctNode));
     } catch (EvalException e) {
       throw new IllegalStateException(e);
     }
 
-    final Map<LabelAndConfiguration, ConfiguredTarget> depMap = new HashMap<>();
-    for (ConfiguredTarget dep : skyframeExecutor.getConfiguredTargets(depNodeNames.values())) {
-      depMap.put(LabelAndConfiguration.of(dep.getLabel(), dep.getConfiguration()), dep);
-    }
+    ImmutableMap<Dependency, ConfiguredTarget> cts = skyframeExecutor.getConfiguredTargetMap(
+        ctNode.getConfiguration(), ImmutableSet.copyOf(depNodeNames.values()), false);
 
-    return Multimaps.transformValues(depNodeNames, new Function<Dependency, ConfiguredTarget>() {
-      @Override
-      public ConfiguredTarget apply(Dependency depName) {
-        return depMap.get(LabelAndConfiguration.of(depName.getLabel(),
-            depName.getConfiguration()));
-      }
-    });
+    ImmutableListMultimap.Builder<Attribute, ConfiguredTarget> builder =
+        ImmutableListMultimap.builder();
+    for (Map.Entry<Attribute, Dependency> entry : depNodeNames.entries()) {
+      builder.put(entry.getKey(), cts.get(entry.getValue()));
+    }
+    return builder.build();
   }
 
   /**
@@ -955,7 +957,7 @@ public class BuildView {
             /*isSystemEnv=*/false, config.extendedSanityChecks(), eventHandler,
             /*skyframeEnv=*/null, config.isActionsEnabled(), binTools);
     return new RuleContext.Builder(analysisEnvironment,
-        (Rule) target.getTarget(), config, getHostConfigurationForTesting(config),
+        (Rule) target.getTarget(), config, configurations.getHostConfiguration(),
         ruleClassProvider.getPrerequisiteValidator())
             .setVisibility(NestedSetBuilder.<PackageSpecification>create(
                 Order.STABLE_ORDER, PackageSpecification.EVERYTHING))
@@ -972,7 +974,7 @@ public class BuildView {
   public RuleContext getRuleContextForTesting(ConfiguredTarget target, AnalysisEnvironment env) {
     BuildConfiguration targetConfig = target.getConfiguration();
     return new RuleContext.Builder(
-        env, (Rule) target.getTarget(), targetConfig, getHostConfigurationForTesting(targetConfig),
+        env, (Rule) target.getTarget(), targetConfig, configurations.getHostConfiguration(),
         ruleClassProvider.getPrerequisiteValidator())
             .setVisibility(NestedSetBuilder.<PackageSpecification>create(
                 Order.STABLE_ORDER, PackageSpecification.EVERYTHING))
@@ -981,11 +983,6 @@ public class BuildView {
             .build();
   }
 
-  private BuildConfiguration getHostConfigurationForTesting(BuildConfiguration config) {
-    // TODO(bazel-team): support dynamic transitions in tests.
-    return config == null ? null : config.getConfiguration(Attribute.ConfigurationTransition.HOST);
-  }
-
   /**
    * For a configured target dependentTarget, returns the desired configured target
    * that is depended upon. Useful for obtaining the a target with aspects
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationCollectionFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationCollectionFactory.java
index 14bb2a9695..14a79415a7 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationCollectionFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationCollectionFactory.java
@@ -15,6 +15,7 @@ package com.google.devtools.build.lib.analysis;
 
 import com.google.common.cache.Cache;
 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.ConfigurationFactory;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
@@ -51,4 +52,16 @@ public interface ConfigurationCollectionFactory {
       BuildOptions buildOptions,
       EventHandler errorEventListener,
       boolean performSanityCheck) throws InvalidConfigurationException;
+
+  /**
+   * Returns the module the given configuration should use for choosing dynamic transitions.
+   *
+   * <p>We can presumably factor away this method once static global configurations are properly
+   * deprecated. But for now we retain the
+   * {@link com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection.Transitions}
+   * interface since that's the same place where static transition logic is determined and
+   * {@link BuildConfigurationCollection.Transitions#configurationHook}
+   * is still used.
+   */
+  BuildConfigurationCollection.Transitions getDynamicTransitionLogic(BuildConfiguration config);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index b875a9db2b..f193298c3e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -281,11 +281,11 @@ public final class ConfiguredTargetFactory {
       AnalysisEnvironment env, RuleConfiguredTarget associatedTarget,
       ConfiguredAspectFactory aspectFactory,
       ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      Set<ConfigMatchingProvider> configConditions) {
+      Set<ConfigMatchingProvider> configConditions, BuildConfiguration hostConfiguration) {
     RuleContext.Builder builder = new RuleContext.Builder(env,
         associatedTarget.getTarget(),
         associatedTarget.getConfiguration(),
-        getHostConfiguration(associatedTarget.getConfiguration()),
+        hostConfiguration,
         ruleClassProvider.getPrerequisiteValidator());
     RuleContext ruleContext = builder
         .setVisibility(convertVisibility(
@@ -300,11 +300,6 @@ public final class ConfiguredTargetFactory {
     return aspectFactory.create(associatedTarget, ruleContext);
   }
 
-  private static BuildConfiguration getHostConfiguration(BuildConfiguration config) {
-    // TODO(bazel-team): support dynamic transitions.
-    return config == null ? null : config.getConfiguration(Attribute.ConfigurationTransition.HOST);
-  }
-
   /**
    * A pseudo-implementation for configured targets that creates fail actions for all declared
    * outputs, both implicit and explicit.
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 4953176b45..9b6ea93ef7 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
@@ -15,6 +15,7 @@ package com.google.devtools.build.lib.analysis;
 
 import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
+import com.google.common.base.Verify;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -26,7 +27,6 @@ import com.google.devtools.build.lib.collect.ImmutableSortedKeyListMultimap;
 import com.google.devtools.build.lib.packages.AspectDefinition;
 import com.google.devtools.build.lib.packages.AspectFactory;
 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.LateBoundDefault;
 import com.google.devtools.build.lib.packages.Attribute.SplitTransition;
 import com.google.devtools.build.lib.packages.AttributeMap;
@@ -65,8 +65,12 @@ public abstract class DependencyResolver {
   /**
    * A dependency of a configured target through a label.
    *
-   * <p>Includes the target and the configuration of the dependency configured target and any
-   * aspects that may be required.
+   * <p>For static configurations: includes the target and the configuration of the dependency
+   * configured target and any aspects that may be required.
+   *
+   * <p>For dynamic configurations: includes the target and the desired configuration transitions
+   * that should be applied to produce the dependency's configuration. It's the caller's
+   * responsibility to construct an actual configuration out of that.
    *
    * <p>Note that the presence of an aspect here does not necessarily mean that it will be created.
    * They will be filtered based on the {@link TransitiveInfoProvider} instances their associated
@@ -91,32 +95,76 @@ public abstract class DependencyResolver {
 
     private final Label label;
 
+    // Only one of the two below fields is set. Use hasStaticConfiguration to determine which.
     @Nullable private final BuildConfiguration configuration;
+    private final Attribute.Transition transition;
 
+    private final boolean hasStaticConfiguration;
     private final ImmutableSet<Class<? extends ConfiguredAspectFactory>> aspects;
 
-    public Dependency(
-        Label label,
+    /**
+     * Constructs a Dependency with a given configuration (suitable for static configuration
+     * builds).
+     */
+    public Dependency(Label label,
         @Nullable BuildConfiguration configuration,
         ImmutableSet<Class<? extends ConfiguredAspectFactory>> aspects) {
       this.label = Preconditions.checkNotNull(label);
       this.configuration = configuration;
+      this.transition = null;
+      this.hasStaticConfiguration = true;
       this.aspects = Preconditions.checkNotNull(aspects);
     }
 
+    /**
+     * Constructs a Dependency with a given configuration (suitable for static configuration
+     * builds).
+     */
     public Dependency(Label label, @Nullable BuildConfiguration configuration) {
       this(label, configuration, ImmutableSet.<Class<? extends ConfiguredAspectFactory>>of());
     }
 
+    /**
+     * Constructs a Dependency with a given transition (suitable for dynamic configuration builds).
+     */
+    public Dependency(Label label, Attribute.Transition transition,
+        ImmutableSet<Class<? extends ConfiguredAspectFactory>> aspects) {
+      this.label = Preconditions.checkNotNull(label);
+      this.configuration = null;
+      this.transition = Preconditions.checkNotNull(transition);
+      this.hasStaticConfiguration = false;
+      this.aspects = Preconditions.checkNotNull(aspects);
+    }
+
+    /**
+     * Does this dependency represent a null configuration?
+     */
+    public boolean isNull() {
+      return configuration == null && transition == null;
+    }
+
+    /**
+     * Does this dependency specify a static configuration (vs. a dynamic transition)?
+     */
+    public boolean hasStaticConfiguration() {
+      return hasStaticConfiguration;
+    }
+
     public Label getLabel() {
       return label;
     }
 
     @Nullable
     public BuildConfiguration getConfiguration() {
+      Verify.verify(hasStaticConfiguration);
       return configuration;
     }
 
+    public Attribute.Transition getTransition() {
+      Verify.verify(!hasStaticConfiguration);
+      return transition;
+    }
+
     public ImmutableSet<Class<? extends ConfiguredAspectFactory>> getAspects() {
       return aspects;
     }
@@ -168,7 +216,7 @@ public abstract class DependencyResolver {
    * dependency.
    */
   public final ListMultimap<Attribute, Dependency> dependentNodeMap(
-      TargetAndConfiguration node, AspectDefinition aspect,
+      TargetAndConfiguration node, BuildConfiguration hostConfig, AspectDefinition aspect,
       Set<ConfigMatchingProvider> configConditions)
       throws EvalException {
     Target target = node.getTarget();
@@ -188,7 +236,7 @@ public abstract class DependencyResolver {
       visitTargetVisibility(node, outgoingEdges.get(null));
       Rule rule = (Rule) target;
       ListMultimap<Attribute, LabelAndConfiguration> labelMap =
-          resolveAttributes(rule, aspect, config, configConditions);
+          resolveAttributes(rule, aspect, config, hostConfig, configConditions);
       visitRule(rule, aspect, labelMap, outgoingEdges);
     } else if (target instanceof PackageGroup) {
       visitPackageGroup(node, (PackageGroup) target, outgoingEdges.get(null));
@@ -200,7 +248,7 @@ public abstract class DependencyResolver {
 
   private ListMultimap<Attribute, LabelAndConfiguration> resolveAttributes(
       Rule rule, AspectDefinition aspect, BuildConfiguration configuration,
-      Set<ConfigMatchingProvider> configConditions)
+      BuildConfiguration hostConfiguration, Set<ConfigMatchingProvider> configConditions)
       throws EvalException {
     ConfiguredAttributeMapper attributeMap = ConfiguredAttributeMapper.of(rule, configConditions);
     attributeMap.validateAttributes();
@@ -220,7 +268,8 @@ public abstract class DependencyResolver {
 
     resolveExplicitAttributes(rule, configuration, attributeMap, result);
     resolveImplicitAttributes(rule, configuration, attributeMap, attributes, result);
-    resolveLateBoundAttributes(rule, configuration, attributeMap, attributes, result);
+    resolveLateBoundAttributes(rule, configuration, hostConfiguration, attributeMap, attributes,
+        result);
 
     // Add the rule's visibility labels (which may come from the rule or from package defaults).
     addExplicitDeps(result, rule, "visibility", rule.getVisibility().getDependencyLabels(),
@@ -377,6 +426,7 @@ public abstract class DependencyResolver {
   private void resolveLateBoundAttributes(
       Rule rule,
       BuildConfiguration configuration,
+      BuildConfiguration hostConfiguration,
       AttributeMap attributeMap,
       Iterable<Attribute> attributes,
       ImmutableSortedKeyListMultimap.Builder<Attribute, LabelAndConfiguration> builder)
@@ -401,8 +451,7 @@ public abstract class DependencyResolver {
         LateBoundDefault<BuildConfiguration> lateBoundDefault =
             (LateBoundDefault<BuildConfiguration>) attribute.getLateBoundDefault();
         if (lateBoundDefault.useHostConfiguration()) {
-          actualConfig =
-              actualConfig.getConfiguration(ConfigurationTransition.HOST);
+          actualConfig = hostConfiguration;
         }
         // TODO(bazel-team): This might be too expensive - can we cache this somehow?
         if (!lateBoundDefault.getRequiredConfigurationFragments().isEmpty()) {
@@ -450,9 +499,11 @@ public abstract class DependencyResolver {
    * IllegalStateException}.
    */
   public final Collection<Dependency> dependentNodes(
-      TargetAndConfiguration node, Set<ConfigMatchingProvider> configConditions) {
+      TargetAndConfiguration node, BuildConfiguration hostConfig,
+      Set<ConfigMatchingProvider> configConditions) {
     try {
-      return dependentNodeMap(node, null, configConditions).values();
+      return ImmutableSet.copyOf(
+          dependentNodeMap(node, hostConfig, null, configConditions).values());
     } catch (EvalException e) {
       throw new IllegalStateException(e);
     }
@@ -550,12 +601,31 @@ public abstract class DependencyResolver {
         if (toTarget == null) {
           continue;
         }
-        Iterable<BuildConfiguration> toConfigurations = config.evaluateTransition(
-            rule, attribute, toTarget);
-        for (BuildConfiguration toConfiguration : toConfigurations) {
+        BuildConfiguration.TransitionApplier transitionApplier = config.getTransitionApplier();
+        if (config.useDynamicConfigurations() && config.isHostConfiguration()
+            && !BuildConfiguration.usesNullConfiguration(toTarget)) {
+          // This condition is needed because resolveLateBoundAttributes may switch config to
+          // the host configuration, which is the only case DependencyResolver applies a
+          // configuration transition outside of this method. We need to reflect that
+          // transition in the results of this method, but config.evaluateTransition is hard-set
+          // to return a NONE transition when the input is a host config. Since the outside
+          // caller originally passed the *original* value of config (before the possible
+          // switch), it can mistakenly interpret the result as a NONE transition from the
+          // original value of config. This condition fixes that. Another fix would be to have
+          // config.evaluateTransition return a HOST transition when the input config is a host,
+          // but since this blemish is specific to DependencyResolver it seems best to keep the
+          // fix here.
+          // TODO(bazel-team): eliminate this special case by passing transitionApplier to
+          // resolveLateBoundAttributes, so that method uses the same interface for transitions.
+          transitionApplier.applyTransition(Attribute.ConfigurationTransition.HOST);
+        } else {
+          config.evaluateTransition(rule, attribute, toTarget, transitionApplier);
+        }
+        for (Dependency dependency : transitionApplier.getDependencies(label,
+            requiredAspects(aspect, attribute, toTarget))) {
           outgoingEdges.put(
               entry.getKey(),
-              new Dependency(label, toConfiguration, requiredAspects(aspect, attribute, toTarget)));
+              dependency);
         }
       }
     }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
index 4cf3b12122..29b5f4be1d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
@@ -15,10 +15,11 @@
 package com.google.devtools.build.lib.analysis.config;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Function;
 import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
+import com.google.common.base.Verify;
 import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ClassToInstanceMap;
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -27,10 +28,14 @@ import com.google.common.collect.Iterables;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Multimap;
+import com.google.common.collect.MutableClassToInstanceMap;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.PackageRootResolver;
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.analysis.ConfiguredAspectFactory;
+import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
+import com.google.devtools.build.lib.analysis.DependencyResolver;
 import com.google.devtools.build.lib.analysis.ViewCreationFailedException;
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection.Transitions;
 import com.google.devtools.build.lib.events.Event;
@@ -43,6 +48,7 @@ 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.RuleClass;
+import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.rules.test.TestActionBuilder;
 import com.google.devtools.build.lib.syntax.Label;
@@ -70,7 +76,6 @@ import java.io.IOException;
 import java.io.Serializable;
 import java.lang.reflect.Field;
 import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
@@ -799,6 +804,13 @@ public final class BuildConfiguration {
         category = "undocumented")
     public Label objcGcovBinary;
 
+    @Option(name = "experimental_dynamic_configs",
+        defaultValue = "false",
+        category = "undocumented",
+        help = "Dynamically instantiates build configurations instead of using the default "
+            + "static globally defined ones")
+    public boolean useDynamicConfigurations;
+
     @Override
     public FragmentOptions getHost(boolean fallback) {
       Options host = (Options) getDefault();
@@ -806,6 +818,7 @@ public final class BuildConfiguration {
       host.outputDirectoryName = "host";
       host.compilationMode = CompilationMode.OPT;
       host.isHost = true;
+      host.useDynamicConfigurations = useDynamicConfigurations;
 
       if (fallback) {
         // In the fallback case, we have already tried the target options and they didn't work, so
@@ -888,10 +901,6 @@ public final class BuildConfiguration {
     }
   }
 
-  /** A list of build configurations that only contains the null element. */
-  private static final List<BuildConfiguration> NULL_LIST =
-      Collections.unmodifiableList(Arrays.asList(new BuildConfiguration[] { null }));
-
   private final String checksum;
 
   private Transitions transitions;
@@ -902,7 +911,7 @@ public final class BuildConfiguration {
 
   /**
    * Directories in the output tree.
-   * 
+   *
    * <p>The computation of the output directory should be a non-injective mapping from
    * BuildConfiguration instances to strings. The result should identify the aspects of the
    * configuration that should be reflected in the output file names.  Furthermore the
@@ -1051,10 +1060,26 @@ public final class BuildConfiguration {
     return builder.build();
   }
 
+  /**
+   * Constructs a new BuildConfiguration instance.
+   */
   public BuildConfiguration(BlazeDirectories directories,
-                     Map<Class<? extends Fragment>, Fragment> fragmentsMap,
-                     BuildOptions buildOptions,
-                     boolean actionsDisabled) {
+      Map<Class<? extends Fragment>, Fragment> fragmentsMap,
+      BuildOptions buildOptions,
+      boolean actionsDisabled) {
+    this(null, directories, fragmentsMap, buildOptions, actionsDisabled);
+  }
+
+  /**
+   * Constructor variation that uses the passed in output roots if non-null, else computes them
+   * from the directories.
+   */
+  public BuildConfiguration(@Nullable OutputRoots outputRoots,
+      @Nullable BlazeDirectories directories,
+      Map<Class<? extends Fragment>, Fragment> fragmentsMap,
+      BuildOptions buildOptions,
+      boolean actionsDisabled) {
+    Preconditions.checkState(outputRoots == null ^ directories == null);
     this.actionsEnabled = !actionsDisabled;
     this.fragments = ImmutableMap.copyOf(fragmentsMap);
 
@@ -1079,7 +1104,9 @@ public final class BuildConfiguration {
 
     this.shExecutable = collectExecutables().get("sh");
 
-    this.outputRoots = new OutputRoots(directories, outputDirName);
+    this.outputRoots = outputRoots != null
+        ? outputRoots
+        : new OutputRoots(directories, outputDirName);
 
     ImmutableSet.Builder<Label> coverageLabelsBuilder = ImmutableSet.builder();
     ImmutableSet.Builder<Label> coverageReportGeneratorLabelsBuilder = ImmutableSet.builder();
@@ -1124,6 +1151,50 @@ public final class BuildConfiguration {
     checksum = Fingerprint.md5Digest(buildOptions.computeCacheKey());
   }
 
+  /**
+   * Returns a copy of this configuration only including the given fragments (which the current
+   * configuration is assumed to have).
+   */
+  public BuildConfiguration clone(
+      Set<Class<? extends BuildConfiguration.Fragment>> fragmentClasses,
+      RuleClassProvider ruleClassProvider) {
+
+    ClassToInstanceMap<Fragment> fragmentsMap = MutableClassToInstanceMap.create();
+    for (Fragment fragment : fragments.values()) {
+      if (fragmentClasses.contains(fragment.getClass())) {
+        fragmentsMap.put(fragment.getClass(), fragment);
+      }
+    }
+    BuildOptions options = buildOptions.trim(
+        getOptionsClasses(fragmentsMap.keySet(), ruleClassProvider));
+    BuildConfiguration newConfig =
+        new BuildConfiguration(outputRoots, null, fragmentsMap, options, !actionsEnabled);
+    newConfig.setConfigurationTransitions(this.transitions);
+    return newConfig;
+  }
+
+  /**
+   * Returns the config fragment options classes used by the given fragment types.
+   */
+  public static Set<Class<? extends FragmentOptions>> getOptionsClasses(
+      Iterable<Class<? extends Fragment>> fragmentClasses, RuleClassProvider ruleClassProvider) {
+
+    Multimap<Class<? extends BuildConfiguration.Fragment>, Class<? extends FragmentOptions>>
+        fragmentToRequiredOptions = ArrayListMultimap.create();
+    for (ConfigurationFragmentFactory fragmentLoader :
+        ((ConfiguredRuleClassProvider) ruleClassProvider).getConfigurationFragments()) {
+      fragmentToRequiredOptions.putAll(fragmentLoader.creates(),
+          fragmentLoader.requiredOptions());
+    }
+    Set<Class<? extends FragmentOptions>> options = new HashSet<>();
+    for (Class<? extends BuildConfiguration.Fragment> fragmentClass : fragmentClasses) {
+      options.addAll(fragmentToRequiredOptions.get(fragmentClass));
+    }
+    return options;
+  }
+
+
+
   private ImmutableMap<String, Class<? extends Fragment>> buildIndexOfVisibleFragments() {
     ImmutableMap.Builder<String, Class<? extends Fragment>> builder = ImmutableMap.builder();
     SkylarkModuleNameResolver resolver = new SkylarkModuleNameResolver();
@@ -1199,9 +1270,10 @@ public final class BuildConfiguration {
   /**
    * Set the outgoing configuration transitions. During the lifetime of a given build configuration,
    * this must happen exactly once, shortly after the configuration is created.
-   * TODO(bazel-team): this makes the object mutable, get rid of it.
    */
   public void setConfigurationTransitions(Transitions transitions) {
+    // TODO(bazel-team): This method makes the object mutable - get rid of it. Dynamic
+    // configurations should eventually make this obsolete.
     Preconditions.checkNotNull(transitions);
     Preconditions.checkState(this.transitions == null);
     this.transitions = transitions;
@@ -1249,10 +1321,13 @@ public final class BuildConfiguration {
    * @param transition the configuration transition
    * @return the new configuration
    * @throws IllegalArgumentException if the transition is a {@link SplitTransition}
+   *
+   * TODO(bazel-team): remove this as part of the static -> dynamic configuration migration
    */
   public BuildConfiguration getConfiguration(Transition transition) {
     Preconditions.checkArgument(!(transition instanceof SplitTransition));
-    return transitions.getConfiguration(transition);
+    // The below call precondition-checks we're indeed using static configurations.
+    return transitions.getStaticConfiguration(transition);
   }
 
   /**
@@ -1267,6 +1342,331 @@ public final class BuildConfiguration {
   }
 
   /**
+   * A common interface for static vs. dynamic configuration implementations that allows
+   * common configuration and transition-selection logic to seamlessly work with either.
+   *
+   * <p>The basic role of this interface is to "accept" a desired transition and produce
+   * an actual configuration change from it in an implementation-appropriate way.
+   */
+  public interface TransitionApplier {
+    /**
+      * Creates a new instance of this transition applier bound to the specified source
+      * configuration.
+      */
+     TransitionApplier create(BuildConfiguration config);
+
+    /**
+     * Accepts the given configuration transition. The implementation decides how to turn
+     * this into an actual configuration. This may be called multiple times (representing a
+     * request for a sequence of transitions).
+     */
+    void applyTransition(Transition transition);
+
+    /**
+     * Accepts the given split transition. The implementation decides how to turn this into
+     * actual configurations.
+     */
+    void split(SplitTransition<?> splitTransition);
+
+    /**
+     * Returns whether or not all configuration(s) represented by the current state of this
+     * instance are null.
+     */
+    boolean isNull();
+
+    /**
+     * Applies the given attribute configurator to the current configuration(s).
+     */
+    void applyAttributeConfigurator(Attribute attribute, Rule fromRule, Target toTarget);
+
+    /**
+     * Calls {@link Transitions#configurationHook} on the current configuration(s) represent by
+     * this instance.
+     */
+    void applyConfigurationHook(Rule fromRule, Attribute attribute, Target toTarget);
+
+    /**
+     * Returns the underlying {@Transitions} object for this instance's current configuration.
+     * Does not work for split configurations.
+     */
+    Transitions getCurrentTransitions();
+
+    /**
+     * Populates a {@link com.google.devtools.build.lib.analysis.DependencyResolver.Dependency}
+     * for each configuration represented by this instance.
+     * TODO(bazel-team): this is a really ugly reverse dependency: factor this away.
+     */
+    Iterable<DependencyResolver.Dependency> getDependencies(Label label,
+        ImmutableSet<Class<? extends ConfiguredAspectFactory>> aspects);
+  }
+
+  /**
+   * Transition applier for static configurations. This implementation populates
+   * {@link com.google.devtools.build.lib.analysis.DependencyResolver.Dependency} objects with
+   * actual configurations.
+   *
+   * <p>Does not support split transitions (see {@link SplittableTransitionApplier}).
+   * TODO(bazel-team): remove this when dynamic configurations are fully production-ready.
+   */
+  private static class StaticTransitionApplier implements TransitionApplier {
+    BuildConfiguration currentConfiguration;
+
+    private StaticTransitionApplier(BuildConfiguration originalConfiguration) {
+      this.currentConfiguration = originalConfiguration;
+    }
+
+    @Override
+    public TransitionApplier create(BuildConfiguration configuration) {
+      return new StaticTransitionApplier(configuration);
+    }
+
+    @Override
+    public void applyTransition(Transition transition) {
+      if (transition == Attribute.ConfigurationTransition.NULL) {
+        currentConfiguration = null;
+      } else {
+        currentConfiguration =
+            currentConfiguration.getTransitions().getStaticConfiguration(transition);
+      }
+    }
+
+    @Override
+    public void split(SplitTransition<?> splitTransition) {
+      throw new UnsupportedOperationException("This only works with SplittableTransitionApplier");
+    }
+
+    @Override
+    public boolean isNull() {
+      return currentConfiguration == null;
+    }
+
+    @Override
+    public void applyAttributeConfigurator(Attribute attribute, Rule fromRule, Target toTarget) {
+      @SuppressWarnings("unchecked")
+      Configurator<BuildConfiguration, Rule> configurator =
+          (Configurator<BuildConfiguration, Rule>) attribute.getConfigurator();
+      Verify.verifyNotNull(configurator);
+      currentConfiguration =
+          configurator.apply(fromRule, currentConfiguration, attribute, toTarget);
+    }
+
+    @Override
+    public void applyConfigurationHook(Rule fromRule, Attribute attribute, Target toTarget) {
+      currentConfiguration.getTransitions().configurationHook(fromRule, attribute, toTarget, this);
+
+      // Allow rule classes to override their own configurations.
+      Rule associatedRule = toTarget.getAssociatedRule();
+      if (associatedRule != null) {
+        @SuppressWarnings("unchecked")
+        RuleClass.Configurator<BuildConfiguration, Rule> func =
+            associatedRule.getRuleClassObject().<BuildConfiguration, Rule>getConfigurator();
+        currentConfiguration = func.apply(associatedRule, currentConfiguration);
+      }
+    }
+
+    @Override
+    public Transitions getCurrentTransitions() {
+      return currentConfiguration.getTransitions();
+    }
+
+    @Override
+    public Iterable<DependencyResolver.Dependency> getDependencies(Label label,
+        ImmutableSet<Class<? extends ConfiguredAspectFactory>> aspects) {
+      return ImmutableList.of(
+          new DependencyResolver.Dependency(label, currentConfiguration, aspects));
+    }
+  }
+
+  /**
+   * Transition applier for dynamic configurations. This implementation populates
+   * {@link com.google.devtools.build.lib.analysis.DependencyResolver.Dependency} objects with
+   * transition definitions that the caller subsequently creates configurations out of.
+   *
+   * <p>Does not support split transitions (see {@link SplittableTransitionApplier}).
+   */
+  private static class DynamicTransitionApplier implements TransitionApplier {
+    private final BuildConfiguration originalConfiguration;
+    private Transition transition = Attribute.ConfigurationTransition.NONE;
+
+    private DynamicTransitionApplier(BuildConfiguration originalConfiguration) {
+      this.originalConfiguration = originalConfiguration;
+    }
+
+    @Override
+    public TransitionApplier create(BuildConfiguration configuration) {
+      return new DynamicTransitionApplier(configuration);
+    }
+
+    @Override
+    public void applyTransition(Transition transition) {
+      if (transition == Attribute.ConfigurationTransition.NONE) {
+        return;
+      } else if (this.transition != HostTransition.INSTANCE) {
+        // We don't currently support composed transitions (e.g. applyTransitions shouldn't be
+        // called multiple times). We can add support for this if needed by simply storing a list of
+        // transitions instead of a single transition. But we only want to do that if really
+        // necessary - if we can simplify BuildConfiguration's transition logic to not require
+        // scenarios like that, it's better to keep this simpler interface.
+        //
+        // The HostTransition exemption is because of limited cases where composition can
+        // occur. See relevant comments beginning with  "BuildConfiguration.applyTransition NOTE"
+        // in the transition logic code if available.
+
+        // Ensure we don't already have any mutating transitions registered.
+        // Note that for dynamic configurations, LipoDataTransition is equivalent to NONE. That's
+        // because dynamic transitions don't work with LIPO, so there's no LIPO context to change.
+        Verify.verify(this.transition == Attribute.ConfigurationTransition.NONE
+            || this.transition.toString().contains("LipoDataTransition"));
+        this.transition = getCurrentTransitions().getDynamicTransition(transition);
+      }
+    }
+
+    @Override
+    public void split(SplitTransition<?> splitTransition) {
+      throw new UnsupportedOperationException("This only works with SplittableTransitionApplier");
+    }
+
+    @Override
+    public boolean isNull() {
+      return transition == Attribute.ConfigurationTransition.NULL;
+    }
+
+    @Override
+    public void applyAttributeConfigurator(Attribute attribute, Rule fromRule, Target toTarget) {
+      // We don't support meaningful attribute configurators (since they produce configurations,
+      // and we're only interested in generating transitions so the calling code can realize
+      // configurations from them). So just check that the configurator is just a no-op.
+      @SuppressWarnings("unchecked")
+      Configurator<BuildConfiguration, Rule> configurator =
+          (Configurator<BuildConfiguration, Rule>) attribute.getConfigurator();
+      Verify.verifyNotNull(configurator);
+      BuildConfiguration toConfiguration =
+          configurator.apply(fromRule, originalConfiguration, attribute, toTarget);
+      Verify.verify(toConfiguration == originalConfiguration);
+    }
+
+    @Override
+    public void applyConfigurationHook(Rule fromRule, Attribute attribute, Target toTarget) {
+      if (isNull()) {
+        return;
+      }
+      getCurrentTransitions().configurationHook(fromRule, attribute, toTarget, this);
+
+      // We don't support rule class configurators (which might imply composed transitions).
+      // The only current use of that is LIPO, which can't currently be invoked with dynamic
+      // configurations (e.g. this code can never get called for LIPO builds). So check that
+      // if there is a configurator, it's for LIPO, in which case we can ignore it.
+      Rule associatedRule = toTarget.getAssociatedRule();
+      if (associatedRule != null) {
+        @SuppressWarnings("unchecked")
+        RuleClass.Configurator<?, ?> func =
+            associatedRule.getRuleClassObject().getConfigurator();
+        Verify.verify(func == RuleClass.NO_CHANGE || func.getCategory().equals("lipo"));
+      }
+    }
+
+    @Override
+    public Transitions getCurrentTransitions() {
+      return originalConfiguration.getTransitions();
+    }
+
+    @Override
+    public Iterable<DependencyResolver.Dependency> getDependencies(Label label,
+        ImmutableSet<Class<? extends ConfiguredAspectFactory>> aspects) {
+      return ImmutableList.of(new DependencyResolver.Dependency(label, transition, aspects));
+    }
+  }
+
+  /**
+   * Transition applier that wraps an underlying implementation with added support for
+   * split transitions. All external calls into BuildConfiguration should use this applier.
+   */
+  private static class SplittableTransitionApplier implements TransitionApplier {
+    private List<TransitionApplier> appliers;
+
+    private SplittableTransitionApplier(TransitionApplier original) {
+      appliers = ImmutableList.of(original);
+    }
+
+    @Override
+    public TransitionApplier create(BuildConfiguration configuration) {
+      throw new UnsupportedOperationException("Not intended to be wrapped under another applier");
+    }
+
+    @Override
+    public void applyTransition(Transition transition) {
+      for (TransitionApplier applier : appliers) {
+        applier.applyTransition(transition);
+      }
+    }
+
+    @Override
+    public void split(SplitTransition<?> splitTransition) {
+      TransitionApplier originalApplier = Iterables.getOnlyElement(appliers);
+      ImmutableList.Builder<TransitionApplier> splitAppliers = ImmutableList.builder();
+      for (BuildConfiguration splitConfig :
+          originalApplier.getCurrentTransitions().getSplitConfigurations(splitTransition)) {
+        splitAppliers.add(originalApplier.create(splitConfig));
+      }
+      appliers = splitAppliers.build();
+    }
+
+    @Override
+    public boolean isNull() {
+      throw new UnsupportedOperationException("Only for use from a Transitions instance");
+    }
+
+
+    @Override
+    public void applyAttributeConfigurator(Attribute attribute, Rule fromRule, Target toTarget) {
+      for (TransitionApplier applier : appliers) {
+        applier.applyAttributeConfigurator(attribute, fromRule, toTarget);
+      }
+    }
+
+    @Override
+    public void applyConfigurationHook(Rule fromRule, Attribute attribute, Target toTarget) {
+      for (TransitionApplier applier : appliers) {
+        applier.applyConfigurationHook(fromRule, attribute, toTarget);
+      }
+    }
+
+    @Override
+    public Transitions getCurrentTransitions() {
+      throw new UnsupportedOperationException("Only for use from a Transitions instance");
+    }
+
+
+    @Override
+    public Iterable<DependencyResolver.Dependency> getDependencies(Label label,
+        ImmutableSet<Class<? extends ConfiguredAspectFactory>> aspects) {
+      ImmutableList.Builder<DependencyResolver.Dependency> builder = ImmutableList.builder();
+      for (TransitionApplier applier : appliers) {
+        builder.addAll(applier.getDependencies(label, aspects));
+      }
+      return builder.build();
+    }
+  }
+
+  /**
+   * Returns the {@link TransitionApplier} that should be passed to {#evaluateTransition} calls.
+   */
+  public TransitionApplier getTransitionApplier() {
+    TransitionApplier applier = useDynamicConfigurations()
+        ? new DynamicTransitionApplier(this)
+        : new StaticTransitionApplier(this);
+    return new SplittableTransitionApplier(applier);
+  }
+
+  /**
+   * Returns true if the given target uses a null configuration, false otherwise. Consider
+   * this method the "source of truth" for determining this.
+   */
+  public static boolean usesNullConfiguration(Target target) {
+    return target instanceof InputFile || target instanceof PackageGroup;
+  }
+
+  /**
    * Calculates the configurations of a direct dependency. If a rule in some BUILD file refers
    * to a target (like another rule or a source file) using a label attribute, that target needs
    * to have a configuration, too. This method figures out the proper configuration for the
@@ -1275,21 +1675,23 @@ public final class BuildConfiguration {
    * @param fromRule the rule that's depending on some target
    * @param attribute the attribute using which the rule depends on that target (eg. "srcs")
    * @param toTarget the target that's dependeded on
-   * @return the configuration that should be associated to {@code toTarget}
+   * @param transitionApplier the transition applier to accept transitions requests
    */
-  public Iterable<BuildConfiguration> evaluateTransition(final Rule fromRule,
-      final Attribute attribute, final Target toTarget) {
+  public void evaluateTransition(final Rule fromRule, final Attribute attribute,
+      final Target toTarget, TransitionApplier transitionApplier) {
     // Fantastic configurations and where to find them:
 
     // I. Input files and package groups have no configurations. We don't want to duplicate them.
-    if (toTarget instanceof InputFile || toTarget instanceof PackageGroup) {
-      return NULL_LIST;
+    if (usesNullConfiguration(toTarget)) {
+      transitionApplier.applyTransition(Attribute.ConfigurationTransition.NULL);
+      return;
     }
 
     // II. Host configurations never switch to another. All prerequisites of host targets have the
     // same host configuration.
     if (isHostConfiguration()) {
-      return ImmutableList.of(this);
+      transitionApplier.applyTransition(Attribute.ConfigurationTransition.NONE);
+      return;
     }
 
     // Make sure config_setting dependencies are resolved in the referencing rule's configuration,
@@ -1306,46 +1708,27 @@ public final class BuildConfiguration {
     // TODO(bazel-team): implement this more elegantly. This is far too hackish. Specifically:
     // don't reference the rule name explicitly and don't require special-casing here.
     if (toTarget instanceof Rule && ((Rule) toTarget).getRuleClass().equals("config_setting")) {
-      return ImmutableList.of(this);
+      transitionApplier.applyTransition(Attribute.ConfigurationTransition.NONE); // Unnecessary.
+      return;
     }
 
-    List<BuildConfiguration> toConfigurations;
     if (attribute.getConfigurationTransition() instanceof SplitTransition) {
       Preconditions.checkState(attribute.getConfigurator() == null);
-      toConfigurations = getSplitConfigurations(
-          (SplitTransition<?>) attribute.getConfigurationTransition());
+      transitionApplier.split((SplitTransition<?>) attribute.getConfigurationTransition());
     } else {
       // III. Attributes determine configurations. The configuration of a prerequisite is determined
       // by the attribute.
       @SuppressWarnings("unchecked")
       Configurator<BuildConfiguration, Rule> configurator =
           (Configurator<BuildConfiguration, Rule>) attribute.getConfigurator();
-      toConfigurations = ImmutableList.of((configurator != null)
-          ? configurator.apply(fromRule, this, attribute, toTarget)
-          : getConfiguration(attribute.getConfigurationTransition()));
-    }
-
-    return Iterables.transform(toConfigurations,
-        new Function<BuildConfiguration, BuildConfiguration>() {
-      @Override
-      public BuildConfiguration apply(BuildConfiguration input) {
-        // IV. Allow the transition object to perform an arbitrary switch. Blaze modules can inject
-        // configuration transition logic by extending the Transitions class.
-        BuildConfiguration actual = getTransitions().configurationHook(
-            fromRule, attribute, toTarget, input);
-
-        // V. Allow rule classes to override their own configurations.
-        Rule associatedRule = toTarget.getAssociatedRule();
-        if (associatedRule != null) {
-          @SuppressWarnings("unchecked")
-          RuleClass.Configurator<BuildConfiguration, Rule> func =
-              associatedRule.getRuleClassObject().<BuildConfiguration, Rule>getConfigurator();
-          actual = func.apply(associatedRule, actual);
-        }
-
-        return actual;
+      if (configurator != null) {
+        transitionApplier.applyAttributeConfigurator(attribute, fromRule, toTarget);
+      } else {
+        transitionApplier.applyTransition(attribute.getConfigurationTransition());
       }
-    });
+    }
+
+    transitionApplier.applyConfigurationHook(fromRule, attribute, toTarget);
   }
 
   /**
@@ -1677,6 +2060,13 @@ public final class BuildConfiguration {
   }
 
   /**
+   * Which fragments does this configuration contain?
+   */
+  public Set<Class<? extends Fragment>> fragmentClasses() {
+    return fragments.keySet();
+  }
+
+  /**
    * Returns true if non-functional build stamps are enabled.
    */
   public boolean stampBinaries() {
@@ -1788,6 +2178,15 @@ public final class BuildConfiguration {
   }
 
   /**
+   * Returns whether we should use dynamically instantiated build configurations
+   * vs. static configurations (e.g. predefined in
+   * {@link com.google.devtools.build.lib.analysis.ConfigurationCollectionFactory}).
+   */
+  public boolean useDynamicConfigurations() {
+    return options.useDynamicConfigurations;
+  }
+
+  /**
    * Returns compilation mode.
    */
   public CompilationMode getCompilationMode() {
@@ -1801,7 +2200,22 @@ public final class BuildConfiguration {
 
   /** Returns a copy of the build configuration options for this configuration. */
   public BuildOptions cloneOptions() {
-    return buildOptions.clone();
+    BuildOptions clone = buildOptions.clone();
+    return clone;
+  }
+
+  /**
+   * Returns the actual options reference used by this configuration.
+   *
+   * <p><b>Be very careful using this method.</b> Options classes are mutable - no caller
+   * should ever call this method if there's any change the reference might be written to.
+   * This method only exists because {@link #cloneOptions} can be expensive when applied to
+   * every edge in a dependency graph, which becomes possible with dynamic configurations.
+   *
+   * <p>Do not use this method without careful review with other Bazel developers..
+   */
+  public BuildOptions getOptions() {
+    return buildOptions;
   }
 
   /**
@@ -1907,7 +2321,12 @@ public final class BuildConfiguration {
    * See {@code BuildConfigurationCollection.Transitions.getArtifactOwnerConfiguration()}.
    */
   public BuildConfiguration getArtifactOwnerConfiguration() {
-    return transitions.getArtifactOwnerConfiguration();
+    // Dynamic configurations inherit transitions objects from other configurations exclusively
+    // for use of Transitions.getDynamicTransitions. No other calls to transitions should be
+    // made for dynamic configurations.
+    // TODO(bazel-team): enforce the above automatically (without having to explicitly check
+    // for dynamic configuration mode).
+    return useDynamicConfigurations() ? this : transitions.getArtifactOwnerConfiguration();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java
index 0374e8ea6b..f7713dfce1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfigurationCollection.java
@@ -153,7 +153,7 @@ public final class BuildConfigurationCollection {
   /**
    * The outgoing transitions for a build configuration.
    */
-  public static class Transitions implements Serializable {
+  public abstract static class Transitions implements Serializable {
     protected final BuildConfiguration configuration;
 
     /**
@@ -172,12 +172,6 @@ public final class BuildConfigurationCollection {
       this.splitTransitionTable = ImmutableListMultimap.copyOf(splitTransitionTable);
     }
 
-    public Transitions(BuildConfiguration configuration,
-        Map<? extends Transition, ConfigurationHolder> transitionTable) {
-      this(configuration, transitionTable,
-          ImmutableListMultimap.<SplitTransition<?>, BuildConfiguration>of());
-    }
-
     public Map<? extends Transition, ConfigurationHolder> getTransitionTable() {
       return transitionTable;
     }
@@ -222,10 +216,13 @@ public final class BuildConfigurationCollection {
      * Returns the new configuration after traversing a dependency edge with a
      * given configuration transition.
      *
+     * <p>Only used for static configuration builds.
+     *
      * @param configurationTransition the configuration transition
      * @return the new configuration
      */
-    public BuildConfiguration getConfiguration(Transition configurationTransition) {
+    public BuildConfiguration getStaticConfiguration(Transition configurationTransition) {
+      Preconditions.checkState(!configuration.useDynamicConfigurations());
       ConfigurationHolder holder = transitionTable.get(configurationTransition);
       if (holder == null && configurationTransition.defaultsToSelf()) {
         return configuration;
@@ -234,12 +231,41 @@ public final class BuildConfigurationCollection {
     }
 
     /**
+     * Translates a static configuration {@link Transition} reference into the corresponding
+     * dynamic configuration transition.
+     *
+     * <p>The difference is that with static configurations, the transition just models a desired
+     * type of transition that subsequently gets linked to a pre-built global configuration through
+     * custom logic in {@link BuildConfigurationCollection.Transitions} and
+     * {@link com.google.devtools.build.lib.analysis.ConfigurationCollectionFactory}.
+     *
+     * <p>With dynamic configurations, the transition directly embeds the semantics, e.g.
+     * it includes not just a name but also the logic of how it should transform its input
+     * configuration.
+     *
+     * <p>This is a connecting method meant to keep the two models in sync for the current time
+     * in which they must co-exist. Once dynamic configurations are production-ready, we'll remove
+     * the static configuration code entirely.
+     */
+    protected Transition getDynamicTransition(Transition transition) {
+      Preconditions.checkState(configuration.useDynamicConfigurations());
+      if (transition == Attribute.ConfigurationTransition.NONE) {
+        return transition;
+      } else if (transition == Attribute.ConfigurationTransition.NULL) {
+        return transition;
+      } else if (transition == Attribute.ConfigurationTransition.HOST) {
+        return HostTransition.INSTANCE;
+      } else {
+        throw new UnsupportedOperationException("No dynamic mapping for " + transition.toString());
+      }
+    }
+
+    /**
      * Arbitrary configuration transitions can be implemented by overriding this hook.
      */
     @SuppressWarnings("unused")
-    public BuildConfiguration configurationHook(Rule fromTarget,
-        Attribute attribute, Target toTarget, BuildConfiguration toConfiguration) {
-      return toConfiguration;
+    public void configurationHook(Rule fromTarget, Attribute attribute, Target toTarget,
+        BuildConfiguration.TransitionApplier transitionApplier) {
     }
 
     /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
index cee3ceb0e1..e77df0c837 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildOptions.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.analysis.config;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
@@ -38,13 +39,14 @@ import java.util.Set;
 import java.util.TreeMap;
 import java.util.TreeSet;
 
+import javax.annotation.Nullable;
+
 /**
- * This is a collection of command-line options from all configuration fragments. Contains
- * a single instance for all FragmentOptions classes provided by Blaze language modules.
+ * Stores the command-line options from a set of configuration fragments.
  */
 public final class BuildOptions implements Cloneable, Serializable {
   /**
-   * Creates a BuildOptions object with all options set to its default value.
+   * Creates a BuildOptions object with all options set to their default values.
    */
   public static BuildOptions createDefaults(Iterable<Class<? extends FragmentOptions>> options) {
     Builder builder = builder();
@@ -55,7 +57,7 @@ public final class BuildOptions implements Cloneable, Serializable {
   }
 
   /**
-   * This function creates a new BuildOptions instance for host.
+   * Creates a new BuildOptions instance for host.
    *
    * @param fallback if true, we have already tried the user specified hostCpu options
    *                 and it didn't work, so now we try the default options instead.
@@ -81,7 +83,22 @@ public final class BuildOptions implements Cloneable, Serializable {
   }
 
   /**
-   * Creates an BuildOptions class by taking the option values from an options provider
+   * Returns an equivalent instance to this one with only options from the given
+   * {@link FragmentOptions} classes.
+   */
+  public BuildOptions trim(Set<Class<? extends FragmentOptions>> optionsClasses) {
+    Builder builder = builder();
+    for (FragmentOptions options : fragmentOptionsMap.values()) {
+      if (optionsClasses.contains(options.getClass())
+          || options instanceof BuildConfiguration.Options) {
+        builder.add(options);
+      }
+    }
+    return builder.build();
+  }
+
+  /**
+   * Creates a BuildOptions class by taking the option values from an options provider
    * (eg. an OptionsParser).
    */
   public static BuildOptions of(List<Class<? extends FragmentOptions>> optionsList,
@@ -94,11 +111,21 @@ public final class BuildOptions implements Cloneable, Serializable {
   }
 
   /**
-   * Creates an BuildOptions class by taking the option values from command-line arguments
+   * Creates a BuildOptions class by taking the option values from command-line arguments
    */
   @VisibleForTesting
   public static BuildOptions of(List<Class<? extends FragmentOptions>> optionsList, String... args)
       throws OptionsParsingException {
+    return of(optionsList, null, args);
+  }
+
+  /**
+   * Creates a BuildOptions class by taking the option values from command-line arguments and
+   * applying the specified original options.
+   */
+  @VisibleForTesting
+  static BuildOptions of(List<Class<?extends FragmentOptions>> optionsList,
+      BuildOptions originalOptions, String... args) throws OptionsParsingException {
     Builder builder = builder();
     OptionsParser parser = OptionsParser.newOptionsParser(
         ImmutableList.<Class<? extends OptionsBase>>copyOf(optionsList));
@@ -106,6 +133,7 @@ public final class BuildOptions implements Cloneable, Serializable {
     for (Class<? extends FragmentOptions> optionsClass : optionsList) {
       builder.add(parser.getOptions(optionsClass));
     }
+    builder.setOriginalOptions(originalOptions);
     return builder.build();
   }
 
@@ -200,19 +228,44 @@ public final class BuildOptions implements Cloneable, Serializable {
    */
   @Override
   public BuildOptions clone() {
+    return clone(null);
+  }
+
+  /**
+   * Creates a copy of the BuildOptions object that stores a set of original options. This can
+   * be used to power "reversion" of options changes.
+   */
+  public BuildOptions clone(@Nullable BuildOptions originalOptions) {
     ImmutableMap.Builder<Class<? extends FragmentOptions>, FragmentOptions> builder =
         ImmutableMap.builder();
     for (Map.Entry<Class<? extends FragmentOptions>, FragmentOptions> entry :
         fragmentOptionsMap.entrySet()) {
       builder.put(entry.getKey(), entry.getValue().clone());
     }
-    return new BuildOptions(builder.build());
+    // TODO(bazel-team): only store the diff between the current options and its original
+    // options. This may be easier with immutable options.
+    return new BuildOptions(builder.build(), originalOptions);
+  }
+
+  /**
+   * Returns the original options these options were spawned from, or null if this info wasn't
+   * recorded.
+   */
+  public BuildOptions getOriginal() {
+    return originalOptions;
   }
 
   @Override
   public boolean equals(Object other) {
-    return (this == other) || (other instanceof BuildOptions &&
-        fragmentOptionsMap.equals(((BuildOptions) other).fragmentOptionsMap));
+    if (this == other) {
+      return true;
+    } else if (!(other instanceof BuildOptions)) {
+      return false;
+    } else {
+      BuildOptions otherOptions = (BuildOptions) other;
+      return fragmentOptionsMap.equals(otherOptions.fragmentOptionsMap)
+          && Objects.equal(originalOptions, otherOptions.originalOptions);
+    }
   }
 
   @Override
@@ -225,9 +278,17 @@ public final class BuildOptions implements Cloneable, Serializable {
    */
   private final ImmutableMap<Class<? extends FragmentOptions>, FragmentOptions> fragmentOptionsMap;
 
+  /**
+   * Records an original set of options these options came from. When set, this
+   * provides the ability to "revert" options back to a previous form.
+   */
+  @Nullable private final BuildOptions originalOptions;
+
   private BuildOptions(
-      ImmutableMap<Class<? extends FragmentOptions>, FragmentOptions> fragmentOptionsMap) {
+      ImmutableMap<Class<? extends FragmentOptions>, FragmentOptions> fragmentOptionsMap,
+      BuildOptions originalOptions) {
     this.fragmentOptionsMap = fragmentOptionsMap;
+    this.originalOptions = originalOptions;
   }
 
   /**
@@ -250,11 +311,21 @@ public final class BuildOptions implements Cloneable, Serializable {
       return this;
     }
 
+    /**
+     * Specify the original options these options were branched from. This should only be used
+     * when there's a desire to revert back to the old options, e.g. for a parent transition.
+     */
+    public Builder setOriginalOptions(BuildOptions originalOptions) {
+      this.originalOptions = originalOptions;
+      return this;
+    }
+
     public BuildOptions build() {
-      return new BuildOptions(ImmutableMap.copyOf(builderMap));
+      return new BuildOptions(ImmutableMap.copyOf(builderMap), originalOptions);
     }
 
     private Map<Class<? extends FragmentOptions>, FragmentOptions> builderMap;
+    @Nullable private BuildOptions originalOptions;
 
     private Builder() {
       builderMap = new HashMap<>();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/HostTransition.java b/src/main/java/com/google/devtools/build/lib/analysis/config/HostTransition.java
new file mode 100644
index 0000000000..081f19c8ae
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/HostTransition.java
@@ -0,0 +1,31 @@
+// Copyright 2015 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.analysis.config;
+
+/**
+ * Dynamic transition to the host configuration.
+ */
+public final class HostTransition implements PatchTransition {
+  public static final HostTransition INSTANCE = new HostTransition();
+
+  private HostTransition() {}
+
+  @Override
+  public BuildOptions apply(BuildOptions options) {
+    return options.createHostOptions(false);
+  }
+
+  @Override
+  public boolean defaultsToSelf() { return false; }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/PatchTransition.java b/src/main/java/com/google/devtools/build/lib/analysis/config/PatchTransition.java
new file mode 100644
index 0000000000..30edd4a960
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/PatchTransition.java
@@ -0,0 +1,45 @@
+// Copyright 2015 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.analysis.config;
+
+import com.google.devtools.build.lib.packages.Attribute;
+
+/**
+ * Interface for a configuration transition using dynamic configurations.
+ *
+ * <p>The concept is simple: given the input configuration's build options, the
+ * transition does whatever it wants to them and returns the modified result.
+ *
+ * <p>Implementations must be stateless: the transformation logic cannot use
+ * any information from any data besides the input build options.
+ *
+ * <p>For performance reasons, the input options are passed in as a <i>reference</i>,
+ * not a <i>copy</i>. Transition implementations should <i>always</i> treat these
+ * options as immutable, and call
+ * {@link com.google.devtools.build.lib.analysis.config.BuildOptions#clone}
+ * before applying any mutations. Unfortunately,
+ * {@link com.google.devtools.build.lib.analysis.config.BuildOptions} does not currently
+ * enforce immutability, so care must be taken not to modify the wrong instance.
+ */
+public interface PatchTransition extends Attribute.Transition {
+
+  /**
+   * Applies the transition.
+   *
+   * @param options the options representing the input configuration to this transition. DO NOT
+   *     MODIFY THIS VARIABLE WITHOUT CLONING IT FIRST.
+   * @return the options representing the desired post-transition configuration
+   */
+  BuildOptions apply(BuildOptions options);
+}