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 2cced64..5afda9f 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
@@ -794,13 +794,13 @@
    * Returns ConfigMatchingProvider instances corresponding to the configurable attribute keys
    * present in this rule's attributes.
    */
-  private Set<ConfigMatchingProvider> getConfigurableAttributeKeysForTesting(
+  private ImmutableMap<Label, ConfigMatchingProvider> getConfigurableAttributeKeysForTesting(
       EventHandler eventHandler, TargetAndConfiguration ctg) {
     if (!(ctg.getTarget() instanceof Rule)) {
-      return ImmutableSet.of();
+      return ImmutableMap.of();
     }
     Rule rule = (Rule) ctg.getTarget();
-    ImmutableSet.Builder<ConfigMatchingProvider> keys = ImmutableSet.builder();
+    ImmutableMap.Builder<Label, ConfigMatchingProvider> keys = ImmutableMap.builder();
     RawAttributeMapper mapper = RawAttributeMapper.of(rule);
     for (Attribute attribute : rule.getAttributes()) {
       for (Label label : mapper.getConfigurabilityKeys(attribute.getName(), attribute.getType())) {
@@ -809,7 +809,7 @@
         }
         ConfiguredTarget ct = getConfiguredTargetForTesting(
             eventHandler, label, ctg.getConfiguration());
-        keys.add(Preconditions.checkNotNull(ct.getProvider(ConfigMatchingProvider.class)));
+        keys.put(label, Preconditions.checkNotNull(ct.getProvider(ConfigMatchingProvider.class)));
       }
     }
     return keys.build();
@@ -876,7 +876,7 @@
             .setVisibility(NestedSetBuilder.<PackageSpecification>create(
                 Order.STABLE_ORDER, PackageSpecification.EVERYTHING))
             .setPrerequisites(getPrerequisiteMapForTesting(eventHandler, target, configurations))
-            .setConfigConditions(ImmutableSet.<ConfigMatchingProvider>of())
+            .setConfigConditions(ImmutableMap.<Label, ConfigMatchingProvider>of())
             .setUniversalFragment(ruleClassProvider.getUniversalFragment())
             .build();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
index 16f8f60..ecf25bd 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.analysis.actions.FileWriteAction;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.rules.AliasProvider;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
@@ -115,7 +116,7 @@
     }
 
     for (TransitiveInfoCollection dep : tools) { // (Note: host configuration)
-      Label label = dep.getLabel();
+      Label label = AliasProvider.getDependencyLabel(dep);
       FilesToRunProvider tool = dep.getProvider(FilesToRunProvider.class);
       if (tool == null) {
         continue;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java
index 87e1fad..2974c3a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapper.java
@@ -59,14 +59,11 @@
   private final Map<Label, ConfigMatchingProvider> configConditions;
   private Rule rule;
 
-  private ConfiguredAttributeMapper(Rule rule, Set<ConfigMatchingProvider> configConditions) {
+  private ConfiguredAttributeMapper(Rule rule,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions) {
     super(Preconditions.checkNotNull(rule).getPackage(), rule.getRuleClassObject(), rule.getLabel(),
         rule.getAttributeContainer());
-    ImmutableMap.Builder<Label, ConfigMatchingProvider> builder = ImmutableMap.builder();
-    for (ConfigMatchingProvider configCondition : configConditions) {
-      builder.put(configCondition.label(), configCondition);
-    }
-    this.configConditions = builder.build();
+    this.configConditions = configConditions;
     this.rule = rule;
   }
 
@@ -86,7 +83,7 @@
    */
   @VisibleForTesting
   public static ConfiguredAttributeMapper of(
-      Rule rule, Set<ConfigMatchingProvider> configConditions) {
+      Rule rule, ImmutableMap<Label, ConfigMatchingProvider> configConditions) {
     return new ConfiguredAttributeMapper(rule, configConditions);
   }
 
@@ -154,8 +151,12 @@
         continue;
       }
 
-      ConfigMatchingProvider curCondition = Verify.verifyNotNull(configConditions.get(
-          rule.getLabel().resolveRepositoryRelative(selectorKey)));
+      ConfigMatchingProvider curCondition = configConditions.get(
+          rule.getLabel().resolveRepositoryRelative(selectorKey));
+      if (curCondition == null) {
+        // This can happen if the rule is in error
+        continue;
+      }
       conditionLabels.add(curCondition.label());
 
       if (curCondition.matches()) {
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 39a0e67..5e39341 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
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.analysis;
 
 import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
@@ -164,7 +165,7 @@
   public final ConfiguredTarget createConfiguredTarget(AnalysisEnvironment analysisEnvironment,
       ArtifactFactory artifactFactory, Target target, BuildConfiguration config,
       BuildConfiguration hostConfig, ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      Set<ConfigMatchingProvider> configConditions)
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws InterruptedException {
     if (target instanceof Rule) {
       return createRule(analysisEnvironment, (Rule) target, config, hostConfig,
@@ -219,7 +220,7 @@
       AnalysisEnvironment env, Rule rule, BuildConfiguration configuration,
       BuildConfiguration hostConfiguration,
       ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      Set<ConfigMatchingProvider> configConditions) throws InterruptedException {
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
     // Visibility computation and checking is done for every rule.
     RuleContext ruleContext =
         new RuleContext.Builder(
@@ -303,7 +304,7 @@
       ConfiguredAspectFactory aspectFactory,
       Aspect aspect,
       ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      Set<ConfigMatchingProvider> configConditions,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       BuildConfiguration aspectConfiguration,
       BuildConfiguration hostConfiguration)
       throws InterruptedException {
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 107a0fc..f71f853 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Sets;
@@ -84,7 +85,7 @@
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       Aspect aspect,
-      Set<ConfigMatchingProvider> configConditions)
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws EvalException, InterruptedException {
     NestedSetBuilder<Label> rootCauses = NestedSetBuilder.<Label>stableOrder();
     ListMultimap<Attribute, Dependency> outgoingEdges =
@@ -118,7 +119,7 @@
       TargetAndConfiguration node,
       BuildConfiguration hostConfig,
       Aspect aspect,
-      Set<ConfigMatchingProvider> configConditions,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Label> rootCauses)
       throws EvalException, InterruptedException {
     Target target = node.getTarget();
@@ -155,7 +156,8 @@
 
   private ListMultimap<Attribute, LabelAndConfiguration> resolveAttributes(
       Rule rule, AspectDefinition aspect, BuildConfiguration configuration,
-      BuildConfiguration hostConfiguration, Set<ConfigMatchingProvider> configConditions)
+      BuildConfiguration hostConfiguration,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions)
       throws EvalException, InterruptedException {
     ConfiguredAttributeMapper attributeMap = ConfiguredAttributeMapper.of(rule, configConditions);
     attributeMap.validateAttributes();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/LicensesProviderImpl.java b/src/main/java/com/google/devtools/build/lib/analysis/LicensesProviderImpl.java
index 99c2124..0952d69 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/LicensesProviderImpl.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/LicensesProviderImpl.java
@@ -14,10 +14,13 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.License;
+import com.google.devtools.build.lib.packages.Rule;
 
 /**
  * A {@link ConfiguredTarget} that has licensed targets in its transitive closure.
@@ -33,6 +36,38 @@
     this.transitiveLicenses = transitiveLicenses;
   }
 
+  /**
+   * Create the appropriate {@link LicensesProvider} for a rule based on its {@code RuleContext}
+   */
+  public static LicensesProvider of(RuleContext ruleContext) {
+    if (!ruleContext.getConfiguration().checkLicenses()) {
+      return EMPTY;
+    }
+
+    NestedSetBuilder<TargetLicense> builder = NestedSetBuilder.linkOrder();
+    BuildConfiguration configuration = ruleContext.getConfiguration();
+    Rule rule = ruleContext.getRule();
+    License toolOutputLicense = rule.getToolOutputLicense(ruleContext.attributes());
+    if (configuration.isHostConfiguration() && toolOutputLicense != null) {
+      if (toolOutputLicense != License.NO_LICENSE) {
+        builder.add(new TargetLicense(rule.getLabel(), toolOutputLicense));
+      }
+    } else {
+      if (rule.getLicense() != License.NO_LICENSE) {
+        builder.add(new TargetLicense(rule.getLabel(), rule.getLicense()));
+      }
+
+      for (TransitiveInfoCollection dep : ruleContext.getConfiguredTargetMap().values()) {
+        LicensesProvider provider = dep.getProvider(LicensesProvider.class);
+        if (provider != null) {
+          builder.addTransitive(provider.getTransitiveLicenses());
+        }
+      }
+    }
+
+    return new LicensesProviderImpl(builder.build());
+  }
+
   @Override
   public NestedSet<TargetLicense> getTransitiveLicenses() {
     return transitiveLicenses;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java b/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
index 9761d6a2..be14f5d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/LocationExpander.java
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.OutputFile;
+import com.google.devtools.build.lib.rules.AliasProvider;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.ArrayList;
@@ -283,7 +284,7 @@
     if (ruleContext.getRule().isAttrDefined("srcs", BuildType.LABEL_LIST)) {
       for (TransitiveInfoCollection src : ruleContext
           .getPrerequisitesIf("srcs", Mode.TARGET, FileProvider.class)) {
-        Iterables.addAll(mapGet(locationMap, src.getLabel()),
+        Iterables.addAll(mapGet(locationMap, AliasProvider.getDependencyLabel(src)),
             src.getProvider(FileProvider.class).getFilesToBuild());
       }
     }
@@ -305,7 +306,7 @@
     }
 
     for (TransitiveInfoCollection dep : depsDataAndTools) {
-      Label label = dep.getLabel();
+      Label label = AliasProvider.getDependencyLabel(dep);
       FilesToRunProvider filesToRun = dep.getProvider(FilesToRunProvider.class);
       Artifact executableArtifact = filesToRun.getExecutable();
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java b/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java
index a51d203..c0bcfba 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RedirectChaser.java
@@ -86,9 +86,8 @@
         }
         Label newLabel = getFilegroupRedirect(possibleRedirect);
         if (newLabel == null) {
-          newLabel = getBindRedirect(possibleRedirect);
+          newLabel = getBindOrAliasRedirect(possibleRedirect);
         }
-
         if (newLabel == null) {
           return label;
         }
@@ -128,13 +127,14 @@
     return labels.get(0);
   }
 
-  private static Label getBindRedirect(Target target) throws InvalidConfigurationException {
+  private static Label getBindOrAliasRedirect(Target target)
+      throws InvalidConfigurationException {
     if (!(target instanceof Rule)) {
       return null;
     }
 
     Rule rule = (Rule) target;
-    if (!rule.getRuleClass().equals("bind")) {
+    if (!rule.getRuleClass().equals("bind") && !rule.getRuleClass().equals("alias")) {
       return null;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTarget.java
index 211097f..f1980ec 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTarget.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
 import com.google.devtools.build.lib.analysis.config.RunUnder;
+import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.rules.SkylarkApiProvider;
@@ -25,7 +26,6 @@
 
 import java.util.LinkedHashMap;
 import java.util.Map;
-import java.util.Set;
 
 /**
  * A generic implementation of RuleConfiguredTarget. Do not use directly. Use {@link
@@ -45,7 +45,7 @@
   }
 
   private final ImmutableMap<Class<? extends TransitiveInfoProvider>, Object> providers;
-  private final Set<ConfigMatchingProvider> configConditions;
+  private final ImmutableMap<Label, ConfigMatchingProvider> configConditions;
 
   RuleConfiguredTarget(RuleContext ruleContext,
       ImmutableMap<String, Object> skylarkProviders,
@@ -93,7 +93,7 @@
   /**
    * The configuration conditions that trigger this rule's configurable attributes.
    */
-  Set<ConfigMatchingProvider> getConfigConditions() {
+  ImmutableMap<Label, ConfigMatchingProvider> getConfigConditions() {
     return configConditions;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
index ab7bdaf..b6fd29c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
@@ -20,8 +20,6 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.analysis.LicensesProvider.TargetLicense;
-import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.constraints.ConstraintSemantics;
 import com.google.devtools.build.lib.analysis.constraints.EnvironmentCollection;
 import com.google.devtools.build.lib.analysis.constraints.SupportedEnvironments;
@@ -30,8 +28,6 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.events.Location;
-import com.google.devtools.build.lib.packages.License;
-import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.rules.test.ExecutionInfoProvider;
 import com.google.devtools.build.lib.rules.test.InstrumentedFilesProvider;
@@ -67,7 +63,7 @@
 
   public RuleConfiguredTargetBuilder(RuleContext ruleContext) {
     this.ruleContext = ruleContext;
-    add(LicensesProvider.class, initializeLicensesProvider());
+    add(LicensesProvider.class, LicensesProviderImpl.of(ruleContext));
     add(VisibilityProvider.class, new VisibilityProviderImpl(ruleContext.getVisibility()));
   }
 
@@ -215,35 +211,6 @@
     return new TestProvider(testParams, testTags);
   }
 
-  private LicensesProvider initializeLicensesProvider() {
-    if (!ruleContext.getConfiguration().checkLicenses()) {
-      return LicensesProviderImpl.EMPTY;
-    }
-
-    NestedSetBuilder<TargetLicense> builder = NestedSetBuilder.linkOrder();
-    BuildConfiguration configuration = ruleContext.getConfiguration();
-    Rule rule = ruleContext.getRule();
-    License toolOutputLicense = rule.getToolOutputLicense(ruleContext.attributes());
-    if (configuration.isHostConfiguration() && toolOutputLicense != null) {
-      if (toolOutputLicense != License.NO_LICENSE) {
-        builder.add(new TargetLicense(rule.getLabel(), toolOutputLicense));
-      }
-    } else {
-      if (rule.getLicense() != License.NO_LICENSE) {
-        builder.add(new TargetLicense(rule.getLabel(), rule.getLicense()));
-      }
-
-      for (TransitiveInfoCollection dep : ruleContext.getConfiguredTargetMap().values()) {
-        LicensesProvider provider = dep.getProvider(LicensesProvider.class);
-        if (provider != null) {
-          builder.addTransitive(provider.getTransitiveLicenses());
-        }
-      }
-    }
-
-    return new LicensesProviderImpl(builder.build());
-  }
-
   private <T extends TransitiveInfoProvider> T findProvider(Class<T> clazz) {
     return clazz.cast(providers.get(clazz));
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index 1bf1926..b22cc12 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -68,6 +68,7 @@
 import com.google.devtools.build.lib.packages.RuleErrorConsumer;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TargetUtils;
+import com.google.devtools.build.lib.rules.AliasProvider;
 import com.google.devtools.build.lib.rules.fileset.FilesetProvider;
 import com.google.devtools.build.lib.shell.ShellUtils;
 import com.google.devtools.build.lib.syntax.EvalException;
@@ -143,7 +144,7 @@
   private final Rule rule;
   private final ListMultimap<String, ConfiguredTarget> targetMap;
   private final ListMultimap<String, ConfiguredFilesetEntry> filesetEntryMap;
-  private final Set<ConfigMatchingProvider> configConditions;
+  private final ImmutableMap<Label, ConfigMatchingProvider> configConditions;
   private final AttributeMap attributes;
   private final ImmutableSet<String> features;
   private final String ruleClassNameForLogging;
@@ -165,7 +166,7 @@
       AttributeMap attributes,
       ListMultimap<String, ConfiguredTarget> targetMap,
       ListMultimap<String, ConfiguredFilesetEntry> filesetEntryMap,
-      Set<ConfigMatchingProvider> configConditions,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       Class<? extends BuildConfiguration.Fragment> universalFragment,
       String ruleClassNameForLogging,
       ImmutableMap<String, Attribute> aspectAttributes) {
@@ -247,7 +248,7 @@
   /**
    * The configuration conditions that trigger this rule's configurable attributes.
    */
-  Set<ConfigMatchingProvider> getConfigConditions() {
+  ImmutableMap<Label, ConfigMatchingProvider> getConfigConditions() {
     return configConditions;
   }
 
@@ -1317,7 +1318,7 @@
     @Nullable private final String aspectName;
     private final ErrorReporter reporter;
     private ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap;
-    private Set<ConfigMatchingProvider> configConditions;
+    private ImmutableMap<Label, ConfigMatchingProvider> configConditions;
     private NestedSet<PackageSpecification> visibility;
     private ImmutableMap<String, Attribute> aspectAttributes;
     private ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>> skylarkProviderRegistry;
@@ -1390,7 +1391,7 @@
      * Sets the configuration conditions needed to determine which paths to follow for this
      * rule's configurable attributes.
      */
-    Builder setConfigConditions(Set<ConfigMatchingProvider> configConditions) {
+    Builder setConfigConditions(ImmutableMap<Label, ConfigMatchingProvider> configConditions) {
       this.configConditions = Preconditions.checkNotNull(configConditions);
       return this;
     }
@@ -1447,7 +1448,7 @@
      * on a PrerequisiteMap instance.
      */
     private ListMultimap<String, ConfiguredFilesetEntry> createFilesetEntryMap(
-        final Rule rule, Set<ConfigMatchingProvider> configConditions) {
+        final Rule rule, ImmutableMap<Label, ConfigMatchingProvider> configConditions) {
       final ImmutableSortedKeyListMultimap.Builder<String, ConfiguredFilesetEntry> mapBuilder =
           ImmutableSortedKeyListMultimap.builder();
       for (Attribute attr : rule.getAttributes()) {
@@ -1544,16 +1545,18 @@
     }
 
     private void reportBadPrerequisite(Attribute attribute, String targetKind,
-        Label prerequisiteLabel, String reason, boolean isWarning) {
+        ConfiguredTarget prerequisite, String reason, boolean isWarning) {
       String msgPrefix = targetKind != null ? targetKind + " " : "";
       String msgReason = reason != null ? " (" + reason + ")" : "";
       if (isWarning) {
         attributeWarning(attribute.getName(), String.format(
-            "%s'%s' is unexpected here%s; continuing anyway",
-            msgPrefix, prerequisiteLabel, msgReason));
+            "%s'%s'%s is unexpected here%s; continuing anyway",
+            msgPrefix, prerequisite.getLabel(), AliasProvider.printVisibilityChain(prerequisite),
+            msgReason));
       } else {
         attributeError(attribute.getName(), String.format(
-            "%s'%s' is misplaced here%s", msgPrefix, prerequisiteLabel, msgReason));
+            "%s'%s'%s is misplaced here%s", msgPrefix, prerequisite.getLabel(),
+            AliasProvider.printVisibilityChain(prerequisite), msgReason));
       }
     }
 
@@ -1568,7 +1571,7 @@
         String reason = attribute.getValidityPredicate().checkValid(rule, prerequisiteRule);
         if (reason != null) {
           reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(),
-              prerequisiteLabel, reason, false);
+              prerequisite, reason, false);
         }
       }
 
@@ -1593,7 +1596,7 @@
               }
             } else {
               // The file exists but has a bad extension
-              reportBadPrerequisite(attribute, "file", prerequisiteLabel,
+              reportBadPrerequisite(attribute, "file", prerequisite,
                   "expected " + attribute.getAllowedFileTypesPredicate(), false);
             }
           }
@@ -1752,7 +1755,7 @@
           != Predicates.<RuleClass>alwaysTrue()) {
         allowedWithWarning = attribute.getAllowedRuleClassesWarningPredicate().apply(ruleClass);
         if (allowedWithWarning) {
-          reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisiteLabel,
+          reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisite,
               "expected " + attribute.getAllowedRuleClassesPredicate(), true);
           return;
         }
@@ -1777,7 +1780,7 @@
                   + missingMandatoryProviders);
         }
       } else if (Boolean.FALSE.equals(allowed)) {
-        reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisiteLabel,
+        reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisite,
             "expected " + attribute.getAllowedRuleClassesPredicate(), false);
       }
     }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
index f2f909a..72cfe3c 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelRuleClassProvider.java
@@ -76,6 +76,8 @@
 import com.google.devtools.build.lib.packages.PackageGroup;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.rules.Alias.AliasRule;
+import com.google.devtools.build.lib.rules.AliasProvider;
 import com.google.devtools.build.lib.rules.android.AndroidBinaryOnlyRule;
 import com.google.devtools.build.lib.rules.android.AndroidConfiguration;
 import com.google.devtools.build.lib.rules.android.AndroidLibraryBaseRule;
@@ -198,10 +200,12 @@
         } else {
           // Oddly enough, we use reportError rather than ruleError here.
           context.reportError(rule.getLocation(),
-              String.format("Target '%s' is not visible from target '%s'. Check "
+              String.format("Target '%s' is not visible from target '%s'%s. Check "
                   + "the visibility declaration of the former target if you think "
                   + "the dependency is legitimate",
-                  prerequisiteLabel, rule.getLabel()));
+                  prerequisiteLabel,
+                  rule.getLabel(),
+                  AliasProvider.printVisibilityChain(prerequisite)));
         }
       }
 
@@ -305,6 +309,7 @@
     builder.addRuleDefinition(new ConfigRuleClasses.ConfigBaseRule());
     builder.addRuleDefinition(new ConfigRuleClasses.ConfigSettingRule());
 
+    builder.addRuleDefinition(new AliasRule());
     builder.addRuleDefinition(new BazelFilegroupRule());
     builder.addRuleDefinition(new BazelTestSuiteRule());
     builder.addRuleDefinition(new BazelGenRuleRule());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/Alias.java b/src/main/java/com/google/devtools/build/lib/rules/Alias.java
new file mode 100644
index 0000000..540bcc9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/rules/Alias.java
@@ -0,0 +1,120 @@
+// Copyright 2016 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.rules;
+
+import static com.google.devtools.build.lib.packages.Attribute.ANY_RULE;
+import static com.google.devtools.build.lib.packages.Attribute.attr;
+import static com.google.devtools.build.lib.packages.BuildType.LABEL;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.analysis.BaseRuleClasses;
+import com.google.devtools.build.lib.analysis.ConfiguredTarget;
+import com.google.devtools.build.lib.analysis.LicensesProvider;
+import com.google.devtools.build.lib.analysis.LicensesProviderImpl;
+import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
+import com.google.devtools.build.lib.analysis.RuleContext;
+import com.google.devtools.build.lib.analysis.RuleDefinition;
+import com.google.devtools.build.lib.analysis.RuleDefinitionEnvironment;
+import com.google.devtools.build.lib.analysis.VisibilityProvider;
+import com.google.devtools.build.lib.analysis.VisibilityProviderImpl;
+import com.google.devtools.build.lib.packages.RuleClass;
+import com.google.devtools.build.lib.packages.RuleClass.Builder;
+import com.google.devtools.build.lib.util.FileTypeSet;
+
+/**
+ * Implementation of the <code>alias</code> rule.
+ */
+public class Alias implements RuleConfiguredTargetFactory {
+  @Override
+  public ConfiguredTarget create(RuleContext ruleContext) throws InterruptedException {
+    ConfiguredTarget actual = (ConfiguredTarget) ruleContext.getPrerequisite("actual", Mode.TARGET);
+    return new AliasConfiguredTarget(
+        actual,
+        ImmutableMap.of(
+            AliasProvider.class, AliasProvider.fromAliasRule(ruleContext.getLabel(), actual),
+            VisibilityProvider.class, new VisibilityProviderImpl(ruleContext.getVisibility()),
+            LicensesProvider.class, LicensesProviderImpl.of(ruleContext)));
+  }
+
+  /**
+   * Rule definition.
+   */
+  public static class AliasRule implements RuleDefinition {
+    @Override
+    public RuleClass build(Builder builder, RuleDefinitionEnvironment environment) {
+      return builder
+          /*<!-- #BLAZE_RULE(alias).ATTRIBUTE(actual) -->
+          The target this alias refers to. It does not need to be a rule, it can also be an input
+          file.
+          <!-- #END_BLAZE_RULE.ATTRIBUTE -->*/
+          .add(attr("actual", LABEL)
+              .allowedFileTypes(FileTypeSet.ANY_FILE)
+              .allowedRuleClasses(ANY_RULE)
+              .mandatory())
+          .build();
+    }
+
+    @Override
+    public Metadata getMetadata() {
+      return Metadata.builder()
+          .name("alias")
+          .factoryClass(Alias.class)
+          .ancestors(BaseRuleClasses.BaseRule.class)
+          .build();
+    }
+  }
+}
+
+/*<!-- #BLAZE_RULE (NAME = alias, TYPE = OTHER, FAMILY = General)[GENERIC_RULE] -->
+
+<p>
+  The <code>alias</code> rule creates another name a rule can be referred to as.
+</p>
+
+<p>
+  Aliasing only works for "regular" targets. In particular, <code>package_group</code>,
+    <code>config_setting</code> and <code>test_suite</code> rules cannot be aliased.
+</p>
+
+<p>
+  The alias rule has its own visibility and license declaration. In all other respects, it behaves
+  like the rule it references with some minor exceptions:
+
+  <ul>
+    <li>
+      Tests are not run if their alias is mentioned on the command line
+    </li>
+    <li>
+      When defining environment groups, the aliases to <code>environment</code> rules are not
+      supported. They are not supported in the <code>--target_environment</code> command line
+      option, either.
+    </li>
+  </ul>
+</p>
+
+<h4 id="alias_example">Examples</h4>
+
+<pre class="code">
+filegroup(
+    name = "data",
+    srcs = ["data.txt"],
+)
+
+alias(
+    name = 'other',
+    actual = ':data',
+)
+</pre>
+
+<!-- #END_BLAZE_RULE -->*/
diff --git a/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java
new file mode 100644
index 0000000..c7d2387
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java
@@ -0,0 +1,111 @@
+// Copyright 2016 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.rules;
+
+import com.google.common.collect.ImmutableCollection;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.analysis.ConfiguredTarget;
+import com.google.devtools.build.lib.analysis.FileProvider;
+import com.google.devtools.build.lib.analysis.SkylarkProviders;
+import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.collect.nestedset.Order;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.ClassObject;
+import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
+
+/**
+ * This configured target pretends to be whatever type of target "actual" is, returning its
+ * transitive info providers and target, but returning its own label.
+ *
+ * <p>Transitive info providers can also be overridden.
+ */
+@Immutable
+public final class AliasConfiguredTarget implements ConfiguredTarget, ClassObject {
+  private final ConfiguredTarget configuredTarget;
+  private final ImmutableMap<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider>
+      overrides;
+
+  public AliasConfiguredTarget(ConfiguredTarget actual,
+      ImmutableMap<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> overrides) {
+    configuredTarget = actual;
+    this.overrides = overrides;
+  }
+
+  @Override
+  public <P extends TransitiveInfoProvider> P getProvider(Class<P> provider) {
+    if (overrides.containsKey(provider)) {
+      return provider.cast(overrides.get(provider));
+    }
+
+    return configuredTarget == null ? null : configuredTarget.getProvider(provider);
+  }
+
+  @Override
+  public Label getLabel() {
+    return configuredTarget.getLabel();
+  }
+
+  @Override
+  public Object get(String providerKey) {
+    return configuredTarget == null ? null : configuredTarget.get(providerKey);
+  }
+
+  @Override
+  public Target getTarget() {
+    return configuredTarget == null ? null : configuredTarget.getTarget();
+  }
+
+  @Override
+  public BuildConfiguration getConfiguration() {
+    return configuredTarget.getConfiguration();
+  }
+
+  /* ClassObject methods */
+
+  @Override
+  public Object getValue(String name) {
+    if (name.equals("label")) {
+      return getLabel();
+    } else if (name.equals("files")) {
+      // A shortcut for files to build in Skylark. FileConfiguredTarget and RunleConfiguredTarget
+      // always has FileProvider and Error- and PackageGroupConfiguredTarget-s shouldn't be
+      // accessible in Skylark.
+      return SkylarkNestedSet.of(Artifact.class, configuredTarget == null
+          ? NestedSetBuilder.<Artifact>emptySet(Order.STABLE_ORDER)
+          : getProvider(FileProvider.class).getFilesToBuild());
+    }
+    return configuredTarget == null ? null : configuredTarget.get(name);
+  }
+
+  @Override
+  public ImmutableCollection<String> getKeys() {
+    ImmutableList.Builder<String> result = ImmutableList.<String>builder().add("label", "files");
+    if (configuredTarget != null) {
+        result.addAll(configuredTarget.getProvider(SkylarkProviders.class).getKeys());
+    }
+    return result.build();
+  }
+
+  @Override
+  public String errorMessage(String name) {
+    // Use the default error message.
+    return null;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/AliasProvider.java b/src/main/java/com/google/devtools/build/lib/rules/AliasProvider.java
new file mode 100644
index 0000000..a6950b2
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/rules/AliasProvider.java
@@ -0,0 +1,79 @@
+// Copyright 2016 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.rules;
+
+import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.analysis.ConfiguredTarget;
+import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
+import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.util.Preconditions;
+
+/**
+ * A provider that gives information about the aliases a rule was resolved through.
+ */
+@Immutable
+public final class AliasProvider implements TransitiveInfoProvider {
+  // We don't expect long alias chains, so it's better to have a list instead of a nested set
+  private final ImmutableList<Label> aliasChain;
+
+  public AliasProvider(ImmutableList<Label> aliasChain) {
+    Preconditions.checkState(!aliasChain.isEmpty());
+    this.aliasChain = aliasChain;
+  }
+
+  public static AliasProvider fromAliasRule(Label label, ConfiguredTarget actual) {
+    ImmutableList.Builder<Label> chain = ImmutableList.builder();
+    chain.add(label);
+    AliasProvider dep = actual.getProvider(AliasProvider.class);
+    if (dep != null) {
+      chain.addAll(dep.getAliasChain());
+    }
+
+    return new AliasProvider(chain.build());
+  }
+
+  /**
+   * Returns the label by which it was referred to in the BUILD file.
+   *
+   * <p>For non-alias rules, it's the label of the rule itself, for alias rules, it's the label of
+   * the alias rule.
+   */
+  public static Label getDependencyLabel(TransitiveInfoCollection dep) {
+    AliasProvider aliasProvider = dep.getProvider(AliasProvider.class);
+    return aliasProvider != null
+        ? aliasProvider.getAliasChain().get(0)
+        : dep.getLabel();
+  }
+
+  /**
+   * Returns the list of aliases from top to bottom (i.e. the last alias depends on the actual
+   * resolved target and the first alias is the one that was in the attribute of the rule currently
+   * being analyzed)
+   */
+  public ImmutableList<Label> getAliasChain() {
+    return aliasChain;
+  }
+
+  public static String printVisibilityChain(ConfiguredTarget target) {
+    AliasProvider aliasProvider = target.getProvider(AliasProvider.class);
+    if (aliasProvider == null) {
+      return "";
+    }
+
+    return " (aliased through '" + Joiner.on("' -> '").join(aliasProvider.getAliasChain()) + "')";
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
index 44f637f..ffe2fca 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
@@ -372,7 +372,7 @@
 
     for (AbstractConfiguredTarget current : knownLabels) {
       builder.put(
-          current.getLabel(),
+          AliasProvider.getDependencyLabel(current),
           ImmutableList.copyOf(current.getProvider(FileProvider.class).getFilesToBuild()));
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java b/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java
index 6ea3ede..a832903 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/repository/Bind.java
@@ -14,107 +14,20 @@
 
 package com.google.devtools.build.lib.rules.repository;
 
-import com.google.common.collect.ImmutableCollection;
-import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.actions.Artifact;
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.FileProvider;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
 import com.google.devtools.build.lib.analysis.RuleContext;
-import com.google.devtools.build.lib.analysis.SkylarkProviders;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
-import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
-import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
-import com.google.devtools.build.lib.collect.nestedset.Order;
-import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.rules.AliasConfiguredTarget;
+import com.google.devtools.build.lib.rules.AliasProvider;
 import com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory;
-import com.google.devtools.build.lib.syntax.ClassObject;
-import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
 /**
  * Implementation for the bind rule.
  */
 public class Bind implements RuleConfiguredTargetFactory {
 
-  /**
-   * This configured target pretends to be whatever type of target "actual" is, returning its
-   * transitive info providers and target, but returning the label for the //external target.
-   */
-  private static class BindConfiguredTarget implements ConfiguredTarget, ClassObject {
-
-    private Label label;
-    private ConfiguredTarget configuredTarget;
-    private BuildConfiguration config;
-
-    BindConfiguredTarget(RuleContext ruleContext) {
-      label = ruleContext.getRule().getLabel();
-      config = ruleContext.getConfiguration();
-      // TODO(bazel-team): we should special case ConfiguredTargetFactory.createConfiguredTarget,
-      // not cast down here.
-      configuredTarget = (ConfiguredTarget) ruleContext.getPrerequisite("actual", Mode.TARGET);
-    }
-
-    @Override
-    public <P extends TransitiveInfoProvider> P getProvider(Class<P> provider) {
-      return configuredTarget == null ? null : configuredTarget.getProvider(provider);
-    }
-
-    @Override
-    public Label getLabel() {
-      return label;
-    }
-
-    @Override
-    public Object get(String providerKey) {
-      return configuredTarget == null ? null : configuredTarget.get(providerKey);
-    }
-
-    @Override
-    public Target getTarget() {
-      return configuredTarget == null ? null : configuredTarget.getTarget();
-    }
-
-    @Override
-    public BuildConfiguration getConfiguration() {
-      return config;
-    }
-
-    /* ClassObject methods */
-
-    @Override
-    public Object getValue(String name) {
-      if (name.equals("label")) {
-        return getLabel();
-      } else if (name.equals("files")) {
-        // A shortcut for files to build in Skylark. FileConfiguredTarget and RunleConfiguredTarget
-        // always has FileProvider and Error- and PackageGroupConfiguredTarget-s shouldn't be
-        // accessible in Skylark.
-        return SkylarkNestedSet.of(Artifact.class, configuredTarget == null
-            ? NestedSetBuilder.<Artifact>emptySet(Order.STABLE_ORDER)
-            : getProvider(FileProvider.class).getFilesToBuild());
-      }
-      return configuredTarget == null ? null : configuredTarget.get(name);
-    }
-
-    @SuppressWarnings("cast")
-    @Override
-    public ImmutableCollection<String> getKeys() {
-      ImmutableList.Builder<String> result = ImmutableList.<String>builder().add("label", "files");
-      if (configuredTarget != null) {
-          result.addAll(
-              configuredTarget.getProvider(SkylarkProviders.class).getKeys());
-      }
-      return result.build();
-    }
-
-    @Override
-    public String errorMessage(String name) {
-      // Use the default error message.
-      return null;
-    }
-  }
-
   @Override
   public ConfiguredTarget create(RuleContext ruleContext) throws InterruptedException {
     if (ruleContext.getPrerequisite("actual", Mode.TARGET) == null) {
@@ -122,6 +35,10 @@
           ruleContext.getLabel()));
       return null;
     }
-    return new BindConfiguredTarget(ruleContext);
+
+    ConfiguredTarget actual = (ConfiguredTarget) ruleContext.getPrerequisite("actual", Mode.TARGET);
+    return new AliasConfiguredTarget(actual,
+        ImmutableMap.<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider>of(
+            AliasProvider.class, AliasProvider.fromAliasRule(ruleContext.getLabel(), actual)));
   }
 }
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 9bf225f..3917534 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
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.analysis.CachingAnalysisEnvironment;
@@ -57,8 +58,6 @@
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
-import java.util.Set;
-
 import javax.annotation.Nullable;
 
 /**
@@ -212,9 +211,10 @@
         new TargetAndConfiguration(target, key.getAspectConfiguration());
     try {
       // Get the configuration targets that trigger this rule's configurable attributes.
-      Set<ConfigMatchingProvider> configConditions = ConfiguredTargetFunction.getConfigConditions(
-          target, env, resolver, originalTargetAndAspectConfiguration,
-          transitivePackages, transitiveRootCauses);
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions =
+          ConfiguredTargetFunction.getConfigConditions(
+              target, env, resolver, originalTargetAndAspectConfiguration,
+              transitivePackages, transitiveRootCauses);
       if (configConditions == null) {
         // Those targets haven't yet been resolved.
         return null;
@@ -299,7 +299,7 @@
       ConfiguredAspectFactory aspectFactory,
       RuleConfiguredTarget associatedTarget,
       BuildConfiguration aspectConfiguration,
-      Set<ConfigMatchingProvider> configConditions,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       ListMultimap<Attribute, ConfiguredTarget> directDeps,
       NestedSetBuilder<Package> transitivePackages)
       throws AspectFunctionException, InterruptedException {
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 6fb86c8..33d68bb 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
@@ -17,7 +17,7 @@
 import com.google.common.base.Verify;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.LinkedListMultimap;
 import com.google.common.collect.ListMultimap;
@@ -54,7 +54,6 @@
 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.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
@@ -76,9 +75,9 @@
 import com.google.devtools.build.skyframe.ValueOrException2;
 
 import java.util.Collection;
-import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Objects;
@@ -92,8 +91,8 @@
 final class ConfiguredTargetFunction implements SkyFunction {
   // This construction is a bit funky, but guarantees that the Object reference here is globally
   // unique.
-  static final Set<ConfigMatchingProvider> NO_CONFIG_CONDITIONS =
-      Collections.unmodifiableSet(ImmutableSet.<ConfigMatchingProvider>of());
+  static final ImmutableMap<Label, ConfigMatchingProvider> NO_CONFIG_CONDITIONS =
+      ImmutableMap.<Label, ConfigMatchingProvider>of();
 
   /**
    * Exception class that signals an error during the evaluation of a dependency.
@@ -159,13 +158,7 @@
           new ConfiguredValueCreationException(e.getMessage()));
     }
     if (pkg.containsErrors()) {
-      if (target == null) {
-        throw new ConfiguredTargetFunctionException(new ConfiguredValueCreationException(
-            new BuildFileContainsErrorsException(
-                lc.getLabel().getPackageIdentifier()).getMessage()));
-      } else {
-        transitiveLoadingRootCauses.add(lc.getLabel());
-      }
+      transitiveLoadingRootCauses.add(lc.getLabel());
     }
     transitivePackages.add(pkg);
     // TODO(bazel-team): This is problematic - we create the right key, but then end up with a value
@@ -180,7 +173,7 @@
     SkyframeDependencyResolver resolver = view.createDependencyResolver(env);
     try {
       // Get the configuration targets that trigger this rule's configurable attributes.
-      Set<ConfigMatchingProvider> configConditions = getConfigConditions(
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions = getConfigConditions(
           ctgValue.getTarget(), env, resolver, ctgValue, transitivePackages,
           transitiveLoadingRootCauses);
       if (env.valuesMissing()) {
@@ -265,7 +258,7 @@
       SkyframeDependencyResolver resolver,
       TargetAndConfiguration ctgValue,
       Aspect aspect,
-      Set<ConfigMatchingProvider> configConditions,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       RuleClassProvider ruleClassProvider,
       BuildConfiguration hostConfiguration,
       NestedSetBuilder<Package> transitivePackages,
@@ -686,8 +679,8 @@
    * dependency resolver, returns null.
    */
   @Nullable
-  static Set<ConfigMatchingProvider> getConfigConditions(Target target, Environment env,
-      SkyframeDependencyResolver resolver, TargetAndConfiguration ctgValue,
+  static ImmutableMap<Label, ConfigMatchingProvider> getConfigConditions(Target target,
+      Environment env, SkyframeDependencyResolver resolver, TargetAndConfiguration ctgValue,
       NestedSetBuilder<Package> transitivePackages,
       NestedSetBuilder<Label> transitiveLoadingRootCauses)
       throws DependencyEvaluationException {
@@ -695,7 +688,7 @@
       return NO_CONFIG_CONDITIONS;
     }
 
-    ImmutableSet.Builder<ConfigMatchingProvider> configConditions = ImmutableSet.builder();
+    Map<Label, ConfigMatchingProvider> configConditions = new LinkedHashMap<>();
 
     // Collect the labels of the configured targets we need to resolve.
     ListMultimap<Attribute, LabelAndConfiguration> configLabelMap = ArrayListMultimap.create();
@@ -717,6 +710,10 @@
     // been computed yet.
     Collection<Dependency> configValueNames = resolver.resolveRuleLabels(
         ctgValue, configLabelMap, transitiveLoadingRootCauses);
+    if (env.valuesMissing()) {
+      return null;
+    }
+
 
     // No need to get new configs from Skyframe - config_setting rules always use the current
     // target's config.
@@ -744,7 +741,7 @@
       // The code above guarantees that value is non-null here.
       ConfigMatchingProvider provider = value.getProvider(ConfigMatchingProvider.class);
       if (provider != null) {
-        configConditions.add(provider);
+        configConditions.put(entry.getLabel(), provider);
       } else {
         // Not a valid provider for configuration conditions.
         String message =
@@ -755,7 +752,7 @@
       }
     }
 
-    return configConditions.build();
+    return ImmutableMap.copyOf(configConditions);
   }
 
   /***
@@ -813,7 +810,7 @@
   private ConfiguredTargetValue createConfiguredTarget(SkyframeBuildView view,
       Environment env, Target target, BuildConfiguration configuration,
       ListMultimap<Attribute, ConfiguredTarget> depValueMap,
-      Set<ConfigMatchingProvider> configConditions,
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions,
       NestedSetBuilder<Package> transitivePackages)
       throws ConfiguredTargetFunctionException, InterruptedException {
     StoredEventHandler events = new StoredEventHandler();
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 c33e599..3289d17 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
@@ -15,7 +15,6 @@
 
 import com.google.common.base.Function;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.ListMultimap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
@@ -90,7 +89,7 @@
     TargetAndConfiguration ctgValue =
         new TargetAndConfiguration(ct.getTarget(), ct.getConfiguration());
 
-    Set<ConfigMatchingProvider> configConditions =
+    ImmutableMap<Label, ConfigMatchingProvider> configConditions =
         getConfigurableAttributeConditions(ctgValue, env);
     if (configConditions == null) {
       return null;
@@ -131,10 +130,10 @@
    * target, or null if not all dependencies have yet been SkyFrame-evaluated.
    */
   @Nullable
-  private Set<ConfigMatchingProvider> getConfigurableAttributeConditions(
+  private ImmutableMap<Label, ConfigMatchingProvider> getConfigurableAttributeConditions(
       TargetAndConfiguration ctg, Environment env) {
     if (!(ctg.getTarget() instanceof Rule)) {
-      return ImmutableSet.of();
+      return ImmutableMap.of();
     }
     Rule rule = (Rule) ctg.getTarget();
     RawAttributeMapper mapper = RawAttributeMapper.of(rule);
@@ -150,10 +149,12 @@
     if (env.valuesMissing()) {
       return null;
     }
-    ImmutableSet.Builder<ConfigMatchingProvider> conditions = ImmutableSet.builder();
-    for (SkyValue ctValue : cts.values()) {
-      ConfiguredTarget ct = ((ConfiguredTargetValue) ctValue).getConfiguredTarget();
-      conditions.add(Preconditions.checkNotNull(ct.getProvider(ConfigMatchingProvider.class)));
+    ImmutableMap.Builder<Label, ConfigMatchingProvider> conditions = ImmutableMap.builder();
+    for (Map.Entry<SkyKey, SkyValue> entry : cts.entrySet()) {
+      Label label = ((ConfiguredTargetKey) entry.getKey().argument()).getLabel();
+      ConfiguredTarget ct = ((ConfiguredTargetValue) entry.getValue()).getConfiguredTarget();
+      conditions.put(label, Preconditions.checkNotNull(
+          ct.getProvider(ConfigMatchingProvider.class)));
     }
     return conditions.build();
   }
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 140dfbc..4231583 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
@@ -473,7 +473,7 @@
   ConfiguredTarget createConfiguredTarget(Target target, BuildConfiguration configuration,
       CachingAnalysisEnvironment analysisEnvironment,
       ListMultimap<Attribute, ConfiguredTarget> prerequisiteMap,
-      Set<ConfigMatchingProvider> configConditions) throws InterruptedException {
+      ImmutableMap<Label, ConfigMatchingProvider> configConditions) throws InterruptedException {
     Preconditions.checkState(enableAnalysis,
         "Already in execution phase %s %s", target, configuration);
     Preconditions.checkNotNull(analysisEnvironment);