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 528ed0b..eed892c 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
@@ -35,7 +35,6 @@
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.PackageRootResolver;
 import com.google.devtools.build.lib.actions.Root;
-import com.google.devtools.build.lib.analysis.DependencyResolver.Dependency;
 import com.google.devtools.build.lib.analysis.ExtraActionArtifactsProvider.ExtraArtifactSet;
 import com.google.devtools.build.lib.analysis.config.BinTools;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -762,7 +761,10 @@
         skyframeExecutor.getConfiguredTargets(
             eventHandler,
             configuration,
-            ImmutableList.of(new Dependency(label, configuration)),
+            ImmutableList.of(
+                configuration != null
+                    ? Dependency.withConfiguration(label, configuration)
+                    : Dependency.withNullConfiguration(label)),
             true),
         null);
   }
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
new file mode 100644
index 0000000..46fcc029
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Dependency.java
@@ -0,0 +1,350 @@
+// Copyright 2014 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.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.packages.Aspect;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.util.Preconditions;
+
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+/**
+ * A dependency of a configured target through a label.
+ *
+ * <p>For static 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.
+ *
+ * <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. A set of aspects is also
+ * included; the caller must also construct configurations for each of these.
+ *
+ * <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
+ * configured targets have (we cannot do that here because the configured targets are not
+ * available yet). No error or warning is reported in this case, because it is expected that rules
+ * sometimes over-approximate the providers they supply in their definitions.
+ */
+public abstract class Dependency {
+
+  /**
+   * Creates a new {@link Dependency} with a null configuration, suitable for edges with no
+   * configuration in static configuration builds.
+   */
+  public static Dependency withNullConfiguration(Label label) {
+    return new NullConfigurationDependency(label);
+  }
+
+  /**
+   * Creates a new {@link Dependency} with the given configuration, suitable for static
+   * configuration builds.
+   *
+   * <p>The configuration must not be {@code null}.
+   *
+   * <p>A {@link Dependency} created this way will have no associated aspects.
+   */
+  public static Dependency withConfiguration(Label label, BuildConfiguration configuration) {
+    return new StaticConfigurationDependency(
+        label, configuration, ImmutableMap.<Aspect, BuildConfiguration>of());
+  }
+
+  /**
+   * Creates a new {@link Dependency} with the given configuration and aspects, suitable for
+   * static configuration builds. The configuration is also applied to all aspects.
+   *
+   * <p>The configuration and aspects must not be {@code null}.
+   */
+  public static Dependency withConfigurationAndAspects(
+      Label label, BuildConfiguration configuration, Set<Aspect> aspects) {
+    ImmutableMap.Builder<Aspect, BuildConfiguration> aspectBuilder = new ImmutableMap.Builder<>();
+    for (Aspect aspect : aspects) {
+      aspectBuilder.put(aspect, configuration);
+    }
+    return new StaticConfigurationDependency(label, configuration, aspectBuilder.build());
+  }
+
+  /**
+   * Creates a new {@link Dependency} with the given configuration and aspects, suitable for
+   * storing the output of a dynamic configuration trimming step. The aspects each have their own
+   * configuration.
+   *
+   * <p>The aspects and configurations must not be {@code null}.
+   */
+  public static Dependency withConfiguredAspects(
+      Label label, BuildConfiguration configuration,
+      Map<Aspect, BuildConfiguration> aspectConfigurations) {
+    return new StaticConfigurationDependency(
+        label, configuration, ImmutableMap.copyOf(aspectConfigurations));
+  }
+
+  /**
+   * Creates a new {@link Dependency} with the given transition and aspects, suitable for dynamic
+   * configuration builds.
+   */
+  public static Dependency withTransitionAndAspects(
+      Label label, Attribute.Transition transition, Set<Aspect> aspects) {
+    return new DynamicConfigurationDependency(label, transition, ImmutableSet.copyOf(aspects));
+  }
+
+  protected final Label label;
+
+  /**
+   * Only the implementations below should extend this class. Use the factory methods above to
+   * create new Dependencies.
+   */
+  private Dependency(Label label) {
+    this.label = Preconditions.checkNotNull(label);
+  }
+
+  /** Returns the label of the target this dependency points to. */
+  public Label getLabel() {
+    return label;
+  }
+
+  /**
+   * Returns true if this dependency specifies a static configuration, false if it specifies
+   * a dynamic transition.
+   */
+  public abstract boolean hasStaticConfiguration();
+
+  /**
+   * Returns the static configuration for the target this dependency points to.
+   *
+   * @throws IllegalStateException if {@link #hasStaticConfiguration} returns false.
+   */
+  @Nullable
+  public abstract BuildConfiguration getConfiguration();
+
+  /**
+   * Returns the dynamic transition to be applied to reach the target this dependency points to.
+   *
+   * @throws IllegalStateException if {@link #hasStaticConfiguration} returns true.
+   */
+  public abstract Attribute.Transition getTransition();
+
+  /**
+   * Returns the set of aspects which should be evaluated and combined with the configured target
+   * pointed to by this dependency.
+   *
+   * @see #getAspectConfigurations()
+   */
+  public abstract ImmutableSet<Aspect> getAspects();
+
+  /**
+   * Returns the mapping from aspects to the static configurations they should be evaluated with.
+   *
+   * <p>The {@link Map#keySet()} of this map is equal to that returned by {@link #getAspects()}.
+   *
+   * @throws IllegalStateException if {@link #hasStaticConfiguration()} returns false.
+   */
+  public abstract ImmutableMap<Aspect, BuildConfiguration> getAspectConfigurations();
+
+  /**
+   * Implementation of a dependency with no configuration, suitable for static configuration
+   * builds of edges to source files or e.g. for visibility.
+   */
+  private static final class NullConfigurationDependency extends Dependency {
+    public NullConfigurationDependency(Label label) {
+      super(label);
+    }
+
+    @Override
+    public boolean hasStaticConfiguration() {
+      return true;
+    }
+
+    @Nullable
+    @Override
+    public BuildConfiguration getConfiguration() {
+      return null;
+    }
+
+    @Override
+    public Attribute.Transition getTransition() {
+      throw new IllegalStateException(
+          "A dependency with a static configuration does not have a transition.");
+    }
+
+    @Override
+    public ImmutableSet<Aspect> getAspects() {
+      return ImmutableSet.of();
+    }
+
+    @Override
+    public ImmutableMap<Aspect, BuildConfiguration> getAspectConfigurations() {
+      return ImmutableMap.of();
+    }
+
+    @Override
+    public int hashCode() {
+      return label.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      if (!(other instanceof NullConfigurationDependency)) {
+        return false;
+      }
+      NullConfigurationDependency otherDep = (NullConfigurationDependency) other;
+      return label.equals(otherDep.label);
+    }
+
+    @Override
+    public String toString() {
+      return String.format("NullConfigurationDependency{label=%s}", label);
+    }
+  }
+
+  /**
+   * Implementation of a dependency with static configurations, suitable for static configuration
+   * builds.
+   */
+  private static final class StaticConfigurationDependency extends Dependency {
+    private final BuildConfiguration configuration;
+    private final ImmutableMap<Aspect, BuildConfiguration> aspectConfigurations;
+
+    public StaticConfigurationDependency(
+        Label label, BuildConfiguration configuration,
+        ImmutableMap<Aspect, BuildConfiguration> aspects) {
+      super(label);
+      this.configuration = Preconditions.checkNotNull(configuration);
+      this.aspectConfigurations = Preconditions.checkNotNull(aspects);
+    }
+
+    @Override
+    public boolean hasStaticConfiguration() {
+      return true;
+    }
+
+    @Override
+    public BuildConfiguration getConfiguration() {
+      return configuration;
+    }
+
+    @Override
+    public Attribute.Transition getTransition() {
+      throw new IllegalStateException(
+          "A dependency with a static configuration does not have a transition.");
+    }
+
+    @Override
+    public ImmutableSet<Aspect> getAspects() {
+      return aspectConfigurations.keySet();
+    }
+
+    @Override
+    public ImmutableMap<Aspect, BuildConfiguration> getAspectConfigurations() {
+      return aspectConfigurations;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(label, configuration, aspectConfigurations);
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      if (!(other instanceof StaticConfigurationDependency)) {
+        return false;
+      }
+      StaticConfigurationDependency otherDep = (StaticConfigurationDependency) other;
+      return label.equals(otherDep.label)
+          && configuration.equals(otherDep.configuration)
+          && aspectConfigurations.equals(otherDep.aspectConfigurations);
+    }
+
+    @Override
+    public String toString() {
+      return String.format(
+          "StaticConfigurationDependency{label=%s, configuration=%s, aspectConfigurations=%s}",
+          label, configuration, aspectConfigurations);
+    }
+  }
+
+  /**
+   * Implementation of a dependency with a given configuration transition, suitable for dynamic
+   * configuration builds.
+   */
+  private static final class DynamicConfigurationDependency extends Dependency {
+    private final Attribute.Transition transition;
+    private final ImmutableSet<Aspect> aspects;
+
+    public DynamicConfigurationDependency(
+        Label label, Attribute.Transition transition, ImmutableSet<Aspect> aspects) {
+      super(label);
+      this.transition = Preconditions.checkNotNull(transition);
+      this.aspects = Preconditions.checkNotNull(aspects);
+    }
+
+    @Override
+    public boolean hasStaticConfiguration() {
+      return false;
+    }
+
+    @Override
+    public BuildConfiguration getConfiguration() {
+      throw new IllegalStateException(
+          "A dependency with a dynamic configuration transition does not have a configuration.");
+    }
+
+    @Override
+    public Attribute.Transition getTransition() {
+      return transition;
+    }
+
+    @Override
+    public ImmutableSet<Aspect> getAspects() {
+      return aspects;
+    }
+
+    @Override
+    public ImmutableMap<Aspect, BuildConfiguration> getAspectConfigurations() {
+      throw new IllegalStateException(
+          "A dependency with a dynamic configuration transition does not have aspect "
+          + "configurations.");
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(label, transition, aspects);
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      if (!(other instanceof DynamicConfigurationDependency)) {
+        return false;
+      }
+      DynamicConfigurationDependency otherDep = (DynamicConfigurationDependency) other;
+      return label.equals(otherDep.label)
+          && transition.equals(otherDep.transition)
+          && aspects.equals(otherDep.aspects);
+    }
+
+    @Override
+    public String toString() {
+      return String.format(
+          "DynamicConfigurationDependency{label=%s, transition=%s, aspects=%s}",
+          label, transition, aspects);
+    }
+  }
+}
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 19d8859..17d9d23 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
@@ -13,8 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.analysis;
 
-import com.google.common.base.Function;
-import com.google.common.base.Verify;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -40,7 +38,6 @@
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.Target;
-import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Type;
@@ -51,7 +48,6 @@
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
-import java.util.Objects;
 import java.util.Set;
 import java.util.regex.Pattern;
 import java.util.regex.PatternSyntaxException;
@@ -64,134 +60,6 @@
  * <p>Includes logic to derive the right configurations depending on transition type.
  */
 public abstract class DependencyResolver {
-  /**
-   * A dependency of a configured target through a label.
-   *
-   * <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
-   * configured targets have (we cannot do that here because the configured targets are not
-   * available yet). No error or warning is reported in this case, because it is expected that rules
-   * sometimes over-approximate the providers they supply in their definitions.
-   */
-  public static final class Dependency {
-
-    /**
-     * Returns the {@link ConfiguredTargetKey} for a direct dependency.
-     *
-     * <p>Essentially the same information as {@link Dependency} minus the aspects.
-     */
-    public static final Function<Dependency, ConfiguredTargetKey>
-        TO_CONFIGURED_TARGET_KEY = new Function<Dependency, ConfiguredTargetKey>() {
-          @Override
-          public ConfiguredTargetKey apply(Dependency input) {
-            return new ConfiguredTargetKey(input.getLabel(), input.getConfiguration());
-          }
-        };
-
-    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<Aspect> aspects;
-
-    /**
-     * Constructs a Dependency with a given configuration (suitable for static configuration
-     * builds).
-     */
-    public Dependency(
-        Label label, @Nullable BuildConfiguration configuration, ImmutableSet<Aspect> 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.<Aspect>of());
-    }
-
-    /**
-     * Constructs a Dependency with a given transition (suitable for dynamic configuration builds).
-     */
-    public Dependency(Label label, Attribute.Transition transition, ImmutableSet<Aspect> 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<Aspect> getAspects() {
-      return aspects;
-    }
-
-    @Override
-    public int hashCode() {
-      return Objects.hash(label, configuration, aspects);
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof Dependency)) {
-        return false;
-      }
-      Dependency otherDep = (Dependency) other;
-      return label.equals(otherDep.label)
-          && (configuration == otherDep.configuration
-              || (configuration != null && configuration.equals(otherDep.configuration)))
-          && aspects.equals(otherDep.aspects);
-    }
-
-    @Override
-    public String toString() {
-      return String.format(
-          "Dependency{label=%s, configuration=%s, aspects=%s}", label, configuration, aspects);
-    }
-  }
 
   protected DependencyResolver() {
   }
@@ -228,7 +96,7 @@
       Preconditions.checkNotNull(config);
       visitTargetVisibility(node, outgoingEdges.get(null));
       Rule rule = ((OutputFile) target).getGeneratingRule();
-      outgoingEdges.put(null, new Dependency(rule.getLabel(), config));
+      outgoingEdges.put(null, Dependency.withConfiguration(rule.getLabel(), config));
     } else if (target instanceof InputFile) {
       visitTargetVisibility(node, outgoingEdges.get(null));
     } else if (target instanceof EnvironmentGroup) {
@@ -554,7 +422,7 @@
           continue;
         }
 
-        outgoingEdges.add(new Dependency(label, null));
+        outgoingEdges.add(Dependency.withNullConfiguration(label));
       } catch (NoSuchThingException e) {
         // Don't visit targets that don't exist (--keep_going)
       }
@@ -676,7 +544,7 @@
         }
 
         // Visibility always has null configuration
-        outgoingEdges.add(new Dependency(label, null));
+        outgoingEdges.add(Dependency.withNullConfiguration(label));
       } catch (NoSuchThingException e) {
         // Don't visit targets that don't exist (--keep_going)
       }
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 cb094c3..7f2d7ff 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
@@ -35,7 +35,7 @@
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
-import com.google.devtools.build.lib.analysis.DependencyResolver;
+import com.google.devtools.build.lib.analysis.Dependency;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.ViewCreationFailedException;
 import com.google.devtools.build.lib.analysis.config.BuildConfigurationCollection.Transitions;
@@ -1502,17 +1502,16 @@
     Transitions getCurrentTransitions();
 
     /**
-     * Populates a {@link com.google.devtools.build.lib.analysis.DependencyResolver.Dependency}
+     * Populates a {@link com.google.devtools.build.lib.analysis.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<Aspect> aspects);
+    Iterable<Dependency> getDependencies(Label label, ImmutableSet<Aspect> aspects);
   }
 
   /**
    * Transition applier for static configurations. This implementation populates
-   * {@link com.google.devtools.build.lib.analysis.DependencyResolver.Dependency} objects with
+   * {@link com.google.devtools.build.lib.analysis.Dependency} objects with
    * actual configurations.
    *
    * <p>Does not support split transitions (see {@link SplittableTransitionApplier}).
@@ -1580,16 +1579,17 @@
     }
 
     @Override
-    public Iterable<DependencyResolver.Dependency> getDependencies(
-        Label label, ImmutableSet<Aspect> aspects) {
+    public Iterable<Dependency> getDependencies(Label label, ImmutableSet<Aspect> aspects) {
       return ImmutableList.of(
-          new DependencyResolver.Dependency(label, currentConfiguration, aspects));
+          currentConfiguration != null
+              ? Dependency.withConfigurationAndAspects(label, currentConfiguration, aspects)
+              : Dependency.withNullConfiguration(label));
     }
   }
 
   /**
    * Transition applier for dynamic configurations. This implementation populates
-   * {@link com.google.devtools.build.lib.analysis.DependencyResolver.Dependency} objects with
+   * {@link com.google.devtools.build.lib.analysis.Dependency} objects with
    * transition definitions that the caller subsequently creates configurations out of.
    *
    * <p>Does not support split transitions (see {@link SplittableTransitionApplier}).
@@ -1681,9 +1681,10 @@
     }
 
     @Override
-    public Iterable<DependencyResolver.Dependency> getDependencies(
+    public Iterable<Dependency> getDependencies(
         Label label, ImmutableSet<Aspect> aspects) {
-      return ImmutableList.of(new DependencyResolver.Dependency(label, transition, aspects));
+      return ImmutableList.of(
+          Dependency.withTransitionAndAspects(label, transition, aspects));
     }
   }
 
@@ -1748,9 +1749,8 @@
 
 
     @Override
-    public Iterable<DependencyResolver.Dependency> getDependencies(
-        Label label, ImmutableSet<Aspect> aspects) {
-      ImmutableList.Builder<DependencyResolver.Dependency> builder = ImmutableList.builder();
+    public Iterable<Dependency> getDependencies(Label label, ImmutableSet<Aspect> aspects) {
+      ImmutableList.Builder<Dependency> builder = ImmutableList.builder();
       for (TransitionApplier applier : appliers) {
         builder.addAll(applier.getDependencies(label, aspects));
       }
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 8b55b1c..f4a7446 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
@@ -30,7 +30,7 @@
 import com.google.devtools.build.lib.analysis.CachingAnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.DependencyResolver.Dependency;
+import com.google.devtools.build.lib.analysis.Dependency;
 import com.google.devtools.build.lib.analysis.LabelAndConfiguration;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
@@ -401,12 +401,11 @@
       if (dep.hasStaticConfiguration()) {
         // Certain targets (like output files) trivially pass their configurations to their deps.
         // So no need to transform them in any way.
-        putOnlyEntry(trimmedDeps, attributeAndLabel,
-            new Dependency(dep.getLabel(), dep.getConfiguration(), dep.getAspects()));
+        putOnlyEntry(trimmedDeps, attributeAndLabel, dep);
         continue;
       } else if (dep.getTransition() == Attribute.ConfigurationTransition.NULL) {
-        putOnlyEntry(trimmedDeps, attributeAndLabel,
-            new Dependency(dep.getLabel(), (BuildConfiguration) null, dep.getAspects()));
+        putOnlyEntry(
+            trimmedDeps, attributeAndLabel, Dependency.withNullConfiguration(dep.getLabel()));
         continue;
       }
 
@@ -428,8 +427,11 @@
       if (sameFragments) {
         if (transition == Attribute.ConfigurationTransition.NONE) {
           // The dep uses the same exact configuration.
-          putOnlyEntry(trimmedDeps, attributeAndLabel,
-              new Dependency(dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects()));
+          putOnlyEntry(
+              trimmedDeps,
+              attributeAndLabel,
+              Dependency.withConfigurationAndAspects(
+                  dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects()));
           continue;
         } else if (transition == HostTransition.INSTANCE) {
           // The current rule's host configuration can also be used for the dep. We short-circuit
@@ -437,8 +439,11 @@
           // uniquely frequent. It's possible, e.g., for every node in the configured target graph
           // to incur multiple host transitions. So we aggressively optimize to avoid hurting
           // analysis time.
-          putOnlyEntry(trimmedDeps, attributeAndLabel,
-              new Dependency(dep.getLabel(), hostConfiguration, dep.getAspects()));
+          putOnlyEntry(
+              trimmedDeps,
+              attributeAndLabel,
+              Dependency.withConfigurationAndAspects(
+                  dep.getLabel(), hostConfiguration, dep.getAspects()));
           continue;
         }
       }
@@ -465,8 +470,11 @@
       // If the transition doesn't change the configuration, trivially re-use the original
       // configuration.
       if (sameFragments && toOptions.equals(ctgOptions)) {
-        putOnlyEntry(trimmedDeps, attributeAndLabel,
-            new Dependency(dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects()));
+        putOnlyEntry(
+            trimmedDeps,
+            attributeAndLabel,
+            Dependency.withConfigurationAndAspects(
+                dep.getLabel(), ctgValue.getConfiguration(), dep.getAspects()));
         continue;
       }
 
@@ -490,7 +498,9 @@
         for (Map.Entry<Attribute, Dependency> info : keysToEntries.get(key)) {
           Dependency originalDep = info.getValue();
           putOnlyEntry(trimmedDeps, new AttributeAndLabel(info.getKey(), originalDep.getLabel()),
-              new Dependency(originalDep.getLabel(), trimmedConfig.getConfiguration(),
+              Dependency.withConfigurationAndAspects(
+                  originalDep.getLabel(),
+                  trimmedConfig.getConfiguration(),
                   originalDep.getAspects()));
         }
       }
@@ -665,7 +675,8 @@
     if (targetConfig != null && targetConfig.useDynamicConfigurations()) {
       ImmutableList.Builder<Dependency> staticConfigs = ImmutableList.builder();
       for (Dependency dep : configValueNames) {
-        staticConfigs.add(new Dependency(dep.getLabel(), targetConfig, dep.getAspects()));
+        staticConfigs.add(
+            Dependency.withConfigurationAndAspects(dep.getLabel(), targetConfig, dep.getAspects()));
       }
       configValueNames = staticConfigs.build();
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
index c5a54dc..284491d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java
@@ -20,7 +20,7 @@
 import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.DependencyResolver.Dependency;
+import com.google.devtools.build.lib.analysis.Dependency;
 import com.google.devtools.build.lib.analysis.LabelAndConfiguration;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
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 7cddb5a..d7eda03 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
@@ -53,7 +53,7 @@
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.DependencyResolver.Dependency;
+import com.google.devtools.build.lib.analysis.Dependency;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
@@ -1312,7 +1312,10 @@
         getConfiguredTargets(
             eventHandler,
             configuration,
-            ImmutableList.of(new Dependency(label, configuration)),
+            ImmutableList.of(
+                configuration != null
+                    ? Dependency.withConfiguration(label, configuration)
+                    : Dependency.withNullConfiguration(label)),
             true),
         null);
   }