diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java
index 718c67b..107e64b 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.PackageSpecification;
 import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.EvalException;
@@ -77,6 +78,15 @@
     return configuration;
   }
 
+  @Nullable
+  @Override
+  public Object get(SkylarkProviderIdentifier id) {
+    if (id.isLegacy()) {
+      return get(id.getLegacyId());
+    }
+    return get(id.getKey());
+  }
+
   @Override
   public Label getLabel() {
     return getTarget().getLabel();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/EnvironmentGroupConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/EnvironmentGroupConfiguredTarget.java
index 3465a1d..4a345f1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/EnvironmentGroupConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/EnvironmentGroupConfiguredTarget.java
@@ -15,7 +15,10 @@
 package com.google.devtools.build.lib.analysis;
 
 import com.google.devtools.build.lib.packages.EnvironmentGroup;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor.Key;
 import com.google.devtools.build.lib.util.Preconditions;
+import javax.annotation.Nullable;
 
 /**
  * Dummy ConfiguredTarget for environment groups. Contains no functionality, since
@@ -37,4 +40,11 @@
     // No providers.
     return null;
   }
+
+  @Nullable
+  @Override
+  public SkylarkClassObject get(Key providerKey) {
+    // No providers.
+    return null;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/FileConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/FileConfiguredTarget.java
index f55298f..3009d1d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/FileConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/FileConfiguredTarget.java
@@ -19,9 +19,12 @@
 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.FileTarget;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor.Key;
 import com.google.devtools.build.lib.rules.fileset.FilesetProvider;
 import com.google.devtools.build.lib.rules.test.InstrumentedFilesProvider;
 import com.google.devtools.build.lib.util.FileType;
+import javax.annotation.Nullable;
 
 /**
  * A ConfiguredTarget for a source FileTarget.  (Generated files use a
@@ -79,4 +82,10 @@
   public Object get(String providerKey) {
     return null;
   }
+
+  @Nullable
+  @Override
+  public SkylarkClassObject get(Key providerKey) {
+    return null;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java
index 4c03666..9a5317f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/MergedConfiguredTarget.java
@@ -14,9 +14,12 @@
 package com.google.devtools.build.lib.analysis;
 
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor.Key;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
+import javax.annotation.Nullable;
 
 /**
  * A single dependency with its configured target and aspects merged together.
@@ -40,6 +43,12 @@
     return getProvider(SkylarkProviders.class).getValue(providerKey);
   }
 
+  @Nullable
+  @Override
+  public SkylarkClassObject get(Key providerKey) {
+    return getProvider(SkylarkProviders.class).getDeclaredProvider(providerKey);
+  }
+
   @Override
   public <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass) {
     AnalysisUtils.checkProvider(providerClass);
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/PackageGroupConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/PackageGroupConfiguredTarget.java
index 549932d..c8b26b9 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/PackageGroupConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/PackageGroupConfiguredTarget.java
@@ -20,7 +20,10 @@
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.PackageGroup;
 import com.google.devtools.build.lib.packages.PackageSpecification;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor.Key;
 import com.google.devtools.build.lib.util.Preconditions;
+import javax.annotation.Nullable;
 
 /**
  * Dummy ConfiguredTarget for package groups. Contains no functionality, since
@@ -69,4 +72,11 @@
     // No providers.
     return null;
   }
+
+  @Nullable
+  @Override
+  public SkylarkClassObject get(Key providerKey) {
+    // No providers.
+    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 2879236..094b10f 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
@@ -21,6 +21,8 @@
 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.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor;
 import com.google.devtools.build.lib.util.Preconditions;
 import javax.annotation.Nullable;
 
@@ -108,6 +110,15 @@
     return getProvider(SkylarkProviders.class).getValue(providerKey);
   }
 
+  /**
+   * Returns a declared provider provided by this target. Only meant to use from Skylark.
+   */
+  @Override
+  public SkylarkClassObject get(SkylarkClassObjectConstructor.Key providerKey) {
+    return getProvider(SkylarkProviders.class).getDeclaredProvider(providerKey);
+  }
+
+
   @Override
   public final Rule getTarget() {
     return (Rule) super.getTarget();
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 49f1c92..5e6d506 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
@@ -70,6 +70,7 @@
 import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.packages.RuleErrorConsumer;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.rules.AliasProvider;
@@ -88,6 +89,7 @@
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -1788,16 +1790,17 @@
     }
 
     private String getMissingMandatoryProviders(ConfiguredTarget prerequisite, Attribute attribute){
-      List<ImmutableSet<String>> mandatoryProvidersList = attribute.getMandatoryProvidersList();
+      ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList
+          = attribute.getMandatoryProvidersList();
       if (mandatoryProvidersList.isEmpty()) {
         return null;
       }
       List<List<String>> missingProvidersList = new ArrayList<>();
-      for (ImmutableSet<String> providers : mandatoryProvidersList) {
+      for (ImmutableSet<SkylarkProviderIdentifier> providers : mandatoryProvidersList) {
         List<String> missing = new ArrayList<>();
-        for (String provider : providers) {
+        for (SkylarkProviderIdentifier provider : providers) {
           if (prerequisite.get(provider) == null) {
-            missing.add(provider);
+            missing.add(provider.toString());
           }
         }
         if (missing.isEmpty()) {
@@ -1864,30 +1867,36 @@
     private void validateRuleDependency(ConfiguredTarget prerequisite, Attribute attribute) {
       Target prerequisiteTarget = prerequisite.getTarget();
       RuleClass ruleClass = ((Rule) prerequisiteTarget).getRuleClassObject();
-      HashSet<String> unfulfilledRequirements = new HashSet<>();
+      String notAllowedRuleClassesMessage = null;
 
       if (attribute.getAllowedRuleClassesPredicate() != Predicates.<RuleClass>alwaysTrue()) {
         if (attribute.getAllowedRuleClassesPredicate().apply(ruleClass)) {
+          // prerequisite has an allowed rule class => accept.
           return;
         }
-        unfulfilledRequirements.add(badPrerequisiteMessage(prerequisiteTarget.getTargetKind(),
-            prerequisite, "expected " + attribute.getAllowedRuleClassesPredicate(), false));
+        // remember that the rule class that was not allowed;
+        // but maybe prerequisite provides required providers? do not reject yet.
+        notAllowedRuleClassesMessage =
+            badPrerequisiteMessage(
+                prerequisiteTarget.getTargetKind(),
+                prerequisite,
+                "expected " + attribute.getAllowedRuleClassesPredicate(),
+                false);
       }
 
-      if (attribute.getAllowedRuleClassesWarningPredicate()
-          != Predicates.<RuleClass>alwaysTrue()) {
+      if (attribute.getAllowedRuleClassesWarningPredicate() != Predicates.<RuleClass>alwaysTrue()) {
         Predicate<RuleClass> warningPredicate = attribute.getAllowedRuleClassesWarningPredicate();
         if (warningPredicate.apply(ruleClass)) {
           reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisite,
               "expected " + attribute.getAllowedRuleClassesPredicate(), true);
+          // prerequisite has a rule class allowed with a warning => accept, emitting a warning.
           return;
         }
       }
 
-      // This condition is required; getMissingMandatory[Native]Providers() would be vacuously true
-      // if no providers were mandatory (thus, none are missing), which would cause an early return
-      // below without emitting the error message about the not-allowed rule class if that
-      // requirement was unfulfilled.
+      // If we got there, we have no allowed rule class.
+      // If mandatory providers are specified, try them.
+      Set<String> unfulfilledRequirements = new LinkedHashSet<>();
       if (!attribute.getMandatoryNativeProvidersList().isEmpty()
           || !attribute.getMandatoryProvidersList().isEmpty()) {
         boolean hadAllMandatoryProviders = true;
@@ -1909,10 +1918,16 @@
         }
 
         if (hadAllMandatoryProviders) {
+          // all mandatory providers are present => accept.
           return;
         }
       }
 
+      // not allowed rule class and some mandatory providers missing => reject.
+      if (notAllowedRuleClassesMessage != null) {
+        unfulfilledRequirements.add(notAllowedRuleClassesMessage);
+      }
+
       if (!unfulfilledRequirements.isEmpty()) {
         attributeError(
             attribute.getName(), StringUtil.joinEnglishList(unfulfilledRequirements, "and"));
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java
index d1a9ece..7fd5d61 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java
@@ -16,6 +16,9 @@
 
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.syntax.SkylarkIndexable;
@@ -78,4 +81,20 @@
    * The transitive information has to have been added using the Skylark framework.
    */
   @Nullable Object get(String providerKey);
+
+  /**
+   * Returns the declared provider requested, or null, if the information is not found.
+   * The transitive information has to have been added using the Skylark framework.
+   */
+  @Nullable SkylarkClassObject get(SkylarkClassObjectConstructor.Key providerKey);
+
+  /**
+   * Returns the provider defined in Skylark, or null, if the information is not found.
+   * The transitive information has to have been added using the Skylark framework.
+   *
+   * This method dispatches to either {@link #get(SkylarkClassObjectConstructor.Key)} or
+   * {@link #get(String)} depending on whether {@link SkylarkProviderIdentifier} is for
+   * legacy or for declared provider.
+   */
+  @Nullable Object get(SkylarkProviderIdentifier id);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaRuleClasses.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaRuleClasses.java
index 4854530..2dd4172 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaRuleClasses.java
@@ -41,7 +41,9 @@
 import com.google.devtools.build.lib.packages.RuleClass.Builder;
 import com.google.devtools.build.lib.packages.RuleClass.Builder.RuleClassType;
 import com.google.devtools.build.lib.packages.RuleClass.PackageNameConstraint;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.packages.TriState;
+import com.google.devtools.build.lib.rules.cpp.CcLinkParamsProvider;
 import com.google.devtools.build.lib.rules.java.JavaSemantics;
 import com.google.devtools.build.lib.rules.java.JavaToolchainProvider;
 import com.google.devtools.build.lib.syntax.Type;
@@ -150,6 +152,8 @@
           .override(builder.copy("deps")
               .allowedFileTypes(JavaSemantics.JAR)
               .allowedRuleClasses(ALLOWED_RULES_IN_DEPS)
+              .mandatoryProviders(ImmutableList.of(
+                  SkylarkProviderIdentifier.forKey(CcLinkParamsProvider.CC_LINK_PARAMS.getKey())))
               .skipAnalysisTimeFileTypeCheck())
           /* <!-- #BLAZE_RULE($java_rule).ATTRIBUTE(runtime_deps) -->
           Libraries to make available to the final binary or test at runtime only.
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPyRuleClasses.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPyRuleClasses.java
index efc13ec9..41ec62c 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPyRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPyRuleClasses.java
@@ -59,7 +59,7 @@
           <a href="${link cc_library}"><code>cc_library</code></a> rules,
           <!-- #END_BLAZE_RULE.ATTRIBUTE --> */
           .override(builder.copy("deps")
-              .mandatoryProviders(ImmutableList.of(PyCommon.PYTHON_SKYLARK_PROVIDER_NAME))
+              .legacyMandatoryProviders(PyCommon.PYTHON_SKYLARK_PROVIDER_NAME)
               .allowedFileTypes())
           /* <!-- #BLAZE_RULE($base_py).ATTRIBUTE(imports) -->
           List of import directories to be added to the <code>PYTHONPATH</code>.
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Attribute.java b/src/main/java/com/google/devtools/build/lib/packages/Attribute.java
index aa28051..2a867ad 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Attribute.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Attribute.java
@@ -434,8 +434,8 @@
     private Predicate<AttributeMap> condition;
     private Set<PropertyFlag> propertyFlags = EnumSet.noneOf(PropertyFlag.class);
     private PredicateWithMessage<Object> allowedValues = null;
-    private ImmutableList<ImmutableSet<String>> mandatoryProvidersList =
-        ImmutableList.<ImmutableSet<String>>of();
+    private ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList =
+        ImmutableList.<ImmutableSet<SkylarkProviderIdentifier>>of();
     private ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
         mandatoryNativeProvidersList = ImmutableList.of();
     private HashMap<String, RuleAspect<?>> aspects = new LinkedHashMap<>();
@@ -905,20 +905,35 @@
     /**
      * Sets a list of sets of mandatory Skylark providers. Every configured target occurring in
      * this label type attribute has to provide all the providers from one of those sets,
-     * otherwise an error is produced during the analysis phase.
+     * or be one of {@link #allowedRuleClasses}, otherwise an error is produced during
+     * the analysis phase.
      */
-    public Builder<TYPE> mandatoryProvidersList(Iterable<? extends Iterable<String>> providersList){
+    public Builder<TYPE> mandatoryProvidersList(
+        Iterable<? extends Iterable<SkylarkProviderIdentifier>> providersList){
       Preconditions.checkState((type == BuildType.LABEL) || (type == BuildType.LABEL_LIST),
           "must be a label-valued type");
-      ImmutableList.Builder<ImmutableSet<String>> listBuilder = ImmutableList.builder();
-      for (Iterable<String> providers : providersList) {
+      ImmutableList.Builder<ImmutableSet<SkylarkProviderIdentifier>> listBuilder
+          = ImmutableList.builder();
+      for (Iterable<SkylarkProviderIdentifier> providers : providersList) {
         listBuilder.add(ImmutableSet.copyOf(providers));
       }
       this.mandatoryProvidersList = listBuilder.build();
       return this;
     }
 
-    public Builder<TYPE> mandatoryProviders(Iterable<String> providers) {
+    public Builder<TYPE> legacyMandatoryProviders(String... ids) {
+      return mandatoryProviders(
+          Iterables.transform(Arrays.asList(ids),
+              new Function<String, SkylarkProviderIdentifier>() {
+        @Override
+        public SkylarkProviderIdentifier apply(String s) {
+          Preconditions.checkNotNull(s);
+          return SkylarkProviderIdentifier.forLegacy(s);
+        }
+      }));
+    }
+
+    public Builder<TYPE> mandatoryProviders(Iterable<SkylarkProviderIdentifier> providers) {
       if (providers.iterator().hasNext()) {
         mandatoryProvidersList(ImmutableList.of(providers));
       }
@@ -1674,7 +1689,7 @@
 
   private final PredicateWithMessage<Object> allowedValues;
 
-  private final ImmutableList<ImmutableSet<String>> mandatoryProvidersList;
+  private final ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList;
 
   private final ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
       mandatoryNativeProvidersList;
@@ -1710,7 +1725,7 @@
       ValidityPredicate validityPredicate,
       Predicate<AttributeMap> condition,
       PredicateWithMessage<Object> allowedValues,
-      ImmutableList<ImmutableSet<String>> mandatoryProvidersList,
+      ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList,
       ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
           mandatoryNativeProvidersList,
       ImmutableList<RuleAspect<?>> aspects) {
@@ -1943,7 +1958,7 @@
   /**
    * Returns the list of sets of mandatory Skylark providers.
    */
-  public ImmutableList<ImmutableSet<String>> getMandatoryProvidersList() {
+  public ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> getMandatoryProvidersList() {
     return mandatoryProvidersList;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkClassObject.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkClassObject.java
index 7afcbd5..830021d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkClassObject.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkClassObject.java
@@ -32,6 +32,7 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import java.io.Serializable;
 import java.util.Map;
+import javax.annotation.Nullable;
 
 /** An implementation class of ClassObject for structs created in Skylark code. */
 @SkylarkModule(
@@ -128,6 +129,11 @@
     return constructor;
   }
 
+  @Nullable
+  public Location getCreationLocOrNull() {
+    return creationLoc;
+  }
+
   private static class StructConcatter implements Concatter {
     private static final StructConcatter INSTANCE = new StructConcatter();
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkProviderIdentifier.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkProviderIdentifier.java
new file mode 100644
index 0000000..f34dffd
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkProviderIdentifier.java
@@ -0,0 +1,106 @@
+// Copyright 2014 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.packages;
+
+import com.google.devtools.build.lib.util.Preconditions;
+import java.util.Objects;
+import javax.annotation.Nullable;
+
+/**
+ * A wrapper around Skylark provider identifier,
+ * representing either a declared provider ({@see SkylarkClassObjectConstructor})
+ * or a "legacy" string identifier.
+ */
+public final class SkylarkProviderIdentifier {
+
+  @Nullable
+  private final String legacyId;
+  @Nullable
+  private final SkylarkClassObjectConstructor.Key key;
+
+  /**
+   * Creates an id for a declared provider with a given key ({@see SkylarkClassObjectConstructor}).
+   */
+  public static SkylarkProviderIdentifier forKey(SkylarkClassObjectConstructor.Key key) {
+    return new SkylarkProviderIdentifier(key);
+  }
+
+  /**
+   * Creates an id for a provider with a given name.
+   */
+  public static SkylarkProviderIdentifier forLegacy(String legacyId) {
+    return new SkylarkProviderIdentifier(legacyId);
+  }
+
+  private SkylarkProviderIdentifier(String legacyId) {
+    this.legacyId = legacyId;
+    this.key = null;
+  }
+
+  private SkylarkProviderIdentifier(SkylarkClassObjectConstructor.Key key) {
+    this.legacyId = null;
+    this.key = key;
+  }
+
+  /**
+   * Returns true if this {@link SkylarkProviderIdentifier} identifies
+   * a legacy provider (with a string name).
+   */
+  public boolean isLegacy() {
+    return legacyId != null;
+  }
+
+  /**
+   * Returns a string identifying the provider (only for legacy providers).
+   */
+  public String getLegacyId() {
+    Preconditions.checkState(isLegacy(), "Check isLegacy() first");
+    return legacyId;
+  }
+
+  /**
+   * Returns a key identifying the declared provider (only for non-legacy providers).
+   */
+  public SkylarkClassObjectConstructor.Key getKey() {
+    Preconditions.checkState(!isLegacy(), "Check !isLegacy() first");
+    return key;
+  }
+
+  @Override
+  public String toString() {
+    if (isLegacy()) {
+      return legacyId;
+    }
+    return key.getExportedName();
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(legacyId, key);
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (!(obj instanceof SkylarkProviderIdentifier)) {
+      return false;
+    }
+    SkylarkProviderIdentifier other = (SkylarkProviderIdentifier) obj;
+    return Objects.equals(legacyId, other.legacyId)
+        && Objects.equals(key, other.key);
+  }
+}
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
index ec184b4..347c728 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/AliasConfiguredTarget.java
@@ -27,6 +27,9 @@
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor.Key;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.EvalException;
@@ -75,6 +78,18 @@
     return actual == null ? null : actual.get(providerKey);
   }
 
+  @Nullable
+  @Override
+  public SkylarkClassObject get(Key providerKey) {
+    return actual == null ? null : actual.get(providerKey);
+  }
+
+  @Nullable
+  @Override
+  public Object get(SkylarkProviderIdentifier id) {
+    return actual == null ? null : actual.get(id);
+  }
+
   @Override
   public Object getIndex(Object key, Location loc) throws EvalException {
     return actual == null ? null : actual.getIndex(key, loc);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
index 015b0f0..71f176d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.rules;
 
+import com.google.common.base.Function;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
@@ -26,6 +27,7 @@
 import com.google.devtools.build.lib.packages.Attribute.SkylarkComputedDefaultTemplate;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.SkylarkAspect;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.skylarkinterface.Param;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
@@ -258,7 +260,7 @@
         }
       }
       if (isSingleListOfStr) {
-        builder.mandatoryProviders(((SkylarkList<?>) obj).getContents(String.class, PROVIDERS_ARG));
+        builder.mandatoryProviders(getSkylarkProviderIdentifiers((SkylarkList<?>) obj));
       } else {
         builder.mandatoryProvidersList(getProvidersList((SkylarkList) obj));
       }
@@ -283,8 +285,20 @@
     return builder;
   }
 
-  private static List<List<String>> getProvidersList(SkylarkList skylarkList) throws EvalException {
-    List<List<String>> providersList = new ArrayList<>();
+  private static Iterable<SkylarkProviderIdentifier> getSkylarkProviderIdentifiers(
+      SkylarkList<?> obj) throws EvalException {
+    return Iterables.transform(obj.getContents(String.class, PROVIDERS_ARG),
+        new Function<String, SkylarkProviderIdentifier>() {
+          @Override
+          public SkylarkProviderIdentifier apply(String s) {
+            return SkylarkProviderIdentifier.forLegacy(s);
+          }
+        });
+  }
+
+  private static List<Iterable<SkylarkProviderIdentifier>> getProvidersList(
+      SkylarkList<?> skylarkList) throws EvalException {
+    List<Iterable<SkylarkProviderIdentifier>> providersList = new ArrayList<>();
     String errorMsg = "Illegal argument: element in '%s' is of unexpected type. "
         + "Should be list of string, but got %s. "
         + "Notice: one single list of string as 'providers' is still supported.";
@@ -300,7 +314,7 @@
                   + EvalUtils.getDataTypeNameFromClass(value.getClass())));
         }
       }
-      providersList.add(((SkylarkList<?>) o).getContents(String.class, PROVIDERS_ARG));
+      providersList.add(getSkylarkProviderIdentifiers((SkylarkList<?>) o));
     }
     return providersList;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
index 50133da..6ac83f5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
@@ -311,7 +311,9 @@
         SkylarkClassObject declaredProvider = SkylarkType.cast(o, SkylarkClassObject.class, loc,
             "A return value of rule implementation function should be "
                 + "a sequence of declared providers");
-        builder.addSkylarkDeclaredProvider(declaredProvider, declaredProvider.getCreationLoc());
+        Location creationLoc = declaredProvider.getCreationLocOrNull();
+        builder.addSkylarkDeclaredProvider(declaredProvider,
+            creationLoc != null ? creationLoc : loc);
       }
     }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
index 2367da2..8e3361b 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
@@ -37,6 +37,7 @@
 import com.google.devtools.build.lib.packages.SkylarkAspect;
 import com.google.devtools.build.lib.packages.SkylarkClassObject;
 import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.rules.SkylarkAttr;
 import com.google.devtools.build.lib.rules.SkylarkFileType;
 import com.google.devtools.build.lib.rules.SkylarkRuleClassFunctions;
@@ -229,7 +230,12 @@
     Attribute attr =
         evalAttributeDefinition("attr.label_list(allow_files = True, providers = ['a', 'b'])")
             .build("a1");
-    assertThat(attr.getMandatoryProvidersList()).containsExactly(ImmutableSet.of("a", "b"));
+    assertThat(attr.getMandatoryProvidersList())
+        .containsExactly(ImmutableSet.of(legacy("a"), legacy("b")));
+  }
+
+  private static SkylarkProviderIdentifier legacy(String legacyId) {
+    return SkylarkProviderIdentifier.forLegacy(legacyId);
   }
 
   @Test
@@ -238,8 +244,9 @@
         evalAttributeDefinition("attr.label_list(allow_files = True,"
             + " providers = [['a', 'b'], ['c']])")
             .build("a1");
-    assertThat(attr.getMandatoryProvidersList()).containsExactly(ImmutableSet.of("a", "b"),
-        ImmutableSet.of("c"));
+    assertThat(attr.getMandatoryProvidersList()).containsExactly(
+        ImmutableSet.of(legacy("a"), legacy("b")),
+        ImmutableSet.of(legacy("c")));
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/testutil/TestRuleClassProvider.java b/src/test/java/com/google/devtools/build/lib/testutil/TestRuleClassProvider.java
index aa8bfb7..6a13bd9 100644
--- a/src/test/java/com/google/devtools/build/lib/testutil/TestRuleClassProvider.java
+++ b/src/test/java/com/google/devtools/build/lib/testutil/TestRuleClassProvider.java
@@ -27,8 +27,8 @@
 import com.google.devtools.build.lib.analysis.RuleDefinitionEnvironment;
 import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.RuleClass.Builder;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.util.FileTypeSet;
-
 import java.lang.reflect.Method;
 
 /**
@@ -97,8 +97,12 @@
       return builder
           .setUndocumented()
           .add(attr("srcs", LABEL_LIST).allowedFileTypes(FileTypeSet.ANY_FILE))
-          .override(builder.copy("deps").mandatoryProvidersList(ImmutableList.of(
-              ImmutableList.of("a"), ImmutableList.of("b", "c"))))
+          .override(builder.copy("deps").mandatoryProvidersList(
+              ImmutableList.of(
+                ImmutableList.of(SkylarkProviderIdentifier.forLegacy("a")),
+                ImmutableList.of(
+                    SkylarkProviderIdentifier.forLegacy("b"),
+                    SkylarkProviderIdentifier.forLegacy("c")))))
           .build();
     }