Use the same data structure for native and Skylark providers.

The memory cost of adding Skylark provider is now the same as native.
Skylark providers (declared and legacy) benefit from the same
shape-sharing optimization as native providers.

RELNOTES: None.
PiperOrigin-RevId: 160944263

23 files changed, 343 insertions, 388 deletions

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 12fd6b9224..8b197298fb 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,12 +25,12 @@ import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.ClassObjectConstructor;
 import com.google.devtools.build.lib.packages.PackageSpecification;
 import com.google.devtools.build.lib.packages.SkylarkClassObject;
-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;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import java.util.concurrent.atomic.AtomicReference;
+import java.util.function.Consumer;
 import javax.annotation.Nullable;
 
 /**
@@ -159,12 +159,13 @@ public abstract class AbstractConfiguredTarget
     if (getProvider(OutputGroupProvider.class) != null) {
       result.add(OutputGroupProvider.SKYLARK_NAME);
     }
-    if (getProvider(SkylarkProviders.class) != null) {
-      result.addAll(getProvider(SkylarkProviders.class).getKeys());
-    }
+    addExtraSkylarkKeys(result::add);
     return result.build();
   }
 
+  protected void addExtraSkylarkKeys(Consumer<String> result) {
+  }
+
   private DefaultProvider getDefaultProvider() {
     if (defaultProvider.get() == null) {
       defaultProvider.compareAndSet(
@@ -177,16 +178,6 @@ public abstract class AbstractConfiguredTarget
     return defaultProvider.get();
   }
 
-  @Nullable
-  @Override
-  public final Object get(SkylarkProviderIdentifier id) {
-    if (id.isLegacy()) {
-      return get(id.getLegacyId());
-    }
-    return get(id.getKey());
-  }
-
-
   /** Returns a declared provider provided by this target. Only meant to use from Skylark. */
   @Nullable
   @Override
@@ -197,13 +188,14 @@ public abstract class AbstractConfiguredTarget
     if (providerKey.equals(OutputGroupProvider.SKYLARK_CONSTRUCTOR.getKey())) {
       return OutputGroupProvider.get(this);
     }
-    SkylarkProviders skylarkProviders = getProvider(SkylarkProviders.class);
-    if (skylarkProviders != null) {
-      return skylarkProviders.getDeclaredProvider(providerKey);
-    }
-    return null;
+    return rawGetSkylarkProvider(providerKey);
   }
 
+  /** Implement in subclasses to get a skylark provider for a given {@code providerKey}. */
+  @Nullable
+  protected abstract SkylarkClassObject rawGetSkylarkProvider(
+      ClassObjectConstructor.Key providerKey);
+
   /**
    * Returns a value provided by this target. Only meant to use from Skylark.
    */
@@ -212,8 +204,10 @@ public abstract class AbstractConfiguredTarget
     if (OutputGroupProvider.SKYLARK_NAME.equals(providerKey)) {
       return getProvider(OutputGroupProvider.class);
     }
-    SkylarkProviders skylarkProviders = getProvider(SkylarkProviders.class);
-    return skylarkProviders != null ? skylarkProviders.getValue(providerKey) : null;
+    return rawGetSkylarkProvider(providerKey);
   }
 
+  /** Implement in subclasses to get a skylark provider for a given {@code providerKey}. */
+  protected abstract Object rawGetSkylarkProvider(String providerKey);
+
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
index f1c4b4d515..6614c1a8a2 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredAspect.java
@@ -31,7 +31,6 @@ import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.packages.ClassObjectConstructor;
 import com.google.devtools.build.lib.packages.ClassObjectConstructor.Key;
 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.syntax.EvalException;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -92,10 +91,6 @@ public final class ConfiguredAspect {
     return providers.getProvider(providerClass);
   }
 
-  SkylarkProviders getSkylarkProviders() {
-    return providers.getProvider(SkylarkProviders.class);
-  }
-
   public Object getProvider(SkylarkProviderIdentifier id) {
     if (id.isLegacy()) {
       return get(id.getLegacyId());
@@ -108,18 +103,14 @@ public final class ConfiguredAspect {
     if (OutputGroupProvider.SKYLARK_CONSTRUCTOR.getKey().equals(key)) {
       return getProvider(OutputGroupProvider.class);
     }
-    SkylarkProviders skylarkProviders = providers.getProvider(SkylarkProviders.class);
-    return skylarkProviders != null ? skylarkProviders.getDeclaredProvider(key) : null;
+    return providers.getProvider(key);
   }
 
   public Object get(String legacyKey) {
     if (OutputGroupProvider.SKYLARK_NAME.equals(legacyKey)) {
       return getProvider(OutputGroupProvider.class);
     }
-    SkylarkProviders skylarkProviders = providers.getProvider(SkylarkProviders.class);
-    return skylarkProviders != null
-        ? skylarkProviders.get(SkylarkProviderIdentifier.forLegacy(legacyKey))
-        : null;
+    return providers.getProvider(legacyKey);
   }
 
   public static ConfiguredAspect forAlias(ConfiguredAspect real) {
@@ -178,18 +169,11 @@ public final class ConfiguredAspect {
 
     private void checkProviderClass(Class<? extends TransitiveInfoProvider> providerClass) {
       Preconditions.checkNotNull(providerClass);
-      Preconditions.checkArgument(
-          !SkylarkProviders.class.equals(providerClass),
-          "Do not provide SkylarkProviders directly");
     }
 
     /** Adds providers to the aspect. */
     public Builder addProviders(TransitiveInfoProviderMap providers) {
-      for (int i = 0; i < providers.getProviderCount(); ++i) {
-        Class<? extends TransitiveInfoProvider> providerClass = providers.getProviderClassAt(i);
-        TransitiveInfoProvider provider = providers.getProviderAt(i);
-        addProvider(providerClass, providerClass.cast(provider));
-      }
+      this.providers.addAll(providers);
       return this;
     }
 
@@ -220,13 +204,13 @@ public final class ConfiguredAspect {
     }
 
     public Builder addSkylarkTransitiveInfo(String name, Object value) {
-      skylarkProviderBuilder.put(name, value);
+      providers.put(name, value);
       return this;
     }
 
     public Builder addSkylarkTransitiveInfo(String name, Object value, Location loc)
         throws EvalException {
-      skylarkProviderBuilder.put(name, value);
+      providers.put(name, value);
       return this;
     }
 
@@ -246,7 +230,7 @@ public final class ConfiguredAspect {
       if (OutputGroupProvider.SKYLARK_CONSTRUCTOR.getKey().equals(key)) {
         addProvider(OutputGroupProvider.class, (OutputGroupProvider) declaredProvider);
       } else {
-        skylarkDeclaredProvidersBuilder.put(key, declaredProvider);
+        providers.put(declaredProvider);
       }
     }
 
@@ -265,8 +249,7 @@ public final class ConfiguredAspect {
           outputGroups.put(entry.getKey(), entry.getValue().build());
         }
 
-        if (skylarkDeclaredProvidersBuilder.containsKey(
-            OutputGroupProvider.SKYLARK_CONSTRUCTOR.getKey())) {
+        if (providers.contains(OutputGroupProvider.SKYLARK_CONSTRUCTOR.getKey())) {
           throw new IllegalStateException(
               "OutputGroupProvider was provided explicitly; do not use addOutputGroup");
         }
@@ -274,13 +257,6 @@ public final class ConfiguredAspect {
             new OutputGroupProvider(outputGroups.build()));
       }
 
-      ImmutableMap<String, Object> skylarkProvidersMap = skylarkProviderBuilder.build();
-      ImmutableMap<SkylarkClassObjectConstructor.Key, SkylarkClassObject>
-          skylarkDeclaredProvidersMap = ImmutableMap.copyOf(skylarkDeclaredProvidersBuilder);
-      if (!skylarkProvidersMap.isEmpty() || !skylarkDeclaredProvidersMap.isEmpty()) {
-        providers.add(new SkylarkProviders(skylarkProvidersMap, skylarkDeclaredProvidersMap));
-      }
-
       addProvider(
           createExtraActionProvider(
               ImmutableSet.<ActionAnalysisMetadata>of() /* actionsWithoutExtraAction */,
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
index 7f8a72f54c..ac5b483a22 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredRuleClassProvider.java
@@ -337,16 +337,6 @@ public class ConfiguredRuleClassProvider implements RuleClassProvider {
     }
 
     /**
-     * Adds a mapping that determines which keys in structs returned by skylark rules should be
-     * interpreted as native TransitiveInfoProvider instances of type (map value).
-     */
-    public Builder registerSkylarkProvider(
-        String name, Class<? extends TransitiveInfoProvider> provider) {
-      this.registeredSkylarkProviders.put(name, provider);
-      return this;
-    }
-
-    /**
      * Do not use - this only exists for backwards compatibility! Platform regexps are part of a
      * legacy mechanism - {@code vardef} - that is not exposed in Bazel.
      *
@@ -442,8 +432,7 @@ public class ConfiguredRuleClassProvider implements RuleClassProvider {
           universalFragment,
           prerequisiteValidator,
           skylarkAccessibleTopLevels.build(),
-          skylarkModules.build(),
-          registeredSkylarkProviders.build());
+          skylarkModules.build());
     }
 
     @Override
@@ -551,9 +540,6 @@ public class ConfiguredRuleClassProvider implements RuleClassProvider {
 
   private final Environment.Frame globals;
 
-  private final ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>>
-      registeredSkylarkProviders;
-
   private ConfiguredRuleClassProvider(
       String productName,
       Label preludeLabel,
@@ -571,8 +557,7 @@ public class ConfiguredRuleClassProvider implements RuleClassProvider {
       Class<? extends BuildConfiguration.Fragment> universalFragment,
       PrerequisiteValidator prerequisiteValidator,
       ImmutableMap<String, Object> skylarkAccessibleJavaClasses,
-      ImmutableList<Class<?>> skylarkModules,
-      ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>> registeredSkylarkProviders) {
+      ImmutableList<Class<?>> skylarkModules) {
     this.productName = productName;
     this.preludeLabel = preludeLabel;
     this.runfilesPrefix = runfilesPrefix;
@@ -589,7 +574,6 @@ public class ConfiguredRuleClassProvider implements RuleClassProvider {
     this.universalFragment = universalFragment;
     this.prerequisiteValidator = prerequisiteValidator;
     this.globals = createGlobals(skylarkAccessibleJavaClasses, skylarkModules);
-    this.registeredSkylarkProviders = registeredSkylarkProviders;
   }
 
   public String getProductName() {
@@ -689,19 +673,6 @@ public class ConfiguredRuleClassProvider implements RuleClassProvider {
   }
 
   /**
-   * Returns a map that indicates which keys in structs returned by skylark rules should be
-   * interpreted as native TransitiveInfoProvider instances of type (map value).
-   *
-   * <p>That is, if this map contains "dummy" -> DummyProvider.class, a "dummy" entry in a skylark
-   * rule implementation's returned struct will be exported from that ConfiguredTarget as a
-   * DummyProvider.
-   */
-  public ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>>
-      getRegisteredSkylarkProviders() {
-    return this.registeredSkylarkProviders;
-  }
-
-  /**
    * Creates a BuildOptions class for the given options taken from an optionsProvider.
    */
   public BuildOptions createBuildOptions(OptionsClassProvider optionsProvider) {
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 db4fe08c5c..664cdb28b9 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
@@ -64,7 +64,6 @@ import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
-
 import java.util.ArrayList;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -290,7 +289,6 @@ public final class ConfiguredTargetFactory {
             .setPrerequisites(prerequisiteMap)
             .setConfigConditions(configConditions)
             .setUniversalFragment(ruleClassProvider.getUniversalFragment())
-            .setSkylarkProvidersRegistry(ruleClassProvider.getRegisteredSkylarkProviders())
             // TODO(katre): Populate the actual selected toolchains.
             .setToolchainContext(
                 new ToolchainContext(rule.getRuleClassObject().getRequiredToolchains(), null))
@@ -319,8 +317,8 @@ public final class ConfiguredTargetFactory {
       return SkylarkRuleConfiguredTargetBuilder.buildRule(
           ruleContext,
           rule.getRuleClassObject().getConfiguredTargetFunction(),
-          env.getSkylarkSemantics(),
-          ruleClassProvider.getRegisteredSkylarkProviders());
+          env.getSkylarkSemantics()
+      );
     } else {
       RuleClass.ConfiguredTargetFactory<ConfiguredTarget, RuleContext> factory =
           rule.getRuleClassObject().<ConfiguredTarget, RuleContext>getConfiguredTargetFactory();
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 e67a2b6395..83a9266fe5 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
@@ -14,7 +14,9 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.devtools.build.lib.packages.ClassObjectConstructor;
 import com.google.devtools.build.lib.packages.EnvironmentGroup;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
 import com.google.devtools.build.lib.util.Preconditions;
 
 /**
@@ -31,4 +33,14 @@ public final class EnvironmentGroupConfiguredTarget extends AbstractConfiguredTa
   public EnvironmentGroup getTarget() {
     return (EnvironmentGroup) super.getTarget();
   }
+
+  @Override
+  protected SkylarkClassObject rawGetSkylarkProvider(ClassObjectConstructor.Key providerKey) {
+    return null;
+  }
+
+  @Override
+  protected Object rawGetSkylarkProvider(String providerKey) {
+    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 7b68c7b2b3..0659bb86cd 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
@@ -18,7 +18,9 @@ import com.google.devtools.build.lib.actions.Artifact;
 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.packages.ClassObjectConstructor;
 import com.google.devtools.build.lib.packages.FileTarget;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
 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;
@@ -77,4 +79,14 @@ public abstract class FileConfiguredTarget extends AbstractConfiguredTarget
     AnalysisUtils.checkProvider(provider);
     return providers.getProvider(provider);
   }
+
+  @Override
+  protected SkylarkClassObject rawGetSkylarkProvider(ClassObjectConstructor.Key providerKey) {
+    return providers.getProvider(providerKey);
+  }
+
+  @Override
+  protected Object rawGetSkylarkProvider(String providerKey) {
+    return providers.getProvider(providerKey);
+  }
 }
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 a9079ad164..f1b0b0debf 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
@@ -15,8 +15,12 @@ package com.google.devtools.build.lib.analysis;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.packages.ClassObjectConstructor;
+import com.google.devtools.build.lib.packages.ClassObjectConstructor.Key;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
 import java.util.ArrayList;
 import java.util.List;
+import java.util.function.Consumer;
 
 /**
  * A single dependency with its configured target and aspects merged together.
@@ -57,6 +61,37 @@ public final class MergedConfiguredTarget extends AbstractConfiguredTarget {
     return provider;
   }
 
+  @Override
+  protected void addExtraSkylarkKeys(Consumer<String> result) {
+    if (base instanceof AbstractConfiguredTarget) {
+      ((AbstractConfiguredTarget) base).addExtraSkylarkKeys(result);
+    }
+    for (int i = 0; i < providers.getProviderCount(); i++) {
+      Object classAt = providers.getProviderKeyAt(i);
+      if (classAt instanceof String) {
+        result.accept((String) classAt);
+      }
+    }
+  }
+
+  @Override
+  protected SkylarkClassObject rawGetSkylarkProvider(ClassObjectConstructor.Key providerKey) {
+    SkylarkClassObject provider = providers.getProvider(providerKey);
+    if (provider == null) {
+      provider = base.get(providerKey);
+    }
+    return provider;
+  }
+
+  @Override
+  protected Object rawGetSkylarkProvider(String providerKey) {
+    Object provider = providers.getProvider(providerKey);
+    if (provider == null) {
+      provider = base.get(providerKey);
+    }
+    return provider;
+  }
+
   /** Creates an instance based on a configured target and a set of aspects. */
   public static ConfiguredTarget of(ConfiguredTarget base, Iterable<ConfiguredAspect> aspects)
       throws DuplicateException {
@@ -69,10 +104,6 @@ public final class MergedConfiguredTarget extends AbstractConfiguredTarget {
     OutputGroupProvider mergedOutputGroupProvider =
         OutputGroupProvider.merge(getAllOutputGroupProviders(base, aspects));
 
-    // Merge Skylark providers.
-    SkylarkProviders mergedSkylarkProviders =
-        SkylarkProviders.merge(getAllProviders(base, aspects, SkylarkProviders.class));
-
     // Merge extra-actions provider.
     ExtraActionArtifactsProvider mergedExtraActionProviders = ExtraActionArtifactsProvider.merge(
         getAllProviders(base, aspects, ExtraActionArtifactsProvider.class));
@@ -81,9 +112,6 @@ public final class MergedConfiguredTarget extends AbstractConfiguredTarget {
     if (mergedOutputGroupProvider != null) {
       aspectProviders.add(mergedOutputGroupProvider);
     }
-    if (mergedSkylarkProviders != null) {
-      aspectProviders.add(mergedSkylarkProviders);
-    }
     if (mergedExtraActionProviders != null) {
       aspectProviders.add(mergedExtraActionProviders);
     }
@@ -91,18 +119,35 @@ public final class MergedConfiguredTarget extends AbstractConfiguredTarget {
     for (ConfiguredAspect aspect : aspects) {
       TransitiveInfoProviderMap providers = aspect.getProviders();
       for (int i = 0; i < providers.getProviderCount(); ++i) {
-        Class<? extends TransitiveInfoProvider> providerClass = providers.getProviderClassAt(i);
-        if (OutputGroupProvider.class.equals(providerClass)
-            || SkylarkProviders.class.equals(providerClass)
-            || ExtraActionArtifactsProvider.class.equals(providerClass)) {
+        Object providerKey = providers.getProviderKeyAt(i);
+        if (OutputGroupProvider.class.equals(providerKey)
+            || ExtraActionArtifactsProvider.class.equals(providerKey)) {
           continue;
         }
 
-        if (base.getProvider(providerClass) != null || aspectProviders.contains(providerClass)) {
-          throw new IllegalStateException("Provider " + providerClass + " provided twice");
+        if (providerKey instanceof Class<?>) {
+          @SuppressWarnings("unchecked")
+          Class<? extends TransitiveInfoProvider> providerClass =
+              (Class<? extends TransitiveInfoProvider>) providerKey;
+          if (base.getProvider(providerClass) != null
+              || aspectProviders.contains(providerClass)) {
+            throw new DuplicateException("Provider " + providerKey + " provided twice");
+          }
+          aspectProviders.put(
+              providerClass, (TransitiveInfoProvider) providers.getProviderInstanceAt(i));
+        } else if (providerKey instanceof String) {
+          String legacyId = (String) providerKey;
+          if (base.get(legacyId) != null || aspectProviders.contains(legacyId)) {
+            throw new DuplicateException("Provider " + legacyId + " provided twice");
+          }
+          aspectProviders.put(legacyId, providers.getProviderInstanceAt(i));
+        } else if (providerKey instanceof ClassObjectConstructor.Key) {
+          ClassObjectConstructor.Key key = (Key) providerKey;
+          if (base.get(key) != null || aspectProviders.contains(key)) {
+            throw new DuplicateException("Provider " + key + " provided twice");
+          }
+          aspectProviders.put((SkylarkClassObject) providers.getProviderInstanceAt(i));
         }
-
-        aspectProviders.add(providers.getProviderAt(i));
       }
     }
     return new MergedConfiguredTarget(base, aspectProviders.build());
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 a8dd30ccee..e0516dc20d 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,8 +20,10 @@ 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.events.Event;
+import com.google.devtools.build.lib.packages.ClassObjectConstructor;
 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.util.Preconditions;
 
 /**
@@ -77,4 +79,14 @@ public final class PackageGroupConfiguredTarget extends AbstractConfiguredTarget
       return super.getProvider(provider);
     }
   }
+
+  @Override
+  protected SkylarkClassObject rawGetSkylarkProvider(ClassObjectConstructor.Key providerKey) {
+    return null;
+  }
+
+  @Override
+  protected Object rawGetSkylarkProvider(String providerKey) {
+    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 85e65940fd..62f0015691 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
@@ -17,11 +17,13 @@ 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.ClassObjectConstructor;
 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.rules.SkylarkApiProvider;
 import com.google.devtools.build.lib.util.Preconditions;
+import java.util.function.Consumer;
 import javax.annotation.Nullable;
 
 /**
@@ -47,11 +49,7 @@ public final class RuleConfiguredTarget extends AbstractConfiguredTarget {
   private final TransitiveInfoProviderMap providers;
   private final ImmutableMap<Label, ConfigMatchingProvider> configConditions;
 
-  RuleConfiguredTarget(
-      RuleContext ruleContext,
-      TransitiveInfoProviderMap providers,
-      ImmutableMap<String, Object> legacySkylarkProviders,
-      ImmutableMap<SkylarkClassObjectConstructor.Key, SkylarkClassObject> skylarkProviders) {
+  RuleConfiguredTarget(RuleContext ruleContext, TransitiveInfoProviderMap providers) {
     super(ruleContext);
     // We don't use ImmutableMap.Builder here to allow augmenting the initial list of 'default'
     // providers by passing them in.
@@ -62,13 +60,14 @@ public final class RuleConfiguredTarget extends AbstractConfiguredTarget {
     Preconditions.checkState(providerBuilder.contains(FilesToRunProvider.class));
 
     // Initialize every SkylarkApiProvider
-    if (!legacySkylarkProviders.isEmpty() || !skylarkProviders.isEmpty()) {
-      SkylarkProviders allSkylarkProviders = new SkylarkProviders(legacySkylarkProviders,
-          skylarkProviders);
-      allSkylarkProviders.init(this);
-      providerBuilder.add(allSkylarkProviders);
+    for (int i = 0; i < providers.getProviderCount(); i++) {
+      Object obj = providers.getProviderInstanceAt(i);
+      if (obj instanceof SkylarkApiProvider) {
+        ((SkylarkApiProvider) obj).init(this);
+      }
     }
 
+
     this.providers = providerBuilder.build();
     this.configConditions = ruleContext.getConfigConditions();
 
@@ -116,4 +115,24 @@ public final class RuleConfiguredTarget extends AbstractConfiguredTarget {
     return String.format("target (rule class of '%s') doesn't have provider '%s'.",
         getTarget().getRuleClass(), name);
   }
+
+  @Override
+  protected void addExtraSkylarkKeys(Consumer<String> result) {
+    for (int i = 0; i < providers.getProviderCount(); i++) {
+      Object classAt = providers.getProviderKeyAt(i);
+      if (classAt instanceof String) {
+        result.accept((String) classAt);
+      }
+    }
+  }
+
+  @Override
+  protected SkylarkClassObject rawGetSkylarkProvider(ClassObjectConstructor.Key providerKey) {
+    return providers.getProvider(providerKey);
+  }
+
+  @Override
+  protected Object rawGetSkylarkProvider(String providerKey) {
+    return providers.getProvider(providerKey);
+  }
 }
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 6e28fdc32a..6bf2ee2df3 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
@@ -42,7 +42,6 @@ import com.google.devtools.build.lib.rules.test.TestProvider.TestParams;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.Preconditions;
-import java.util.HashMap;
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.TreeMap;
@@ -60,9 +59,6 @@ public final class RuleConfiguredTargetBuilder {
   private final RuleContext ruleContext;
   private final TransitiveInfoProviderMapBuilder providersBuilder =
       new TransitiveInfoProviderMapBuilder();
-  private final ImmutableMap.Builder<String, Object> skylarkProviders = ImmutableMap.builder();
-  private final ImmutableMap.Builder<ClassObjectConstructor.Key, SkylarkClassObject>
-      skylarkDeclaredProviders = ImmutableMap.builder();
   private final Map<String, NestedSetBuilder<Artifact>> outputGroupBuilders = new TreeMap<>();
 
   /** These are supported by all configured targets and need to be specially handled. */
@@ -135,30 +131,10 @@ public final class RuleConfiguredTargetBuilder {
     }
 
     TransitiveInfoProviderMap providers = providersBuilder.build();
-    addRegisteredProvidersToSkylarkProviders(providers);
 
-    return new RuleConfiguredTarget(
-        ruleContext,
-        providers,
-        skylarkProviders.build(), skylarkDeclaredProviders.build());
+    return new RuleConfiguredTarget(ruleContext, providers);
   }
 
-  /** Adds skylark providers from a skylark provider registry, and checks for collisions. */
-  private void addRegisteredProvidersToSkylarkProviders(TransitiveInfoProviderMap providers) {
-    Map<String, Object> nativeSkylarkProviders = new HashMap<>();
-    for (int i = 0; i < providers.getProviderCount(); ++i) {
-      Class<? extends TransitiveInfoProvider> providerClass = providers.getProviderClassAt(i);
-      if (ruleContext.getSkylarkProviderRegistry().containsValue(providerClass)) {
-        String skylarkName = ruleContext.getSkylarkProviderRegistry().inverse().get(providerClass);
-        nativeSkylarkProviders.put(skylarkName, providers.getProviderAt(i));
-      }
-    }
-    try {
-      skylarkProviders.putAll(nativeSkylarkProviders);
-    } catch (IllegalArgumentException e) {
-      ruleContext.ruleError("Collision caused by duplicate skylark providers: " + e.getMessage());
-    }
-  }
 
   /**
    * Like getFilesToBuild(), except that it also includes the runfiles middleman, if any. Middlemen
@@ -215,9 +191,7 @@ public final class RuleConfiguredTargetBuilder {
 
     TestEnvironmentProvider environmentProvider =
         (TestEnvironmentProvider)
-            skylarkDeclaredProviders
-                .build()
-                .get(TestEnvironmentProvider.SKYLARK_CONSTRUCTOR.getKey());
+            providersBuilder.getProvider(TestEnvironmentProvider.SKYLARK_CONSTRUCTOR.getKey());
     if (environmentProvider != null) {
       testActionBuilder.addExtraEnv(environmentProvider.getEnvironment());
     }
@@ -226,10 +200,8 @@ public final class RuleConfiguredTargetBuilder {
         testActionBuilder
             .setFilesToRunProvider(filesToRunProvider)
             .setExecutionRequirements(
-                (ExecutionInfoProvider)
-                    skylarkDeclaredProviders
-                        .build()
-                        .get(ExecutionInfoProvider.SKYLARK_CONSTRUCTOR.getKey()))
+                (ExecutionInfoProvider) providersBuilder
+                    .getProvider(ExecutionInfoProvider.SKYLARK_CONSTRUCTOR.getKey()))
             .setShardCount(explicitShardCount)
             .build();
     ImmutableList<String> testTags = ImmutableList.copyOf(ruleContext.getRule().getRuleTags());
@@ -240,6 +212,7 @@ public final class RuleConfiguredTargetBuilder {
   public <T extends TransitiveInfoProvider> RuleConfiguredTargetBuilder addProvider(
       TransitiveInfoProvider provider) {
     providersBuilder.add(provider);
+    maybeAddSkylarkProvider(provider);
     return this;
   }
 
@@ -247,6 +220,9 @@ public final class RuleConfiguredTargetBuilder {
   public <T extends TransitiveInfoProvider> RuleConfiguredTargetBuilder addProviders(
       Iterable<TransitiveInfoProvider> providers) {
     providersBuilder.addAll(providers);
+    for (TransitiveInfoProvider provider : providers) {
+      maybeAddSkylarkProvider(provider);
+    }
     return this;
   }
 
@@ -274,9 +250,18 @@ public final class RuleConfiguredTargetBuilder {
     Preconditions.checkNotNull(key);
     Preconditions.checkNotNull(value);
     providersBuilder.put(key, value);
+    maybeAddSkylarkProvider(value);
     return this;
   }
 
+  protected <T extends TransitiveInfoProvider> void maybeAddSkylarkProvider(T value) {
+    if (value instanceof TransitiveInfoProvider.WithLegacySkylarkName) {
+      addSkylarkTransitiveInfo(
+          ((TransitiveInfoProvider.WithLegacySkylarkName) value).getSkylarkName(),
+          value);
+    }
+  }
+
   /**
    * Add a Skylark transitive info. The provider value must be safe (i.e. a String, a Boolean,
    * an Integer, an Artifact, a Label, None, a Java TransitiveInfoProvider or something composed
@@ -285,7 +270,7 @@ public final class RuleConfiguredTargetBuilder {
    */
   public RuleConfiguredTargetBuilder addSkylarkTransitiveInfo(
       String name, Object value, Location loc) throws EvalException {
-    skylarkProviders.put(name, value);
+    providersBuilder.put(name, value);
     return this;
   }
 
@@ -312,7 +297,7 @@ public final class RuleConfiguredTargetBuilder {
         addOutputGroup(outputGroup, outputGroupProvider.getOutputGroup(outputGroup));
       }
     } else {
-      skylarkDeclaredProviders.put(constructor.getKey(), provider);
+      providersBuilder.put(provider);
     }
     return this;
   }
@@ -342,7 +327,7 @@ public final class RuleConfiguredTargetBuilder {
   public RuleConfiguredTargetBuilder addNativeDeclaredProvider(SkylarkClassObject provider) {
     ClassObjectConstructor constructor = provider.getConstructor();
     Preconditions.checkState(constructor.isExported());
-    skylarkDeclaredProviders.put(constructor.getKey(), provider);
+    providersBuilder.put(provider);
     return this;
   }
 
@@ -351,7 +336,7 @@ public final class RuleConfiguredTargetBuilder {
    */
   public RuleConfiguredTargetBuilder addSkylarkTransitiveInfo(
       String name, Object value) {
-    skylarkProviders.put(name, value);
+    providersBuilder.put(name, value);
     return this;
   }
 
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 1f06b71e9b..5c8248d0c2 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
@@ -167,8 +167,6 @@ public final class RuleContext extends TargetContext
   private final ConfigurationFragmentPolicy configurationFragmentPolicy;
   private final Class<? extends BuildConfiguration.Fragment> universalFragment;
   private final ErrorReporter reporter;
-  private final ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>>
-      skylarkProviderRegistry;
   @Nullable private final ToolchainContext toolchainContext;
 
   private ActionOwner actionOwner;
@@ -198,7 +196,6 @@ public final class RuleContext extends TargetContext
     this.attributes = new AspectAwareAttributeMapper(attributes, aspectAttributes);
     this.features = getEnabledFeatures();
     this.ruleClassNameForLogging = ruleClassNameForLogging;
-    this.skylarkProviderRegistry = builder.skylarkProviderRegistry;
     this.hostConfiguration = builder.hostConfiguration;
     reporter = builder.reporter;
     this.toolchainContext = toolchainContext;
@@ -304,15 +301,6 @@ public final class RuleContext extends TargetContext
   }
 
   /**
-   * Returns a map that indicates which providers should be exported to skylark under the key
-   * (map key).  These provider types will also be exportable by skylark rules under (map key).
-   */
-  public ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>>
-      getSkylarkProviderRegistry() {
-    return skylarkProviderRegistry;
-  }
-
-  /**
    * Returns whether this instance is known to have errors at this point during analysis. Do not
    * call this method after the initializationHook has returned.
    */
@@ -1577,7 +1565,6 @@ public final class RuleContext extends TargetContext
     private ImmutableMap<Label, ConfigMatchingProvider> configConditions;
     private NestedSet<PackageSpecification> visibility;
     private ImmutableMap<String, Attribute> aspectAttributes;
-    private ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>> skylarkProviderRegistry;
     private ImmutableList<AspectDescriptor> aspectDescriptors;
     private ToolchainContext toolchainContext;
 
@@ -1673,7 +1660,6 @@ public final class RuleContext extends TargetContext
      */
     Builder setSkylarkProvidersRegistry(
         ImmutableBiMap<String, Class<? extends TransitiveInfoProvider>> skylarkProviderRegistry) {
-      this.skylarkProviderRegistry = skylarkProviderRegistry;
       return this;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SkylarkProviderCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/SkylarkProviderCollection.java
index c5c2130dd0..3289b49f85 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/SkylarkProviderCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SkylarkProviderCollection.java
@@ -48,5 +48,11 @@ public interface SkylarkProviderCollection {
    * declared provider.
    */
   @Nullable
-  Object get(SkylarkProviderIdentifier id);
+  default Object get(SkylarkProviderIdentifier id) {
+    if (id.isLegacy()) {
+      return this.get(id.getLegacyId());
+    } else {
+      return this.get(id.getKey());
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SkylarkProviders.java b/src/main/java/com/google/devtools/build/lib/analysis/SkylarkProviders.java
deleted file mode 100644
index a9046eb03e..0000000000
--- a/src/main/java/com/google/devtools/build/lib/analysis/SkylarkProviders.java
+++ /dev/null
@@ -1,171 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.analysis;
-
-import com.google.common.base.Function;
-import com.google.common.collect.ImmutableCollection;
-import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.analysis.MergedConfiguredTarget.DuplicateException;
-import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
-import com.google.devtools.build.lib.packages.ClassObjectConstructor;
-import com.google.devtools.build.lib.packages.SkylarkClassObject;
-import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
-import com.google.devtools.build.lib.rules.SkylarkApiProvider;
-import com.google.devtools.build.lib.syntax.EvalException;
-import com.google.devtools.build.lib.syntax.SkylarkType;
-import com.google.devtools.build.lib.util.Preconditions;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-/**
- * A helper class for transitive infos provided by Skylark rule implementations.
- *
- * DO NOT USE THIS CLASS to access Skylark providers.
- * Use {@link ConfiguredTarget#get(SkylarkProviderIdentifier)} or
- * {@link ConfiguredAspect#getProvider(SkylarkProviderIdentifier)}.
- */
-@Immutable
-final class SkylarkProviders implements TransitiveInfoProvider {
-  private final ImmutableMap<ClassObjectConstructor.Key, SkylarkClassObject>
-      declaredProviders;
-  private final ImmutableMap<String, Object> skylarkProviders;
-
-  SkylarkProviders(
-      ImmutableMap<String, Object> skylarkProviders,
-      ImmutableMap<ClassObjectConstructor.Key, SkylarkClassObject> declaredProviders) {
-    this.declaredProviders = Preconditions.checkNotNull(declaredProviders);
-    this.skylarkProviders = Preconditions.checkNotNull(skylarkProviders);
-  }
-
-  public void init(ConfiguredTarget target) {
-    for (Object o : skylarkProviders.values()) {
-      if (o instanceof SkylarkApiProvider) {
-        ((SkylarkApiProvider) o).init(target);
-      }
-    }
-  }
-
-  /**
-   * Returns the keys for the Skylark providers.
-   */
-  public ImmutableCollection<String> getKeys() {
-    return skylarkProviders.keySet();
-  }
-
-  public boolean isEmpty() {
-    return skylarkProviders.isEmpty() && declaredProviders.isEmpty();
-  }
-
-  /** Returns the keys for the declared providers. */
-  public ImmutableCollection<ClassObjectConstructor.Key> getDeclaredProviderKeys() {
-    return declaredProviders.keySet();
-  }
-
-  /**
-   * Returns a Skylark provider; "key" must be one from {@link #getKeys()}.
-   */
-  public Object getValue(String key) {
-    return skylarkProviders.get(key);
-  }
-
-  /**
-   * Returns a Skylark provider and try to cast it into the specified type
-   */
-  public <TYPE> TYPE getValue(String key, Class<TYPE> type) throws EvalException {
-    Object obj = skylarkProviders.get(key);
-    if (obj == null) {
-      return null;
-    }
-    SkylarkType.checkType(obj, type, key);
-    return type.cast(obj);
-  }
-
-  public SkylarkClassObject getDeclaredProvider(ClassObjectConstructor.Key key) {
-    return declaredProviders.get(key);
-  }
-
-  public Object get(SkylarkProviderIdentifier id) {
-    if (id.isLegacy()) {
-      return getValue(id.getLegacyId());
-    }
-    return getDeclaredProvider(id.getKey());
-  }
-
-
-  private static final Function<SkylarkProviders, Map<String, Object>>
-      SKYLARK_PROVIDERS_MAP_FUNCTION = new Function<SkylarkProviders, Map<String, Object>>() {
-        @Override
-        public Map<String, Object> apply(SkylarkProviders skylarkProviders) {
-          return skylarkProviders.skylarkProviders;
-        }
-      };
-
-  public static final Function<SkylarkProviders,
-                               Map<ClassObjectConstructor.Key, SkylarkClassObject>>
-      DECLARED_PROVIDERS_MAP_FUNCTION =
-      new Function<SkylarkProviders, Map<ClassObjectConstructor.Key, SkylarkClassObject>>() {
-        @Override
-        public Map<ClassObjectConstructor.Key, SkylarkClassObject> apply(
-            SkylarkProviders skylarkProviders) {
-          return skylarkProviders.declaredProviders;
-        }
-      };
-
-  /**
-   * Merges skylark providers. The set of providers must be disjoint.
-   *
-   * @param providers providers to merge {@code this} with.
-   */
-  public static SkylarkProviders merge(List<SkylarkProviders> providers)
-      throws DuplicateException {
-    if (providers.size() == 0) {
-      return null;
-    }
-    if (providers.size() == 1) {
-      return providers.get(0);
-    }
-
-    ImmutableMap<String, Object> skylarkProviders = mergeMaps(providers,
-        SKYLARK_PROVIDERS_MAP_FUNCTION);
-
-    ImmutableMap<ClassObjectConstructor.Key, SkylarkClassObject> declaredProviders =
-        mergeMaps(providers, DECLARED_PROVIDERS_MAP_FUNCTION);
-
-    return new SkylarkProviders(skylarkProviders, declaredProviders);
-  }
-
-  private static <K, V> ImmutableMap<K, V> mergeMaps(List<SkylarkProviders> providers,
-      Function<SkylarkProviders, Map<K, V>> mapGetter)
-      throws DuplicateException {
-    Set<K> seenKeys = new HashSet<>();
-    ImmutableMap.Builder<K, V> resultBuilder = ImmutableMap.builder();
-    for (SkylarkProviders provider : providers) {
-      Map<K, V> map = mapGetter.apply(provider);
-      for (K key : map.keySet()) {
-        if (!seenKeys.add(key)) {
-          // TODO(dslomov): add better diagnostics.
-          throw new DuplicateException("Provider " + key + " provided twice");
-        }
-
-        V v = map.get(key);
-        if (v != null) {
-          resultBuilder.put(key, v);
-        }
-      }
-    }
-    return resultBuilder.build();
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProvider.java
index de538b974c..9ee8933366 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProvider.java
@@ -60,4 +60,19 @@ package com.google.devtools.build.lib.analysis;
  * @see com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory
  */
 public interface TransitiveInfoProvider {
+
+  /**
+   * Implement this to mark that a native provider should be exported with
+   * certain name to Skylark.
+   * Broken: only works for rules, not for aspects.
+   * DO NOT USE FOR NEW CODE!
+   *
+   * Use native declared providers
+   * ({@link com.google.devtools.build.lib.packages.NativeClassObjectConstructor}) to
+   * expose providers to both native and Skylark code.
+   */
+  @Deprecated
+  interface WithLegacySkylarkName {
+    String getSkylarkName();
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java
index 96f9cb7cab..d8fa9ae4ae 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMap.java
@@ -14,19 +14,81 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.devtools.build.lib.packages.ClassObjectConstructor;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
+import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import javax.annotation.Nullable;
 import javax.annotation.concurrent.Immutable;
 
-/** Provides a mapping between a TransitiveInfoProvider class and an instance. */
+/**
+ * Provides a mapping between an identifier for transitive information and its instance.
+ * (between provider identifier and provider instance)
+ *
+ * We have three kinds of provider identifiers:
+ * <ul>
+ *   <li>Declared providers. They are exposed to Skylark and identified by
+ *   {@link ClassObjectConstructor.Key}. Provider instances are {@link SkylarkClassObject}s.</li>
+ *   <li>Native providers. They are identified by their {@link Class} and their instances
+ *   are instances of that class. They should implement {@link TransitiveInfoProvider} marker
+ *   interface.
+ *   </li>
+ *   <li>Legacy Skylark providers (deprecated). They are identified by simple strings,
+ *   and their instances are more-less random objects.</li>
+ * </ul>
+ */
 @Immutable
 public interface TransitiveInfoProviderMap {
-  /** Returns the instance for the provided providerClass, or <tt>null</tt> if not present. */
+  /** Returns the instance for the provided providerClass, or {@code null}  if not present. */
   @Nullable
   <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass);
 
+  /**
+   * Returns the instance of declared provider with the given {@code key},
+   * or {@code null} if not present.
+   */
+  @Nullable
+  SkylarkClassObject getProvider(ClassObjectConstructor.Key key);
+
+  /**
+   * Returns the instance of a legacy Skylark  with the given name, or {@code null} if not present.
+   *
+   * todo(dslomov,skylark): remove this as part of legacy provider removal.
+   */
+  @Nullable
+  Object getProvider(String legacyKey);
+
+  /**
+   * Helper method to access SKylark provider with a give {@code id} and validate its type.
+   */
+  @Nullable
+  default <T> T getProvider(
+      SkylarkProviderIdentifier id, Class<T> result) {
+    return result.cast(
+        id.isLegacy() ? this.getProvider(id.getLegacyId()) : this.getProvider(id.getKey())
+    );
+  }
+
+  /**
+   * Returns a count of providers.
+   *
+   * Upper bound for {@code index} in {@link #getProviderKeyAt(int index)}
+   * and {@link #getProviderInstanceAt(int index)} }.
+   *
+   * Low-level method, use with care.
+   */
   int getProviderCount();
 
-  Class<? extends TransitiveInfoProvider> getProviderClassAt(int i);
+  /**
+   * Return value is one of:
+   * <ul>
+   *   <li>{@code Class<? extends TransitiveInfoProvider>}</li>
+   *   <li>String</li>
+   *   <li>{@link ClassObjectConstructor.Key}</li>
+   * </ul>
+   *
+   * Low-level method, use with care.
+   */
+  Object getProviderKeyAt(int index);
 
-  TransitiveInfoProvider getProviderAt(int i);
+  Object getProviderInstanceAt(int index);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java
index 89ca1f13bd..38eb63d767 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapBuilder.java
@@ -14,6 +14,8 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.devtools.build.lib.packages.ClassObjectConstructor;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
 import com.google.devtools.build.lib.util.Preconditions;
 import java.util.Arrays;
 import java.util.LinkedHashMap;
@@ -23,8 +25,7 @@ import javax.annotation.Nullable;
 public class TransitiveInfoProviderMapBuilder {
 
   // TODO(arielb): share the instance with the outerclass and copy on write instead?
-  private final LinkedHashMap<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider>
-      providers = new LinkedHashMap();
+  private final LinkedHashMap<Object, Object> providers = new LinkedHashMap<>();
 
   /**
    * Returns <tt>true</tt> if a {@link TransitiveInfoProvider} has been added for the class
@@ -34,6 +35,15 @@ public class TransitiveInfoProviderMapBuilder {
     return providers.containsKey(providerClass);
   }
 
+  public boolean contains(String legacyId) {
+    return providers.containsKey(legacyId);
+  }
+
+  public boolean contains(ClassObjectConstructor.Key key) {
+    return providers.containsKey(key);
+  }
+
+
   public <T extends TransitiveInfoProvider> TransitiveInfoProviderMapBuilder put(
       Class<? extends T> providerClass, T provider) {
     Preconditions.checkNotNull(providerClass);
@@ -45,6 +55,20 @@ public class TransitiveInfoProviderMapBuilder {
     return this;
   }
 
+  public TransitiveInfoProviderMapBuilder put(SkylarkClassObject classObject) {
+    Preconditions.checkNotNull(classObject);
+    providers.put(classObject.getConstructor().getKey(), classObject);
+    return this;
+  }
+
+  public TransitiveInfoProviderMapBuilder put(String legacyKey, Object classObject) {
+    Preconditions.checkNotNull(legacyKey);
+    Preconditions.checkNotNull(classObject);
+    providers.put(legacyKey, classObject);
+    return this;
+  }
+
+
   public TransitiveInfoProviderMapBuilder add(TransitiveInfoProvider provider) {
     return put(TransitiveInfoProviderEffectiveClassHelper.get(provider), provider);
   }
@@ -53,9 +77,9 @@ public class TransitiveInfoProviderMapBuilder {
     return addAll(Arrays.asList(providers));
   }
 
-  public TransitiveInfoProviderMapBuilder addAll(TransitiveInfoProviderMap providers) {
-    for (int i = 0; i < providers.getProviderCount(); ++i) {
-      add(providers.getProviderAt(i));
+  public TransitiveInfoProviderMapBuilder addAll(TransitiveInfoProviderMap other) {
+    for (int i = 0; i < other.getProviderCount(); ++i) {
+      providers.put(other.getProviderKeyAt(i), other.getProviderInstanceAt(i));
     }
     return this;
   }
@@ -72,6 +96,11 @@ public class TransitiveInfoProviderMapBuilder {
     return (P) providers.get(providerClass);
   }
 
+  @Nullable
+  public SkylarkClassObject getProvider(ClassObjectConstructor.Key key) {
+    return (SkylarkClassObject) providers.get(key);
+  }
+
   public TransitiveInfoProviderMap build() {
     return new TransitiveInfoProviderMapImpl(providers);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapImpl.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapImpl.java
index ca1b9c854a..b0ba5836a3 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapImpl.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoProviderMapImpl.java
@@ -15,6 +15,8 @@
 package com.google.devtools.build.lib.analysis;
 
 import com.google.devtools.build.lib.collect.ImmutableSharedKeyMap;
+import com.google.devtools.build.lib.packages.ClassObjectConstructor;
+import com.google.devtools.build.lib.packages.SkylarkClassObject;
 import java.util.Map;
 import javax.annotation.Nullable;
 
@@ -23,11 +25,10 @@ import javax.annotation.Nullable;
  * memory efficiency, inheritance is used instead of aggregation as an implementation detail.
  */
 class TransitiveInfoProviderMapImpl
-    extends ImmutableSharedKeyMap<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider>
+    extends ImmutableSharedKeyMap<Object, Object>
     implements TransitiveInfoProviderMap {
 
-  TransitiveInfoProviderMapImpl(
-      Map<Class<? extends TransitiveInfoProvider>, TransitiveInfoProvider> map) {
+  TransitiveInfoProviderMapImpl(Map<Object, Object> map) {
     super(map);
   }
 
@@ -40,18 +41,30 @@ class TransitiveInfoProviderMapImpl
     return (P) get(effectiveClass);
   }
 
+  @Nullable
+  @Override
+  public SkylarkClassObject getProvider(ClassObjectConstructor.Key key) {
+    return (SkylarkClassObject) get(key);
+  }
+
+  @Nullable
+  @Override
+  public Object getProvider(String legacyKey) {
+    return get(legacyKey);
+  }
+
   @Override
   public int getProviderCount() {
     return size();
   }
 
   @Override
-  public Class<? extends TransitiveInfoProvider> getProviderClassAt(int i) {
+  public Object getProviderKeyAt(int i) {
     return keyAt(i);
   }
 
   @Override
-  public TransitiveInfoProvider getProviderAt(int i) {
+  public Object getProviderInstanceAt(int i) {
     return valueAt(i);
   }
 }
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 e2ebb44dab..ec8d7c412e 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
@@ -150,9 +150,7 @@ import com.google.devtools.build.lib.rules.objc.ObjcImportRule;
 import com.google.devtools.build.lib.rules.objc.ObjcLibraryRule;
 import com.google.devtools.build.lib.rules.objc.ObjcProtoAspect;
 import com.google.devtools.build.lib.rules.objc.ObjcProtoLibraryRule;
-import com.google.devtools.build.lib.rules.objc.ObjcProvider;
 import com.google.devtools.build.lib.rules.objc.ObjcRuleClasses;
-import com.google.devtools.build.lib.rules.objc.XcTestAppProvider;
 import com.google.devtools.build.lib.rules.platform.ConstraintSettingRule;
 import com.google.devtools.build.lib.rules.platform.ConstraintValueRule;
 import com.google.devtools.build.lib.rules.platform.PlatformCommon;
@@ -558,10 +556,6 @@ public class BazelRuleClassProvider {
           String toolsRepository = checkNotNull(builder.getToolsRepository());
 
           builder.addBuildInfoFactory(new ObjcBuildInfoFactory());
-          builder.registerSkylarkProvider(
-              ObjcProvider.OBJC_SKYLARK_PROVIDER_NAME, ObjcProvider.class);
-          builder.registerSkylarkProvider(
-              XcTestAppProvider.XCTEST_APP_SKYLARK_PROVIDER_NAME, XcTestAppProvider.class);
           builder.addSkylarkAccessibleTopLevels("apple_common", new AppleSkylarkCommon());
 
           builder.addConfig(ObjcCommandLineOptions.class, new ObjcConfigurationLoader());
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 3ac06faff7..6ef753c92c 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
@@ -28,7 +28,6 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.ClassObjectConstructor;
 import com.google.devtools.build.lib.packages.SkylarkClassObject;
-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;
@@ -83,12 +82,6 @@ public final class AliasConfiguredTarget implements ConfiguredTarget, ClassObjec
     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/SkylarkApiProvider.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkApiProvider.java
index 96e0588f90..b9fbdd07e0 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkApiProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkApiProvider.java
@@ -28,9 +28,12 @@ public abstract class SkylarkApiProvider {
     return info;
   }
 
-  /** Must be called once (and only once). */
-  public void init(TransitiveInfoCollection info) {
-    Preconditions.checkState(this.info == null);
+  public final void init(TransitiveInfoCollection info) {
+    if (this.info != null) {
+      // Allow multiple calls, but only consistent ones.
+      Preconditions.checkState(info == this.info);
+      return;
+    }
     this.info = Preconditions.checkNotNull(info);
   }
 }
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 a6704b59e5..e990d20b21 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
@@ -62,15 +62,12 @@ import java.util.Map;
 public final class SkylarkRuleConfiguredTargetBuilder {
 
   /**
-   * Create a Rule Configured Target from the ruleContext and the ruleImplementation.  The
-   * registeredProviderTypes map indicates which keys in structs returned by skylark rules
-   * should be interpreted as native TransitiveInfoProvider instances of type (map value).
+   * Create a Rule Configured Target from the ruleContext and the ruleImplementation.
    */
   public static ConfiguredTarget buildRule(
       RuleContext ruleContext,
       BaseFunction ruleImplementation,
-      SkylarkSemanticsOptions skylarkSemantics,
-      Map<String, Class<? extends TransitiveInfoProvider>> registeredProviderTypes)
+      SkylarkSemanticsOptions skylarkSemantics)
       throws InterruptedException {
     String expectFailure = ruleContext.attributes().get("expect_failure", Type.STRING);
     SkylarkRuleContext skylarkRuleContext = null;
@@ -103,8 +100,7 @@ public final class SkylarkRuleConfiguredTargetBuilder {
         ruleContext.ruleError("Expected failure not found: " + expectFailure);
         return null;
       }
-      ConfiguredTarget configuredTarget =
-          createTarget(ruleContext, target, registeredProviderTypes);
+      ConfiguredTarget configuredTarget = createTarget(ruleContext, target);
       SkylarkProviderValidationUtil.checkOrphanArtifacts(ruleContext);
       return configuredTarget;
     } catch (EvalException e) {
@@ -149,10 +145,7 @@ public final class SkylarkRuleConfiguredTargetBuilder {
 
   // TODO(bazel-team): this whole defaulting - overriding executable, runfiles and files_to_build
   // is getting out of hand. Clean this whole mess up.
-  private static ConfiguredTarget createTarget(
-      RuleContext ruleContext,
-      Object target,
-      Map<String, Class<? extends TransitiveInfoProvider>> registeredProviderTypes)
+  private static ConfiguredTarget createTarget(RuleContext ruleContext, Object target)
       throws EvalException {
     Artifact executable = getExecutable(ruleContext, target);
     RuleConfiguredTargetBuilder builder = new RuleConfiguredTargetBuilder(ruleContext);
@@ -164,7 +157,7 @@ public final class SkylarkRuleConfiguredTargetBuilder {
     }
     builder.setFilesToBuild(filesToBuild.build());
     return addStructFieldsAndBuild(
-        ruleContext, builder, target, executable, registeredProviderTypes);
+        ruleContext, builder, target, executable);
   }
 
   private static Artifact getExecutable(RuleContext ruleContext, Object target)
@@ -238,15 +231,14 @@ public final class SkylarkRuleConfiguredTargetBuilder {
       RuleContext ruleContext,
       RuleConfiguredTargetBuilder builder,
       Object target,
-      Artifact executable,
-      Map<String, Class<? extends TransitiveInfoProvider>> registeredProviderTypes)
+      Artifact executable)
       throws EvalException {
     Location loc = null;
     Boolean isParsed = false;
     if (target instanceof SkylarkClassObject) {
       SkylarkClassObject struct = (SkylarkClassObject) target;
       loc = struct.getCreationLoc();
-      parseProviderKeys(struct, false, ruleContext, loc, executable, registeredProviderTypes,
+      parseProviderKeys(struct, false, ruleContext, loc, executable,
           builder);
       isParsed = true;
     } else if (target instanceof Iterable) {
@@ -262,7 +254,7 @@ public final class SkylarkRuleConfiguredTargetBuilder {
         if (declaredProvider.getConstructor().getKey().equals(
             DefaultProvider.SKYLARK_CONSTRUCTOR.getKey())) {
           parseProviderKeys(declaredProvider, true, ruleContext, loc, executable,
-              registeredProviderTypes, builder);
+              builder);
           isParsed = true;
         } else {
           Location creationLoc = declaredProvider.getCreationLocOrNull();
@@ -289,7 +281,6 @@ public final class SkylarkRuleConfiguredTargetBuilder {
       RuleContext ruleContext,
       Location loc,
       Artifact executable,
-      Map<String, Class<? extends TransitiveInfoProvider>> registeredProviderTypes,
       RuleConfiguredTargetBuilder builder) throws EvalException {
     Runfiles statelessRunfiles = null;
     Runfiles dataRunfiles = null;
@@ -348,10 +339,8 @@ public final class SkylarkRuleConfiguredTargetBuilder {
                 InstrumentedFilesCollector.NO_METADATA_COLLECTOR,
                 Collections.<Artifact>emptySet());
         builder.addProvider(InstrumentedFilesProvider.class, instrumentedFilesProvider);
-      } else if (registeredProviderTypes.containsKey(key) && !isDefaultProvider) {
-        Class<? extends TransitiveInfoProvider> providerType = registeredProviderTypes.get(key);
-        TransitiveInfoProvider providerField = cast(key, provider, providerType, loc);
-        builder.addProvider(providerType, providerField);
+      } else if (provider.getValue(key) instanceof TransitiveInfoProvider.WithLegacySkylarkName) {
+        builder.addProvider((TransitiveInfoProvider) provider.getValue(key));
       } else if (isDefaultProvider) {
         // Custom keys are not allowed for default providers
         throw new EvalException(loc, "Invalid key for default provider: " + key);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
index 3590f5c10e..e918abb94a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
@@ -56,13 +56,19 @@ import java.util.Map;
   category = SkylarkModuleCategory.PROVIDER,
   doc = "A provider for compilation and linking of objc."
 )
-public final class ObjcProvider extends SkylarkClassObject implements TransitiveInfoProvider {
+public final class ObjcProvider extends SkylarkClassObject
+    implements TransitiveInfoProvider, TransitiveInfoProvider.WithLegacySkylarkName {
 
   /**
    * The skylark struct key name for a rule implementation to use when exporting an ObjcProvider.
    */
   public static final String OBJC_SKYLARK_PROVIDER_NAME = "objc";
 
+  @Override
+  public String getSkylarkName() {
+    return OBJC_SKYLARK_PROVIDER_NAME;
+  }
+
   /**
    * Represents one of the things this provider can provide transitively. Things are provided as
    * {@link NestedSet}s of type E.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/XcTestAppProvider.java b/src/main/java/com/google/devtools/build/lib/rules/objc/XcTestAppProvider.java
index 38219406c1..e25c88c154 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/XcTestAppProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/XcTestAppProvider.java
@@ -32,12 +32,18 @@ import com.google.devtools.build.lib.util.Preconditions;
   category = SkylarkModuleCategory.PROVIDER,
   doc = "A provider for XCTest apps for testing."
 )
-public final class XcTestAppProvider extends SkylarkClassObject implements TransitiveInfoProvider {
+public final class XcTestAppProvider extends SkylarkClassObject
+    implements TransitiveInfoProvider, TransitiveInfoProvider.WithLegacySkylarkName {
   /**
    * The skylark struct key name for a rule implementation to use when exporting an ObjcProvider.
    */
   public static final String XCTEST_APP_SKYLARK_PROVIDER_NAME = "xctest_app";
 
+  @Override
+  public String getSkylarkName() {
+    return XCTEST_APP_SKYLARK_PROVIDER_NAME;
+  }
+
   private static final ClassObjectConstructor XCTEST_APP_PROVIDER =
       new NativeClassObjectConstructor("xctest_app_provider") {
         @Override