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 0fa4dad..b5e6167 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BUILD
@@ -704,6 +704,7 @@
         ":config/transitions/configuration_transition",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
         "//src/main/java/com/google/devtools/build/lib/packages",
+        "//third_party:auto_value",
         "//third_party:guava",
         "//third_party:jsr305",
     ],
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 f2a7e56..abfa5ed 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
@@ -13,19 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.lib.analysis;
 
+import com.google.auto.value.AutoValue;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.transitions.ConfigurationTransition;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.AspectDescriptor;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-import java.util.Objects;
 import javax.annotation.Nullable;
 
 /**
@@ -42,23 +36,16 @@
  * 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.
  */
+@AutoValue
 public abstract class Dependency {
   /** Builder to assist in creating dependency instances. */
-  public static class Builder {
-    private Label label;
-    private BuildConfiguration configuration;
-    private AspectCollection aspects = AspectCollection.EMPTY;
-    private List<String> transitionKeys = new ArrayList<>();
+  @AutoValue.Builder
+  public abstract static class Builder {
+    /** Sets the label of the target this dependency points to. */
+    public abstract Builder setLabel(Label label);
 
-    public Builder setLabel(Label label) {
-      this.label = Preconditions.checkNotNull(label);
-      return this;
-    }
-
-    public Builder setConfiguration(BuildConfiguration configuration) {
-      this.configuration = configuration;
-      return this;
-    }
+    /** Sets the configuration intended for this dependency. */
+    public abstract Builder setConfiguration(BuildConfiguration configuration);
 
     /** Explicitly set the configuration for this dependency to null. */
     public Builder withNullConfiguration() {
@@ -66,65 +53,42 @@
     }
 
     /** Add aspects to this Dependency. The same configuration is applied to all aspects. */
-    public Builder setAspects(AspectCollection aspects) {
-      this.aspects = aspects;
-      return this;
+    public abstract Builder setAspects(AspectCollection aspects);
+
+    /** Sets the keys of a configuration transition. */
+    public Builder setTransitionKey(String key) {
+      return setTransitionKeys(ImmutableList.of(key));
     }
 
-    public Builder addTransitionKey(String key) {
-      this.transitionKeys.add(key);
-      return this;
-    }
+    /** Sets the keys of a configuration transition. */
+    public abstract Builder setTransitionKeys(ImmutableList<String> keys);
 
-    public Builder addTransitionKeys(Collection<String> keys) {
-      this.transitionKeys = new ArrayList<>(keys);
-      return this;
-    }
+    // Not public.
+    abstract Dependency autoBuild();
 
     /** Returns the full Dependency instance. */
     public Dependency build() {
-      if (configuration == null) {
-        Preconditions.checkState(aspects.equals(AspectCollection.EMPTY));
-        return new NullConfigurationDependency(label, ImmutableList.copyOf(transitionKeys));
+      Dependency dependency = autoBuild();
+      if (dependency.getConfiguration() == null) {
+        Preconditions.checkState(
+            dependency.getAspects().equals(AspectCollection.EMPTY),
+            "Dependency with null Configuration cannot have aspects");
       }
-
-      // Use the target configuration for all aspects with none of their own.
-      Map<AspectDescriptor, BuildConfiguration> aspectConfigurations = new HashMap<>();
-      for (AspectDescriptor aspect : aspects.getAllAspects()) {
-        aspectConfigurations.put(aspect, configuration);
-      }
-      return new ExplicitConfigurationDependency(
-          label,
-          configuration,
-          aspects,
-          ImmutableMap.copyOf(aspectConfigurations),
-          ImmutableList.copyOf(transitionKeys));
+      return dependency;
     }
   }
 
   /** Returns a new {@link Builder} to create {@link Dependency} instances. */
   public static Builder builder() {
-    return new Builder();
-  }
-
-  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);
+    return new AutoValue_Dependency.Builder()
+        .setAspects(AspectCollection.EMPTY)
+        .setTransitionKeys(ImmutableList.of());
   }
 
   /** Returns the label of the target this dependency points to. */
-  public Label getLabel() {
-    return label;
-  }
+  public abstract Label getLabel();
 
-  /**
-   * Returns the explicit configuration intended for this dependency.
-   */
+  /** Returns the explicit configuration intended for this dependency. */
   @Nullable
   public abstract BuildConfiguration getConfiguration();
 
@@ -137,136 +101,19 @@
   public abstract AspectCollection getAspects();
 
   /** Returns the configuration an aspect should be evaluated with. */
-  public abstract BuildConfiguration getAspectConfiguration(AspectDescriptor aspect);
+  @Nullable
+  public BuildConfiguration getAspectConfiguration(AspectDescriptor aspect) {
+    return getConfiguration();
+  }
 
   /**
-   * Returns the keys of a configuration transition, if exist, associated with this dependency. See
-   * {@link ConfigurationTransition#apply} for more details. Normally, this returns an empty list,
-   * when there was no configuration transition in effect, or one with a single entry, when there
-   * was a specific configuration transition result that led to this. It may also return a list with
-   * 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.
+   * Returns the keys of a configuration transition, if any exist, associated with this dependency.
+   * See {@link ConfigurationTransition#apply} for more details. Normally, this returns an empty
+   * list, when there was no configuration transition in effect, or one with a single entry, when
+   * there was a specific configuration transition result that led to this. It may also return a
+   * list with 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.
    */
   public abstract ImmutableList<String> getTransitionKeys();
-
-  /**
-   * Implementation of a dependency with no configuration, suitable for, e.g., source files or
-   * visibility.
-   */
-  private static final class NullConfigurationDependency extends Dependency {
-    private final ImmutableList<String> transitionKeys;
-
-    public NullConfigurationDependency(Label label, ImmutableList<String> transitionKeys) {
-      super(label);
-      this.transitionKeys = Preconditions.checkNotNull(transitionKeys);
-    }
-
-    @Nullable
-    @Override
-    public BuildConfiguration getConfiguration() {
-      return null;
-    }
-
-    @Override
-    public AspectCollection getAspects() {
-      return AspectCollection.EMPTY;
-    }
-
-    @Override
-    public BuildConfiguration getAspectConfiguration(AspectDescriptor aspect) {
-      return null;
-    }
-
-    @Override
-    public ImmutableList<String> getTransitionKeys() {
-      return transitionKeys;
-    }
-
-    @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 an explicitly set configuration.
-   */
-  private static final class ExplicitConfigurationDependency extends Dependency {
-    private final BuildConfiguration configuration;
-    private final AspectCollection aspects;
-    private final ImmutableMap<AspectDescriptor, BuildConfiguration> aspectConfigurations;
-    private final ImmutableList<String> transitionKeys;
-
-    public ExplicitConfigurationDependency(
-        Label label,
-        BuildConfiguration configuration,
-        AspectCollection aspects,
-        ImmutableMap<AspectDescriptor, BuildConfiguration> aspectConfigurations,
-        ImmutableList<String> transitionKeys) {
-      super(label);
-      this.configuration = Preconditions.checkNotNull(configuration);
-      this.aspects = Preconditions.checkNotNull(aspects);
-      this.aspectConfigurations = Preconditions.checkNotNull(aspectConfigurations);
-      this.transitionKeys = Preconditions.checkNotNull(transitionKeys);
-    }
-
-    @Override
-    public BuildConfiguration getConfiguration() {
-      return configuration;
-    }
-
-    @Override
-    public AspectCollection getAspects() {
-      return aspects;
-    }
-
-    @Override
-    public BuildConfiguration getAspectConfiguration(AspectDescriptor aspect) {
-      return aspectConfigurations.get(aspect);
-    }
-
-    @Override
-    public ImmutableList<String> getTransitionKeys() {
-      return transitionKeys;
-    }
-
-    @Override
-    public int hashCode() {
-      return Objects.hash(label, configuration, aspectConfigurations, transitionKeys);
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof ExplicitConfigurationDependency)) {
-        return false;
-      }
-      ExplicitConfigurationDependency otherDep = (ExplicitConfigurationDependency) other;
-      return label.equals(otherDep.label)
-          && configuration.equals(otherDep.configuration)
-          && aspects.equals(otherDep.aspects)
-          && aspectConfigurations.equals(otherDep.aspectConfigurations);
-    }
-
-    @Override
-    public String toString() {
-      return String.format(
-          "%s{label=%s, configuration=%s, aspectConfigurations=%s}",
-          getClass().getSimpleName(), label, configuration, aspectConfigurations);
-    }
-  }
 }
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 8fa0701..f0b8405 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
@@ -218,7 +218,7 @@
                   Dependency.builder()
                       .setLabel(dep.getLabel())
                       .withNullConfiguration()
-                      .addTransitionKeys(ImmutableList.copyOf(toOptions.keySet()))
+                      .setTransitionKeys(ImmutableList.copyOf(toOptions.keySet()))
                       .build();
             }
           }
@@ -338,6 +338,9 @@
                 .setLabel(dep.getLabel())
                 .setConfiguration(ctgValue.getConfiguration())
                 .setAspects(dep.getAspects())
+                // Explicitly do not set the transition key, since there is only one configuration
+                // and it matches the current one. This ignores the transition key set if this
+                // was a split transition.
                 .build());
         continue;
       }
@@ -429,7 +432,7 @@
                   .setLabel(originalDep.getLabel())
                   .setConfiguration(trimmedConfig)
                   .setAspects(originalDep.getAspects())
-                  .addTransitionKey(info.second)
+                  .setTransitionKey(info.second)
                   .build();
           Attribute attribute = attr.dependencyKind.getAttribute();
           if (attribute != null && attribute.getTransitionFactory().isSplit()) {