Split ConfigurationTransitionDependency into a new class

 and break relation to the existing Dependency.

Part of work on toolchain transitions, #10523.

Closes #11398.

PiperOrigin-RevId: 312256302
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
index 30020f7..78d7c6a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
@@ -200,20 +200,17 @@
     }
 
     // We'll get the configs from ConfigurationsCollector#getConfigurations, which gets
-    // configurations
-    // for deps including transitions. So to satisfy its API we resolve transitions and repackage
-    // each target as a Dependency (with a NONE transition if necessary).
-    Multimap<BuildConfiguration, Dependency> asDeps = targetsToDeps(nodes, ruleClassProvider);
+    // configurations for deps including transitions.
+    Multimap<BuildConfiguration, DependencyKey> asDeps = targetsToDeps(nodes, ruleClassProvider);
 
     return ConfigurationResolver.getConfigurationsFromExecutor(
         nodes, asDeps, eventHandler, configurationsCollector);
   }
 
   @VisibleForTesting
-  public static Multimap<BuildConfiguration, Dependency> targetsToDeps(
+  public static Multimap<BuildConfiguration, DependencyKey> targetsToDeps(
       Collection<TargetAndConfiguration> nodes, ConfiguredRuleClassProvider ruleClassProvider) {
-    Multimap<BuildConfiguration, Dependency> asDeps =
-        ArrayListMultimap.<BuildConfiguration, Dependency>create();
+    Multimap<BuildConfiguration, DependencyKey> asDeps = ArrayListMultimap.create();
     for (TargetAndConfiguration targetAndConfig : nodes) {
       ConfigurationTransition transition =
           TransitionResolver.evaluateTransition(
@@ -222,13 +219,13 @@
               targetAndConfig.getTarget(),
               ruleClassProvider.getTrimmingTransitionFactory());
       if (targetAndConfig.getConfiguration() != null) {
+        // TODO(bazel-team): support top-level aspects
         asDeps.put(
             targetAndConfig.getConfiguration(),
-            Dependency.withTransitionAndAspects(
-                targetAndConfig.getLabel(),
-                transition,
-                // TODO(bazel-team): support top-level aspects
-                AspectCollection.EMPTY));
+            DependencyKey.builder()
+                .setLabel(targetAndConfig.getLabel())
+                .setTransition(transition)
+                .build());
       }
     }
     return asDeps;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BUILD b/src/main/java/com/google/devtools/build/lib/analysis/BUILD
index ee6b7de..d22f09e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BUILD
@@ -320,6 +320,7 @@
         ":constraints/supported_environments",
         ":constraints/supported_environments_provider",
         ":dependency",
+        ":dependency_key",
         ":dependency_kind",
         ":duplicate_exception",
         ":extra/extra_action_info_file_write_action",
@@ -662,7 +663,7 @@
         ":config/build_configuration",
         ":config/build_options",
         ":config/invalid_configuration_exception",
-        ":dependency",
+        ":dependency_key",
         "//src/main/java/com/google/devtools/build/lib/events",
         "//third_party:guava",
     ],
@@ -709,6 +710,17 @@
 )
 
 java_library(
+    name = "dependency_key",
+    srcs = ["DependencyKey.java"],
+    deps = [
+        ":aspect_collection",
+        ":config/transitions/configuration_transition",
+        "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//third_party:auto_value",
+    ],
+)
+
+java_library(
     name = "dependency_kind",
     srcs = ["DependencyKind.java"],
     deps = [
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsCollector.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsCollector.java
index 3c66c76..8c7a778 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsCollector.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsCollector.java
@@ -28,6 +28,6 @@
    * <p>Skips targets with loading phase errors.
    */
   ConfigurationsResult getConfigurations(
-      ExtendedEventHandler eventHandler, BuildOptions fromOptions, Iterable<Dependency> keys)
+      ExtendedEventHandler eventHandler, BuildOptions fromOptions, Iterable<DependencyKey> keys)
       throws InvalidConfigurationException;
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsResult.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsResult.java
index f1b4770..2916733 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsResult.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationsResult.java
@@ -24,11 +24,11 @@
  * registers if an error was recorded.
  */
 public class ConfigurationsResult {
-  private final Multimap<Dependency, BuildConfiguration> configurations;
+  private final Multimap<DependencyKey, BuildConfiguration> configurations;
   private final boolean hasError;
 
   private ConfigurationsResult(
-      Multimap<Dependency, BuildConfiguration> configurations, boolean hasError) {
+      Multimap<DependencyKey, BuildConfiguration> configurations, boolean hasError) {
     this.configurations = configurations;
     this.hasError = hasError;
   }
@@ -37,7 +37,7 @@
     return hasError;
   }
 
-  public Multimap<Dependency, BuildConfiguration> getConfigurationMap() {
+  public Multimap<DependencyKey, BuildConfiguration> getConfigurationMap() {
     return configurations;
   }
 
@@ -47,11 +47,11 @@
 
   /** Builder for {@link ConfigurationsResult} */
   public static class Builder {
-    private final Multimap<Dependency, BuildConfiguration> configurations =
-        ArrayListMultimap.<Dependency, BuildConfiguration>create();
+    private final Multimap<DependencyKey, BuildConfiguration> configurations =
+        ArrayListMultimap.create();
     private boolean hasError = false;
 
-    public void put(Dependency key, BuildConfiguration value) {
+    public void put(DependencyKey key, BuildConfiguration value) {
       configurations.put(key, value);
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/Dependency.java b/src/main/java/com/google/devtools/build/lib/analysis/Dependency.java
index 0b7e227..c34be2a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/Dependency.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Dependency.java
@@ -27,17 +27,10 @@
 /**
  * A dependency of a configured target through a label.
  *
- * <p>The dep's configuration can be specified in one of two ways:
- *
- * <p>Explicit configurations: includes the target and the configuration of the dependency
- * configured target and any aspects that may be required, as well as the configurations for these
- * aspects and transition keys. {@link Dependency#getTransitionKeys} provides some more context on
- * transition keys.
- *
- * <p>Configuration transitions: 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. A set of aspects is also included; the caller must
- * also construct configurations for each of these.
+ * <p>All instances have an explicit configuration, which includes the target and the configuration
+ * of the dependency configured target and any aspects that may be required, as well as the
+ * configurations for these aspects and transition keys. {@link Dependency#getTransitionKeys}
+ * provides some more context on transition keys.
  *
  * <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
@@ -144,14 +137,6 @@
         ImmutableList.of());
   }
 
-  /**
-   * Creates a new {@link Dependency} with the given transition and aspects.
-   */
-  public static Dependency withTransitionAndAspects(
-      Label label, ConfigurationTransition transition, AspectCollection aspects) {
-    return new ConfigurationTransitionDependency(label, transition, aspects);
-  }
-
   protected final Label label;
 
   /**
@@ -168,27 +153,12 @@
   }
 
   /**
-   * Returns true if this dependency specifies an explicit configuration, false if it specifies
-   * a configuration transition.
-   */
-  public abstract boolean hasExplicitConfiguration();
-
-  /**
    * Returns the explicit configuration intended for this dependency.
-   *
-   * @throws IllegalStateException if {@link #hasExplicitConfiguration} returns false.
    */
   @Nullable
   public abstract BuildConfiguration getConfiguration();
 
   /**
-   * Returns the configuration transition to apply to reach the target this dependency points to.
-   *
-   * @throws IllegalStateException if {@link #hasExplicitConfiguration} returns true.
-   */
-  public abstract ConfigurationTransition getTransition();
-
-  /**
    * Returns the set of aspects which should be evaluated and combined with the configured target
    * pointed to by this dependency.
    *
@@ -198,8 +168,6 @@
 
   /**
    * Returns the configuration an aspect should be evaluated with
-   **
-   * @throws IllegalStateException if {@link #hasExplicitConfiguration()} returns false.
    */
   public abstract BuildConfiguration getAspectConfiguration(AspectDescriptor aspect);
 
@@ -211,8 +179,6 @@
    * multiple entries if the dependency has a null configuration, yet the outgoing edge has a split
    * transition. In such cases all transition keys returned by the transition are tagged to the
    * dependency.
-   *
-   * @throws IllegalStateException if {@link #hasExplicitConfiguration()} returns false.
    */
   public abstract ImmutableList<String> getTransitionKeys();
 
@@ -228,11 +194,6 @@
       this.transitionKeys = Preconditions.checkNotNull(transitionKeys);
     }
 
-    @Override
-    public boolean hasExplicitConfiguration() {
-      return true;
-    }
-
     @Nullable
     @Override
     public BuildConfiguration getConfiguration() {
@@ -240,12 +201,6 @@
     }
 
     @Override
-    public ConfigurationTransition getTransition() {
-      throw new IllegalStateException(
-          "This dependency has an explicit configuration, not a transition.");
-    }
-
-    @Override
     public AspectCollection getAspects() {
       return AspectCollection.EMPTY;
     }
@@ -303,22 +258,11 @@
     }
 
     @Override
-    public boolean hasExplicitConfiguration() {
-      return true;
-    }
-
-    @Override
     public BuildConfiguration getConfiguration() {
       return configuration;
     }
 
     @Override
-    public ConfigurationTransition getTransition() {
-      throw new IllegalStateException(
-          "This dependency has an explicit configuration, not a transition.");
-    }
-
-    @Override
     public AspectCollection getAspects() {
       return aspects;
     }
@@ -358,74 +302,4 @@
     }
   }
 
-  /**
-   * Implementation of a dependency with a given configuration transition.
-   */
-  private static final class ConfigurationTransitionDependency extends Dependency {
-    private final ConfigurationTransition transition;
-    private final AspectCollection aspects;
-
-    public ConfigurationTransitionDependency(
-        Label label, ConfigurationTransition transition, AspectCollection aspects) {
-      super(label);
-      this.transition = Preconditions.checkNotNull(transition);
-      this.aspects = Preconditions.checkNotNull(aspects);
-    }
-
-    @Override
-    public boolean hasExplicitConfiguration() {
-      return false;
-    }
-
-    @Override
-    public BuildConfiguration getConfiguration() {
-      throw new IllegalStateException(
-          "This dependency has a transition, not an explicit configuration.");
-    }
-
-    @Override
-    public ConfigurationTransition getTransition() {
-      return transition;
-    }
-
-    @Override
-    public AspectCollection getAspects() {
-      return aspects;
-    }
-
-    @Override
-    public BuildConfiguration getAspectConfiguration(AspectDescriptor aspect) {
-      throw new IllegalStateException(
-          "This dependency has a transition, not an explicit aspect configuration.");
-    }
-
-    @Override
-    public ImmutableList<String> getTransitionKeys() {
-      throw new IllegalStateException(
-          "This dependency has a transition, not an explicit configuration.");
-    }
-
-    @Override
-    public int hashCode() {
-      return Objects.hash(label, transition, aspects);
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof ConfigurationTransitionDependency)) {
-        return false;
-      }
-      ConfigurationTransitionDependency otherDep = (ConfigurationTransitionDependency) other;
-      return label.equals(otherDep.label)
-          && transition.equals(otherDep.transition)
-          && aspects.equals(otherDep.aspects);
-    }
-
-    @Override
-    public String toString() {
-      return String.format(
-          "%s{label=%s, transition=%s, aspects=%s}",
-          getClass().getSimpleName(), label, transition, aspects);
-    }
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyKey.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyKey.java
new file mode 100644
index 0000000..f7ba381
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyKey.java
@@ -0,0 +1,56 @@
+// Copyright 2020 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;
+
+import com.google.auto.value.AutoValue;
+import com.google.devtools.build.lib.analysis.config.transitions.ConfigurationTransition;
+import com.google.devtools.build.lib.cmdline.Label;
+
+/**
+ * Information about a dependency, including the label and configuration transition. This will be
+ * used to create the actual {@link Dependency}.
+ */
+@AutoValue
+public abstract class DependencyKey {
+
+  /** Builder to help construct instances of {@link DependencyKey}. */
+  @AutoValue.Builder
+  public interface Builder {
+    /** Sets the label of the target this dependency points to. */
+    Builder setLabel(Label label);
+
+    /** Sets the transition to use when evaluating the target this dependency points to. */
+    Builder setTransition(ConfigurationTransition transition);
+
+    /** Sets the aspects that are propagating to the target this dependency points to. */
+    Builder setAspects(AspectCollection aspectCollection);
+
+    /** Returns the new instance. */
+    DependencyKey build();
+  }
+
+  /** Returns a new {@link Builder} to construct instances of {@link DependencyKey}. */
+  public static Builder builder() {
+    return new AutoValue_DependencyKey.Builder().setAspects(AspectCollection.EMPTY);
+  }
+
+  /** Returns the label of the target this dependency points to. */
+  public abstract Label getLabel();
+
+  /** Returns the transition to use when evaluating the target this dependency points to. */
+  public abstract ConfigurationTransition getTransition();
+
+  /** Returns the aspects that are propagating to the target this dependency points to. */
+  public abstract AspectCollection getAspects();
+}
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 b8e7736..9711cba 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
@@ -117,7 +117,7 @@
    *     temporary feature; see the corresponding methods in ConfiguredRuleClassProvider)
    * @return a mapping of each attribute in this rule or aspects to its dependent nodes
    */
-  public final OrderedSetMultimap<DependencyKind, Dependency> dependentNodeMap(
+  public final OrderedSetMultimap<DependencyKind, DependencyKey> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       @Nullable Aspect aspect,
@@ -126,7 +126,7 @@
       @Nullable TransitionFactory<Rule> trimmingTransitionFactory)
       throws EvalException, InterruptedException, InconsistentAspectOrderException {
     NestedSetBuilder<Cause> rootCauses = NestedSetBuilder.stableOrder();
-    OrderedSetMultimap<DependencyKind, Dependency> outgoingEdges =
+    OrderedSetMultimap<DependencyKind, DependencyKey> outgoingEdges =
         dependentNodeMap(
             node,
             hostConfig,
@@ -172,7 +172,7 @@
    * @param rootCauses collector for dep labels that can't be (loading phase) loaded
    * @return a mapping of each attribute in this rule or aspects to its dependent nodes
    */
-  public final OrderedSetMultimap<DependencyKind, Dependency> dependentNodeMap(
+  public final OrderedSetMultimap<DependencyKind, DependencyKey> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       Iterable<Aspect> aspects,
@@ -219,7 +219,7 @@
         partiallyResolveDependencies(
             outgoingLabels, fromRule, attributeMap, toolchainContexts, aspects);
 
-    OrderedSetMultimap<DependencyKind, Dependency> outgoingEdges =
+    OrderedSetMultimap<DependencyKind, DependencyKey> outgoingEdges =
         fullyResolveDependencies(
             partiallyResolvedDeps, targetMap, node.getConfiguration(), trimmingTransitionFactory);
 
@@ -331,13 +331,13 @@
    * being calculated as an argument or its attributes and it should <b>NOT</b> do anything with the
    * keys of {@code partiallyResolvedDeps} other than passing them on to the output map.
    */
-  private OrderedSetMultimap<DependencyKind, Dependency> fullyResolveDependencies(
+  private OrderedSetMultimap<DependencyKind, DependencyKey> fullyResolveDependencies(
       OrderedSetMultimap<DependencyKind, PartiallyResolvedDependency> partiallyResolvedDeps,
       Map<Label, Target> targetMap,
       BuildConfiguration originalConfiguration,
       @Nullable TransitionFactory<Rule> trimmingTransitionFactory)
       throws InconsistentAspectOrderException {
-    OrderedSetMultimap<DependencyKind, Dependency> outgoingEdges = OrderedSetMultimap.create();
+    OrderedSetMultimap<DependencyKind, DependencyKey> outgoingEdges = OrderedSetMultimap.create();
 
     for (Map.Entry<DependencyKind, PartiallyResolvedDependency> entry :
         partiallyResolvedDeps.entries()) {
@@ -359,7 +359,11 @@
 
       outgoingEdges.put(
           entry.getKey(),
-          Dependency.withTransitionAndAspects(dep.getLabel(), transition, requiredAspects));
+          DependencyKey.builder()
+              .setLabel(dep.getLabel())
+              .setTransition(transition)
+              .setAspects(requiredAspects)
+              .build());
     }
     return outgoingEdges;
   }
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 26b923c..2862d54 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
@@ -16,7 +16,6 @@
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Joiner;
-import com.google.common.base.Preconditions;
 import com.google.common.base.Verify;
 import com.google.common.base.VerifyException;
 import com.google.common.collect.ImmutableList;
@@ -29,6 +28,7 @@
 import com.google.devtools.build.lib.analysis.ConfigurationsCollector;
 import com.google.devtools.build.lib.analysis.ConfigurationsResult;
 import com.google.devtools.build.lib.analysis.Dependency;
+import com.google.devtools.build.lib.analysis.DependencyKey;
 import com.google.devtools.build.lib.analysis.DependencyKind;
 import com.google.devtools.build.lib.analysis.PlatformOptions;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
@@ -106,7 +106,7 @@
    *
    * @param env Skyframe evaluation environment
    * @param ctgValue the label and configuration of the source target
-   * @param originalDeps the transition requests for each dep and each dependency kind
+   * @param dependencyKeys the transition requests for each dep and each dependency kind
    * @param hostConfiguration the host configuration
    * @param defaultBuildOptions default build options to diff options against for optimization
    * @param configConditions {@link ConfigMatchingProvider} map for the rule
@@ -118,7 +118,7 @@
   public static OrderedSetMultimap<DependencyKind, Dependency> resolveConfigurations(
       SkyFunction.Environment env,
       TargetAndConfiguration ctgValue,
-      OrderedSetMultimap<DependencyKind, Dependency> originalDeps,
+      OrderedSetMultimap<DependencyKind, DependencyKey> dependencyKeys,
       BuildConfiguration hostConfiguration,
       BuildOptions defaultBuildOptions,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions)
@@ -128,7 +128,7 @@
     // configuration paired with a transition key corresponding to the BuildConfiguration. 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<SkyKey, Pair<Map.Entry<DependencyKind, Dependency>, String>> keysToEntries =
+    Multimap<SkyKey, Pair<Map.Entry<DependencyKind, DependencyKey>, String>> keysToEntries =
         LinkedListMultimap.create();
 
     // Stores the result of applying a transition to the current configuration using a
@@ -142,13 +142,13 @@
     BuildConfiguration currentConfiguration = ctgValue.getConfiguration();
 
     // 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
+    // original label ordering of each attribute. For example, if dependencyKeys.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
+    // For split transitions, dependencyKeys.get("data") = [":a", ":b"] can produce the output
     // [":a"<config1>, ":a"<config2>, ..., ":b"<config1>, ":b"<config2>, ...]. All instances of ":a"
     // still appear before all instances of ":b". But the [":a"<config1>, ":a"<config2>"] subset may
     // be in any (deterministic) order. In particular, this may not be the same order as
@@ -159,19 +159,17 @@
     // This map is used heavily by all builds. Inserts and gets should be as fast as possible.
     Multimap<DependencyEdge, Dependency> resolvedDeps = LinkedHashMultimap.create();
 
-    // Performance optimization: This method iterates over originalDeps twice. By storing
+    // Performance optimization: This method iterates over dependencyKeys twice. By storing
     // DependencyEdge 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<DependencyEdge> attributesAndLabels = new ArrayList<>(originalDeps.size());
+    ArrayList<DependencyEdge> attributesAndLabels = new ArrayList<>(dependencyKeys.size());
 
-    for (Map.Entry<DependencyKind, Dependency> depsEntry : originalDeps.entries()) {
-      Dependency dep = depsEntry.getValue();
+    for (Map.Entry<DependencyKind, DependencyKey> depsEntry : dependencyKeys.entries()) {
+      DependencyKey dep = depsEntry.getValue();
       DependencyKind depKind = depsEntry.getKey();
       DependencyEdge dependencyEdge = new DependencyEdge(depKind, dep.getLabel());
       attributesAndLabels.add(dependencyEdge);
-      // DependencyResolver should never emit a Dependency with an explicit configuration
-      Preconditions.checkState(!dep.hasExplicitConfiguration());
 
       // The null configuration can be trivially computed (it's, well, null), so special-case that
       // transition here and skip the rest of the logic. A *lot* of targets have null deps, so
@@ -399,8 +397,8 @@
         }
         BuildConfiguration trimmedConfig =
             ((BuildConfigurationValue) valueOrException.get()).getConfiguration();
-        for (Pair<Map.Entry<DependencyKind, Dependency>, String> info : keysToEntries.get(key)) {
-          Dependency originalDep = info.first.getValue();
+        for (Pair<Map.Entry<DependencyKind, DependencyKey>, String> info : keysToEntries.get(key)) {
+          DependencyKey originalDep = info.first.getValue();
           if (trimmedConfig.trimConfigurationsRetroactively()
               && !originalDep.getAspects().isEmpty()) {
             String message =
@@ -427,7 +425,7 @@
       throw new DependencyEvaluationException(e);
     }
 
-    return sortResolvedDeps(originalDeps, resolvedDeps, attributesAndLabels);
+    return sortResolvedDeps(dependencyKeys, resolvedDeps, attributesAndLabels);
   }
 
   /**
@@ -629,7 +627,7 @@
       SkyFunction.Environment env,
       TargetAndConfiguration ctgValue,
       Attribute attribute,
-      Dependency dep,
+      DependencyKey dep,
       Set<Class<? extends Fragment>> expectedDepFragments)
       throws DependencyEvaluationException {
     Set<String> ctgFragmentNames = new HashSet<>();
@@ -670,23 +668,20 @@
   /**
    * 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 dependencyKeys the input deps with the ordering to preserve
    * @param resolvedDeps the unordered output deps
    * @param attributesAndLabels collection of <attribute, depLabel> pairs guaranteed to match the
-   *     ordering of originalDeps.entries(). This is a performance optimization: see {@link
+   *     ordering of dependencyKeys.entries(). This is a performance optimization: see {@link
    *     #resolveConfigurations#attributesAndLabels} for details.
    */
   private static OrderedSetMultimap<DependencyKind, Dependency> sortResolvedDeps(
-      OrderedSetMultimap<DependencyKind, Dependency> originalDeps,
+      OrderedSetMultimap<DependencyKind, DependencyKey> dependencyKeys,
       Multimap<DependencyEdge, Dependency> resolvedDeps,
       ArrayList<DependencyEdge> attributesAndLabels) {
     Iterator<DependencyEdge> iterator = attributesAndLabels.iterator();
     OrderedSetMultimap<DependencyKind, Dependency> result = OrderedSetMultimap.create();
-    for (Map.Entry<DependencyKind, Dependency> depsEntry : originalDeps.entries()) {
+    for (Map.Entry<DependencyKind, DependencyKey> depsEntry : dependencyKeys.entries()) {
       DependencyEdge edge = iterator.next();
-      if (depsEntry.getValue().hasExplicitConfiguration()) {
-        result.put(edge.dependencyKind, depsEntry.getValue());
-      } else {
         Collection<Dependency> resolvedDepWithSplit = resolvedDeps.get(edge);
         Verify.verify(!resolvedDepWithSplit.isEmpty());
         if (resolvedDepWithSplit.size() > 1) {
@@ -695,7 +690,6 @@
           resolvedDepWithSplit = sortedSplitList;
         }
         result.putAll(depsEntry.getKey(), resolvedDepWithSplit);
-      }
     }
     return result;
   }
@@ -743,7 +737,7 @@
   // Keep this in sync with {@link PrepareAnalysisPhaseFunction#resolveConfigurations}.
   public static TopLevelTargetsAndConfigsResult getConfigurationsFromExecutor(
       Iterable<TargetAndConfiguration> defaultContext,
-      Multimap<BuildConfiguration, Dependency> targetsToEvaluate,
+      Multimap<BuildConfiguration, DependencyKey> targetsToEvaluate,
       ExtendedEventHandler eventHandler,
       ConfigurationsCollector configurationsCollector)
       throws InvalidConfigurationException {
@@ -764,7 +758,7 @@
             configurationsCollector.getConfigurations(
                 eventHandler, fromConfig.getOptions(), targetsToEvaluate.get(fromConfig));
         hasError |= configurationsResult.hasError();
-        for (Map.Entry<Dependency, BuildConfiguration> evaluatedTarget :
+        for (Map.Entry<DependencyKey, BuildConfiguration> evaluatedTarget :
             configurationsResult.getConfigurationMap().entries()) {
           Target target = labelsToTargets.get(evaluatedTarget.getKey().getLabel());
           successfullyEvaluatedTargets.put(
diff --git a/src/main/java/com/google/devtools/build/lib/query2/BUILD b/src/main/java/com/google/devtools/build/lib/query2/BUILD
index 8991d0a..287d410 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/query2/BUILD
@@ -36,7 +36,7 @@
         "//src/main/java/com/google/devtools/build/lib/analysis:config/transitions/null_transition",
         "//src/main/java/com/google/devtools/build/lib/analysis:config/transitions/transition_factory",
         "//src/main/java/com/google/devtools/build/lib/analysis:configured_target",
-        "//src/main/java/com/google/devtools/build/lib/analysis:dependency",
+        "//src/main/java/com/google/devtools/build/lib/analysis:dependency_key",
         "//src/main/java/com/google/devtools/build/lib/analysis:dependency_kind",
         "//src/main/java/com/google/devtools/build/lib/analysis:inconsistent_aspect_order_exception",
         "//src/main/java/com/google/devtools/build/lib/analysis:required_config_fragments_provider",
diff --git a/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java
index 48c98b8..9991a1d 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/cquery/TransitionsOutputFormatterCallback.java
@@ -13,11 +13,10 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.cquery;
 
-import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.Dependency;
+import com.google.devtools.build.lib.analysis.DependencyKey;
 import com.google.devtools.build.lib.analysis.DependencyKind;
 import com.google.devtools.build.lib.analysis.DependencyResolver;
 import com.google.devtools.build.lib.analysis.InconsistentAspectOrderException;
@@ -113,7 +112,7 @@
       if (!(configuredTarget instanceof RuleConfiguredTarget)) {
         continue;
       }
-      OrderedSetMultimap<DependencyKind, Dependency> deps;
+      OrderedSetMultimap<DependencyKind, DependencyKey> deps;
       ImmutableMap<Label, ConfigMatchingProvider> configConditions =
           ((RuleConfiguredTarget) configuredTarget).getConfigConditions();
 
@@ -136,15 +135,12 @@
       } catch (EvalException | InconsistentAspectOrderException e) {
         throw new InterruptedException(e.getMessage());
       }
-      for (Map.Entry<DependencyKind, Dependency> attributeAndDep : deps.entries()) {
-        // DependencyResolver should only ever return Dependency instances with transitions and not
-        // with explicit configurations
-        Preconditions.checkState(!attributeAndDep.getValue().hasExplicitConfiguration());
+      for (Map.Entry<DependencyKind, DependencyKey> attributeAndDep : deps.entries()) {
         if (attributeAndDep.getValue().getTransition() == NoTransition.INSTANCE
             || attributeAndDep.getValue().getTransition() == NullTransition.INSTANCE) {
           continue;
         }
-        Dependency dep = attributeAndDep.getValue();
+        DependencyKey dep = attributeAndDep.getValue();
         BuildOptions fromOptions = config.getOptions();
         // TODO(bazel-team): support transitions on Starlark-defined build flags. These require
         // Skyframe loading to get flag default values. See ConfigurationResolver.applyTransition
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
index 5bcc96b..1d01bb8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -229,7 +229,6 @@
         "//src/main/java/com/google/devtools/build/lib/actionsketch:action_sketch",
         "//src/main/java/com/google/devtools/build/lib/analysis:actions/parameter_file_write_action",
         "//src/main/java/com/google/devtools/build/lib/analysis:analysis_cluster",
-        "//src/main/java/com/google/devtools/build/lib/analysis:aspect_collection",
         "//src/main/java/com/google/devtools/build/lib/analysis:blaze_directories",
         "//src/main/java/com/google/devtools/build/lib/analysis:buildinfo/build_info_collection",
         "//src/main/java/com/google/devtools/build/lib/analysis:buildinfo/build_info_key",
@@ -248,6 +247,7 @@
         "//src/main/java/com/google/devtools/build/lib/analysis:configured_object_value",
         "//src/main/java/com/google/devtools/build/lib/analysis:configured_target",
         "//src/main/java/com/google/devtools/build/lib/analysis:dependency",
+        "//src/main/java/com/google/devtools/build/lib/analysis:dependency_key",
         "//src/main/java/com/google/devtools/build/lib/analysis:dependency_kind",
         "//src/main/java/com/google/devtools/build/lib/analysis:duplicate_exception",
         "//src/main/java/com/google/devtools/build/lib/analysis:inconsistent_aspect_order_exception",
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 08c5987..56efefd 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
@@ -32,6 +32,7 @@
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.Dependency;
+import com.google.devtools.build.lib.analysis.DependencyKey;
 import com.google.devtools.build.lib.analysis.DependencyKind;
 import com.google.devtools.build.lib.analysis.DuplicateException;
 import com.google.devtools.build.lib.analysis.EmptyConfiguredTarget;
@@ -590,12 +591,12 @@
       BuildOptions defaultBuildOptions)
       throws DependencyEvaluationException, ConfiguredTargetFunctionException,
           AspectCreationException, InterruptedException {
-    // Create the map from attributes to set of (target, configuration) pairs.
-    OrderedSetMultimap<DependencyKind, Dependency> depValueNames;
+    // Create the map from attributes to set of (target, transition) pairs.
+    OrderedSetMultimap<DependencyKind, DependencyKey> initialDependencies;
     BuildConfiguration configuration = ctgValue.getConfiguration();
     Label label = ctgValue.getLabel();
     try {
-      depValueNames =
+      initialDependencies =
           resolver.dependentNodeMap(
               ctgValue,
               hostConfiguration,
@@ -616,11 +617,11 @@
     }
     // Trim each dep's configuration so it only includes the fragments needed by its transitive
     // closure.
-    depValueNames =
+    OrderedSetMultimap<DependencyKind, Dependency> depValueNames =
         ConfigurationResolver.resolveConfigurations(
             env,
             ctgValue,
-            depValueNames,
+            initialDependencies,
             hostConfiguration,
             defaultBuildOptions,
             configConditions);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseFunction.java
index ce2c580..4ab7bf2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareAnalysisPhaseFunction.java
@@ -21,7 +21,7 @@
 import com.google.common.collect.Multimap;
 import com.google.devtools.build.lib.analysis.AnalysisUtils;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
-import com.google.devtools.build.lib.analysis.Dependency;
+import com.google.devtools.build.lib.analysis.DependencyKey;
 import com.google.devtools.build.lib.analysis.PlatformOptions;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -166,7 +166,7 @@
     // for now, to satisfy its API we resolve transitions and repackage each target as a Dependency
     // (with a NONE transition if necessary).
     // Keep this in sync with AnalysisUtils#getTargetsWithConfigs.
-    Multimap<BuildConfiguration, Dependency> asDeps =
+    Multimap<BuildConfiguration, DependencyKey> asDeps =
         AnalysisUtils.targetsToDeps(nodes, ruleClassProvider);
     LinkedHashSet<TargetAndConfiguration> topLevelTargetsWithConfigs;
     try {
@@ -211,7 +211,7 @@
   private LinkedHashSet<TargetAndConfiguration> resolveConfigurations(
       SkyFunction.Environment env,
       Iterable<TargetAndConfiguration> nodes,
-      Multimap<BuildConfiguration, Dependency> asDeps)
+      Multimap<BuildConfiguration, DependencyKey> asDeps)
       throws InterruptedException, TransitionException, OptionsParsingException {
     Map<Label, Target> labelsToTargets = new LinkedHashMap<>();
     for (TargetAndConfiguration node : nodes) {
@@ -223,13 +223,12 @@
     Map<TargetAndConfiguration, TargetAndConfiguration> successfullyEvaluatedTargets =
         new LinkedHashMap<>();
     for (BuildConfiguration fromConfig : asDeps.keySet()) {
-      Multimap<Dependency, BuildConfiguration> trimmedTargets =
-          getConfigurations(
-              env, fromConfig.getOptions(), asDeps.get(fromConfig));
+      Multimap<DependencyKey, BuildConfiguration> trimmedTargets =
+          getConfigurations(env, fromConfig.getOptions(), asDeps.get(fromConfig));
       if (trimmedTargets == null) {
         continue;
       }
-      for (Map.Entry<Dependency, BuildConfiguration> trimmedTarget : trimmedTargets.entries()) {
+      for (Map.Entry<DependencyKey, BuildConfiguration> trimmedTarget : trimmedTargets.entries()) {
         Target target = labelsToTargets.get(trimmedTarget.getKey().getLabel());
         successfullyEvaluatedTargets.put(
             new TargetAndConfiguration(target, fromConfig),
@@ -264,12 +263,11 @@
 
   // Keep in sync with {@link SkyframeExecutor#getConfigurations}.
   // Note: this implementation runs inside Skyframe, so it has access to SkyFunction.Environment.
-  private Multimap<Dependency, BuildConfiguration> getConfigurations(
-      SkyFunction.Environment env, BuildOptions fromOptions, Iterable<Dependency> keys)
+  private Multimap<DependencyKey, BuildConfiguration> getConfigurations(
+      SkyFunction.Environment env, BuildOptions fromOptions, Iterable<DependencyKey> keys)
       throws InterruptedException, TransitionException, OptionsParsingException {
-    Multimap<Dependency, BuildConfiguration> builder =
-        ArrayListMultimap.<Dependency, BuildConfiguration>create();
-    Set<Dependency> depsToEvaluate = new HashSet<>();
+    Multimap<DependencyKey, BuildConfiguration> builder = ArrayListMultimap.create();
+    Set<DependencyKey> depsToEvaluate = new HashSet<>();
 
     ImmutableSortedSet<Class<? extends Fragment>> allFragments = null;
     if (useUntrimmedConfigs(fromOptions)) {
@@ -280,10 +278,8 @@
     final List<SkyKey> transitiveFragmentSkyKeys = new ArrayList<>();
     Map<Label, ImmutableSortedSet<Class<? extends Fragment>>> fragmentsMap = new HashMap<>();
     Set<Label> labelsWithErrors = new HashSet<>();
-    for (Dependency key : keys) {
-      if (key.hasExplicitConfiguration()) {
-        builder.put(key, key.getConfiguration());
-      } else if (useUntrimmedConfigs(fromOptions)) {
+    for (DependencyKey key : keys) {
+      if (useUntrimmedConfigs(fromOptions)) {
         fragmentsMap.put(key.getLabel(), allFragments);
       } else {
         depsToEvaluate.add(key);
@@ -295,7 +291,7 @@
     if (env.valuesMissing()) {
       return null;
     }
-    for (Dependency key : keys) {
+    for (DependencyKey key : keys) {
       if (!depsToEvaluate.contains(key)) {
         // No fragments to compute here.
       } else {
@@ -324,8 +320,8 @@
     }
 
     final List<SkyKey> configSkyKeys = new ArrayList<>();
-    for (Dependency key : keys) {
-      if (labelsWithErrors.contains(key.getLabel()) || key.hasExplicitConfiguration()) {
+    for (DependencyKey key : keys) {
+      if (labelsWithErrors.contains(key.getLabel())) {
         continue;
       }
       if (key.getTransition() == NullTransition.INSTANCE) {
@@ -358,8 +354,8 @@
     if (env.valuesMissing()) {
       return null;
     }
-    for (Dependency key : keys) {
-      if (labelsWithErrors.contains(key.getLabel()) || key.hasExplicitConfiguration()) {
+    for (DependencyKey key : keys) {
+      if (labelsWithErrors.contains(key.getLabel())) {
         continue;
       }
       if (key.getTransition() == NullTransition.INSTANCE) {
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 b1df35b..20fa6e1 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
@@ -65,7 +65,6 @@
 import com.google.devtools.build.lib.actions.ResourceManager;
 import com.google.devtools.build.lib.actions.UserExecException;
 import com.google.devtools.build.lib.analysis.AnalysisProtos.ActionGraphContainer;
-import com.google.devtools.build.lib.analysis.AspectCollection;
 import com.google.devtools.build.lib.analysis.AspectValue;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfigurationsCollector;
@@ -74,6 +73,7 @@
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.Dependency;
+import com.google.devtools.build.lib.analysis.DependencyKey;
 import com.google.devtools.build.lib.analysis.DuplicateException;
 import com.google.devtools.build.lib.analysis.PlatformOptions;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
@@ -1697,7 +1697,7 @@
   public ImmutableList<ConfiguredTargetAndData> getConfiguredTargetsForTesting(
       ExtendedEventHandler eventHandler,
       BuildConfiguration originalConfig,
-      Iterable<Dependency> keys)
+      Iterable<DependencyKey> keys)
       throws TransitionException, InvalidConfigurationException, InterruptedException {
     return getConfiguredTargetMapForTesting(eventHandler, originalConfig, keys).values().asList();
   }
@@ -1714,7 +1714,7 @@
   public ImmutableList<ConfiguredTargetAndData> getConfiguredTargetsForTesting(
       ExtendedEventHandler eventHandler,
       BuildConfigurationValue.Key originalConfig,
-      Iterable<Dependency> keys)
+      Iterable<DependencyKey> keys)
       throws InvalidConfigurationException, InterruptedException {
     return getConfiguredTargetMapForTesting(eventHandler, originalConfig, keys).values().asList();
   }
@@ -1729,10 +1729,10 @@
    * returned list.
    */
   @ThreadSafety.ThreadSafe
-  public ImmutableMultimap<Dependency, ConfiguredTargetAndData> getConfiguredTargetMapForTesting(
+  public ImmutableMultimap<DependencyKey, ConfiguredTargetAndData> getConfiguredTargetMapForTesting(
       ExtendedEventHandler eventHandler,
       BuildConfigurationValue.Key originalConfig,
-      Iterable<Dependency> keys)
+      Iterable<DependencyKey> keys)
       throws InvalidConfigurationException, InterruptedException {
     return getConfiguredTargetMapForTesting(
         eventHandler, getConfiguration(eventHandler, originalConfig), keys);
@@ -1748,26 +1748,27 @@
    * returned list except...
    */
   @ThreadSafety.ThreadSafe
-  private ImmutableMultimap<Dependency, ConfiguredTargetAndData> getConfiguredTargetMapForTesting(
-      ExtendedEventHandler eventHandler,
-      BuildConfiguration originalConfig,
-      Iterable<Dependency> keys)
-      throws InvalidConfigurationException, InterruptedException {
+  private ImmutableMultimap<DependencyKey, ConfiguredTargetAndData>
+      getConfiguredTargetMapForTesting(
+          ExtendedEventHandler eventHandler,
+          BuildConfiguration originalConfig,
+          Iterable<DependencyKey> keys)
+          throws InvalidConfigurationException, InterruptedException {
     checkActive();
 
-    Multimap<Dependency, BuildConfiguration> configs;
+    Multimap<DependencyKey, BuildConfiguration> configs;
     if (originalConfig != null) {
       configs =
           getConfigurations(eventHandler, originalConfig.getOptions(), keys).getConfigurationMap();
     } else {
-      configs = ArrayListMultimap.<Dependency, BuildConfiguration>create();
-      for (Dependency key : keys) {
+      configs = ArrayListMultimap.create();
+      for (DependencyKey key : keys) {
         configs.put(key, null);
       }
     }
 
     final List<SkyKey> skyKeys = new ArrayList<>();
-    for (Dependency key : keys) {
+    for (DependencyKey key : keys) {
       if (!configs.containsKey(key)) {
         // If we couldn't compute a configuration for this target, the target was in error (e.g.
         // it couldn't be loaded). Exclude it from the results.
@@ -1786,17 +1787,17 @@
 
     EvaluationResult<SkyValue> result = evaluateSkyKeys(eventHandler, skyKeys);
 
-    ImmutableMultimap.Builder<Dependency, ConfiguredTargetAndData> cts =
+    ImmutableMultimap.Builder<DependencyKey, ConfiguredTargetAndData> cts =
         ImmutableMultimap.builder();
 
     // Logic copied from ConfiguredTargetFunction#computeDependencies.
     Set<SkyKey> aliasPackagesToFetch = new HashSet<>();
-    List<Dependency> aliasKeysToRedo = new ArrayList<>();
+    List<DependencyKey> aliasKeysToRedo = new ArrayList<>();
     EvaluationResult<SkyValue> aliasPackageValues = null;
-    Iterable<Dependency> keysToProcess = keys;
+    Iterable<DependencyKey> keysToProcess = keys;
     for (int i = 0; i < 2; i++) {
       DependentNodeLoop:
-      for (Dependency key : keysToProcess) {
+      for (DependencyKey key : keysToProcess) {
         if (!configs.containsKey(key)) {
           // If we couldn't compute a configuration for this target, the target was in error (e.g.
           // it couldn't be loaded). Exclude it from the results.
@@ -1996,8 +1997,8 @@
 
   /**
    * Retrieves the configurations needed for the given deps. If {@link
-   * CoreOptions#trimConfigurations()} is true, trims their fragments to only those needed by their
-   * transitive closures. Else unconditionally includes all fragments.
+   * BuildConfiguration#trimConfigurations()} is true, trims their fragments to only those needed by
+   * their transitive closures. Else unconditionally includes all fragments.
    *
    * <p>Skips targets with loading phase errors.
    */
@@ -2005,10 +2006,10 @@
   // TODO(ulfjack): Remove this legacy method after switching to the Skyframe-based implementation.
   @Override
   public ConfigurationsResult getConfigurations(
-      ExtendedEventHandler eventHandler, BuildOptions fromOptions, Iterable<Dependency> keys)
+      ExtendedEventHandler eventHandler, BuildOptions fromOptions, Iterable<DependencyKey> keys)
       throws InvalidConfigurationException {
     ConfigurationsResult.Builder builder = ConfigurationsResult.newBuilder();
-    Set<Dependency> depsToEvaluate = new HashSet<>();
+    Set<DependencyKey> depsToEvaluate = new HashSet<>();
 
     ImmutableSortedSet<Class<? extends Fragment>> allFragments = null;
     if (useUntrimmedConfigs(fromOptions)) {
@@ -2019,10 +2020,8 @@
     final List<SkyKey> transitiveFragmentSkyKeys = new ArrayList<>();
     Map<Label, ImmutableSortedSet<Class<? extends Fragment>>> fragmentsMap = new HashMap<>();
     Set<Label> labelsWithErrors = new HashSet<>();
-    for (Dependency key : keys) {
-      if (key.hasExplicitConfiguration()) {
-        builder.put(key, key.getConfiguration());
-      } else if (useUntrimmedConfigs(fromOptions)) {
+    for (DependencyKey key : keys) {
+      if (useUntrimmedConfigs(fromOptions)) {
         fragmentsMap.put(key.getLabel(), allFragments);
       } else {
         depsToEvaluate.add(key);
@@ -2034,7 +2033,7 @@
     for (Map.Entry<SkyKey, ErrorInfo> entry : fragmentsResult.errorMap().entrySet()) {
       reportCycles(eventHandler, entry.getValue().getCycleInfo(), entry.getKey());
     }
-    for (Dependency key : keys) {
+    for (DependencyKey key : keys) {
       if (!depsToEvaluate.contains(key)) {
         // No fragments to compute here.
       } else if (fragmentsResult.getError(TransitiveTargetKey.of(key.getLabel())) != null) {
@@ -2055,8 +2054,8 @@
 
     // Now get the configurations.
     final List<SkyKey> configSkyKeys = new ArrayList<>();
-    for (Dependency key : keys) {
-      if (labelsWithErrors.contains(key.getLabel()) || key.hasExplicitConfiguration()) {
+    for (DependencyKey key : keys) {
+      if (labelsWithErrors.contains(key.getLabel())) {
         continue;
       }
       ImmutableSortedSet<Class<? extends Fragment>> depFragments = fragmentsMap.get(key.getLabel());
@@ -2085,8 +2084,8 @@
     }
     EvaluationResult<SkyValue> configsResult =
         evaluateSkyKeys(eventHandler, configSkyKeys, /*keepGoing=*/ true);
-    for (Dependency key : keys) {
-      if (labelsWithErrors.contains(key.getLabel()) || key.hasExplicitConfiguration()) {
+    for (DependencyKey key : keys) {
+      if (labelsWithErrors.contains(key.getLabel())) {
         continue;
       }
       ImmutableSortedSet<Class<? extends Fragment>> depFragments = fragmentsMap.get(key.getLabel());
@@ -2310,15 +2309,14 @@
       BuildConfiguration configuration,
       ConfigurationTransition transition)
       throws TransitionException, InvalidConfigurationException, InterruptedException {
+
+    ConfigurationTransition transition1 =
+        configuration == null ? NullTransition.INSTANCE : transition;
+    DependencyKey dependencyKey =
+        DependencyKey.builder().setLabel(label).setTransition(transition1).build();
     return Iterables.getFirst(
         getConfiguredTargetsForTesting(
-            eventHandler,
-            configuration,
-            ImmutableList.of(
-                configuration == null
-                    ? Dependency.withNullConfiguration(label)
-                    : Dependency.withTransitionAndAspects(
-                        label, transition, AspectCollection.EMPTY))),
+            eventHandler, configuration, ImmutableList.of(dependencyKey)),
         null);
   }