Aspects-on-aspects implementation.

--
MOS_MIGRATED_REVID=139189444

15 files changed, 587 insertions, 295 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 5f03ec2fe0..20b89b0f82 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
@@ -50,6 +50,7 @@ import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.AspectClass;
+import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.NativeAspectClass;
@@ -479,14 +480,16 @@ public class BuildView {
             if (!(targetSpec.getTarget() instanceof Rule)) {
               continue;
             }
+            // For invoking top-level aspects, use the top-level configuration for both the
+            // aspect and the base target while the top-level configuration is untrimmed.
+            BuildConfiguration configuration = targetSpec.getConfiguration();
             aspectKeys.add(
                 AspectValue.createAspectKey(
                     targetSpec.getLabel(),
-                    // For invoking top-level aspects, use the top-level configuration for both the
-                    // aspect and the base target while the top-level configuration is untrimmed.
-                    targetSpec.getConfiguration(),
-                    targetSpec.getConfiguration(),
-                    aspectFactoryClass));
+                    configuration,
+                    new AspectDescriptor(aspectFactoryClass, AspectParameters.EMPTY),
+                    configuration
+                ));
           }
         } else {
           throw new ViewCreationFailedException("Aspect '" + aspect + "' is unknown");
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index 7a375cedad..fdc0c74684 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -310,7 +310,7 @@ public final class ConfiguredTargetFactory {
    */
   public ConfiguredAspect createAspect(
       AnalysisEnvironment env,
-      RuleConfiguredTarget associatedTarget,
+      ConfiguredTarget associatedTarget,
       ConfiguredAspectFactory aspectFactory,
       Aspect aspect,
       OrderedSetMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
@@ -318,16 +318,15 @@ public final class ConfiguredTargetFactory {
       BuildConfiguration aspectConfiguration,
       BuildConfiguration hostConfiguration)
       throws InterruptedException {
-    RuleContext.Builder builder =
-        new RuleContext.Builder(
-            env,
-            associatedTarget.getTarget(),
-            aspect.getAspectClass().getName(),
-            aspect.getParameters(),
-            aspectConfiguration,
-            hostConfiguration,
-            ruleClassProvider.getPrerequisiteValidator(),
-            aspect.getDefinition().getConfigurationFragmentPolicy());
+    RuleContext.Builder builder = new RuleContext.Builder(
+        env,
+        associatedTarget.getTarget().getAssociatedRule(),
+        aspect.getAspectClass().getName(),
+        aspect.getParameters(),
+        aspectConfiguration,
+        hostConfiguration,
+        ruleClassProvider.getPrerequisiteValidator(),
+        aspect.getDefinition().getConfigurationFragmentPolicy());
     RuleContext ruleContext =
         builder
             .setVisibility(
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 abbd401a37..755b991d86 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
@@ -19,11 +19,8 @@ import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
 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;
 
 /**
@@ -74,7 +71,7 @@ public abstract class Dependency {
    * <p>The configuration and aspects must not be {@code null}.
    */
   public static Dependency withConfigurationAndAspects(
-      Label label, BuildConfiguration configuration, Set<AspectDescriptor> aspects) {
+      Label label, BuildConfiguration configuration, Iterable<AspectDescriptor> aspects) {
     ImmutableMap.Builder<AspectDescriptor, BuildConfiguration> aspectBuilder =
         new ImmutableMap.Builder<>();
     for (AspectDescriptor aspect : aspects) {
@@ -102,7 +99,7 @@ public abstract class Dependency {
    * configuration builds.
    */
   public static Dependency withTransitionAndAspects(
-      Label label, Attribute.Transition transition, Set<AspectDescriptor> aspects) {
+      Label label, Attribute.Transition transition, Iterable<AspectDescriptor> aspects) {
     return new DynamicConfigurationDependency(label, transition, ImmutableSet.copyOf(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 00e76931bf..635b39a3ce 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
@@ -47,7 +47,6 @@ import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -85,7 +84,7 @@ public abstract class DependencyResolver {
    *     This is needed to support {@link LateBoundDefault#useHostConfiguration()}.
    * @param aspect the aspect applied to this target (if any)
    * @param configConditions resolver for config_setting labels
-   * @return a mapping of each attribute in this rule or aspect to its dependent nodes
+   * @return a mapping of each attribute in this rule or aspects to its dependent nodes
    */
   public final OrderedSetMultimap<Attribute, Dependency> dependentNodeMap(
       TargetAndConfiguration node,
@@ -95,7 +94,9 @@ public abstract class DependencyResolver {
       throws EvalException, InvalidConfigurationException, InterruptedException {
     NestedSetBuilder<Label> rootCauses = NestedSetBuilder.<Label>stableOrder();
     OrderedSetMultimap<Attribute, Dependency> outgoingEdges = dependentNodeMap(
-        node, hostConfig, aspect, configConditions, rootCauses);
+        node, hostConfig,
+        aspect != null ? ImmutableList.of(aspect) : ImmutableList.<Aspect>of(),
+        configConditions, rootCauses);
     if (!rootCauses.isEmpty()) {
       throw new IllegalStateException(rootCauses.build().iterator().next().toString());
     }
@@ -107,11 +108,14 @@ public abstract class DependencyResolver {
    * dependencies do not have a corresponding attribute here, and we use the null attribute to
    * represent those edges.
    *
-   * <p>If {@code aspect} is null, returns the dependent nodes of the configured target node
-   * representing the given target and configuration, otherwise that of the aspect node accompanying
-   * the aforementioned configured target node for the specified aspect.
+   * <p>If {@code aspects} is empty, returns the dependent nodes of the configured target node
+   * representing the given target and configuration.
    *
-   * <p>The values are not simply labels because this also implements the first step of applying
+   * Otherwise {@code aspects} represents an aspect path. The function returns dependent nodes
+   * of the entire path applied to given target and configuration. These are the depenent nodes
+   * of the last aspect in the path.
+   *
+   * <p>This also implements the first step of applying
    * configuration transitions, namely, split transitions. This needs to be done before the labels
    * are resolved because late bound attributes depend on the configuration. A good example for this
    * is @{code :cc_toolchain}.
@@ -123,15 +127,15 @@ public abstract class DependencyResolver {
    * @param node the target/configuration being evaluated
    * @param hostConfig the configuration this target would use if it was evaluated as a host tool.
    *     This is needed to support {@link LateBoundDefault#useHostConfiguration()}.
-   * @param aspect the aspect applied to this target (if any)
+   * @param aspects the aspects applied to this target (if any)
    * @param configConditions resolver for config_setting labels
    * @param rootCauses collector for dep labels that can't be (loading phase) loaded
-   * @return a mapping of each attribute in this rule or aspect to its dependent nodes
+   * @return a mapping of each attribute in this rule or aspects to its dependent nodes
    */
   public final OrderedSetMultimap<Attribute, Dependency> dependentNodeMap(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
-      @Nullable Aspect aspect,
+      Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Label> rootCauses)
       throws EvalException, InvalidConfigurationException, InterruptedException {
@@ -148,7 +152,7 @@ public abstract class DependencyResolver {
     } else if (target instanceof EnvironmentGroup) {
       visitTargetVisibility(node, rootCauses, outgoingEdges.get(null));
     } else if (target instanceof Rule) {
-      visitRule(node, hostConfig, aspect, configConditions, rootCauses, outgoingEdges);
+      visitRule(node, hostConfig, aspects, configConditions, rootCauses, outgoingEdges);
     } else if (target instanceof PackageGroup) {
       visitPackageGroup(node, (PackageGroup) target, rootCauses, outgoingEdges.get(null));
     } else {
@@ -160,7 +164,7 @@ public abstract class DependencyResolver {
   private void visitRule(
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
-      @Nullable Aspect aspect,
+      Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Label> rootCauses,
       OrderedSetMultimap<Attribute, Dependency> outgoingEdges)
@@ -172,7 +176,7 @@ public abstract class DependencyResolver {
     ConfiguredAttributeMapper attributeMap = ConfiguredAttributeMapper.of(rule, configConditions);
     attributeMap.validateAttributes();
     RuleResolver depResolver =
-        new RuleResolver(rule, ruleConfig, aspect, attributeMap, rootCauses, outgoingEdges);
+        new RuleResolver(rule, ruleConfig, aspects, attributeMap, rootCauses, outgoingEdges);
 
     visitTargetVisibility(node, rootCauses, outgoingEdges.get(null));
     resolveEarlyBoundAttributes(depResolver);
@@ -479,7 +483,8 @@ public abstract class DependencyResolver {
     Preconditions.checkArgument(node.getTarget() instanceof Rule);
     Rule rule = (Rule) node.getTarget();
     OrderedSetMultimap<Attribute, Dependency> outgoingEdges = OrderedSetMultimap.create();
-    RuleResolver depResolver = new RuleResolver(rule, node.getConfiguration(), /*aspect=*/null,
+    RuleResolver depResolver = new RuleResolver(
+        rule, node.getConfiguration(), ImmutableList.<Aspect>of(),
         /*attributeMap=*/null, rootCauses, outgoingEdges);
     Map<Attribute, Collection<Label>> m = depLabels.asMap();
     for (Map.Entry<Attribute, Collection<Label>> entry : depLabels.asMap().entrySet()) {
@@ -513,8 +518,9 @@ public abstract class DependencyResolver {
     }
   }
 
+
   private static ImmutableSet<AspectDescriptor> requiredAspects(
-      @Nullable Aspect aspect,
+      Iterable<Aspect> aspects,
       AttributeAndOwner attributeAndOwner,
       final Target target,
       Rule originalRule) {
@@ -522,8 +528,13 @@ public abstract class DependencyResolver {
       return ImmutableSet.of();
     }
 
+    if (attributeAndOwner.ownerAspect != null) {
+      // Do not propagate aspects along aspect attributes.
+      return ImmutableSet.of();
+    }
+
     Iterable<Aspect> aspectCandidates =
-        extractAspectCandidates(aspect, attributeAndOwner, originalRule);
+        extractAspectCandidates(aspects, attributeAndOwner.attribute, originalRule);
     RuleClass ruleClass = ((Rule) target).getRuleClassObject();
     ImmutableSet.Builder<AspectDescriptor> result = ImmutableSet.builder();
     for (Aspect aspectCandidate : aspectCandidates) {
@@ -541,15 +552,11 @@ public abstract class DependencyResolver {
   }
 
   private static Iterable<Aspect> extractAspectCandidates(
-      @Nullable Aspect aspect, AttributeAndOwner attributeAndOwner, Rule originalRule) {
-    // The order of this set will be deterministic. This is necessary because this order eventually
-    // influences the order in which aspects are merged into the main configured target, which in
-    // turn influences which aspect takes precedence if two emit the same provider (maybe this
-    // should be an error)
-    Attribute attribute = attributeAndOwner.attribute;
-    Set<Aspect> aspectCandidates = new LinkedHashSet<>();
+      Iterable<Aspect> aspects,
+      Attribute attribute, Rule originalRule) {
+    ImmutableList.Builder<Aspect> aspectCandidates = ImmutableList.builder();
     aspectCandidates.addAll(attribute.getAspects(originalRule));
-    if (aspect != null && !aspect.getAspectClass().equals(attributeAndOwner.ownerAspect)) {
+    for (Aspect aspect : aspects) {
       for (AspectClass aspectClass :
           aspect.getDefinition().getAttributeAspects(attribute)) {
         if (aspectClass.equals(aspect.getAspectClass())) {
@@ -565,7 +572,7 @@ public abstract class DependencyResolver {
         }
       }
     }
-    return aspectCandidates;
+    return aspectCandidates.build();
   }
 
   /**
@@ -598,7 +605,7 @@ public abstract class DependencyResolver {
   private class RuleResolver {
     private final Rule rule;
     private final BuildConfiguration ruleConfig;
-    private final Aspect aspect;
+    private final Iterable<Aspect> aspects;
     private final ConfiguredAttributeMapper attributeMap;
     private final NestedSetBuilder<Label> rootCauses;
     private final OrderedSetMultimap<Attribute, Dependency> outgoingEdges;
@@ -609,21 +616,27 @@ public abstract class DependencyResolver {
      *
      * @param rule the rule being evaluated
      * @param ruleConfig the rule's configuration
-     * @param aspect the aspect applied to this rule (if any)
+     * @param aspects the aspects applied to this rule (if any)
      * @param attributeMap mapper for the rule's attribute values
      * @param rootCauses output collector for dep labels that can't be (loading phase) loaded
      * @param outgoingEdges output collector for the resolved dependencies
      */
-    RuleResolver(Rule rule, BuildConfiguration ruleConfig, Aspect aspect,
+    RuleResolver(Rule rule, BuildConfiguration ruleConfig, Iterable<Aspect> aspects,
         ConfiguredAttributeMapper attributeMap, NestedSetBuilder<Label> rootCauses,
         OrderedSetMultimap<Attribute, Dependency> outgoingEdges) {
       this.rule = rule;
       this.ruleConfig = ruleConfig;
-      this.aspect = aspect;
+      this.aspects = aspects;
       this.attributeMap = attributeMap;
       this.rootCauses = rootCauses;
       this.outgoingEdges = outgoingEdges;
-      this.attributes = getAttributes(rule, aspect);
+
+      this.attributes = getAttributes(rule,
+          // These are attributes that the application of `aspects` "path"
+          // to the rule will see. Application of path is really the
+          // application of the last aspect in the path, so we only let it see
+          // it's own attributes.
+          Iterables.getLast(aspects, null));
     }
 
     /** Returns the attributes that should be visited for this rule/aspect combination. */
@@ -655,8 +668,8 @@ public abstract class DependencyResolver {
       ruleConfig.evaluateTransition(rule, attributeAndOwner.attribute, toTarget, resolver);
       // An <Attribute, Label> pair can resolve to multiple deps because of split transitions.
       for (Dependency dependency :
-          resolver.getDependencies(
-              depLabel, requiredAspects(aspect, attributeAndOwner, toTarget, rule))) {
+          resolver.getDependencies(depLabel,
+              requiredAspects(aspects, attributeAndOwner, toTarget, rule))) {
         outgoingEdges.put(attributeAndOwner.attribute, dependency);
       }
     }
@@ -684,7 +697,7 @@ public abstract class DependencyResolver {
       }
 
       ImmutableSet<AspectDescriptor> aspects =
-          requiredAspects(aspect, attributeAndOwner, toTarget, rule);
+          requiredAspects(this.aspects, attributeAndOwner, toTarget, rule);
       Dependency dep;
       if (config.useDynamicConfigurations() && !applyNullTransition) {
         // Pass a transition rather than directly feeding the configuration so deps get trimmed.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index 0b7c91160a..4bf0f81c5d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -21,7 +21,8 @@ import com.google.devtools.build.lib.analysis.CachingAnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.ConfiguredAspectFactory;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.RuleConfiguredTarget;
+import com.google.devtools.build.lib.analysis.MergedConfiguredTarget;
+import com.google.devtools.build.lib.analysis.MergedConfiguredTarget.DuplicateException;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
@@ -58,6 +59,8 @@ import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
+import java.util.ArrayList;
+import java.util.Map;
 import javax.annotation.Nullable;
 
 /**
@@ -200,6 +203,7 @@ public final class AspectFunction implements SkyFunction {
       return null;
     }
 
+
     if (configuredTargetValue.getConfiguredTarget() == null) {
       return null;
     }
@@ -209,8 +213,32 @@ public final class AspectFunction implements SkyFunction {
           configuredTargetValue.getConfiguredTarget());
     }
 
-    RuleConfiguredTarget associatedTarget =
-        (RuleConfiguredTarget) configuredTargetValue.getConfiguredTarget();
+    ConfiguredTarget associatedTarget =
+      configuredTargetValue.getConfiguredTarget();
+
+    ImmutableList.Builder<Aspect> aspectPath = ImmutableList.builder();
+
+    if (key.getBaseKey() != null) {
+      ImmutableList<SkyKey> aspectKeys = getSkyKeysForAspects(key.getBaseKey());
+
+      Map<SkyKey, SkyValue> values = env.getValues(aspectKeys);
+      if (env.valuesMissing()) {
+        return null;
+      }
+      try {
+        associatedTarget = getBaseTargetAndCollectPath(
+            associatedTarget, aspectKeys, values, aspectPath);
+      } catch (DuplicateException e) {
+        env.getListener().handle(
+            Event.error(associatedTarget.getTarget().getLocation(), e.getMessage()));
+
+        throw new AspectFunctionException(
+            new AspectCreationException(e.getMessage(), associatedTarget.getLabel()));
+
+      }
+    }
+    aspectPath.add(aspect);
+
     SkyframeDependencyResolver resolver = view.createDependencyResolver(env);
 
     // When getting the dependencies of this hybrid aspect+base target, use the aspect's
@@ -238,7 +266,7 @@ public final class AspectFunction implements SkyFunction {
             env,
             resolver,
             originalTargetAndAspectConfiguration,
-            aspect,
+            aspectPath.build(),
             configConditions,
             ruleClassProvider,
             view.getHostConfiguration(originalTargetAndAspectConfiguration.getConfiguration()),
@@ -258,6 +286,7 @@ public final class AspectFunction implements SkyFunction {
       return createAspect(
           env,
           key,
+          target,
           aspect,
           aspectFactory,
           associatedTarget,
@@ -281,6 +310,43 @@ public final class AspectFunction implements SkyFunction {
     }
   }
 
+  /**
+   * Merges aspects defined by {@code aspectKeys} into the {@code target} using
+   * previously computed {@code values}.
+   *
+   * Also populates {@code aspectPath}.
+   *
+   * @return A {@link ConfiguredTarget} that is a result of a merge.
+   * @throws DuplicateException if there is a duplicate provider provided by aspects.
+   */
+  private ConfiguredTarget getBaseTargetAndCollectPath(ConfiguredTarget target,
+      ImmutableList<SkyKey> aspectKeys, Map<SkyKey, SkyValue> values,
+      ImmutableList.Builder<Aspect> aspectPath)
+      throws DuplicateException {
+    ArrayList<ConfiguredAspect> aspectValues = new ArrayList<>();
+    for (SkyKey skyAspectKey : aspectKeys) {
+      AspectValue aspectValue = (AspectValue) values.get(skyAspectKey);
+      ConfiguredAspect configuredAspect = aspectValue.getConfiguredAspect();
+      aspectValues.add(configuredAspect);
+      aspectPath.add(aspectValue.getAspect());
+    }
+    return MergedConfiguredTarget.of(target, aspectValues);
+  }
+
+  /**
+   *  Returns a list of SkyKeys for all aspects the given aspect key depends on.
+   *  The order corresponds to the order the aspects should be merged into a configured target.
+   */
+  private ImmutableList<SkyKey> getSkyKeysForAspects(AspectKey key) {
+    ImmutableList.Builder<SkyKey> aspectKeysBuilder = ImmutableList.builder();
+    AspectKey baseKey = key;
+    while (baseKey != null) {
+      aspectKeysBuilder.add(baseKey.getSkyKey());
+      baseKey = baseKey.getBaseKey();
+    }
+    return aspectKeysBuilder.build().reverse();
+  }
+
   private static SkyValue createAliasAspect(
       Environment env,
       Target originalTarget,
@@ -293,12 +359,7 @@ public final class AspectFunction implements SkyFunction {
     // the real configured target.
     Label aliasLabel = aliasChain.size() > 1 ? aliasChain.get(1) : configuredTarget.getLabel();
 
-    SkyKey depKey = AspectValue.key(
-        aliasLabel,
-        originalKey.getAspectConfiguration(),
-        originalKey.getBaseConfiguration(),
-        originalKey.getAspectClass(),
-        originalKey.getParameters());
+    SkyKey depKey = ActionLookupValue.key(originalKey.withLabel(aliasLabel));
 
     // Compute the AspectValue of the target the alias refers to (which can itself be either an
     // alias or a real target)
@@ -326,9 +387,10 @@ public final class AspectFunction implements SkyFunction {
   private AspectValue createAspect(
       Environment env,
       AspectKey key,
+      Target baseTarget,
       Aspect aspect,
       ConfiguredAspectFactory aspectFactory,
-      RuleConfiguredTarget associatedTarget,
+      ConfiguredTarget associatedTarget,
       BuildConfiguration aspectConfiguration,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       OrderedSetMultimap<Attribute, ConfiguredTarget> directDeps,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
index 2db8a4d907..1d3b0fd44f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Objects;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.analysis.AspectDescriptor;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -27,7 +28,6 @@ import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunctionName;
-import com.google.devtools.build.skyframe.SkyKey;
 
 import javax.annotation.Nullable;
 
@@ -40,7 +40,6 @@ public final class AspectValue extends ActionLookupValue {
    * A base class for keys that have AspectValue as a Sky value.
    */
   public abstract static class AspectValueKey extends ActionLookupKey {
-
     public abstract String getDescription();
   }
 
@@ -49,17 +48,19 @@ public final class AspectValue extends ActionLookupValue {
    */
   public static final class AspectKey extends AspectValueKey {
     private final Label label;
+    private final AspectKey baseKey;
     private final BuildConfiguration aspectConfiguration;
     private final BuildConfiguration baseConfiguration;
     private final AspectClass aspectClass;
     private final AspectParameters parameters;
 
-    protected AspectKey(
+    private AspectKey(
         Label label,
         BuildConfiguration aspectConfiguration,
         BuildConfiguration baseConfiguration,
         AspectClass aspectClass,
         AspectParameters parameters) {
+      this.baseKey = null;
       this.label = label;
       this.aspectConfiguration = aspectConfiguration;
       this.baseConfiguration = baseConfiguration;
@@ -67,6 +68,18 @@ public final class AspectValue extends ActionLookupValue {
       this.parameters = parameters;
     }
 
+    private AspectKey(
+        AspectKey baseKey,
+        AspectClass aspectClass, AspectParameters aspectParameters,
+        BuildConfiguration aspectConfiguration) {
+      this.baseKey = baseKey;
+      this.label = baseKey.label;
+      this.baseConfiguration = baseKey.getBaseConfiguration();
+      this.aspectConfiguration = aspectConfiguration;
+      this.aspectClass = aspectClass;
+      this.parameters = aspectParameters;
+    }
+
     @Override
     SkyFunctionName getType() {
       return SkyFunctions.ASPECT;
@@ -87,9 +100,18 @@ public final class AspectValue extends ActionLookupValue {
       return parameters;
     }
 
+    @Nullable
+    public AspectKey getBaseKey() {
+      return baseKey;
+    }
+
     @Override
     public String getDescription() {
-      return String.format("%s of %s", aspectClass.getName(), getLabel());
+      if (baseKey == null) {
+        return String.format("%s of %s", aspectClass.getName(), getLabel());
+      } else {
+        return String.format("%s on top of %s", aspectClass.getName(), baseKey.toString());
+      }
     }
 
     /**
@@ -132,6 +154,7 @@ public final class AspectValue extends ActionLookupValue {
     public int hashCode() {
       return Objects.hashCode(
           label,
+          baseKey,
           aspectConfiguration,
           baseConfiguration,
           aspectClass,
@@ -150,6 +173,7 @@ public final class AspectValue extends ActionLookupValue {
 
       AspectKey that = (AspectKey) other;
       return Objects.equal(label, that.label)
+          && Objects.equal(baseKey, that.baseKey)
           && Objects.equal(aspectConfiguration, that.aspectConfiguration)
           && Objects.equal(baseConfiguration, that.baseConfiguration)
           && Objects.equal(aspectClass, that.aspectClass)
@@ -161,7 +185,7 @@ public final class AspectValue extends ActionLookupValue {
         return "null";
       }
       return String.format("%s with aspect %s%s",
-          label.toString(),
+          baseKey == null ? label.toString() : baseKey.prettyPrint(),
           aspectClass.getName(),
           (aspectConfiguration != null && aspectConfiguration.isHostConfiguration())
               ? "(host) " : "");
@@ -169,7 +193,7 @@ public final class AspectValue extends ActionLookupValue {
 
     @Override
     public String toString() {
-      return label
+      return (baseKey == null ? label : baseKey.toString())
           + "#"
           + aspectClass.getName()
           + " "
@@ -179,6 +203,16 @@ public final class AspectValue extends ActionLookupValue {
           + " "
           + parameters;
     }
+
+    public AspectKey withLabel(Label label) {
+      if (baseKey == null) {
+        return new AspectKey(
+            label, aspectConfiguration, baseConfiguration, aspectClass, parameters);
+      } else {
+        return new AspectKey(
+            baseKey.withLabel(label), aspectClass, parameters, aspectConfiguration);
+      }
+    }
   }
 
   /**
@@ -293,34 +327,25 @@ public final class AspectValue extends ActionLookupValue {
     return transitivePackages;
   }
 
-  /**
-   * Constructs a new SkyKey containing an AspectKey.
-   */
-  public static SkyKey key(
-      Label label,
-      BuildConfiguration aspectConfiguration,
-      BuildConfiguration baseConfiguration,
-      AspectClass aspectFactory,
-      AspectParameters additionalConfiguration) {
-    return SkyKey.create(
-        SkyFunctions.ASPECT,
-        new AspectKey(
-            label, aspectConfiguration, baseConfiguration, aspectFactory, additionalConfiguration));
+  public static AspectKey createAspectKey(AspectKey baseKey, AspectDescriptor aspectDescriptor,
+      BuildConfiguration aspectConfiguration) {
+    return new AspectKey(
+        baseKey, aspectDescriptor.getAspectClass(), aspectDescriptor.getParameters(),
+        aspectConfiguration
+    );
   }
 
-  public static SkyKey key(AspectValueKey aspectKey) {
-    return SkyKey.create(aspectKey.getType(), aspectKey);
-  }
 
   public static AspectKey createAspectKey(
       Label label,
-      BuildConfiguration aspectConfiguration,
-      BuildConfiguration baseConfiguration,
-      AspectClass aspectFactory) {
+      BuildConfiguration baseConfiguration, AspectDescriptor aspectDescriptor,
+      BuildConfiguration aspectConfiguration) {
     return new AspectKey(
-        label, aspectConfiguration, baseConfiguration, aspectFactory, AspectParameters.EMPTY);
+        label, aspectConfiguration, baseConfiguration,
+        aspectDescriptor.getAspectClass(), aspectDescriptor.getParameters());
   }
 
+
   public static SkylarkAspectLoadingKey createSkylarkAspectKey(
       Label targetLabel,
       BuildConfiguration aspectConfiguration,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
index 03fdeb2ab7..8744f1a975 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
@@ -161,7 +161,7 @@ public final class CompletionFunction<TValue extends SkyValue, TResult extends S
         throws InterruptedException {
       AspectCompletionKey acKey = (AspectCompletionKey) skyKey.argument();
       AspectKey aspectKey = acKey.aspectKey();
-      return (AspectValue) env.getValue(AspectValue.key(aspectKey));
+      return (AspectValue) env.getValue(aspectKey.getSkyKey());
     }
 
     @Override
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 c4bd5e5d78..ed7673e7a7 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
@@ -54,9 +54,7 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.packages.Aspect;
-import com.google.devtools.build.lib.packages.AspectClass;
 import com.google.devtools.build.lib.packages.AspectDefinition;
-import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
@@ -68,6 +66,7 @@ import com.google.devtools.build.lib.packages.RuleClassProvider;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.skyframe.AspectFunction.AspectCreationException;
+import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor.BuildViewProvider;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
@@ -78,7 +77,6 @@ import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.ValueOrException;
 import com.google.devtools.build.skyframe.ValueOrException2;
-
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashSet;
@@ -222,7 +220,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
               env,
               resolver,
               ctgValue,
-              null,
+              ImmutableList.<Aspect>of(),
               configConditions,
               ruleClassProvider,
               view.getHostConfiguration(configuration),
@@ -263,14 +261,14 @@ final class ConfiguredTargetFunction implements SkyFunction {
 
   /**
    * Computes the direct dependencies of a node in the configured target graph (a configured
-   * target or an aspect).
+   * target or an aspects).
    *
    * <p>Returns null if Skyframe hasn't evaluated the required dependencies yet. In this case, the
    * caller should also return null to Skyframe.
    *  @param env the Skyframe environment
    * @param resolver The dependency resolver
    * @param ctgValue The label and the configuration of the node
-   * @param aspect
+   * @param aspects
    * @param configConditions the configuration conditions for evaluating the attributes of the node
    * @param ruleClassProvider rule class provider for determining the right configuration fragments
    *   to apply to deps
@@ -283,7 +281,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
       Environment env,
       SkyframeDependencyResolver resolver,
       TargetAndConfiguration ctgValue,
-      Aspect aspect,
+      Iterable<Aspect> aspects,
       ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       RuleClassProvider ruleClassProvider,
       BuildConfiguration hostConfiguration,
@@ -295,7 +293,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
     OrderedSetMultimap<Attribute, Dependency> depValueNames;
     try {
       depValueNames = resolver.dependentNodeMap(
-          ctgValue, hostConfiguration, aspect, configConditions, transitiveLoadingRootCauses);
+          ctgValue, hostConfiguration, aspects, configConditions, transitiveLoadingRootCauses);
     } catch (EvalException e) {
       // EvalException can only be thrown by computed Skylark attributes in the current rule.
       env.getListener().handle(Event.error(e.getLocation(), e.getMessage()));
@@ -734,6 +732,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
       Dependency dep = entry.getValue();
       SkyKey depKey = TO_KEYS.apply(dep);
       ConfiguredTarget depConfiguredTarget = depConfiguredTargetMap.get(depKey);
+
       result.put(entry.getKey(),
           MergedConfiguredTarget.of(depConfiguredTarget, depAspectMap.get(depKey)));
     }
@@ -757,11 +756,11 @@ final class ConfiguredTargetFunction implements SkyFunction {
     OrderedSetMultimap<SkyKey, ConfiguredAspect> result = OrderedSetMultimap.create();
     Set<SkyKey> aspectKeys = new HashSet<>();
     for (Dependency dep : deps) {
+      AspectKey key = null;
       for (Entry<AspectDescriptor, BuildConfiguration> depAspect
           : dep.getAspectConfigurations().entrySet()) {
-        aspectKeys.add(createAspectKey(
-            dep.getLabel(), depAspect.getValue(), dep.getConfiguration(),
-            depAspect.getKey().getAspectClass(), depAspect.getKey().getParameters()));
+        key = getNextAspectKey(key, dep, depAspect);
+        aspectKeys.add(key.getSkyKey());
       }
     }
 
@@ -775,14 +774,13 @@ final class ConfiguredTargetFunction implements SkyFunction {
       if (result.containsKey(depKey)) {
         continue;
       }
+      AspectKey key = null;
       ConfiguredTarget depConfiguredTarget = configuredTargetMap.get(depKey);
       for (Entry<AspectDescriptor, BuildConfiguration> depAspect
           : dep.getAspectConfigurations().entrySet()) {
-        SkyKey aspectKey = createAspectKey(
-            dep.getLabel(), depAspect.getValue(), dep.getConfiguration(),
-            depAspect.getKey().getAspectClass(),
-            depAspect.getKey().getParameters());
-        AspectValue aspectValue = null;
+        key = getNextAspectKey(key, dep, depAspect);
+        SkyKey aspectKey = key.getSkyKey();
+        AspectValue aspectValue;
         try {
           // TODO(ulfjack): Catch all thrown AspectCreationException and NoSuchThingException
           // instances and merge them into a single Exception to get full root cause data.
@@ -811,17 +809,16 @@ final class ConfiguredTargetFunction implements SkyFunction {
     return result;
   }
 
-  public static SkyKey createAspectKey(
-      Label label,
-      BuildConfiguration aspectConfiguration,
-      BuildConfiguration baseConfiguration,
-      AspectClass aspectClass,
-      AspectParameters parameters) {
-    return AspectValue.key(label,
-        aspectConfiguration,
-        baseConfiguration,
-        aspectClass,
-        parameters);
+  private static AspectKey getNextAspectKey(AspectKey key, Dependency dep,
+      Entry<AspectDescriptor, BuildConfiguration> depAspect) {
+    if (key == null) {
+      key = AspectValue.createAspectKey(dep.getLabel(),
+          dep.getConfiguration(), depAspect.getKey(), depAspect.getValue()
+      );
+    } else {
+      key = AspectValue.createAspectKey(key, depAspect.getKey(), depAspect.getValue());
+    }
+    return key;
   }
 
   private static boolean aspectMatchesConfiguredTarget(ConfiguredTarget dep, Aspect aspect) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index 0c162b1783..21d6f7b12c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -218,7 +218,7 @@ public final class SkyframeBuildView {
     Collection<AspectValue> goodAspects = Lists.newArrayListWithCapacity(values.size());
     NestedSetBuilder<Package> packages = NestedSetBuilder.stableOrder();
     for (AspectValueKey aspectKey : aspectKeys) {
-      AspectValue value = (AspectValue) result.get(AspectValue.key(aspectKey));
+      AspectValue value = (AspectValue) result.get(aspectKey.getSkyKey());
       if (value == null) {
         // Skip aspects that couldn't be applied to targets.
         continue;
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 825fc78a60..b4cb3059fd 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
@@ -1187,6 +1187,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
 
     Map<Dependency, BuildConfiguration> configs;
     if (originalConfig != null) {
+
       if (useOriginalConfig) {
         // This flag is used because of some unfortunate complexity in the configuration machinery:
         // Most callers of this method pass a <Label, Configuration> pair to directly create a
@@ -1219,10 +1220,10 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
       skyKeys.add(ConfiguredTargetValue.key(key.getLabel(), configs.get(key)));
       for (AspectDescriptor aspectDescriptor : key.getAspects()) {
         skyKeys.add(
-            ConfiguredTargetFunction.createAspectKey(
-                key.getLabel(), configs.get(key), configs.get(key),
-                aspectDescriptor.getAspectClass(),
-                aspectDescriptor.getParameters()));
+            ActionLookupValue.key(AspectValue.createAspectKey(
+                key.getLabel(), configs.get(key),
+                aspectDescriptor, configs.get(key)
+            )));
       }
     }
 
@@ -1252,10 +1253,10 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
 
       for (AspectDescriptor aspectDescriptor : key.getAspects()) {
         SkyKey aspectKey =
-            ConfiguredTargetFunction.createAspectKey(
-                key.getLabel(), configs.get(key), configs.get(key),
-                aspectDescriptor.getAspectClass(),
-                aspectDescriptor.getParameters());
+            ActionLookupValue.key(AspectValue.createAspectKey(
+                key.getLabel(), configs.get(key),
+                aspectDescriptor, configs.get(key)
+            ));
         if (result.get(aspectKey) == null) {
           continue DependentNodeLoop;
         }
@@ -1490,7 +1491,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
 
     List<SkyKey> keys = new ArrayList<>(ConfiguredTargetValue.keys(values));
     for (AspectValueKey aspectKey : aspectKeys) {
-      keys.add(AspectValue.key(aspectKey));
+      keys.add(aspectKey.getSkyKey());
     }
     // Make sure to not run too many analysis threads. This can cause memory thrashing.
     return buildDriver.evaluate(keys, keepGoing, ResourceUsage.getAvailableProcessors(),
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
index 785e7407f4..5d2c163ef8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.analysis.AspectDescriptor;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.AspectParameters;
@@ -77,12 +78,11 @@ public class ToplevelSkylarkAspectFunction implements SkyFunction {
       throw new LoadSkylarkAspectFunctionException(e);
     }
     SkyKey aspectKey =
-        AspectValue.key(
-            aspectLoadingKey.getTargetLabel(),
-            aspectLoadingKey.getAspectConfiguration(),
-            aspectLoadingKey.getTargetConfiguration(),
-            skylarkAspect.getAspectClass(),
-            AspectParameters.EMPTY);
+        ActionLookupValue.key(AspectValue.createAspectKey(
+            aspectLoadingKey.getTargetLabel(), aspectLoadingKey.getTargetConfiguration(),
+            new AspectDescriptor(skylarkAspect.getAspectClass(), AspectParameters.EMPTY),
+            aspectLoadingKey.getAspectConfiguration()
+        ));
 
     return env.getValue(aspectKey);
   }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java b/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
index bcdb951185..b5e3bcda49 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
@@ -21,8 +21,12 @@ import com.google.devtools.build.lib.analysis.util.TestAspects.AttributeAspect;
 import com.google.devtools.build.lib.analysis.util.TestAspects.ExtraAttributeAspect;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.AspectParameters;
+import com.google.devtools.build.lib.packages.NativeAspectClass;
+import com.google.devtools.build.lib.skyframe.ActionLookupValue;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 
+import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
+import com.google.devtools.build.skyframe.SkyKey;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -62,145 +66,177 @@ public class AspectValueTest extends AnalysisTestCase {
 
     new EqualsTester()
         .addEqualityGroup(
-            AspectValue.key(l1, c1, c1, a1, i1),
-            AspectValue.key(l1, c1, c1, a1, i1b),
-            AspectValue.key(l1, c1, c1, a1b, i1),
-            AspectValue.key(l1, c1, c1, a1b, i1b),
-            AspectValue.key(l1b, c1, c1, a1, i1),
-            AspectValue.key(l1b, c1, c1, a1, i1b),
-            AspectValue.key(l1b, c1, c1, a1b, i1),
-            AspectValue.key(l1b, c1, c1, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c1, c1, a1, i2),
-            AspectValue.key(l1, c1, c1, a1b, i2),
-            AspectValue.key(l1b, c1, c1, a1, i2),
-            AspectValue.key(l1b, c1, c1, a1b, i2))
-        .addEqualityGroup(
-            AspectValue.key(l1, c1, c1, a2, i1),
-            AspectValue.key(l1, c1, c1, a2, i1b),
-            AspectValue.key(l1b, c1, c1, a2, i1),
-            AspectValue.key(l1b, c1, c1, a2, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c1, c1, a2, i2),
-            AspectValue.key(l1b, c1, c1, a2, i2))
-        .addEqualityGroup(
-            AspectValue.key(l1, c1, c2, a1, i1),
-            AspectValue.key(l1, c1, c2, a1, i1b),
-            AspectValue.key(l1, c1, c2, a1b, i1),
-            AspectValue.key(l1, c1, c2, a1b, i1b),
-            AspectValue.key(l1b, c1, c2, a1, i1),
-            AspectValue.key(l1b, c1, c2, a1, i1b),
-            AspectValue.key(l1b, c1, c2, a1b, i1),
-            AspectValue.key(l1b, c1, c2, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c1, c2, a1, i2),
-            AspectValue.key(l1, c1, c2, a1b, i2),
-            AspectValue.key(l1b, c1, c2, a1, i2),
-            AspectValue.key(l1b, c1, c2, a1b, i2))
-        .addEqualityGroup(
-            AspectValue.key(l1, c1, c2, a2, i1),
-            AspectValue.key(l1, c1, c2, a2, i1b),
-            AspectValue.key(l1b, c1, c2, a2, i1),
-            AspectValue.key(l1b, c1, c2, a2, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c1, c2, a2, i2),
-            AspectValue.key(l1b, c1, c2, a2, i2))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c1, a1, i1),
-            AspectValue.key(l1, c2, c1, a1, i1b),
-            AspectValue.key(l1, c2, c1, a1b, i1),
-            AspectValue.key(l1, c2, c1, a1b, i1b),
-            AspectValue.key(l1b, c2, c1, a1, i1),
-            AspectValue.key(l1b, c2, c1, a1, i1b),
-            AspectValue.key(l1b, c2, c1, a1b, i1),
-            AspectValue.key(l1b, c2, c1, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c1, a1, i2),
-            AspectValue.key(l1, c2, c1, a1b, i2),
-            AspectValue.key(l1b, c2, c1, a1, i2),
-            AspectValue.key(l1b, c2, c1, a1b, i2))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c1, a2, i1),
-            AspectValue.key(l1, c2, c1, a2, i1b),
-            AspectValue.key(l1b, c2, c1, a2, i1),
-            AspectValue.key(l1b, c2, c1, a2, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c1, a2, i2),
-            AspectValue.key(l1b, c2, c1, a2, i2))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c2, a1, i1),
-            AspectValue.key(l1, c2, c2, a1, i1b),
-            AspectValue.key(l1, c2, c2, a1b, i1),
-            AspectValue.key(l1, c2, c2, a1b, i1b),
-            AspectValue.key(l1b, c2, c2, a1, i1),
-            AspectValue.key(l1b, c2, c2, a1, i1b),
-            AspectValue.key(l1b, c2, c2, a1b, i1),
-            AspectValue.key(l1b, c2, c2, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c2, a1, i2),
-            AspectValue.key(l1, c2, c2, a1b, i2),
-            AspectValue.key(l1b, c2, c2, a1, i2),
-            AspectValue.key(l1b, c2, c2, a1b, i2))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c2, a2, i1),
-            AspectValue.key(l1, c2, c2, a2, i1b),
-            AspectValue.key(l1b, c2, c2, a2, i1),
-            AspectValue.key(l1b, c2, c2, a2, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l1, c2, c2, a2, i2),
-            AspectValue.key(l1b, c2, c2, a2, i2))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c1, a1, i1),
-            AspectValue.key(l2, c1, c1, a1, i1b),
-            AspectValue.key(l2, c1, c1, a1b, i1),
-            AspectValue.key(l2, c1, c1, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c1, a1, i2),
-            AspectValue.key(l2, c1, c1, a1b, i2))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c1, a2, i1),
-            AspectValue.key(l2, c1, c1, a2, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c1, a2, i2))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c2, a1, i1),
-            AspectValue.key(l2, c1, c2, a1, i1b),
-            AspectValue.key(l2, c1, c2, a1b, i1),
-            AspectValue.key(l2, c1, c2, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c2, a1, i2),
-            AspectValue.key(l2, c1, c2, a1b, i2))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c2, a2, i1),
-            AspectValue.key(l2, c1, c2, a2, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l2, c1, c2, a2, i2))
-        .addEqualityGroup(
-            AspectValue.key(l2, c2, c1, a1, i1),
-            AspectValue.key(l2, c2, c1, a1, i1b),
-            AspectValue.key(l2, c2, c1, a1b, i1),
-            AspectValue.key(l2, c2, c1, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l2, c2, c1, a1, i2),
-            AspectValue.key(l2, c2, c1, a1b, i2))
-        .addEqualityGroup(
-            AspectValue.key(l2, c2, c1, a2, i1),
-            AspectValue.key(l2, c2, c1, a2, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l2, c2, c1, a2, i2))
-        .addEqualityGroup(
-            AspectValue.key(l2, c2, c2, a1, i1),
-            AspectValue.key(l2, c2, c2, a1, i1b),
-            AspectValue.key(l2, c2, c2, a1b, i1),
-            AspectValue.key(l2, c2, c2, a1b, i1b))
-        .addEqualityGroup(
-            AspectValue.key(l2, c2, c2, a1, i2),
-            AspectValue.key(l2, c2, c2, a1b, i2))
+            createKey(l1, c1, a1, i1, c1),
+            createKey(l1, c1, a1, i1b, c1),
+            createKey(l1, c1, a1b, i1, c1),
+            createKey(l1, c1, a1b, i1b, c1),
+            createKey(l1b, c1, a1, i1, c1),
+            createKey(l1b, c1, a1, i1b, c1),
+            createKey(l1b, c1, a1b, i1, c1),
+            createKey(l1b, c1, a1b, i1b, c1))
+        .addEqualityGroup(
+            createKey(l1, c1, a1, i2, c1),
+            createKey(l1, c1, a1b, i2, c1),
+            createKey(l1b, c1, a1, i2, c1),
+            createKey(l1b, c1, a1b, i2, c1))
+        .addEqualityGroup(
+            createKey(l1, c1, a2, i1, c1),
+            createKey(l1, c1, a2, i1b, c1),
+            createKey(l1b, c1, a2, i1, c1),
+            createKey(l1b, c1, a2, i1b, c1))
+        .addEqualityGroup(
+            createKey(l1, c1, a2, i2, c1),
+            createKey(l1b, c1, a2, i2, c1))
+        .addEqualityGroup(
+            createKey(l1, c2, a1, i1, c1),
+            createKey(l1, c2, a1, i1b, c1),
+            createKey(l1, c2, a1b, i1, c1),
+            createKey(l1, c2, a1b, i1b, c1),
+            createKey(l1b, c2, a1, i1, c1),
+            createKey(l1b, c2, a1, i1b, c1),
+            createKey(l1b, c2, a1b, i1, c1),
+            createKey(l1b, c2, a1b, i1b, c1))
+        .addEqualityGroup(
+            createKey(l1, c2, a1, i2, c1),
+            createKey(l1, c2, a1b, i2, c1),
+            createKey(l1b, c2, a1, i2, c1),
+            createKey(l1b, c2, a1b, i2, c1))
+        .addEqualityGroup(
+            createKey(l1, c2, a2, i1, c1),
+            createKey(l1, c2, a2, i1b, c1),
+            createKey(l1b, c2, a2, i1, c1),
+            createKey(l1b, c2, a2, i1b, c1))
+        .addEqualityGroup(
+            createKey(l1, c2, a2, i2, c1),
+            createKey(l1b, c2, a2, i2, c1))
+        .addEqualityGroup(
+            createKey(l1, c1, a1, i1, c2),
+            createKey(l1, c1, a1, i1b, c2),
+            createKey(l1, c1, a1b, i1, c2),
+            createKey(l1, c1, a1b, i1b, c2),
+            createKey(l1b, c1, a1, i1, c2),
+            createKey(l1b, c1, a1, i1b, c2),
+            createKey(l1b, c1, a1b, i1, c2),
+            createKey(l1b, c1, a1b, i1b, c2))
+        .addEqualityGroup(
+            createKey(l1, c1, a1, i2, c2),
+            createKey(l1, c1, a1b, i2, c2),
+            createKey(l1b, c1, a1, i2, c2),
+            createKey(l1b, c1, a1b, i2, c2))
+        .addEqualityGroup(
+            createKey(l1, c1, a2, i1, c2),
+            createKey(l1, c1, a2, i1b, c2),
+            createKey(l1b, c1, a2, i1, c2),
+            createKey(l1b, c1, a2, i1b, c2))
+        .addEqualityGroup(
+            createKey(l1, c1, a2, i2, c2),
+            createKey(l1b, c1, a2, i2, c2))
+        .addEqualityGroup(
+            createKey(l1, c2, a1, i1, c2),
+            createKey(l1, c2, a1, i1b, c2),
+            createKey(l1, c2, a1b, i1, c2),
+            createKey(l1, c2, a1b, i1b, c2),
+            createKey(l1b, c2, a1, i1, c2),
+            createKey(l1b, c2, a1, i1b, c2),
+            createKey(l1b, c2, a1b, i1, c2),
+            createKey(l1b, c2, a1b, i1b, c2))
+        .addEqualityGroup(
+            createKey(l1, c2, a1, i2, c2),
+            createKey(l1, c2, a1b, i2, c2),
+            createKey(l1b, c2, a1, i2, c2),
+            createKey(l1b, c2, a1b, i2, c2))
+        .addEqualityGroup(
+            createKey(l1, c2, a2, i1, c2),
+            createKey(l1, c2, a2, i1b, c2),
+            createKey(l1b, c2, a2, i1, c2),
+            createKey(l1b, c2, a2, i1b, c2))
+        .addEqualityGroup(
+            createKey(l1, c2, a2, i2, c2),
+            createKey(l1b, c2, a2, i2, c2))
+        .addEqualityGroup(
+            createKey(l2, c1, a1, i1, c1),
+            createKey(l2, c1, a1, i1b, c1),
+            createKey(l2, c1, a1b, i1, c1),
+            createKey(l2, c1, a1b, i1b, c1))
+        .addEqualityGroup(
+            createKey(l2, c1, a1, i2, c1),
+            createKey(l2, c1, a1b, i2, c1))
+        .addEqualityGroup(
+            createKey(l2, c1, a2, i1, c1),
+            createKey(l2, c1, a2, i1b, c1))
+        .addEqualityGroup(
+            createKey(l2, c1, a2, i2, c1))
+        .addEqualityGroup(
+            createKey(l2, c2, a1, i1, c1),
+            createKey(l2, c2, a1, i1b, c1),
+            createKey(l2, c2, a1b, i1, c1),
+            createKey(l2, c2, a1b, i1b, c1))
+        .addEqualityGroup(
+            createKey(l2, c2, a1, i2, c1),
+            createKey(l2, c2, a1b, i2, c1))
+        .addEqualityGroup(
+            createKey(l2, c2, a2, i1, c1),
+            createKey(l2, c2, a2, i1b, c1))
+        .addEqualityGroup(
+            createKey(l2, c2, a2, i2, c1))
+        .addEqualityGroup(
+            createKey(l2, c1, a1, i1, c2),
+            createKey(l2, c1, a1, i1b, c2),
+            createKey(l2, c1, a1b, i1, c2),
+            createKey(l2, c1, a1b, i1b, c2))
+        .addEqualityGroup(
+            createKey(l2, c1, a1, i2, c2),
+            createKey(l2, c1, a1b, i2, c2))
+        .addEqualityGroup(
+            createKey(l2, c1, a2, i1, c2),
+            createKey(l2, c1, a2, i1b, c2))
+        .addEqualityGroup(
+            createKey(l2, c1, a2, i2, c2))
+        .addEqualityGroup(
+            createKey(l2, c2, a1, i1, c2),
+            createKey(l2, c2, a1, i1b, c2),
+            createKey(l2, c2, a1b, i1, c2),
+            createKey(l2, c2, a1b, i1b, c2))
+        .addEqualityGroup(
+            createKey(l2, c2, a1, i2, c2),
+            createKey(l2, c2, a1b, i2, c2))
         .addEqualityGroup(
-            AspectValue.key(l2, c2, c2, a2, i1),
-            AspectValue.key(l2, c2, c2, a2, i1b))
+            createKey(l2, c2, a2, i1, c2),
+            createKey(l2, c2, a2, i1b, c2))
         .addEqualityGroup(
-            AspectValue.key(l2, c2, c2, a2, i2))
+            createKey(l2, c2, a2, i2, c2))
+        .addEqualityGroup(
+            createDerivedKey(l1, c1, a1, i1, c1, a2, i2, c2),
+            createDerivedKey(l1, c1, a1, i1b, c1, a2, i2, c2)
+        )
+        .addEqualityGroup(
+            createDerivedKey(l1, c1, a2, i1, c1, a1, i2, c2),
+            createDerivedKey(l1, c1, a2, i1b, c1, a1, i2, c2)
+        )
         .testEquals();
   }
+
+  private static SkyKey createKey(
+      Label label, BuildConfiguration baseConfiguration, NativeAspectClass aspectClass,
+      AspectParameters parameters, BuildConfiguration aspectConfiguration) {
+    return ActionLookupValue.key(AspectValue.createAspectKey(
+                label, baseConfiguration, new AspectDescriptor(aspectClass, parameters),
+        aspectConfiguration
+    ));
+  }
+
+  private static SkyKey createDerivedKey(
+      Label label, BuildConfiguration baseConfiguration,
+      NativeAspectClass aspectClass1, AspectParameters parameters1,
+      BuildConfiguration aspectConfiguration1,
+      NativeAspectClass aspectClass2, AspectParameters parameters2,
+      BuildConfiguration aspectConfiguration2) {
+    AspectKey baseKey = AspectValue.createAspectKey(label, baseConfiguration,
+        new AspectDescriptor(aspectClass1, parameters1), aspectConfiguration1);
+    return ActionLookupValue.key(AspectValue.createAspectKey(
+        baseKey, new AspectDescriptor(aspectClass2, parameters2),
+        aspectConfiguration2
+    ));
+  }
+
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index 4a4b03dbc4..f5b15a85c8 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -48,6 +48,7 @@ import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
 import com.google.devtools.build.lib.analysis.AnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.AnalysisUtils;
+import com.google.devtools.build.lib.analysis.AspectDescriptor;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.BuildView;
 import com.google.devtools.build.lib.analysis.BuildView.AnalysisResult;
@@ -119,6 +120,7 @@ import com.google.devtools.build.lib.pkgcache.TransitivePackageLoader;
 import com.google.devtools.build.lib.rules.extra.ExtraAction;
 import com.google.devtools.build.lib.rules.test.BaselineCoverageAction;
 import com.google.devtools.build.lib.rules.test.InstrumentedFilesProvider;
+import com.google.devtools.build.lib.skyframe.ActionLookupValue;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
 import com.google.devtools.build.lib.skyframe.DiffAwareness;
@@ -1063,12 +1065,10 @@ public abstract class BuildViewTestCase extends FoundationTestCase {
         packageRelativePath,
         owner.getConfiguration().getBinDirectory(RepositoryName.MAIN),
         (AspectValue.AspectKey)
-            AspectValue.key(
-                    owner.getLabel(),
-                    owner.getConfiguration(),
-                    owner.getConfiguration(),
-                    creatingAspectFactory,
-                    parameters)
+            ActionLookupValue.key(AspectValue.createAspectKey(
+                owner.getLabel(), owner.getConfiguration(),
+                new AspectDescriptor(creatingAspectFactory, parameters), owner.getConfiguration()
+            ))
                 .argument());
   }
 
@@ -1141,12 +1141,10 @@ public abstract class BuildViewTestCase extends FoundationTestCase {
         owner.getConfiguration().getGenfilesDirectory(
             owner.getTarget().getLabel().getPackageIdentifier().getRepository()),
         (AspectValue.AspectKey)
-            AspectValue.key(
-                    owner.getLabel(),
-                    owner.getConfiguration(),
-                    owner.getConfiguration(),
-                    creatingAspectFactory,
-                    params)
+            ActionLookupValue.key(AspectValue.createAspectKey(
+                owner.getLabel(), owner.getConfiguration(),
+                new AspectDescriptor(creatingAspectFactory, params), owner.getConfiguration()
+            ))
                 .argument());
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
index 4e258a9379..e6bfebc8ac 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
@@ -20,6 +20,7 @@ import static org.junit.Assert.fail;
 import com.google.common.base.VerifyException;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.HashMultimap;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.ListMultimap;
@@ -34,6 +35,7 @@ import com.google.devtools.build.lib.analysis.util.AnalysisMock;
 import com.google.devtools.build.lib.analysis.util.AnalysisTestCase;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.packages.Aspect;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
@@ -118,7 +120,7 @@ public class ConfigurationsForTargetsTest extends AnalysisTestCase {
                 env,
                 new SkyframeDependencyResolver(env),
                 (TargetAndConfiguration) skyKey.argument(),
-                null,
+                ImmutableList.<Aspect>of(),
                 ImmutableMap.<Label, ConfigMatchingProvider>of(),
                 stateProvider.lateBoundRuleClassProvider(),
                 stateProvider.lateBoundHostConfig(),
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java
index cebf63dccc..3e1a552875 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkAspectsTest.java
@@ -37,6 +37,7 @@ import com.google.devtools.build.lib.packages.Attribute.ConfigurationTransition;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration;
 import com.google.devtools.build.lib.rules.java.Jvm;
 import com.google.devtools.build.lib.skyframe.AspectValue;
+import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import java.util.Arrays;
@@ -1361,19 +1362,177 @@ public class SkylarkAspectsTest extends AnalysisTestCase {
     Object names = skylarkProviders.getValue("target_labels");
     assertThat(names).isInstanceOf(SkylarkNestedSet.class);
     assertThat(
-            transform(
-                (SkylarkNestedSet) names,
-                new Function<Object, String>() {
-                  @Nullable
-                  @Override
-                  public String apply(Object o) {
-                    assertThat(o).isInstanceOf(Label.class);
-                    return ((Label) o).getName();
-                  }
-                }))
+        transform(
+              (SkylarkNestedSet) names,
+              new Function<Object, String>() {
+                @Nullable
+                @Override
+                public String apply(Object o) {
+                  assertThat(o).isInstanceOf(Label.class);
+                  return ((Label) o).getName();
+                }
+              }))
         .containsExactly("foo", "bar", "tool");
   }
 
+  /**
+   * Simple straightforward linear aspects-on-aspects.
+   */
+  @Test
+  public void aspectOnAspectLinear() throws Exception {
+    scratch.file(
+        "test/aspect.bzl",
+        "a1p = provider()",
+        "def _a1_impl(target,ctx):",
+        "  return struct(a1p = a1p(text = 'random'))",
+        "a1 = aspect(_a1_impl, attr_aspects = ['dep'])",
+        "a2p = provider()",
+        "def _a2_impl(target,ctx):",
+        "  value = []",
+        "  if hasattr(ctx.rule.attr.dep, 'a2p'):",
+        "     value += ctx.rule.attr.dep.a2p.value",
+        "  if hasattr(target, 'a1p'):",
+        "     value.append(str(target.label) + '=yes')",
+        "  else:",
+        "     value.append(str(target.label) + '=no')",
+        "  return struct(a2p = a2p(value = value))",
+        "a2 = aspect(_a2_impl, attr_aspects = ['dep'])",
+        "def _r1_impl(ctx):",
+        "  pass",
+        "def _r2_impl(ctx):",
+        "  return struct(result = ctx.attr.dep.a2p.value)",
+        "r1 = rule(_r1_impl, attrs = { 'dep' : attr.label(aspects = [a1])})",
+        "r2 = rule(_r2_impl, attrs = { 'dep' : attr.label(aspects = [a2])})"
+    );
+    scratch.file(
+        "test/BUILD",
+        "load(':aspect.bzl', 'r1', 'r2')",
+        "r1(name = 'r0')",
+        "r1(name = 'r1', dep = ':r0')",
+        "r2(name = 'r2', dep = ':r1')"
+    );
+    AnalysisResult analysisResult = update("//test:r2");
+    ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
+    SkylarkList result = (SkylarkList) target.get("result");
+
+    // "yes" means that aspect a2 sees a1's providers.
+    assertThat(result).containsExactly("//test:r0=yes", "//test:r1=no");
+  }
+
+  /**
+   * Diamond case.
+   * rule r1 depends or r0 with aspect a1.
+   * rule r2 depends or r0 with aspect a2.
+   * rule rcollect depends on r1, r2 with aspect a3.
+   *
+   * Aspect a3 should be applied twice to target r0: once in [a1, a3] sequence
+   * and once in [a2, a3] sequence.
+   */
+  @Test
+  public void aspectOnAspectDiamond() throws Exception {
+    scratch.file(
+        "test/aspect.bzl",
+        "def _a1_impl(target,ctx):",
+        "  return struct(a1p = 'text from a1')",
+        "a1 = aspect(_a1_impl, attr_aspects = ['deps'])",
+        "",
+        "def _a2_impl(target,ctx):",
+        "  return struct(a2p = 'text from a2')",
+        "a2 = aspect(_a2_impl, attr_aspects = ['deps'])",
+        "",
+        "def _a3_impl(target,ctx):",
+        "  value = []",
+        "  f = ctx.new_file('a3.out')",
+        "  ctx.file_action(f, 'text')",
+        "  for dep in ctx.rule.attr.deps:",
+        "     if hasattr(dep, 'a3p'):",
+        "         value += dep.a3p",
+        "  s = str(target.label) + '='",
+        "  if hasattr(target, 'a1p'):",
+        "     s += 'a1p'",
+        "  if hasattr(target, 'a2p'):",
+        "     s += 'a2p'",
+        "  value.append(s)",
+        "  return struct(a3p = value)",
+        "a3 = aspect(_a3_impl, attr_aspects = ['deps'])",
+        "def _r1_impl(ctx):",
+        "  pass",
+        "def _rcollect_impl(ctx):",
+        "  value = []",
+        "  for dep in ctx.attr.deps:",
+        "     if hasattr(dep, 'a3p'):",
+        "         value += dep.a3p",
+        "  return struct(result = value)",
+        "r1 = rule(_r1_impl, attrs = { 'deps' : attr.label_list(aspects = [a1])})",
+        "r2 = rule(_r1_impl, attrs = { 'deps' : attr.label_list(aspects = [a2])})",
+        "rcollect = rule(_rcollect_impl, attrs = { 'deps' : attr.label_list(aspects = [a3])})"
+    );
+    scratch.file(
+        "test/BUILD",
+        "load(':aspect.bzl', 'r1', 'r2', 'rcollect')",
+        "r1(name = 'r0')",
+        "r1(name = 'r1', deps = [':r0'])",
+        "r2(name = 'r2', deps = [':r0'])",
+        "rcollect(name = 'rcollect', deps = [':r1', ':r2'])"
+    );
+    AnalysisResult analysisResult = update("//test:rcollect");
+    ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
+    SkylarkList result = (SkylarkList) target.get("result");
+    assertThat(result).containsExactly(
+        "//test:r0=a1p", "//test:r1=", "//test:r0=a2p", "//test:r2=");
+  }
+
+  /**
+   * Linear with duplicates.
+   * r2_1 depends on r0 with aspect a2.
+   * r1 depends on r2_1 with aspect a1.
+   * r2 depends on r1 with aspect a2.
+   *
+   * There should be just one instance of aspect a2 on r0, and is should *not* see a1.
+   */
+  @Test
+  public void aspectOnAspectLinearDuplicates() throws Exception {
+    scratch.file(
+        "test/aspect.bzl",
+        "a1p = provider()",
+        "def _a1_impl(target,ctx):",
+        "  return struct(a1p = 'a1p')",
+        "a1 = aspect(_a1_impl, attr_aspects = ['dep'])",
+        "a2p = provider()",
+        "def _a2_impl(target,ctx):",
+        "  value = []",
+        "  if hasattr(ctx.rule.attr.dep, 'a2p'):",
+        "     value += ctx.rule.attr.dep.a2p.value",
+        "  if hasattr(target, 'a1p'):",
+        "     value.append(str(target.label) + '=yes')",
+        "  else:",
+        "     value.append(str(target.label) + '=no')",
+        "  return struct(a2p = a2p(value = value))",
+        "a2 = aspect(_a2_impl, attr_aspects = ['dep'])",
+        "def _r1_impl(ctx):",
+        "  pass",
+        "def _r2_impl(ctx):",
+        "  return struct(result = ctx.attr.dep.a2p.value)",
+        "r1 = rule(_r1_impl, attrs = { 'dep' : attr.label(aspects = [a1])})",
+        "r2 = rule(_r2_impl, attrs = { 'dep' : attr.label(aspects = [a2])})"
+    );
+    scratch.file(
+        "test/BUILD",
+        "load(':aspect.bzl', 'r1', 'r2')",
+        "r1(name = 'r0')",
+        "r2(name = 'r2_1', dep = ':r0')",
+        "r1(name = 'r1', dep = ':r2_1')",
+        "r2(name = 'r2', dep = ':r1')"
+    );
+    AnalysisResult analysisResult = update("//test:r2");
+    ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
+    SkylarkList result = (SkylarkList) target.get("result");
+    // "yes" means that aspect a2 sees a1's providers.
+    assertThat(result).containsExactly("//test:r0=no", "//test:r1=no", "//test:r2_1=yes");
+  }
+
+
+
   @RunWith(JUnit4.class)
   public static final class WithKeepGoing extends SkylarkAspectsTest {
     @Override