diff --git a/src/main/java/com/google/devtools/build/lib/analysis/Allowlist.java b/src/main/java/com/google/devtools/build/lib/analysis/Allowlist.java
index 1dfa950..b6ff313 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/Allowlist.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Allowlist.java
@@ -48,7 +48,7 @@
     String attributeName = getAttributeNameFromAllowlistName(allowlistName).iterator().next();
     return attr(attributeName, LABEL)
         .cfg(HostTransition.createFactory())
-        .mandatoryNativeProviders(ImmutableList.of(PackageSpecificationProvider.class));
+        .mandatoryBuiltinProviders(ImmutableList.of(PackageSpecificationProvider.class));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
index 3253160..d3a78ce 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
@@ -32,7 +32,6 @@
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.Info;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TriState;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -93,23 +92,6 @@
    */
   public static <T extends Info> List<T> getProviders(
       Iterable<? extends TransitiveInfoCollection> prerequisites,
-      final NativeProvider<T> starlarkKey) {
-    ImmutableList.Builder<T> result = ImmutableList.builder();
-    for (TransitiveInfoCollection prerequisite : prerequisites) {
-      T prerequisiteProvider = prerequisite.get(starlarkKey);
-      if (prerequisiteProvider != null) {
-        result.add(prerequisiteProvider);
-      }
-    }
-    return result.build();
-  }
-
-  /**
-   * Returns the list of declared providers (native and Starlark) of the specified Starlark key from
-   * a set of transitive info collections.
-   */
-  public static <T extends Info> List<T> getProviders(
-      Iterable<? extends TransitiveInfoCollection> prerequisites,
       final BuiltinProvider<T> starlarkKey) {
     ImmutableList.Builder<T> result = ImmutableList.builder();
     for (TransitiveInfoCollection prerequisite : prerequisites) {
@@ -131,12 +113,6 @@
 
   /** Returns the iterable of collections that have the specified provider. */
   public static <S extends TransitiveInfoCollection, C extends Info> Iterable<S> filterByProvider(
-      Iterable<S> prerequisites, final NativeProvider<C> provider) {
-    return Iterables.filter(prerequisites, target -> target.get(provider) != null);
-  }
-
-  /** Returns the iterable of collections that have the specified provider. */
-  public static <S extends TransitiveInfoCollection, C extends Info> Iterable<S> filterByProvider(
       Iterable<S> prerequisites, final BuiltinProvider<C> provider) {
     return Iterables.filter(prerequisites, target -> target.get(provider) != null);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildSettingProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildSettingProvider.java
index b43af77..9abee25 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildSettingProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildSettingProvider.java
@@ -21,14 +21,14 @@
 import com.google.devtools.build.lib.packages.Type;
 
 /**
- * A native provider to allow select()s to know the type, default value, and label when selecting on
- * build settings
+ * A built-in provider to allow select()s to know the type, default value, and label when selecting
+ * on build settings
  */
 public class BuildSettingProvider implements TransitiveInfoProvider {
 
   public static final RequiredProviders REQUIRE_BUILD_SETTING_PROVIDER =
       RequiredProviders.acceptAnyBuilder()
-          .addNativeSet(ImmutableSet.of(BuildSettingProvider.class))
+          .addBuiltinSet(ImmutableSet.of(BuildSettingProvider.class))
           .build();
 
   private final BuildSetting buildSetting;
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 ee92dce..f0539ed 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
@@ -595,7 +595,7 @@
     if (advertisedProviders.canHaveAnyProvider()) {
       return;
     }
-    for (Class<?> aClass : advertisedProviders.getNativeProviders()) {
+    for (Class<?> aClass : advertisedProviders.getBuiltinProviders()) {
       if (configuredAspect.getProvider(aClass.asSubclass(TransitiveInfoProvider.class)) == null) {
         eventHandler.handle(
             Event.error(
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DefaultInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/DefaultInfo.java
index a09a4e6..8fb7367 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/DefaultInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DefaultInfo.java
@@ -63,7 +63,7 @@
       Runfiles defaultRunfiles,
       Artifact executable,
       @Nullable FilesToRunProvider filesToRunProvider) {
-    super(PROVIDER, loc);
+    super(loc);
     this.files = files;
     this.runfiles = runfiles;
     this.dataRunfiles = dataRunfiles;
@@ -72,6 +72,11 @@
     this.filesToRunProvider = filesToRunProvider;
   }
 
+  @Override
+  public DefaultInfoProvider getProvider() {
+    return PROVIDER;
+  }
+
   public static DefaultInfo build(
       @Nullable RunfilesProvider runfilesProvider,
       FileProvider fileProvider,
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/OutputGroupInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/OutputGroupInfo.java
index b696494..7655dc6 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/OutputGroupInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/OutputGroupInfo.java
@@ -137,11 +137,16 @@
   private final ImmutableMap<String, NestedSet<Artifact>> outputGroups;
 
   public OutputGroupInfo(ImmutableMap<String, NestedSet<Artifact>> outputGroups) {
-    super(STARLARK_CONSTRUCTOR, Location.BUILTIN);
+    super(Location.BUILTIN);
     this.outputGroups = outputGroups;
   }
 
   @Override
+  public OutputGroupInfoProvider getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
+  @Override
   public boolean isImmutable() {
     return true; // immutable and Starlark-hashable
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ProviderCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/ProviderCollection.java
index f941685..dbe78e7 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ProviderCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ProviderCollection.java
@@ -16,7 +16,6 @@
 
 import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.Info;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.packages.StarlarkProviderIdentifier;
 import javax.annotation.Nullable;
@@ -43,7 +42,7 @@
   /**
    * Returns the declared provider requested, or null, if the information is not found.
    *
-   * <p>Use {@link #get(NativeProvider)} for native providers.
+   * <p>Use {@link #get(BuiltinProvider)} for built-in providers.
    */
   @Nullable
   Info get(Provider.Key providerKey);
@@ -51,17 +50,7 @@
   /**
    * Returns the native declared provider requested, or null, if the information is not found.
    *
-   * <p>Type-safe version of {@link #get(Provider.Key)} for native providers.
-   */
-  @Nullable
-  default <T extends Info> T get(NativeProvider<T> provider) {
-    return provider.getValueClass().cast(get(provider.getKey()));
-  }
-
-  /**
-   * Returns the native declared provider requested, or null, if the information is not found.
-   *
-   * <p>Type-safe version of {@link #get(Provider.Key)} for native providers.
+   * <p>Type-safe version of {@link #get(Provider.Key)} for built-in providers.
    */
   @Nullable
   default <T extends Info> T get(BuiltinProvider<T> provider) {
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 d1ca30d..78ee802 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
@@ -76,7 +76,6 @@
 import com.google.devtools.build.lib.packages.ImplicitOutputsFunction;
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.InputFile;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
 import com.google.devtools.build.lib.packages.RawAttributeMapper;
@@ -1091,15 +1090,6 @@
    * the specified attribute of this target in the BUILD file.
    */
   public <T extends Info> List<T> getPrerequisites(
-      String attributeName, NativeProvider<T> starlarkKey) {
-    return AnalysisUtils.getProviders(getPrerequisites(attributeName), starlarkKey);
-  }
-
-  /**
-   * Returns all the declared providers (native and Starlark) for the specified constructor under
-   * the specified attribute of this target in the BUILD file.
-   */
-  public <T extends Info> List<T> getPrerequisites(
       String attributeName, BuiltinProvider<T> starlarkKey) {
     return AnalysisUtils.getProviders(getPrerequisites(attributeName), starlarkKey);
   }
@@ -1110,22 +1100,10 @@
    * TransitiveInfoCollection under the specified attribute.
    */
   @Nullable
-  public <T extends Info> T getPrerequisite(String attributeName, NativeProvider<T> starlarkKey) {
-    TransitiveInfoCollection prerequisite = getPrerequisite(attributeName);
-    return prerequisite == null ? null : prerequisite.get(starlarkKey);
-  }
-
-  /**
-   * Returns the declared provider (native and Starlark) for the specified constructor under the
-   * specified attribute of this target in the BUILD file. May return null if there is no
-   * TransitiveInfoCollection under the specified attribute.
-   */
-  @Nullable
   public <T extends Info> T getPrerequisite(String attributeName, BuiltinProvider<T> starlarkKey) {
     TransitiveInfoCollection prerequisite = getPrerequisite(attributeName);
     return prerequisite == null ? null : prerequisite.get(starlarkKey);
   }
-
   /**
    * Returns all the providers of the specified type that are listed under the specified attribute
    * of this target in the BUILD file, and that contain the specified provider.
@@ -1142,15 +1120,6 @@
    * of this target in the BUILD file, and that contain the specified provider.
    */
   public <C extends Info> Iterable<? extends TransitiveInfoCollection> getPrerequisitesIf(
-      String attributeName, NativeProvider<C> classType) {
-    return AnalysisUtils.filterByProvider(getPrerequisites(attributeName), classType);
-  }
-
-  /**
-   * Returns all the providers of the specified type that are listed under the specified attribute
-   * of this target in the BUILD file, and that contain the specified provider.
-   */
-  public <C extends Info> Iterable<? extends TransitiveInfoCollection> getPrerequisitesIf(
       String attributeName, BuiltinProvider<C> classType) {
     return AnalysisUtils.filterByProvider(getPrerequisites(attributeName), classType);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TemplateVariableInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/TemplateVariableInfo.java
index d542743..6d0916d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TemplateVariableInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TemplateVariableInfo.java
@@ -52,11 +52,16 @@
 
   @AutoCodec.Instantiator
   public TemplateVariableInfo(ImmutableMap<String, String> variables, Location location) {
-    super(PROVIDER, location);
+    super(location);
     this.variables = variables;
   }
 
   @Override
+  public BuiltinProvider<TemplateVariableInfo> getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public ImmutableMap<String, String> getVariables() {
     return variables;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintSettingInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintSettingInfo.java
index 01489a3..abfb7b3 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintSettingInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintSettingInfo.java
@@ -43,13 +43,18 @@
 
   @VisibleForSerialization
   ConstraintSettingInfo(Label label, Label defaultConstraintValueLabel, Location location) {
-    super(PROVIDER, location);
+    super(location);
 
     this.label = label;
     this.defaultConstraintValueLabel = defaultConstraintValueLabel;
   }
 
   @Override
+  public BuiltinProvider<ConstraintSettingInfo> getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Label label() {
     return label;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintValueInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintValueInfo.java
index 328fea7..012f7af 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintValueInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintValueInfo.java
@@ -46,13 +46,17 @@
 
   @VisibleForSerialization
   ConstraintValueInfo(ConstraintSettingInfo constraint, Label label, Location location) {
-    super(PROVIDER, location);
-
+    super(location);
     this.constraint = constraint;
     this.label = label;
   }
 
   @Override
+  public BuiltinProvider<ConstraintValueInfo> getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public ConstraintSettingInfo constraint() {
     return constraint;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformInfo.java
index 9fbd1fd..64bf4ce 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/PlatformInfo.java
@@ -113,7 +113,7 @@
       String remoteExecutionProperties,
       ImmutableMap<String, String> execProperties,
       Location location) {
-    super(PROVIDER, location);
+    super(location);
 
     this.label = label;
     this.constraints = constraints;
@@ -122,6 +122,11 @@
   }
 
   @Override
+  public BuiltinProvider<PlatformInfo> getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Label label() {
     return label;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainInfo.java
index cdc2915..e793d81 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainInfo.java
@@ -65,15 +65,19 @@
 
   /** Constructs a ToolchainInfo. The {@code values} map itself is not retained. */
   protected ToolchainInfo(Map<String, Object> values, Location location) {
-    super(PROVIDER, location);
+    super(location);
     this.values = copyValues(values);
   }
 
   public ToolchainInfo(Map<String, Object> values) {
-    super(PROVIDER, Location.BUILTIN);
     this.values = copyValues(values);
   }
 
+  @Override
+  public BuiltinProvider<ToolchainInfo> getProvider() {
+    return PROVIDER;
+  }
+
   /**
    * Preprocesses a map of field values to convert the field names and field values to
    * Starlark-acceptable names and types.
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainTypeInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainTypeInfo.java
index 7422803..82d23ef 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainTypeInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/ToolchainTypeInfo.java
@@ -48,11 +48,16 @@
 
   @VisibleForSerialization
   ToolchainTypeInfo(Label typeLabel, Location location) {
-    super(PROVIDER, location);
+    super(location);
     this.typeLabel = typeLabel;
   }
 
   @Override
+  public BuiltinProvider<ToolchainTypeInfo> getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Label typeLabel() {
     return typeLabel;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkApiProvider.java b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkApiProvider.java
index d30afa8..75df5de 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkApiProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkApiProvider.java
@@ -18,7 +18,7 @@
 import com.google.devtools.build.lib.analysis.ProviderCollection;
 
 /**
- * An abstract class for adding a Starlark API for the native providers. Derived classes should
+ * An abstract class for adding a Starlark API for the built-in providers. Derived classes should
  * declare functions to be used from Starlark.
  */
 public abstract class StarlarkApiProvider {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleConfiguredTargetUtil.java b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleConfiguredTargetUtil.java
index 1aba00b..3d1cf1a 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleConfiguredTargetUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/starlark/StarlarkRuleConfiguredTargetUtil.java
@@ -37,10 +37,9 @@
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
 import com.google.devtools.build.lib.packages.BazelStarlarkContext;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.FunctionSplitTransitionAllowlist;
 import com.google.devtools.build.lib.packages.Info;
-import com.google.devtools.build.lib.packages.NativeProvider;
-import com.google.devtools.build.lib.packages.NativeProvider.WithLegacyStarlarkName;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
@@ -405,9 +404,9 @@
         builder.addNativeDeclaredProvider(info);
       }
 
-      if (info.getProvider() instanceof NativeProvider.WithLegacyStarlarkName) {
-        WithLegacyStarlarkName providerWithLegacyName =
-            (WithLegacyStarlarkName) info.getProvider();
+      if (info.getProvider() instanceof BuiltinProvider.WithLegacyStarlarkName) {
+        BuiltinProvider.WithLegacyStarlarkName providerWithLegacyName =
+            (BuiltinProvider.WithLegacyStarlarkName) info.getProvider();
         if (shouldAddWithLegacyKey(oldStyleProviders, providerWithLegacyName)) {
           builder.addStarlarkTransitiveInfo(providerWithLegacyName.getStarlarkName(), info);
         }
@@ -426,9 +425,9 @@
     if (builder.containsProviderKey(info.getProvider().getKey())) {
       return false;
     }
-    if (info.getProvider() instanceof NativeProvider.WithLegacyStarlarkName) {
+    if (info.getProvider() instanceof BuiltinProvider.WithLegacyStarlarkName) {
       String canonicalLegacyKey =
-          ((WithLegacyStarlarkName) info.getProvider()).getStarlarkName();
+          ((BuiltinProvider.WithLegacyStarlarkName) info.getProvider()).getStarlarkName();
       // Add info using its modern key if it was specified using its canonical legacy key, or
       // if no provider was used using that canonical legacy key.
       return fieldName.equals(canonicalLegacyKey)
@@ -440,7 +439,7 @@
 
   @SuppressWarnings("deprecation") // For legacy migrations
   private static boolean shouldAddWithLegacyKey(
-      StructImpl oldStyleProviders, WithLegacyStarlarkName provider)
+      StructImpl oldStyleProviders, BuiltinProvider.WithLegacyStarlarkName provider)
       throws EvalException {
     String canonicalLegacyKey = provider.getStarlarkName();
     // Add info using its canonical legacy key if no provider was specified using that canonical
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/ExecutionInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/test/ExecutionInfo.java
index 4ef6c69..c7c1bce 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/ExecutionInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/ExecutionInfo.java
@@ -15,8 +15,8 @@
 
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.test.ExecutionInfoApi;
 import java.util.Map;
 
@@ -28,16 +28,20 @@
 public final class ExecutionInfo extends NativeInfo implements ExecutionInfoApi {
 
   /** Starlark constructor and identifier for ExecutionInfo. */
-  public static final NativeProvider<ExecutionInfo> PROVIDER =
-      new NativeProvider<ExecutionInfo>(ExecutionInfo.class, "ExecutionInfo") {};
+  public static final BuiltinProvider<ExecutionInfo> PROVIDER =
+      new BuiltinProvider<ExecutionInfo>("ExecutionInfo", ExecutionInfo.class) {};
 
   private final ImmutableMap<String, String> executionInfo;
 
   public ExecutionInfo(Map<String, String> requirements) {
-    super(PROVIDER);
     this.executionInfo = ImmutableMap.copyOf(requirements);
   }
 
+  @Override
+  public BuiltinProvider<ExecutionInfo> getProvider() {
+    return PROVIDER;
+  }
+
   /**
    * Returns a map to indicate special execution requirements, such as hardware
    * platforms, etc. Rule tags, such as "requires-XXX", may also be added
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesInfo.java
index 24544e5..334a43e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/InstrumentedFilesInfo.java
@@ -57,7 +57,6 @@
       NestedSet<Artifact> coverageSupportFiles,
       NestedSet<Pair<String, String>> coverageEnvironment,
       NestedSet<Pair<String, String>> reportedToActualSources) {
-    super(STARLARK_CONSTRUCTOR);
     this.instrumentedFiles = instrumentedFiles;
     this.instrumentationMetadataFiles = instrumentationMetadataFiles;
     this.baselineCoverageFiles = baselineCoverageFiles;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/test/TestEnvironmentInfo.java b/src/main/java/com/google/devtools/build/lib/analysis/test/TestEnvironmentInfo.java
index 15054e2..f7e4100 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/test/TestEnvironmentInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/test/TestEnvironmentInfo.java
@@ -16,8 +16,8 @@
 
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.test.TestEnvironmentInfoApi;
 import java.util.Map;
 
@@ -26,17 +26,21 @@
 public final class TestEnvironmentInfo extends NativeInfo implements TestEnvironmentInfoApi {
 
   /** Starlark constructor and identifier for TestEnvironmentInfo. */
-  public static final NativeProvider<TestEnvironmentInfo> PROVIDER =
-      new NativeProvider<TestEnvironmentInfo>(TestEnvironmentInfo.class, "TestEnvironment") {};
+  public static final BuiltinProvider<TestEnvironmentInfo> PROVIDER =
+      new BuiltinProvider<TestEnvironmentInfo>("TestEnvironment", TestEnvironmentInfo.class) {};
 
   private final Map<String, String> environment;
 
   /** Constructs a new provider with the given variable name to variable value mapping. */
   public TestEnvironmentInfo(Map<String, String> environment) {
-    super(PROVIDER);
     this.environment = Preconditions.checkNotNull(environment);
   }
 
+  @Override
+  public BuiltinProvider<TestEnvironmentInfo> getProvider() {
+    return PROVIDER;
+  }
+
   /**
    * Returns environment variables which should be set on the test action.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/proto/BazelJavaLiteProtoLibraryRule.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/proto/BazelJavaLiteProtoLibraryRule.java
index 7342224..470aca6 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/proto/BazelJavaLiteProtoLibraryRule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/proto/BazelJavaLiteProtoLibraryRule.java
@@ -60,7 +60,7 @@
         .add(attr("strict_deps", BOOLEAN).value(true).undocumented("for migration"))
         .add(
             attr(JavaProtoAspectCommon.LITE_PROTO_TOOLCHAIN_ATTR, LABEL)
-                .mandatoryNativeProviders(
+                .mandatoryBuiltinProviders(
                     ImmutableList.<Class<? extends TransitiveInfoProvider>>of(
                         ProtoLangToolchainProvider.class))
                 .value(getProtoToolchainLabel(DEFAULT_PROTO_TOOLCHAIN_LABEL)))
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 7f0e4bf..631077c 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
@@ -228,7 +228,7 @@
           </ul>
           <!-- #END_BLAZE_RULE.ATTRIBUTE --> */
           .add(attr("stamp", TRISTATE).value(TriState.AUTO))
-          // TODO(brandjon): Consider adding to py_interpreter a .mandatoryNativeProviders() of
+          // TODO(brandjon): Consider adding to py_interpreter a .mandatoryBuiltinProviders() of
           // PyRuntimeInfoProvider. (Add a test case to PythonConfigurationTest for violations of
           // this requirement.) Probably moot now that this is going to be replaced by toolchains.
           .add(attr(":py_interpreter", LABEL).value(PY_INTERPRETER))
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AdvertisedProviderSet.java b/src/main/java/com/google/devtools/build/lib/packages/AdvertisedProviderSet.java
index 9adeab9..4cce3a1 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AdvertisedProviderSet.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AdvertisedProviderSet.java
@@ -23,26 +23,26 @@
  * Captures the set of providers rules and aspects can advertise. It is either of:
  *
  * <ul>
- *   <li>a set of native and Starlark providers
+ *   <li>a set of builtin and Starlark providers
  *   <li>"can have any provider" set that alias rules have.
  * </ul>
  *
- * <p>Native providers should in theory only contain subclasses of {@link
+ * <p>Built-in providers should in theory only contain subclasses of {@link
  * com.google.devtools.build.lib.analysis.TransitiveInfoProvider}, but our current dependency
  * structure does not allow a reference to that class here.
  */
 @Immutable
 public final class AdvertisedProviderSet {
   private final boolean canHaveAnyProvider;
-  private final ImmutableSet<Class<?>> nativeProviders;
+  private final ImmutableSet<Class<?>> builtinProviders;
   private final ImmutableSet<StarlarkProviderIdentifier> starlarkProviders;
 
   private AdvertisedProviderSet(
       boolean canHaveAnyProvider,
-      ImmutableSet<Class<?>> nativeProviders,
+      ImmutableSet<Class<?>> builtinProviders,
       ImmutableSet<StarlarkProviderIdentifier> starlarkProviders) {
     this.canHaveAnyProvider = canHaveAnyProvider;
-    this.nativeProviders = nativeProviders;
+    this.builtinProviders = builtinProviders;
     this.starlarkProviders = starlarkProviders;
   }
 
@@ -54,17 +54,17 @@
           false, ImmutableSet.<Class<?>>of(), ImmutableSet.<StarlarkProviderIdentifier>of());
 
   public static AdvertisedProviderSet create(
-      ImmutableSet<Class<?>> nativeProviders,
+      ImmutableSet<Class<?>> builtinProviders,
       ImmutableSet<StarlarkProviderIdentifier> starlarkProviders) {
-    if (nativeProviders.isEmpty() && starlarkProviders.isEmpty()) {
+    if (builtinProviders.isEmpty() && starlarkProviders.isEmpty()) {
       return EMPTY;
     }
-    return new AdvertisedProviderSet(false, nativeProviders, starlarkProviders);
+    return new AdvertisedProviderSet(false, builtinProviders, starlarkProviders);
   }
 
   @Override
   public int hashCode() {
-    return Objects.hash(canHaveAnyProvider, nativeProviders, starlarkProviders);
+    return Objects.hash(canHaveAnyProvider, builtinProviders, starlarkProviders);
   }
 
   @Override
@@ -79,7 +79,7 @@
 
     AdvertisedProviderSet that = (AdvertisedProviderSet) obj;
     return Objects.equals(this.canHaveAnyProvider, that.canHaveAnyProvider)
-        && Objects.equals(this.nativeProviders, that.nativeProviders)
+        && Objects.equals(this.builtinProviders, that.builtinProviders)
         && Objects.equals(this.starlarkProviders, that.starlarkProviders);
   }
 
@@ -89,8 +89,8 @@
       return "Any Provider";
     }
     return String.format(
-        "allowed native providers=%s, allowed Starlark providers=%s",
-        getNativeProviders(), getStarlarkProviders());
+        "allowed built-in providers=%s, allowed Starlark providers=%s",
+        getBuiltinProviders(), getStarlarkProviders());
   }
 
   /** Checks whether the rule can have any provider.
@@ -101,11 +101,9 @@
     return canHaveAnyProvider;
   }
 
-  /**
-   * Get all advertised native providers.
-   */
-  public ImmutableSet<Class<?>> getNativeProviders() {
-    return nativeProviders;
+  /** Get all advertised built-in providers. */
+  public ImmutableSet<Class<?>> getBuiltinProviders() {
+    return builtinProviders;
   }
 
   /** Get all advertised Starlark providers. */
@@ -119,13 +117,13 @@
 
   /**
    * Returns {@code true} if this provider set can have any provider, or if it advertises the
-   * specific native provider requested.
+   * specific built-in provider requested.
    */
-  public boolean advertises(Class<?> nativeProviderClass) {
+  public boolean advertises(Class<?> builtinProviderClass) {
     if (canHaveAnyProvider()) {
       return true;
     }
-    return nativeProviders.contains(nativeProviderClass);
+    return builtinProviders.contains(builtinProviderClass);
   }
 
   /**
@@ -142,11 +140,11 @@
   /** Builder for {@link AdvertisedProviderSet} */
   public static class Builder {
     private boolean canHaveAnyProvider;
-    private final ArrayList<Class<?>> nativeProviders;
+    private final ArrayList<Class<?>> builtinProviders;
     private final ArrayList<StarlarkProviderIdentifier> starlarkProviders;
 
     private Builder() {
-      nativeProviders = new ArrayList<>();
+      builtinProviders = new ArrayList<>();
       starlarkProviders = new ArrayList<>();
     }
 
@@ -157,28 +155,28 @@
       Preconditions.checkState(!canHaveAnyProvider, "Alias rules inherit from no other rules");
       Preconditions.checkState(!parentSet.canHaveAnyProvider(),
           "Cannot inherit from alias rules");
-      nativeProviders.addAll(parentSet.getNativeProviders());
+      builtinProviders.addAll(parentSet.getBuiltinProviders());
       starlarkProviders.addAll(parentSet.getStarlarkProviders());
       return this;
     }
 
-    public Builder addNative(Class<?> nativeProvider) {
-      this.nativeProviders.add(nativeProvider);
+    public Builder addBuiltin(Class<?> builtinProvider) {
+      this.builtinProviders.add(builtinProvider);
       return this;
     }
 
     public void canHaveAnyProvider() {
-      Preconditions.checkState(nativeProviders.isEmpty() && starlarkProviders.isEmpty());
+      Preconditions.checkState(builtinProviders.isEmpty() && starlarkProviders.isEmpty());
       this.canHaveAnyProvider = true;
     }
 
     public AdvertisedProviderSet build() {
       if (canHaveAnyProvider) {
-        Preconditions.checkState(nativeProviders.isEmpty() && starlarkProviders.isEmpty());
+        Preconditions.checkState(builtinProviders.isEmpty() && starlarkProviders.isEmpty());
         return ANY;
       }
       return AdvertisedProviderSet.create(
-          ImmutableSet.copyOf(nativeProviders), ImmutableSet.copyOf(starlarkProviders));
+          ImmutableSet.copyOf(builtinProviders), ImmutableSet.copyOf(starlarkProviders));
     }
 
     public Builder addStarlark(String providerName) {
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
index 04f23b5..7fe802d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
@@ -269,7 +269,7 @@
     public Builder requireProviderSets(
         Iterable<ImmutableSet<Class<? extends TransitiveInfoProvider>>> providerSets) {
       for (ImmutableSet<Class<? extends TransitiveInfoProvider>> providerSet : providerSets) {
-        requiredProviders.addNativeSet(providerSet);
+        requiredProviders.addBuiltinSet(providerSet);
       }
       return this;
     }
@@ -279,7 +279,7 @@
      * providers.
      */
     public Builder requireProviders(Class<? extends TransitiveInfoProvider>... providers) {
-      requiredProviders.addNativeSet(ImmutableSet.copyOf(providers));
+      requiredProviders.addBuiltinSet(ImmutableSet.copyOf(providers));
       return this;
     }
 
@@ -302,9 +302,9 @@
       return this;
     }
 
-    public Builder requireAspectsWithNativeProviders(
+    public Builder requireAspectsWithBuiltinProviders(
         Class<? extends TransitiveInfoProvider>... providers) {
-      requiredAspectProviders.addNativeSet(ImmutableSet.copyOf(providers));
+      requiredAspectProviders.addBuiltinSet(ImmutableSet.copyOf(providers));
       return this;
     }
 
@@ -313,7 +313,7 @@
      */
     public Builder advertiseProvider(Class<?>... providers) {
       for (Class<?> provider : providers) {
-        advertisedProviders.addNative(provider);
+        advertisedProviders.addBuiltin(provider);
       }
       return this;
     }
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 4f35aeb..31ad21f 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
@@ -790,11 +790,11 @@
      *
      * <p>If the attribute contains Labels of any other rule type, then if they're in {@link
      * #allowedRuleClassesForLabelsWarning}, the build continues with a warning. Else if they
-     * fulfill {@link #mandatoryNativeProvidersList}, the build continues without error. Else the
+     * fulfill {@link #mandatoryBuiltinProvidersList}, the build continues without error. Else the
      * build fails during analysis.
      *
      * <p>If neither this nor {@link #allowedRuleClassesForLabelsWarning} is set, only rules that
-     * fulfill {@link #mandatoryNativeProvidersList} build without error.
+     * fulfill {@link #mandatoryBuiltinProvidersList} build without error.
      *
      * <p>This only works on a per-target basis, not on a per-file basis; with other words, it works
      * for 'deps' attributes, but not 'srcs' attributes.
@@ -810,11 +810,11 @@
      *
      * <p>If the attribute contains Labels of any other rule type, then if they're in {@link
      * #allowedRuleClassesForLabelsWarning}, the build continues with a warning. Else if they
-     * fulfill {@link #mandatoryNativeProvidersList}, the build continues without error. Else the
+     * fulfill {@link #mandatoryBuiltinProvidersList}, the build continues without error. Else the
      * build fails during analysis.
      *
      * <p>If neither this nor {@link #allowedRuleClassesForLabelsWarning} is set, only rules that
-     * fulfill {@link #mandatoryNativeProvidersList} build without error.
+     * fulfill {@link #mandatoryBuiltinProvidersList} build without error.
      *
      * <p>This only works on a per-target basis, not on a per-file basis; with other words, it works
      * for 'deps' attributes, but not 'srcs' attributes.
@@ -833,11 +833,11 @@
      *
      * <p>If the attribute contains Labels of any other rule type, then if they're in {@link
      * #allowedRuleClassesForLabelsWarning}, the build continues with a warning. Else if they
-     * fulfill {@link #mandatoryNativeProvidersList}, the build continues without error. Else the
+     * fulfill {@link #mandatoryBuiltinProvidersList}, the build continues without error. Else the
      * build fails during analysis.
      *
      * <p>If neither this nor {@link #allowedRuleClassesForLabelsWarning} is set, only rules that
-     * fulfill {@link #mandatoryNativeProvidersList} build without error.
+     * fulfill {@link #mandatoryBuiltinProvidersList} build without error.
      *
      * <p>This only works on a per-target basis, not on a per-file basis; with other words, it works
      * for 'deps' attributes, but not 'srcs' attributes.
@@ -887,18 +887,18 @@
 
     /**
      * If this is a label or label-list attribute, then this sets the allowed rule types with
-     * warning for the labels occurring in the attribute. This must be a disjoint set from
-     * {@link #allowedRuleClasses}.
+     * warning for the labels occurring in the attribute. This must be a disjoint set from {@link
+     * #allowedRuleClasses}.
      *
      * <p>If the attribute contains Labels of any other rule type (other than this or those set in
-     * allowedRuleClasses()) and they fulfill {@link #getMandatoryNativeProvidersList()}}, the build
+     * allowedRuleClasses()) and they fulfill {@link #mandatoryBuiltinProvidersList}}, the build
      * continues without error. Else the build fails during analysis.
      *
-     * <p>If neither this nor {@link #allowedRuleClassesForLabels} is set, only rules that
-     * fulfill {@link #getMandatoryNativeProvidersList()} build without error.
+     * <p>If neither this nor {@link #allowedRuleClassesForLabels} is set, only rules that fulfill
+     * {@link #mandatoryBuiltinProvidersList} build without error.
      *
-     * <p>This only works on a per-target basis, not on a per-file basis; with other words, it
-     * works for 'deps' attributes, but not 'srcs' attributes.
+     * <p>This only works on a per-target basis, not on a per-file basis; with other words, it works
+     * for 'deps' attributes, but not 'srcs' attributes.
      */
     public Builder<TYPE> allowedRuleClassesWithWarning(Collection<String> allowedRuleClasses) {
       return allowedRuleClassesWithWarning(
@@ -907,18 +907,18 @@
 
     /**
      * If this is a label or label-list attribute, then this sets the allowed rule types with
-     * warning for the labels occurring in the attribute. This must be a disjoint set from
-     * {@link #allowedRuleClasses}.
+     * warning for the labels occurring in the attribute. This must be a disjoint set from {@link
+     * #allowedRuleClasses}.
      *
      * <p>If the attribute contains Labels of any other rule type (other than this or those set in
-     * allowedRuleClasses()) and they fulfill {@link #getMandatoryNativeProvidersList()}}, the build
+     * allowedRuleClasses()) and they fulfill {@link #mandatoryBuiltinProvidersList}}, the build
      * continues without error. Else the build fails during analysis.
      *
-     * <p>If neither this nor {@link #allowedRuleClassesForLabels} is set, only rules that
-     * fulfill {@link #getMandatoryNativeProvidersList()} build without error.
+     * <p>If neither this nor {@link #allowedRuleClassesForLabels} is set, only rules that fulfill
+     * {@link #mandatoryBuiltinProvidersList} build without error.
      *
-     * <p>This only works on a per-target basis, not on a per-file basis; with other words, it
-     * works for 'deps' attributes, but not 'srcs' attributes.
+     * <p>This only works on a per-target basis, not on a per-file basis; with other words, it works
+     * for 'deps' attributes, but not 'srcs' attributes.
      */
     public Builder<TYPE> allowedRuleClassesWithWarning(RuleClassNamePredicate allowedRuleClasses) {
       Preconditions.checkState(type.getLabelClass() == LabelClass.DEPENDENCY,
@@ -948,25 +948,25 @@
     }
 
     /**
-     * Sets a list of lists of mandatory native providers. Every configured target occurring in this
-     * label type attribute has to provide all the providers from one of those lists, otherwise an
-     * error is produced during the analysis phase.
+     * Sets a list of lists of mandatory built-in providers. Every configured target occurring in
+     * this label type attribute has to provide all the providers from one of those lists, otherwise
+     * an error is produced during the analysis phase.
      */
-    public final Builder<TYPE> mandatoryNativeProvidersList(
+    public final Builder<TYPE> mandatoryBuiltinProvidersList(
         Iterable<? extends Iterable<Class<? extends TransitiveInfoProvider>>> providersList) {
       Preconditions.checkState(type.getLabelClass() == LabelClass.DEPENDENCY,
           "must be a label-valued type");
 
       for (Iterable<Class<? extends TransitiveInfoProvider>> providers : providersList) {
-        this.requiredProvidersBuilder.addNativeSet(ImmutableSet.copyOf(providers));
+        this.requiredProvidersBuilder.addBuiltinSet(ImmutableSet.copyOf(providers));
       }
       return this;
     }
 
-    public Builder<TYPE> mandatoryNativeProviders(
+    public Builder<TYPE> mandatoryBuiltinProviders(
         Iterable<Class<? extends TransitiveInfoProvider>> providers) {
       if (providers.iterator().hasNext()) {
-        mandatoryNativeProvidersList(ImmutableList.of(providers));
+        mandatoryBuiltinProvidersList(ImmutableList.of(providers));
       }
       return this;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/BuiltinProvider.java b/src/main/java/com/google/devtools/build/lib/packages/BuiltinProvider.java
index 0ff81ee..13aae66 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/BuiltinProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/BuiltinProvider.java
@@ -14,18 +14,21 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
-import com.google.devtools.build.lib.packages.NativeProvider.NativeKey;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import javax.annotation.Nullable;
-import net.starlark.java.eval.EvalException;
 import net.starlark.java.eval.Printer;
-import net.starlark.java.eval.Starlark;
 import net.starlark.java.syntax.Location;
 
 /**
- * Base class for declared providers {@see Provider} defined in native code.
+ * Base class for declared providers {@see Provider} built into Blaze.
  *
- * <p>Every subclass of {@link BuiltinProvider} corresponds to a single declared provider. This is
- * enforced by final {@link #equals(Object)} and {@link #hashCode()}.
+ * <p>Every subclass of {@link BuiltinProvider} should have exactly one instance. If multiple
+ * instances of the same subclass are instantiated, they are considered equivalent. This design is
+ * motivated by the need for serialization. Starlark providers are readily identified by the pair
+ * (.bzl file name, sequence number during execution). BuiltinProviders need an analogous
+ * serializable identifier, yet JVM classes (notoriously) don't have a predictable initialization
+ * order, so we can't use a sequence number. A distinct subclass for each built-in provider acts as
+ * that identifier.
  *
  * <p>Implementations of native declared providers should subclass this class, and define a method
  * in the subclass definition to create instances of its corresponding Info object. The method
@@ -34,33 +37,29 @@
  */
 @Immutable
 public abstract class BuiltinProvider<T extends Info> implements Provider {
-  private final NativeKey key;
+  private final Key key;
   private final String name;
   private final Class<T> valueClass;
 
+  public BuiltinProvider(String name, Class<T> valueClass) {
+    this.key = new Key(name, getClass());
+    this.name = name;
+    this.valueClass = valueClass;
+  }
+
   public Class<T> getValueClass() {
     return valueClass;
   }
 
-  public BuiltinProvider(String name, Class<T> valueClass) {
-    @SuppressWarnings("unchecked")
-    Class<? extends BuiltinProvider<?>> clazz = (Class<? extends BuiltinProvider<?>>) getClass();
-    key = new NativeKey(name, clazz);
-    this.name = name;
-    this.valueClass = valueClass;
-  }
-
   /**
-   * equals() implements singleton class semantics.
+   * Defines the equivalence relation: all BuiltinProviders of the same Java class are equal,
+   * regardless of {@code name} or {@code valueClass}.
    */
   @Override
   public final boolean equals(@Nullable Object other) {
     return other != null && this.getClass().equals(other.getClass());
   }
 
-  /**
-   * hashCode() implements singleton class semantics.
-   */
   @Override
   public final int hashCode() {
     return getClass().hashCode();
@@ -72,7 +71,7 @@
   }
 
   @Override
-  public NativeKey getKey() {
+  public Key getKey() {
     return key;
   }
 
@@ -88,19 +87,60 @@
 
   @Override
   public void repr(Printer printer) {
+    // TODO(adonovan): change to '<provider name>'.
     printer.append("<function " + getPrintableName() + ">");
   }
 
-  /**
-   * Convenience method for subclasses of this class to throw a consistent error when a provider is
-   * unable to be constructed from Starlark.
-   */
-  protected final T throwUnsupportedConstructorException() throws EvalException {
-    throw Starlark.errorf("'%s' cannot be constructed from Starlark", getPrintableName());
-  }
-
   /** Returns the identifier of this provider. */
   public StarlarkProviderIdentifier id() {
     return StarlarkProviderIdentifier.forKey(getKey());
   }
+
+  /**
+   * Implement this to mark that a built-in provider should be exported with certain name to
+   * Starlark. Broken: only works for rules, not for aspects. DO NOT USE FOR NEW CODE!
+   *
+   * @deprecated Use declared providers mechanism exclusively to expose providers to both native and
+   *     Starlark code.
+   */
+  @Deprecated
+  public interface WithLegacyStarlarkName {
+    String getStarlarkName();
+  }
+
+  /** A serializable reference to a {@link BuiltinProvider}. */
+  @AutoCodec
+  @Immutable
+  public static final class Key extends Provider.Key {
+    private final String name;
+    private final Class<? extends Provider> providerClass;
+
+    public Key(String name, Class<? extends Provider> providerClass) {
+      this.name = name;
+      this.providerClass = providerClass;
+    }
+
+    public String getName() {
+      return name;
+    }
+
+    public Class<? extends Provider> getProviderClass() {
+      return providerClass;
+    }
+
+    @Override
+    public int hashCode() {
+      return providerClass.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      return obj instanceof Key && providerClass.equals(((Key) obj).providerClass);
+    }
+
+    @Override
+    public String toString() {
+      return name;
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Info.java b/src/main/java/com/google/devtools/build/lib/packages/Info.java
index 2d013b2..5eb2527 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Info.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Info.java
@@ -23,6 +23,34 @@
  * values, each keyed by its Provider. Every Info is an instance of a Provider: if a Provider is
  * like a Java class, then an Info is like an instance of that class.
  */
+// TODO(adonovan): simplify the hierarchies below in these steps:
+// - Once to_{json,proto} are gone, StructApi can be deleted; structs should never again have
+//   methods.
+// - StructImpl.location can be pushed down into subclasses that need it, much as we did for
+//   StructImpl.provider in this CL.
+// - getErrorMessageFormatForUnknownField can become a method on provider.
+//   It should compute a string from a parameter, not use higher-order formatting.
+// - StructImpl is then really just a collection of helper functions for subclasses
+//   getValue(String, Class), repr, equals, hash. Move them, and merge it into Info interface.
+// - Move StructProvider.STRUCT and make StructProvider private.
+//   The StructProvider.createStruct method could be a simple function like depset, select.
+//   StructProviderApi could be eliminated.
+// - eliminate StarlarkInfo + StarlarkInfo.
+// - NativeInfo's two methods can (IIUC) be deleted immediately, and then NativeInfo itself.
+//
+// Info (result of analysis)
+// - StructImpl (structure with fields, to_{json,proto}). Implements Structure, StructApi.
+//   - OutputGroupInfo. Fields are output group names.
+//   - NativeInfo. Fields are Java annotated methods (tricky).
+//     - dozens of subclasses
+//   - StarlarkInfo. Has table of k/v pairs. Final. Supports x+y.
+//
+// Provider (key for analysis result Info; class symbol for StructImpls). Implements ProviderApi.
+// - BuiltinProvider
+//   - StructProvider (for basic 'struct' values). Callable. Implements ProviderApi.
+//   - dozens of singleton subclasses
+// - StarlarkProvider. Callable.
+//
 public interface Info extends StarlarkValue {
 
   /** Returns the provider that instantiated this Info. */
diff --git a/src/main/java/com/google/devtools/build/lib/packages/NativeInfo.java b/src/main/java/com/google/devtools/build/lib/packages/NativeInfo.java
index 1c1eda1..6e9bc8e 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/NativeInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/NativeInfo.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableCollection;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import javax.annotation.Nullable;
 import net.starlark.java.eval.EvalException;
 import net.starlark.java.eval.Starlark;
 import net.starlark.java.eval.StarlarkSemantics;
@@ -25,15 +26,19 @@
  * StarlarkCallable-annotated fields (not just methods) to Starlark code. Subclasses must be
  * immutable.
  */
+// TODO(adonovan): ensure that all subclasses are named *Info and not *Provider.
+// (Info is to object as Provider is to class.)
 @Immutable
 public abstract class NativeInfo extends StructImpl {
 
-  protected NativeInfo(Provider provider) {
-    this(provider, Location.BUILTIN);
+  protected NativeInfo() {
+    this(Location.BUILTIN);
   }
 
-  protected NativeInfo(Provider provider, Location loc) {
-    super(provider, loc);
+  // TODO(adonovan): most subclasses pass Location.BUILTIN most of the time.
+  // Make only those classes that pass a real location pay for it.
+  protected NativeInfo(@Nullable Location loc) {
+    super(loc);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/packages/NativeProvider.java b/src/main/java/com/google/devtools/build/lib/packages/NativeProvider.java
deleted file mode 100644
index ed8ebfe..0000000
--- a/src/main/java/com/google/devtools/build/lib/packages/NativeProvider.java
+++ /dev/null
@@ -1,171 +0,0 @@
-// Copyright 2017 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.concurrent.ThreadSafety.Immutable;
-import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
-import com.google.devtools.build.lib.util.Pair;
-import javax.annotation.Nullable;
-import net.starlark.java.eval.StarlarkValue;
-import net.starlark.java.syntax.Location;
-
-/**
- * Base class for declared providers {@see Provider} defined in native code.
- *
- * <p>Every non-abstract derived class of {@link NativeProvider} corresponds to a single declared
- * provider. This is enforced by final {@link #equals(Object)} and {@link #hashCode()}.
- *
- * <p>Typical implementation of a non-constructable from Starlark declared provider is as follows:
- *
- * <pre>
- *     public static final Provider PROVIDER = new NativeProvider("link_params") {};
- * </pre>
- *
- * @deprecated use {@link BuiltinProvider} instead.
- */
-@Immutable
-@Deprecated
-public abstract class NativeProvider<V extends Info> implements StarlarkValue, Provider {
-  private final String name;
-  private final NativeKey key;
-  private final String errorMessageFormatForUnknownField;
-
-  private final Class<V> valueClass;
-
-  public Class<V> getValueClass() {
-    return valueClass;
-  }
-
-  /**
-   * Implement this to mark that a native provider should be exported with certain name to Starlark.
-   * Broken: only works for rules, not for aspects. DO NOT USE FOR NEW CODE!
-   *
-   * <p>Use native declared providers mechanism exclusively to expose providers to both native and
-   * Starlark code.
-   */
-  @Deprecated
-  public interface WithLegacyStarlarkName {
-    String getStarlarkName();
-  }
-
-  protected NativeProvider(Class<V> valueClass, String name) {
-    this.name = name;
-    this.key = new NativeKey(name, getClass());
-    this.valueClass = valueClass;
-    this.errorMessageFormatForUnknownField =
-        String.format("'%s' value has no field or method '%%s'", name);
-  }
-
-  public final StarlarkProviderIdentifier id() {
-    return StarlarkProviderIdentifier.forKey(getKey());
-  }
-
-  @Override
-  public boolean isImmutable() {
-    return true; // immutable and Starlark-hashable
-  }
-
-  /**
-   * equals() implements singleton class semantics.
-   *
-   * <p>Every non-abstract derived class of {@link NativeProvider} corresponds to a single declared
-   * provider.
-   */
-  @Override
-  public final boolean equals(@Nullable Object other) {
-    return other != null && this.getClass().equals(other.getClass());
-  }
-
-  /**
-   * hashCode() implements singleton class semantics.
-   *
-   * <p>Every non-abstract derived class of {@link NativeProvider} corresponds to a single declared
-   * provider.
-   */
-  @Override
-  public final int hashCode() {
-    return getClass().hashCode();
-  }
-
-  @Override
-  public String getPrintableName() {
-    return name; // for provider-related errors
-  }
-
-  @Override
-  public String getErrorMessageFormatForUnknownField() {
-    return errorMessageFormatForUnknownField;
-  }
-
-  @Override
-  public Location getLocation() {
-    return Location.BUILTIN;
-  }
-
-  @Override
-  public boolean isExported() {
-    return true;
-  }
-
-  @Override
-  public NativeKey getKey() {
-    return key;
-  }
-
-  public static Pair<String, String> getSerializedRepresentationForNativeKey(NativeKey key) {
-    return Pair.of(key.name, key.aClass.getName());
-  }
-
-  @SuppressWarnings("unchecked")
-  public static NativeKey getNativeKeyFromSerializedRepresentation(Pair<String, String> serialized)
-      throws ClassNotFoundException {
-    Class<? extends Provider> aClass = Class.forName(serialized.second).asSubclass(Provider.class);
-    return new NativeKey(serialized.first, aClass);
-  }
-
-  /**
-   * A serializable representation of {@link NativeProvider}.
-   *
-   * <p>Just a wrapper around its class.
-   */
-  @AutoCodec
-  @Immutable
-  // TODO(cparsons): Move this class, as NativeProvider is deprecated.
-  public static final class NativeKey extends Key {
-    private final String name;
-    private final Class<? extends Provider> aClass;
-
-    @VisibleForSerialization
-    NativeKey(String name, Class<? extends Provider> aClass) {
-      this.name = name;
-      this.aClass = aClass;
-    }
-
-    @Override
-    public int hashCode() {
-      return aClass.hashCode();
-    }
-
-    @Override
-    public boolean equals(Object obj) {
-      return obj instanceof NativeKey && aClass.equals(((NativeKey) obj).aClass);
-    }
-
-    @Override
-    public String toString() {
-      return name;
-    }
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Provider.java b/src/main/java/com/google/devtools/build/lib/packages/Provider.java
index 7b9f0e0..106722f 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Provider.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Provider.java
@@ -20,7 +20,7 @@
 /**
  * Declared Provider (a constructor for {@link Info}).
  *
- * <p>Declared providers can be declared either natively ({@link NativeProvider} or in Starlark
+ * <p>Declared providers can be declared either natively ({@link BuiltinProvider} or in Starlark
  * {@link StarlarkProvider}.
  *
  * <p>{@link Provider} serves both as "type identifier" for declared provider instances and as a
@@ -35,7 +35,7 @@
 public interface Provider extends ProviderApi {
 
   /**
-   * Has this {@link Provider} been exported? All native providers are always exported. Starlark
+   * Has this {@link Provider} been exported? All built-in providers are always exported. Starlark
    * providers are exported if they are assigned to top-level name in a Starlark module.
    */
   boolean isExported();
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RequiredProviders.java b/src/main/java/com/google/devtools/build/lib/packages/RequiredProviders.java
index 4602f92..0bf6a48d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RequiredProviders.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RequiredProviders.java
@@ -36,7 +36,7 @@
  *   <li>accept no dependency (used for aspects-on-aspects to indicate that an aspect never wants to
  *       see any other aspect applied to a target.
  *   <li>accept a dependency that provides all providers from one of several sets of providers. It
- *       just so happens that in all current usages these sets are either all native providers or
+ *       just so happens that in all current usages these sets are either all builtin providers or
  *       all Starlark providers, so this is the only use case this class currently supports.
  * </ul>
  */
@@ -46,12 +46,12 @@
   /** A constraint: either ANY, NONE, or RESTRICTED */
   private final Constraint constraint;
   /**
-   * Sets of native providers. If non-empty, {@link #constraint} is {@link Constraint#RESTRICTED}
+   * Sets of builtin providers. If non-empty, {@link #constraint} is {@link Constraint#RESTRICTED}
    */
   private final ImmutableList<ImmutableSet<Class<? extends TransitiveInfoProvider>>>
-      nativeProviders;
+      builtinProviders;
   /**
-   * Sets of native providers. If non-empty, {@link #constraint} is {@link Constraint#RESTRICTED}
+   * Sets of builtin providers. If non-empty, {@link #constraint} is {@link Constraint#RESTRICTED}
    */
   private final ImmutableList<ImmutableSet<StarlarkProviderIdentifier>> starlarkProviders;
 
@@ -79,7 +79,7 @@
 
       @Override
       public boolean satisfies(
-          Predicate<Class<? extends TransitiveInfoProvider>> hasNativeProvider,
+          Predicate<Class<? extends TransitiveInfoProvider>> hasBuiltinProvider,
           Predicate<StarlarkProviderIdentifier> hasStarlarkProvider,
           RequiredProviders requiredProviders,
           Builder missingProviders) {
@@ -108,7 +108,7 @@
 
       @Override
       public boolean satisfies(
-          Predicate<Class<? extends TransitiveInfoProvider>> hasNativeProvider,
+          Predicate<Class<? extends TransitiveInfoProvider>> hasBuiltinProvider,
           Predicate<StarlarkProviderIdentifier> hasStarlarkProvider,
           RequiredProviders requiredProviders,
           Builder missingProviders) {
@@ -137,7 +137,7 @@
           return true;
         }
         return satisfies(
-            advertisedProviderSet.getNativeProviders()::contains,
+            advertisedProviderSet.getBuiltinProviders()::contains,
             advertisedProviderSet.getStarlarkProviders()::contains,
             requiredProviders,
             missing);
@@ -145,22 +145,21 @@
 
       @Override
       public boolean satisfies(
-          Predicate<Class<? extends TransitiveInfoProvider>> hasNativeProvider,
+          Predicate<Class<? extends TransitiveInfoProvider>> hasBuiltinProvider,
           Predicate<StarlarkProviderIdentifier> hasStarlarkProvider,
           RequiredProviders requiredProviders,
           Builder missingProviders) {
-        for (ImmutableSet<Class<? extends TransitiveInfoProvider>> nativeProviderSet :
-            requiredProviders.nativeProviders) {
-          if (nativeProviderSet.stream().allMatch(hasNativeProvider)) {
+        for (ImmutableSet<Class<? extends TransitiveInfoProvider>> builtinProviderSet :
+            requiredProviders.builtinProviders) {
+          if (builtinProviderSet.stream().allMatch(hasBuiltinProvider)) {
             return true;
           }
 
           // Collect missing providers
           if (missingProviders != null) {
-            missingProviders.addNativeSet(
-                nativeProviderSet
-                    .stream()
-                    .filter(hasNativeProvider.negate())
+            missingProviders.addBuiltinSet(
+                builtinProviderSet.stream()
+                    .filter(hasBuiltinProvider.negate())
                     .collect(ImmutableSet.toImmutableSet()));
           }
         }
@@ -184,9 +183,9 @@
       @Override
       Builder copyAsBuilder(RequiredProviders providers) {
         Builder result = acceptAnyBuilder();
-        for (ImmutableSet<Class<? extends TransitiveInfoProvider>> nativeProviderSet :
-            providers.nativeProviders) {
-          result.addNativeSet(nativeProviderSet);
+        for (ImmutableSet<Class<? extends TransitiveInfoProvider>> builtinProviderSet :
+            providers.builtinProviders) {
+          result.addBuiltinSet(builtinProviderSet);
         }
         for (ImmutableSet<StarlarkProviderIdentifier> starlarkProviderSet :
             providers.starlarkProviders) {
@@ -198,7 +197,7 @@
       @Override
       public String getDescription(RequiredProviders providers) {
         StringBuilder result = new StringBuilder();
-        describe(result, providers.nativeProviders, Class::getSimpleName);
+        describe(result, providers.builtinProviders, Class::getSimpleName);
         describe(result, providers.starlarkProviders, id -> "'" + id.toString() + "'");
         return result.toString();
       }
@@ -211,11 +210,11 @@
         Builder missing);
 
     /**
-     * Checks if a set of providers encoded by predicates {@code hasNativeProviders} and {@code
+     * Checks if a set of providers encoded by predicates {@code hasBuiltinProvider} and {@code
      * hasStarlarkProvider} satisfies these {@code RequiredProviders}
      */
     abstract boolean satisfies(
-        Predicate<Class<? extends TransitiveInfoProvider>> hasNativeProvider,
+        Predicate<Class<? extends TransitiveInfoProvider>> hasBuiltinProvider,
         Predicate<StarlarkProviderIdentifier> hasStarlarkProvider,
         RequiredProviders requiredProviders,
         @Nullable Builder missingProviders);
@@ -232,13 +231,13 @@
   }
 
   /**
-   * Checks if a set of providers encoded by predicates {@code hasNativeProviders} and {@code
+   * Checks if a set of providers encoded by predicates {@code hasBuiltinProvider} and {@code
    * hasStarlarkProvider} satisfies this {@code RequiredProviders} instance.
    */
   public boolean isSatisfiedBy(
-      Predicate<Class<? extends TransitiveInfoProvider>> hasNativeProvider,
+      Predicate<Class<? extends TransitiveInfoProvider>> hasBuiltinProvider,
       Predicate<StarlarkProviderIdentifier> hasStarlarkProvider) {
-    return constraint.satisfies(hasNativeProvider, hasStarlarkProvider, this, null);
+    return constraint.satisfies(hasBuiltinProvider, hasStarlarkProvider, this, null);
   }
 
   /**
@@ -246,10 +245,10 @@
    * accept anything.
    */
   public RequiredProviders getMissing(
-      Predicate<Class<? extends TransitiveInfoProvider>> hasNativeProvider,
+      Predicate<Class<? extends TransitiveInfoProvider>> hasBuiltinProvider,
       Predicate<StarlarkProviderIdentifier> hasStarlarkProvider) {
     Builder builder = acceptAnyBuilder();
-    if (constraint.satisfies(hasNativeProvider, hasStarlarkProvider, this, builder)) {
+    if (constraint.satisfies(hasBuiltinProvider, hasStarlarkProvider, this, builder)) {
       // Ignore all collected missing providers.
       return acceptAnyBuilder().build();
     }
@@ -277,15 +276,15 @@
   @VisibleForSerialization
   RequiredProviders(
       Constraint constraint,
-      ImmutableList<ImmutableSet<Class<? extends TransitiveInfoProvider>>> nativeProviders,
+      ImmutableList<ImmutableSet<Class<? extends TransitiveInfoProvider>>> builtinProviders,
       ImmutableList<ImmutableSet<StarlarkProviderIdentifier>> starlarkProviders) {
     this.constraint = constraint;
 
     Preconditions.checkState(
         constraint.equals(Constraint.RESTRICTED)
-            || (nativeProviders.isEmpty() && starlarkProviders.isEmpty()));
+            || (builtinProviders.isEmpty() && starlarkProviders.isEmpty()));
 
-    this.nativeProviders = nativeProviders;
+    this.builtinProviders = builtinProviders;
     this.starlarkProviders = starlarkProviders;
   }
 
@@ -315,13 +314,13 @@
     }
     RequiredProviders that = (RequiredProviders) o;
     return constraint == that.constraint
-        && Objects.equals(nativeProviders, that.nativeProviders)
+        && Objects.equals(builtinProviders, that.builtinProviders)
         && Objects.equals(starlarkProviders, that.starlarkProviders);
   }
 
   @Override
   public int hashCode() {
-    return Objects.hash(constraint, nativeProviders, starlarkProviders);
+    return Objects.hash(constraint, builtinProviders, starlarkProviders);
   }
 
   /**
@@ -348,13 +347,13 @@
   /** A builder for {@link RequiredProviders} */
   public static class Builder {
     private final ImmutableList.Builder<ImmutableSet<Class<? extends TransitiveInfoProvider>>>
-        nativeProviders;
+        builtinProviders;
     private final ImmutableList.Builder<ImmutableSet<StarlarkProviderIdentifier>> starlarkProviders;
     private Constraint constraint;
 
     private Builder(boolean acceptNone) {
       constraint = acceptNone ? Constraint.NONE : Constraint.ANY;
-      nativeProviders = ImmutableList.builder();
+      builtinProviders = ImmutableList.builder();
       starlarkProviders = ImmutableList.builder();
     }
 
@@ -372,21 +371,21 @@
     }
 
     /**
-     * Add an alternative set of native providers.
+     * Add an alternative set of builtin providers.
      *
      * <p>If all of these providers are present in the dependency, the dependency satisfies {@link
      * RequiredProviders}.
      */
-    public Builder addNativeSet(
-        ImmutableSet<Class<? extends TransitiveInfoProvider>> nativeProviderSet) {
+    public Builder addBuiltinSet(
+        ImmutableSet<Class<? extends TransitiveInfoProvider>> builtinProviderSet) {
       constraint = Constraint.RESTRICTED;
-      Preconditions.checkState(!nativeProviderSet.isEmpty());
-      this.nativeProviders.add(nativeProviderSet);
+      Preconditions.checkState(!builtinProviderSet.isEmpty());
+      this.builtinProviders.add(builtinProviderSet);
       return this;
     }
 
     public RequiredProviders build() {
-      return new RequiredProviders(constraint, nativeProviders.build(), starlarkProviders.build());
+      return new RequiredProviders(constraint, builtinProviders.build(), starlarkProviders.build());
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index c1c2e5d..3b3b02d 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -1186,7 +1186,7 @@
      */
     public Builder advertiseProvider(Class<?>... providers) {
       for (Class<?> provider : providers) {
-        advertisedProviders.addNative(provider);
+        advertisedProviders.addBuiltin(provider);
       }
       return this;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StarlarkInfo.java b/src/main/java/com/google/devtools/build/lib/packages/StarlarkInfo.java
index ee9000c..94f88b6 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StarlarkInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StarlarkInfo.java
@@ -27,15 +27,17 @@
 import net.starlark.java.eval.EvalException;
 import net.starlark.java.eval.HasBinary;
 import net.starlark.java.eval.Starlark;
-import net.starlark.java.eval.Structure;
 import net.starlark.java.syntax.Location;
 import net.starlark.java.syntax.TokenKind;
 
-/** An Info (provider instance) for providers defined in Starlark. */
-public final class StarlarkInfo extends StructImpl implements HasBinary, Structure {
+/** An struct-like Info (provider instance) for providers defined in Starlark. */
+public final class StarlarkInfo extends StructImpl implements HasBinary {
 
+  // TODO(adonovan): move to sole use in js_common.provider(transpilation_mapping=...).
   public static final Depset.ElementType TYPE = Depset.ElementType.of(StarlarkInfo.class);
 
+  private final Provider provider;
+
   // For a n-element info, the table contains n key strings, sorted,
   // followed by the n corresponding legal Starlark values.
   private final Object[] table;
@@ -47,16 +49,31 @@
   // relation, and other observable behaviors).
   @Nullable private final String unknownFieldError;
 
+  // TODO(adonovan): restrict type of provider to StarlarkProvider?
+  // Do we ever need StarlarkInfos of BuiltinProviders? Such BuiltinProviders could
+  // be  moved to Starlark using bzl builtins injection.
+  // Alternatively: what about this implementation is specific to StarlarkProvider?
+  // It's really just a "generic" or "dynamic" representation of a struct,
+  // analogous to reflection versus generated message classes in the protobuf world.
+  // The efficient table algorithms would be a nice addition to the Starlark
+  // interpreter, to allow other clients to define their own fast structs
+  // (or to define a standard one). See also comments at Info about upcoming clean-ups.
   private StarlarkInfo(
       Provider provider,
       Object[] table,
       @Nullable Location loc,
       @Nullable String unknownFieldError) {
-    super(provider, loc);
+    super(loc);
+    this.provider = provider;
     this.table = table;
     this.unknownFieldError = unknownFieldError;
   }
 
+  @Override
+  public Provider getProvider() {
+    return provider;
+  }
+
   // Converts a map to a table of sorted keys followed by corresponding values.
   private static Object[] toTable(Map<String, Object> values) {
     int n = values.size();
@@ -291,12 +308,12 @@
    * <p>{@code unknownFieldError} is a string format, as for {@link
    * Provider#getErrorMessageFormatForUnknownField}.
    *
-   * @deprecated Do not use this method. Instead, create a new subclass of {@link NativeProvider}
+   * @deprecated Do not use this method. Instead, create a new subclass of {@link BuiltinProvider}
    *     with the desired error message format, and create a corresponding {@link NativeInfo}
    *     subclass.
    */
   // TODO(bazel-team): Make the special structs that need a custom error message use a different
-  // provider (subclassing NativeProvider) and a different StructImpl implementation. Then remove
+  // provider (subclassing BuiltinProvider) and a different StructImpl implementation. Then remove
   // this functionality, thereby saving a string pointer field for the majority of providers that
   // don't need it.
   @Deprecated
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StructImpl.java b/src/main/java/com/google/devtools/build/lib/packages/StructImpl.java
index d6c7bc1..5f15113 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StructImpl.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StructImpl.java
@@ -47,27 +47,19 @@
  */
 public abstract class StructImpl implements Info, Structure, StructApi {
 
-  private final Provider provider;
   private final Location location;
 
   /**
-   * Constructs an {@link StructImpl}.
+   * Constructs a {@link StructImpl}.
    *
-   * @param provider the provider describing the type of this instance
    * @param location the Starlark location where this instance is created. If null, defaults to
    *     {@link Location#BUILTIN}.
    */
-  protected StructImpl(Provider provider, @Nullable Location location) {
-    this.provider = provider;
+  protected StructImpl(@Nullable Location location) {
     this.location = location != null ? location : Location.BUILTIN;
   }
 
   @Override
-  public Provider getProvider() {
-    return provider;
-  }
-
-  @Override
   public Location getCreationLoc() {
     return location;
   }
@@ -83,9 +75,7 @@
     }
     try {
       return type.cast(obj);
-    } catch (
-        @SuppressWarnings("UnusedException")
-        ClassCastException unused) {
+    } catch (ClassCastException unused) {
       throw Starlark.errorf(
           "for %s field, got %s, want %s", key, Starlark.type(obj), Starlark.classType(type));
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidApplicationResourceInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidApplicationResourceInfo.java
index 7b584a3..c817031 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidApplicationResourceInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidApplicationResourceInfo.java
@@ -51,7 +51,6 @@
       Artifact rTxt,
       Artifact resourcesZip,
       Artifact databindingLayoutInfoZip) {
-    super(PROVIDER);
     this.resourceApk = resourceApk;
     this.resourceJavaSrcJar = resourceJavaSrcJar;
     this.resourceJavaClassJar = resourceJavaClassJar;
@@ -64,6 +63,11 @@
   }
 
   @Override
+  public AndroidApplicationResourceInfoProvider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Artifact getResourceApk() {
     return resourceApk;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java
index 84c3b06..ba20e80 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidAssetsInfo.java
@@ -86,7 +86,6 @@
       NestedSet<Artifact> transitiveAssets,
       NestedSet<Artifact> transitiveSymbols,
       NestedSet<Artifact> transitiveCompiledSymbols) {
-    super(PROVIDER);
     this.label = label;
     this.hasLocalAssets = validationResult != null;
     this.validationResult = validationResult;
@@ -98,6 +97,11 @@
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Label getLabel() {
     return label;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinaryDataInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinaryDataInfo.java
index c961f84..507d01a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinaryDataInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinaryDataInfo.java
@@ -53,7 +53,6 @@
       AndroidResourcesInfo resourcesInfo,
       AndroidAssetsInfo assetsInfo,
       AndroidManifestInfo manifestInfo) {
-    super(PROVIDER);
     this.dataApk = dataApk;
     this.resourceProguardConfig = resourceProguardConfig;
     this.resourcesInfo = resourcesInfo;
@@ -62,6 +61,11 @@
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Artifact getApk() {
     return dataApk;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCcLinkParamsProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCcLinkParamsProvider.java
index 543a88e..a4b3bb3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCcLinkParamsProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCcLinkParamsProvider.java
@@ -32,11 +32,15 @@
   private final CcInfo ccInfo;
 
   public AndroidCcLinkParamsProvider(CcInfo ccInfo) {
-    super(PROVIDER);
     this.ccInfo = CcInfo.builder().setCcLinkingContext(ccInfo.getCcLinkingContext()).build();
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public CcInfo getLinkParams() {
     return ccInfo;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
index 9a24029..7cb2d3d21 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
@@ -684,7 +684,7 @@
             .setNeverlink(isNeverlink)
             .build();
 
-    // Do not convert the ResourceApk into native providers when it is created from
+    // Do not convert the ResourceApk into builtin providers when it is created from
     // Starlark via AndroidApplicationResourceInfo, because native dependency providers are not
     // created in the Starlark pipeline.
     if (resourceApk.isFromAndroidApplicationResourceInfo()
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceBrokerInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceBrokerInfo.java
index 7432277..536273e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceBrokerInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceBrokerInfo.java
@@ -35,10 +35,14 @@
   private final String deviceBrokerType;
 
   public AndroidDeviceBrokerInfo(String deviceBrokerType) {
-    super(PROVIDER);
     this.deviceBrokerType = deviceBrokerType;
   }
 
+  @Override
+  public AndroidDeviceBrokerInfoProvider getProvider() {
+    return PROVIDER;
+  }
+
   /**
    * Returns the type of device broker that is appropriate to use to interact with devices obtained
    * by this artifact.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceScriptFixtureInfoProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceScriptFixtureInfoProvider.java
index 94aaf62..15c2eea 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceScriptFixtureInfoProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDeviceScriptFixtureInfoProvider.java
@@ -16,8 +16,8 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 
 /**
  * Information about an {@code android_device_script_fixture} to run as part of an {@code
@@ -27,9 +27,9 @@
 public class AndroidDeviceScriptFixtureInfoProvider extends NativeInfo {
 
   private static final String STARLARK_NAME = "DeviceScriptFixtureInfo";
-  public static final NativeProvider<AndroidDeviceScriptFixtureInfoProvider> STARLARK_CONSTRUCTOR =
-      new NativeProvider<AndroidDeviceScriptFixtureInfoProvider>(
-          AndroidDeviceScriptFixtureInfoProvider.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<AndroidDeviceScriptFixtureInfoProvider> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<AndroidDeviceScriptFixtureInfoProvider>(
+          STARLARK_NAME, AndroidDeviceScriptFixtureInfoProvider.class) {};
 
   private final Artifact fixtureScript;
   private final NestedSet<Artifact> supportApks;
@@ -38,13 +38,17 @@
 
   public AndroidDeviceScriptFixtureInfoProvider(
       Artifact fixtureScript, NestedSet<Artifact> supportApks, boolean daemon, boolean strictExit) {
-    super(STARLARK_CONSTRUCTOR);
     this.fixtureScript = fixtureScript;
     this.supportApks = supportApks;
     this.daemon = daemon;
     this.strictExit = strictExit;
   }
 
+  @Override
+  public BuiltinProvider<AndroidDeviceScriptFixtureInfoProvider> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   public Artifact getFixtureScript() {
     return fixtureScript;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDex2OatInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDex2OatInfo.java
index ace8885..3476ce3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDex2OatInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidDex2OatInfo.java
@@ -72,7 +72,6 @@
       Artifact framework,
       Artifact dalvikCache,
       Artifact deviceProps) {
-    super(PROVIDER);
     this.dex2OatEnabled = dex2OatEnabled;
     this.executeDex2OatOnHost = executeDex2OatOnHost;
     this.sandboxForPregeneratingOatFilesForTests = sandboxForPregeneratingOatFilesForTests;
@@ -81,6 +80,11 @@
     this.deviceProps = deviceProps;
   }
 
+  @Override
+  public BuiltinProvider<AndroidDex2OatInfo> getProvider() {
+    return PROVIDER;
+  }
+
   /** Returns if the device should run cloud dex2oat. */
   public boolean isDex2OatEnabled() {
     return dex2OatEnabled;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidFeatureFlagSetProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidFeatureFlagSetProvider.java
index 30f1aa8..b62d382 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidFeatureFlagSetProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidFeatureFlagSetProvider.java
@@ -55,10 +55,14 @@
   private final Optional<ImmutableMap<Label, String>> flags;
 
   AndroidFeatureFlagSetProvider(Optional<? extends Map<Label, String>> flags) {
-    super(PROVIDER);
     this.flags = flags.transform(ImmutableMap::copyOf);
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   public static AndroidFeatureFlagSetProvider create(Optional<? extends Map<Label, String>> flags) {
     return new AndroidFeatureFlagSetProvider(flags.transform(ImmutableMap::copyOf));
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidHostServiceFixtureInfoProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidHostServiceFixtureInfoProvider.java
index b4f9d9f..708b9c4 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidHostServiceFixtureInfoProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidHostServiceFixtureInfoProvider.java
@@ -17,8 +17,8 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 
 /**
  * Information about an {@code android_host_service_fixture} to run as part of an {@code
@@ -28,10 +28,10 @@
 public class AndroidHostServiceFixtureInfoProvider extends NativeInfo {
 
   private static final String STARLARK_NAME = "HostServiceFixtureInfo";
-  static final NativeProvider<AndroidHostServiceFixtureInfoProvider>
+  static final BuiltinProvider<AndroidHostServiceFixtureInfoProvider>
       ANDROID_HOST_SERVICE_FIXTURE_INFO =
-          new NativeProvider<AndroidHostServiceFixtureInfoProvider>(
-              AndroidHostServiceFixtureInfoProvider.class, STARLARK_NAME) {};
+          new BuiltinProvider<AndroidHostServiceFixtureInfoProvider>(
+              STARLARK_NAME, AndroidHostServiceFixtureInfoProvider.class) {};
 
   private final Artifact executable;
   private final ImmutableList<String> serviceNames;
@@ -45,7 +45,6 @@
       NestedSet<Artifact> supportApks,
       boolean providesTestArgs,
       boolean isDaemon) {
-    super(ANDROID_HOST_SERVICE_FIXTURE_INFO);
     this.executable = executable;
     this.serviceNames = serviceNames;
     this.supportApks = supportApks;
@@ -53,6 +52,11 @@
     this.daemon = isDaemon;
   }
 
+  @Override
+  public BuiltinProvider<AndroidHostServiceFixtureInfoProvider> getProvider() {
+    return ANDROID_HOST_SERVICE_FIXTURE_INFO;
+  }
+
   public Artifact getExecutable() {
     return executable;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdeInfoProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdeInfoProvider.java
index 215663b..52736dcc 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdeInfoProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdeInfoProvider.java
@@ -198,7 +198,6 @@
       ImmutableCollection<Artifact> apksUnderTest,
       ImmutableMap<String, NestedSet<Artifact>> nativeLibs,
       @Nullable Artifact resourceApk) {
-    super(PROVIDER);
     this.javaPackage = javaPackage;
     this.idlImportRoot = idlImportRoot;
     this.manifest = manifest;
@@ -217,6 +216,11 @@
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   @Nullable
   public String getJavaPackage() {
     return javaPackage;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java
index 852a87d..b60b920 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlProvider.java
@@ -43,7 +43,6 @@
       NestedSet<Artifact> transitiveIdlImports,
       NestedSet<Artifact> transitiveIdlJars,
       NestedSet<Artifact> transitiveIdlPreprocessed) {
-    super(PROVIDER);
     this.transitiveIdlImportRoots = transitiveIdlImportRoots;
     this.transitiveIdlImports = transitiveIdlImports;
     this.transitiveIdlJars = transitiveIdlJars;
@@ -51,6 +50,11 @@
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Depset /*<String>*/ getTransitiveIdlImportRootsForStarlark() {
     return Depset.of(Depset.ElementType.STRING, transitiveIdlImportRoots);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidInstrumentationInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidInstrumentationInfo.java
index 062e8a3..c3dcb10 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidInstrumentationInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidInstrumentationInfo.java
@@ -34,11 +34,15 @@
   private final ApkInfo target;
 
   AndroidInstrumentationInfo(ApkInfo target) {
-    super(PROVIDER);
     this.target = target;
   }
 
   @Override
+  public AndroidInstrumentationInfoProvider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public ApkInfo getTarget() {
     return target;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java
index 92accf0..504c9fb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryAarInfo.java
@@ -48,12 +48,16 @@
       @Nullable Aar aar,
       NestedSet<Aar> transitiveAars,
       NestedSet<Artifact> transitiveAarArtifacts) {
-    super(PROVIDER);
     this.aar = aar;
     this.transitiveAars = transitiveAars;
     this.transitiveAarArtifacts = transitiveAarArtifacts;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   public static AndroidLibraryAarInfo create(
       @Nullable Aar aar,
       NestedSet<Aar> transitiveAars,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java
index 8b5acd5..801cd81 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibraryResourceClassJarProvider.java
@@ -36,21 +36,25 @@
   private final NestedSet<Artifact> resourceClassJars;
 
   private AndroidLibraryResourceClassJarProvider(NestedSet<Artifact> resourceClassJars) {
-    super(PROVIDER);
     this.resourceClassJars = resourceClassJars;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  // TODO(adonovan): rename to avoid unrelated overloading.
+  static AndroidLibraryResourceClassJarProvider getProvider(TransitiveInfoCollection target) {
+    return (AndroidLibraryResourceClassJarProvider)
+        target.get(AndroidLibraryResourceClassJarProvider.PROVIDER.getKey());
+  }
+
   public static AndroidLibraryResourceClassJarProvider create(
       NestedSet<Artifact> resourceClassJars) {
     return new AndroidLibraryResourceClassJarProvider(resourceClassJars);
   }
 
-  public static AndroidLibraryResourceClassJarProvider getProvider(
-      TransitiveInfoCollection target) {
-    return (AndroidLibraryResourceClassJarProvider)
-        target.get(AndroidLibraryResourceClassJarProvider.PROVIDER.getKey());
-  }
-
   @Override
   public Depset /*<Artifact>*/ getResourceClassJarsForStarlark() {
     return Depset.of(Artifact.TYPE, resourceClassJars);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidManifestInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidManifestInfo.java
index 4764162..0e59d9c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidManifestInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidManifestInfo.java
@@ -47,13 +47,17 @@
   }
 
   private AndroidManifestInfo(Artifact manifest, String pkg, boolean exportsManifest) {
-    super(PROVIDER);
     this.manifest = manifest;
     this.pkg = pkg;
     this.exportsManifest = exportsManifest;
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Artifact getManifest() {
     return manifest;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java
index 42b0ccd..e019cc3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidNativeLibsInfo.java
@@ -32,17 +32,20 @@
 
   private static final String STARLARK_NAME = "AndroidNativeLibsInfo";
 
-  public static final AndroidNativeLibsInfoProvider PROVIDER =
-      new AndroidNativeLibsInfoProvider();
+  public static final AndroidNativeLibsInfoProvider PROVIDER = new AndroidNativeLibsInfoProvider();
 
   private final NestedSet<Artifact> nativeLibs;
 
   public AndroidNativeLibsInfo(NestedSet<Artifact> nativeLibs) {
-    super(PROVIDER);
     this.nativeLibs = nativeLibs;
   }
 
   @Override
+  public AndroidNativeLibsInfoProvider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Depset /*<Artifact>*/ getNativeLibsForStarlark() {
     return Depset.of(Artifact.TYPE, nativeLibs);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidPreDexJarProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidPreDexJarProvider.java
index 5b4a2bb..f12ee2e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidPreDexJarProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidPreDexJarProvider.java
@@ -37,10 +37,14 @@
   }
 
   public AndroidPreDexJarProvider(Artifact preDexJar) {
-    super(PROVIDER);
     this.preDexJar = preDexJar;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   /** Provider class for {@link AndroidPreDexJarProvider} objects. */
   public static class Provider extends BuiltinProvider<AndroidPreDexJarProvider>
       implements AndroidPreDexJarProviderApi.Provider<Artifact> {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidProguardInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidProguardInfo.java
index 816c076..dfc1e36 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidProguardInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidProguardInfo.java
@@ -38,11 +38,15 @@
   private final ImmutableList<Artifact> localProguardSpecs;
 
   public AndroidProguardInfo(ImmutableList<Artifact> localProguardSpecs) {
-    super(PROVIDER);
     this.localProguardSpecs = localProguardSpecs;
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public ImmutableList<Artifact> getLocalProguardSpecs() {
     return localProguardSpecs;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java
index 1312244..28f216f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesInfo.java
@@ -79,7 +79,6 @@
       NestedSet<Artifact> transitiveCompiledSymbols,
       NestedSet<Artifact> transitiveStaticLib,
       NestedSet<Artifact> transitiveRTxt) {
-    super(PROVIDER);
     this.label = label;
     this.manifest = manifest;
     this.rTxt = rTxt;
@@ -96,6 +95,11 @@
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Label getLabel() {
     return label;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSdkProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSdkProvider.java
index 82e2984..ed95426 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSdkProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSdkProvider.java
@@ -87,7 +87,6 @@
       FilesToRunProvider proguard,
       FilesToRunProvider zipalign,
       @Nullable BootClassPathInfo system) {
-    super(PROVIDER);
     this.buildToolsVersion = buildToolsVersion;
     this.frameworkAidl = frameworkAidl;
     this.aidlLib = aidlLib;
@@ -108,6 +107,11 @@
     this.system = system;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   /**
    * Returns the Android SDK associated with the rule being analyzed or null if the Android SDK is
    * not specified.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidStarlarkData.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidStarlarkData.java
index a5550a4..5d5c1ed 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidStarlarkData.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidStarlarkData.java
@@ -26,7 +26,6 @@
 import com.google.devtools.build.lib.packages.BazelStarlarkContext;
 import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.rules.android.AndroidLibraryAarInfo.Aar;
@@ -662,15 +661,6 @@
   }
 
   public static <T extends NativeInfo> Sequence<T> getProviders(
-      List<ConfiguredTarget> targets, NativeProvider<T> provider) {
-    return StarlarkList.immutableCopyOf(
-        targets.stream()
-            .map(target -> target.get(provider))
-            .filter(Objects::nonNull)
-            .collect(ImmutableList.toImmutableList()));
-  }
-
-  protected static <T extends NativeInfo> Sequence<T> getProviders(
       List<ConfiguredTarget> targets, BuiltinProvider<T> provider) {
     return StarlarkList.immutableCopyOf(
         targets.stream()
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ApkInfo.java b/src/main/java/com/google/devtools/build/lib/rules/android/ApkInfo.java
index 5bd3e05..b4f5f98 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ApkInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ApkInfo.java
@@ -23,6 +23,7 @@
 import javax.annotation.Nullable;
 import net.starlark.java.eval.Dict;
 import net.starlark.java.eval.EvalException;
+import net.starlark.java.eval.Starlark;
 
 /** A provider for targets that produce an apk file. */
 @Immutable
@@ -51,7 +52,6 @@
       Artifact mergedManifest,
       List<Artifact> signingKeys,
       @Nullable Artifact signingLineage) {
-    super(PROVIDER);
     this.apk = apk;
     this.unsignedApk = unsignedApk;
     this.deployJar = deployJar;
@@ -62,6 +62,11 @@
   }
 
   @Override
+  public ApkInfoProvider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Artifact getApk() {
     return apk;
   }
@@ -117,7 +122,7 @@
 
     @Override
     public ApkInfoApi<?> createInfo(Dict<String, Object> kwargs) throws EvalException {
-      return throwUnsupportedConstructorException();
+      throw Starlark.errorf("'%s' cannot be constructed from Starlark", getPrintableName());
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
index 72cedfb..0592c81 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
@@ -163,7 +163,7 @@
             .requiresConfigurationFragments(AndroidConfiguration.class)
             .requireAspectsWithProviders(
                 ImmutableList.of(ImmutableSet.of(forKey(JavaInfo.PROVIDER.getKey()))))
-            .requireAspectsWithNativeProviders(JavaProtoLibraryAspectProvider.class);
+            .requireAspectsWithBuiltinProviders(JavaProtoLibraryAspectProvider.class);
     if (TriState.valueOf(params.getOnlyValueOfAttribute("incremental_dexing")) != TriState.NO) {
       // Marginally improves "query2" precision for targets that disable incremental dexing
       result.add(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ProguardMappingProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/ProguardMappingProvider.java
index 8c5822d..225afb0 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ProguardMappingProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ProguardMappingProvider.java
@@ -30,11 +30,15 @@
   private final Artifact proguardMapping;
 
   public ProguardMappingProvider(Artifact proguardMapping) {
-    super(PROVIDER);
     this.proguardMapping = proguardMapping;
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Artifact getProguardMapping() {
     return proguardMapping;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java b/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java
index 01a60f0..ff3fcc15 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/databinding/DataBindingV2Provider.java
@@ -57,7 +57,6 @@
       NestedSet<Artifact> transitiveBRFiles,
       ImmutableList<LabelJavaPackagePair> labelAndJavaPackages,
       NestedSet<LabelJavaPackagePair> transitiveLabelAndJavaPackages) {
-    super(PROVIDER);
     this.classInfos = classInfos;
     this.setterStores = setterStores;
     this.transitiveBRFiles = transitiveBRFiles;
@@ -66,6 +65,11 @@
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public ImmutableList<Artifact> getClassInfos() {
     return classInfos;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/databinding/UsesDataBindingProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/databinding/UsesDataBindingProvider.java
index 49f9910..6afef59 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/databinding/UsesDataBindingProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/databinding/UsesDataBindingProvider.java
@@ -35,11 +35,15 @@
   private final ImmutableList<Artifact> metadataOutputs;
 
   public UsesDataBindingProvider(Collection<Artifact> metadataOutputs) {
-    super(PROVIDER);
     this.metadataOutputs = ImmutableList.copyOf(metadataOutputs);
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public ImmutableList<Artifact> getMetadataOutputs() {
     return metadataOutputs;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java b/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java
index 7759984..4a7cf1a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/ApplePlatform.java
@@ -17,7 +17,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
-import com.google.devtools.build.lib.packages.NativeProvider;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.packages.StarlarkInfo;
 import com.google.devtools.build.lib.packages.StructImpl;
@@ -189,7 +189,7 @@
 
   /** Returns a Starlark struct that contains the instances of this enum. */
   public static StructImpl getStarlarkStruct() {
-    Provider constructor = new NativeProvider<StructImpl>(StructImpl.class, "platforms") {};
+    Provider constructor = new BuiltinProvider<StructImpl>("platforms", StructImpl.class) {};
     HashMap<String, Object> fields = new HashMap<>();
     for (ApplePlatform type : values()) {
       fields.put(type.starlarkKey, type);
@@ -259,7 +259,7 @@
 
     /** Returns a Starlark struct that contains the instances of this enum. */
     public static StructImpl getStarlarkStruct() {
-      Provider constructor = new NativeProvider<StructImpl>(StructImpl.class, "platform_types") {};
+      Provider constructor = new BuiltinProvider<StructImpl>("platform_types", StructImpl.class) {};
       HashMap<String, Object> fields = new HashMap<>();
       for (PlatformType type : values()) {
         fields.put(type.starlarkKey, type);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/AvailableXcodesInfo.java b/src/main/java/com/google/devtools/build/lib/rules/apple/AvailableXcodesInfo.java
index c44815e..a4fec2e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/AvailableXcodesInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/AvailableXcodesInfo.java
@@ -32,11 +32,15 @@
 
   public AvailableXcodesInfo(
       Iterable<XcodeVersionRuleData> availableXcodes, XcodeVersionRuleData defaultVersion) {
-    super(PROVIDER);
     this.availableXcodes = availableXcodes;
     this.defaultVersion = defaultVersion;
   }
 
+  @Override
+  public BuiltinProvider<AvailableXcodesInfo> getProvider() {
+    return PROVIDER;
+  }
+
   /** Returns the available xcode versions from {@code available_xcodes}. */
   public Iterable<XcodeVersionRuleData> getAvailableVersions() {
     return availableXcodes;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeConfigInfo.java b/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeConfigInfo.java
index 08d9de2..deee314 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeConfigInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeConfigInfo.java
@@ -60,7 +60,6 @@
       DottedVersion macosMinimumOsVersion,
       DottedVersion xcodeVersion,
       Availability availability) {
-    super(PROVIDER);
     this.iosSdkVersion = Preconditions.checkNotNull(iosSdkVersion);
     this.iosMinimumOsVersion = Preconditions.checkNotNull(iosMinimumOsVersion);
     this.watchosSdkVersion = Preconditions.checkNotNull(watchosSdkVersion);
@@ -88,6 +87,11 @@
     this.executionRequirements = builder.buildImmutable();
   }
 
+  @Override
+  public BuiltinProvider<XcodeConfigInfo> getProvider() {
+    return PROVIDER;
+  }
+
   /** Indicates the platform(s) on which an Xcode version is available. */
   public static enum Availability {
     LOCAL("local"),
diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeVersionProperties.java b/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeVersionProperties.java
index cfce700..03760fb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeVersionProperties.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/XcodeVersionProperties.java
@@ -18,8 +18,8 @@
 import com.google.common.base.Optional;
 import com.google.common.base.Strings;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.apple.XcodePropertiesApi;
 import java.util.Objects;
 import javax.annotation.Nullable;
@@ -32,8 +32,8 @@
   public static final String STARLARK_NAME = "XcodeProperties";
 
   /** Starlark constructor and identifier for XcodeVersionProperties provider. */
-  public static final NativeProvider<XcodeVersionProperties> STARLARK_CONSTRUCTOR =
-      new NativeProvider<XcodeVersionProperties>(XcodeVersionProperties.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<XcodeVersionProperties> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<XcodeVersionProperties>(STARLARK_NAME, XcodeVersionProperties.class) {};
 
   @VisibleForTesting public static final String DEFAULT_IOS_SDK_VERSION = "8.4";
   @VisibleForTesting public static final String DEFAULT_WATCHOS_SDK_VERSION = "2.0";
@@ -76,7 +76,6 @@
       @Nullable String defaultWatchosSdkVersion,
       @Nullable String defaultTvosSdkVersion,
       @Nullable String defaultMacosSdkVersion) {
-    super(STARLARK_CONSTRUCTOR);
     this.xcodeVersion = Optional.fromNullable(xcodeVersion);
     this.defaultIosSdkVersion =
         Strings.isNullOrEmpty(defaultIosSdkVersion)
@@ -96,6 +95,11 @@
             : DottedVersion.fromStringUnchecked(defaultMacosSdkVersion);
   }
 
+  @Override
+  public BuiltinProvider<XcodeVersionProperties> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   /** Returns the xcode version, or null if the xcode version is unknown. */
   @Override
   public String getXcodeVersionString() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/config/ConfigFeatureFlagProvider.java b/src/main/java/com/google/devtools/build/lib/rules/config/ConfigFeatureFlagProvider.java
index 4a5468b..34cebf2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/config/ConfigFeatureFlagProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/config/ConfigFeatureFlagProvider.java
@@ -19,8 +19,8 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.RequiredProviders;
 import com.google.devtools.build.lib.packages.StarlarkProviderIdentifier;
 import com.google.devtools.build.lib.starlarkbuildapi.config.ConfigFeatureFlagProviderApi;
@@ -42,7 +42,7 @@
    * Constructor and identifier for ConfigFeatureFlagProvider. This is the value of {@code
    * config_common.FeatureFlagInfo}.
    */
-  static final NativeProvider<ConfigFeatureFlagProvider> STARLARK_CONSTRUCTOR = new Constructor();
+  static final BuiltinProvider<ConfigFeatureFlagProvider> STARLARK_CONSTRUCTOR = new Constructor();
 
   static final RequiredProviders REQUIRE_CONFIG_FEATURE_FLAG_PROVIDER =
       RequiredProviders.acceptAnyBuilder().addStarlarkSet(ImmutableSet.of(id())).build();
@@ -51,12 +51,15 @@
   private final Predicate<String> validityPredicate;
 
   private ConfigFeatureFlagProvider(String value, Predicate<String> validityPredicate) {
-    super(STARLARK_CONSTRUCTOR);
-
     this.value = value;
     this.validityPredicate = validityPredicate;
   }
 
+  @Override
+  public BuiltinProvider<ConfigFeatureFlagProvider> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   /** Creates a new ConfigFeatureFlagProvider with the given value and valid value predicate. */
   public static ConfigFeatureFlagProvider create(String value, Predicate<String> isValidValue) {
     return new ConfigFeatureFlagProvider(value, isValidValue);
@@ -68,11 +71,11 @@
    */
   @StarlarkBuiltin(name = "FeatureFlagInfo", documented = false)
   @Immutable
-  private static final class Constructor extends NativeProvider<ConfigFeatureFlagProvider>
+  private static final class Constructor extends BuiltinProvider<ConfigFeatureFlagProvider>
       implements StarlarkValue {
 
     Constructor() {
-      super(ConfigFeatureFlagProvider.class, STARLARK_NAME);
+      super(STARLARK_NAME, ConfigFeatureFlagProvider.class);
     }
 
     @StarlarkMethod(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
index eab29ca..5d44cef 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
@@ -152,11 +152,15 @@
     private final CcInfo ccInfo;
 
     public CcLauncherInfo(CcInfo ccInfo, CcCompilationOutputs ccCompilationOutputs) {
-      super(PROVIDER);
       this.ccInfo = ccInfo;
       this.ccCompilationOutputs = ccCompilationOutputs;
     }
 
+    @Override
+    public Provider getProvider() {
+      return PROVIDER;
+    }
+
     public CcCompilationOutputs getCcCompilationOutputs(RuleContext ruleContext) {
       checkRestrictedUsage(ruleContext);
       return ccCompilationOutputs;
@@ -1299,7 +1303,6 @@
           return null;
         }
 
-        @SuppressWarnings("rawtypes")
         NestedSet<Tuple> dynamicDeps =
             Depset.noneableCast(dynamicDepsField, Tuple.class, "dynamic_deps");
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcInfo.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcInfo.java
index c802de3..87116f8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcInfo.java
@@ -41,13 +41,17 @@
       CcCompilationContext ccCompilationContext,
       CcLinkingContext ccLinkingContext,
       CcDebugInfoContext ccDebugInfoContext) {
-    super(PROVIDER);
     this.ccCompilationContext = ccCompilationContext;
     this.ccLinkingContext = ccLinkingContext;
     this.ccDebugInfoContext = ccDebugInfoContext;
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public CcCompilationContext getCcCompilationContext() {
     return ccCompilationContext;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainAttributesProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainAttributesProvider.java
index e153e12..b09a7bf 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainAttributesProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainAttributesProvider.java
@@ -36,8 +36,8 @@
 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.BuildType;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.License;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.Type;
 import com.google.devtools.build.lib.rules.cpp.CcToolchain.AdditionalBuildVariablesComputer;
 import net.starlark.java.syntax.Location;
@@ -46,11 +46,12 @@
  * Provider encapsulating all the information from the cc_toolchain rule that affects creation of
  * {@link CcToolchainProvider}
  */
+// TODO(adonovan): rename s/Provider/Info/.
 public class CcToolchainAttributesProvider extends ToolchainInfo implements HasCcToolchainLabel {
 
-  public static final NativeProvider<CcToolchainAttributesProvider> PROVIDER =
-      new NativeProvider<CcToolchainAttributesProvider>(
-          CcToolchainAttributesProvider.class, "CcToolchainAttributesInfo") {};
+  public static final BuiltinProvider<CcToolchainAttributesProvider> PROVIDER =
+      new BuiltinProvider<CcToolchainAttributesProvider>(
+          "CcToolchainAttributesInfo", CcToolchainAttributesProvider.class) {};
 
   private final boolean supportsParamFiles;
   private final boolean supportsHeaderParsing;
@@ -69,7 +70,6 @@
   private final NestedSet<Artifact> libcMiddleman;
   private final TransitiveInfoCollection libcTop;
   private final NestedSet<Artifact> targetLibc;
-  private final NestedSet<Artifact> targetLibcMiddleman;
   private final TransitiveInfoCollection targetLibcTop;
   private final NestedSet<Artifact> fullInputsForCrosstool;
   private final NestedSet<Artifact> fullInputsForLink;
@@ -138,8 +138,6 @@
     this.libc = getOptionalFiles(ruleContext, CcToolchainRule.LIBC_TOP_ATTR);
     this.libcTop = ruleContext.getPrerequisite(CcToolchainRule.LIBC_TOP_ATTR);
 
-    this.targetLibcMiddleman =
-        getOptionalMiddlemanOrFiles(ruleContext, CcToolchainRule.TARGET_LIBC_TOP_ATTR);
     this.targetLibc = getOptionalFiles(ruleContext, CcToolchainRule.TARGET_LIBC_TOP_ATTR);
     this.targetLibcTop = ruleContext.getPrerequisite(CcToolchainRule.TARGET_LIBC_TOP_ATTR);
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainConfigInfo.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainConfigInfo.java
index d5bed42..6f52f39 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainConfigInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainConfigInfo.java
@@ -83,7 +83,6 @@
       ImmutableList<Pair<String, String>> makeVariables,
       String builtinSysroot,
       String ccTargetOs) {
-    super(PROVIDER);
     this.actionConfigs = actionConfigs;
     this.features = features;
     this.artifactNamePatterns = artifactNamePatterns;
@@ -102,6 +101,11 @@
     this.ccTargetOs = ccTargetOs;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   public static CcToolchainConfigInfo fromToolchain(CToolchain toolchain) throws EvalException {
     ImmutableList.Builder<ActionConfig> actionConfigBuilder = ImmutableList.builder();
     for (CToolchain.ActionConfig actionConfig : toolchain.getActionConfigList()) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/DebugPackageProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/DebugPackageProvider.java
index d610338..2ac5ad1 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/DebugPackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/DebugPackageProvider.java
@@ -47,7 +47,6 @@
       @Nullable Artifact strippedArtifact,
       Artifact unstrippedArtifact,
       @Nullable Artifact dwpArtifact) {
-    super(PROVIDER);
     Preconditions.checkNotNull(unstrippedArtifact);
     this.targetLabel = targetLabel;
     this.strippedArtifact = strippedArtifact;
@@ -55,6 +54,11 @@
     this.dwpArtifact = dwpArtifact;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   /** Returns the label for the *_binary target. */
   @Override
   public final Label getTargetLabel() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/DeniedImplicitOutputMarkerProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/DeniedImplicitOutputMarkerProvider.java
index f15495b..395e8fd 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/DeniedImplicitOutputMarkerProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/DeniedImplicitOutputMarkerProvider.java
@@ -15,17 +15,18 @@
 package com.google.devtools.build.lib.rules.cpp;
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 
 /** TODO(plf): Remove once implicit outputs are removed from cc_library */
 @Immutable
 public class DeniedImplicitOutputMarkerProvider extends NativeInfo {
-  public static final NativeProvider<DeniedImplicitOutputMarkerProvider> PROVIDER =
-      new NativeProvider<DeniedImplicitOutputMarkerProvider>(
-          DeniedImplicitOutputMarkerProvider.class, "DeniedImplicitOutputMarkerProvider") {};
+  public static final BuiltinProvider<DeniedImplicitOutputMarkerProvider> PROVIDER =
+      new BuiltinProvider<DeniedImplicitOutputMarkerProvider>(
+          "DeniedImplicitOutputMarkerProvider", DeniedImplicitOutputMarkerProvider.class) {};
 
-  public DeniedImplicitOutputMarkerProvider() {
-    super(PROVIDER);
+  @Override
+  public BuiltinProvider<DeniedImplicitOutputMarkerProvider> getProvider() {
+    return PROVIDER;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoPrefetchHintsProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoPrefetchHintsProvider.java
index e7a7ebf..45c3f66 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoPrefetchHintsProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoPrefetchHintsProvider.java
@@ -14,23 +14,27 @@
 package com.google.devtools.build.lib.rules.cpp;
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 
 /** Provider that contains the profile used for prefetch hints. */
 @Immutable
 public final class FdoPrefetchHintsProvider extends NativeInfo {
-  public static final NativeProvider<FdoPrefetchHintsProvider> PROVIDER =
-      new NativeProvider<FdoPrefetchHintsProvider>(
-          FdoPrefetchHintsProvider.class, "FdoPrefetchHintsInfo") {};
+  public static final BuiltinProvider<FdoPrefetchHintsProvider> PROVIDER =
+      new BuiltinProvider<FdoPrefetchHintsProvider>(
+          "FdoPrefetchHintsInfo", FdoPrefetchHintsProvider.class) {};
 
   private final FdoInputFile fdoInputFile;
 
   public FdoPrefetchHintsProvider(FdoInputFile fdoInputFile) {
-    super(PROVIDER);
     this.fdoInputFile = fdoInputFile;
   }
 
+  @Override
+  public BuiltinProvider<FdoPrefetchHintsProvider> getProvider() {
+    return PROVIDER;
+  }
+
   public FdoInputFile getInputFile() {
     return fdoInputFile;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoProfileProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoProfileProvider.java
index 4d8aad3..3ae476e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoProfileProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoProfileProvider.java
@@ -15,24 +15,28 @@
 
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 
 /** Provider that contains the profile used for FDO. */
 @Immutable
 public final class FdoProfileProvider extends NativeInfo {
-  public static final NativeProvider<FdoProfileProvider> PROVIDER =
-      new NativeProvider<FdoProfileProvider>(FdoProfileProvider.class, "FdoProfileInfo") {};
+  public static final BuiltinProvider<FdoProfileProvider> PROVIDER =
+      new BuiltinProvider<FdoProfileProvider>("FdoProfileInfo", FdoProfileProvider.class) {};
 
   private final FdoInputFile fdoInputFile;
   private final Artifact protoProfileArtifact;
 
   public FdoProfileProvider(FdoInputFile fdoInputFile, Artifact protoProfileArtifact) {
-    super(PROVIDER);
     this.fdoInputFile = fdoInputFile;
     this.protoProfileArtifact = protoProfileArtifact;
   }
 
+  @Override
+  public BuiltinProvider<FdoProfileProvider> getProvider() {
+    return PROVIDER;
+  }
+
   public FdoInputFile getInputFile() {
     return fdoInputFile;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/PropellerOptimizeProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/PropellerOptimizeProvider.java
index 51bfb5a..0d15b8f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/PropellerOptimizeProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/PropellerOptimizeProvider.java
@@ -14,23 +14,27 @@
 package com.google.devtools.build.lib.rules.cpp;
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 
 /** Provider that contains the profile used for propeller. */
 @Immutable
 public final class PropellerOptimizeProvider extends NativeInfo {
-  public static final NativeProvider<PropellerOptimizeProvider> PROVIDER =
-      new NativeProvider<PropellerOptimizeProvider>(
-          PropellerOptimizeProvider.class, "PropellerOptimizeInfo") {};
+  public static final BuiltinProvider<PropellerOptimizeProvider> PROVIDER =
+      new BuiltinProvider<PropellerOptimizeProvider>(
+          "PropellerOptimizeInfo", PropellerOptimizeProvider.class) {};
 
   private final PropellerOptimizeInputFile propellerOptimizeInputFile;
 
   public PropellerOptimizeProvider(PropellerOptimizeInputFile propellerOptimizeInputFile) {
-    super(PROVIDER);
     this.propellerOptimizeInputFile = propellerOptimizeInputFile;
   }
 
+  @Override
+  public BuiltinProvider<PropellerOptimizeProvider> getProvider() {
+    return PROVIDER;
+  }
+
   public PropellerOptimizeInputFile getInputFile() {
     return propellerOptimizeInputFile;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java
index cae4cff..6b2b150 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/proto/CcProtoAspect.java
@@ -126,7 +126,7 @@
             .useToolchainTransition(true)
             .add(
                 attr(PROTO_TOOLCHAIN_ATTR, LABEL)
-                    .mandatoryNativeProviders(ImmutableList.of(ProtoLangToolchainProvider.class))
+                    .mandatoryBuiltinProviders(ImmutableList.of(ProtoLangToolchainProvider.class))
                     .value(PROTO_TOOLCHAIN_LABEL))
             .add(
                 attr(CcToolchain.CC_TOOLCHAIN_DEFAULT_ATTRIBUTE_NAME, LABEL)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/BootClassPathInfo.java b/src/main/java/com/google/devtools/build/lib/rules/java/BootClassPathInfo.java
index f6e9669..443f33c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/BootClassPathInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/BootClassPathInfo.java
@@ -42,16 +42,14 @@
 @Immutable
 public class BootClassPathInfo extends NativeInfo implements StarlarkValue {
 
-  public static final String STARLARK_NAME = "BootClassPathInfo";
-
   /** Provider singleton constant. */
-  public static final BuiltinProvider<BootClassPathInfo> PROVIDER = new Provider();
+  public static final Provider PROVIDER = new Provider();
 
   /** Provider class for {@link BootClassPathInfo} objects. */
   @StarlarkBuiltin(name = "Provider", documented = false, doc = "")
   public static class Provider extends BuiltinProvider<BootClassPathInfo> implements ProviderApi {
     private Provider() {
-      super(STARLARK_NAME, BootClassPathInfo.class);
+      super("BootClassPathInfo", BootClassPathInfo.class);
     }
 
     @StarlarkMethod(
@@ -120,12 +118,17 @@
       NestedSet<Artifact> auxiliary,
       Artifact system,
       Location location) {
-    super(PROVIDER, location);
+    super(location);
     this.bootclasspath = bootclasspath;
     this.auxiliary = auxiliary;
     this.system = system;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   public static BootClassPathInfo create(NestedSet<Artifact> bootclasspath) {
     return new BootClassPathInfo(
         bootclasspath, NestedSetBuilder.emptySet(Order.NAIVE_LINK_ORDER), null, null);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java
index b35c4ae..a1bfd01 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java
@@ -109,12 +109,6 @@
   // Whether or not this library should be used only for compilation and not at runtime.
   private final boolean neverlink;
 
-  /** Returns the instance for the provided providerClass, or <tt>null</tt> if not present. */
-  @Nullable
-  public <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass) {
-    return providers.getProvider(providerClass);
-  }
-
   public TransitiveInfoProviderMap getProviders() {
     return providers;
   }
@@ -199,6 +193,14 @@
         .filter(Objects::nonNull);
   }
 
+  /** Returns the instance for the provided providerClass, or <tt>null</tt> if not present. */
+  // TODO(adonovan): rename these three overloads of getProvider to avoid
+  // confusion with the unrelated no-arg Info.getProvider method.
+  @Nullable
+  public <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass) {
+    return providers.getProvider(providerClass);
+  }
+
   /**
    * Returns a provider of the specified class, fetched from the specified target or, if not found,
    * from the JavaInfo of the given target. JavaInfo can be found as a declared provider in
@@ -221,10 +223,6 @@
     return javaInfo.getProvider(providerClass);
   }
 
-  public static JavaInfo getJavaInfo(TransitiveInfoCollection target) {
-    return (JavaInfo) target.get(JavaInfo.PROVIDER.getKey());
-  }
-
   public static <T extends TransitiveInfoProvider> T getProvider(
       Class<T> providerClass, TransitiveInfoProviderMap providerMap) {
     T provider = providerMap.getProvider(providerClass);
@@ -238,6 +236,10 @@
     return javaInfo.getProvider(providerClass);
   }
 
+  public static JavaInfo getJavaInfo(TransitiveInfoCollection target) {
+    return (JavaInfo) target.get(JavaInfo.PROVIDER.getKey());
+  }
+
   public static <T extends TransitiveInfoProvider> List<T> getProvidersFromListOfTargets(
       Class<T> providerClass, Iterable<? extends TransitiveInfoCollection> targets) {
     List<T> providersList = new ArrayList<>();
@@ -259,7 +261,7 @@
       boolean neverlink,
       ImmutableList<String> javaConstraints,
       Location location) {
-    super(PROVIDER, location);
+    super(location);
     this.directRuntimeJars = directRuntimeJars;
     this.transitiveOnlyRuntimeJars = transitiveOnlyRuntimeJars;
     this.providers = providers;
@@ -267,6 +269,11 @@
     this.javaConstraints = javaConstraints;
   }
 
+  @Override
+  public JavaInfoProvider getProvider() {
+    return PROVIDER;
+  }
+
   public Boolean isNeverlink() {
     return neverlink;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaNativeLibraryInfo.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaNativeLibraryInfo.java
index 61fa7c0..24e8840 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaNativeLibraryInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaNativeLibraryInfo.java
@@ -40,10 +40,14 @@
   private final NestedSet<LibraryToLink> transitiveJavaNativeLibraries;
 
   public JavaNativeLibraryInfo(NestedSet<LibraryToLink> transitiveJavaNativeLibraries) {
-    super(PROVIDER);
     this.transitiveJavaNativeLibraries = transitiveJavaNativeLibraries;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   /**
    * Collects native libraries in the transitive closure of its deps that are needed for executing
    * Java code.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaPackageConfigurationRule.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaPackageConfigurationRule.java
index 76100a5..7cc2738 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaPackageConfigurationRule.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaPackageConfigurationRule.java
@@ -46,7 +46,7 @@
             attr("packages", LABEL_LIST)
                 .cfg(ExecutionTransitionFactory.create())
                 .allowedFileTypes()
-                .mandatoryNativeProviders(ImmutableList.of(PackageSpecificationProvider.class)))
+                .mandatoryBuiltinProviders(ImmutableList.of(PackageSpecificationProvider.class)))
         /* <!-- #BLAZE_RULE(java_package_configuration).ATTRIBUTE(javacopts) -->
         Java compiler flags.
         <!-- #END_BLAZE_RULE.ATTRIBUTE --> */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainRule.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainRule.java
index 0d16385..84ec73c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainRule.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainRule.java
@@ -264,7 +264,8 @@
                 .allowedFileTypes()
                 // This needs to be in the execution configuration.
                 .cfg(ExecutionTransitionFactory.create())
-                .mandatoryNativeProviders(ImmutableList.of(JavaPackageConfigurationProvider.class)))
+                .mandatoryBuiltinProviders(
+                    ImmutableList.of(JavaPackageConfigurationProvider.class)))
         /* <!-- #BLAZE_RULE(java_toolchain).ATTRIBUTE(jacocorunner) -->
         Label of the JacocoCoverageRunner deploy jar.
         <!-- #END_BLAZE_RULE.ATTRIBUTE --> */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/MessageBundleInfo.java b/src/main/java/com/google/devtools/build/lib/rules/java/MessageBundleInfo.java
index 7b2c07c..3e17d0c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/MessageBundleInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/MessageBundleInfo.java
@@ -77,10 +77,15 @@
   @VisibleForSerialization
   @AutoCodec.Instantiator
   MessageBundleInfo(ImmutableList<Artifact> messages, Location location) {
-    super(PROVIDER, location);
+    super(location);
     this.messages = Preconditions.checkNotNull(messages);
   }
 
+  @Override
+  public BuiltinProvider<MessageBundleInfo> getProvider() {
+    return PROVIDER;
+  }
+
   public ImmutableList<Artifact> getMessages() {
     return messages;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java b/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java
index 2950dcd..fe9f82f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/ProguardSpecProvider.java
@@ -34,11 +34,15 @@
   private final NestedSet<Artifact> transitiveProguardSpecs;
 
   public ProguardSpecProvider(NestedSet<Artifact> transitiveProguardSpecs) {
-    super(PROVIDER);
     this.transitiveProguardSpecs = transitiveProguardSpecs;
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public Depset /*<Artifact>*/ getTransitiveProguardSpecsForStarlark() {
     return Depset.of(Artifact.TYPE, transitiveProguardSpecs);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java b/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java
index b1de0eb..5c5b440 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/proto/GeneratedExtensionRegistryProvider.java
@@ -88,7 +88,6 @@
       Artifact classJar,
       Artifact srcJar,
       NestedSet<Artifact> inputs) {
-    super(PROVIDER);
     this.generatingRuleLabel = generatingRuleLabel;
     this.isLite = isLite;
     this.classJar = classJar;
@@ -96,6 +95,11 @@
     this.inputs = inputs;
   }
 
+  @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
   /** A builder for {@link GeneratedExtensionRegistryProvider}. */
   public static class Builder {
     private Label generatingRuleLabel = null;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java
index 1208de8..47eb60f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaLiteProtoAspect.java
@@ -109,7 +109,7 @@
                 ImmutableList.of(StarlarkProviderIdentifier.forKey(JavaInfo.PROVIDER.getKey())))
             .add(
                 attr(JavaProtoAspectCommon.LITE_PROTO_TOOLCHAIN_ATTR, LABEL)
-                    .mandatoryNativeProviders(
+                    .mandatoryBuiltinProviders(
                         ImmutableList.<Class<? extends TransitiveInfoProvider>>of(
                             ProtoLangToolchainProvider.class))
                     .value(getProtoToolchainLabel(defaultProtoToolchainLabel)))
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java
index 7d73bf4..58fed22 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/proto/JavaProtoAspect.java
@@ -129,7 +129,7 @@
                 ImmutableList.of(StarlarkProviderIdentifier.forKey(JavaInfo.PROVIDER.getKey())))
             .add(
                 attr(JavaProtoAspectCommon.SPEED_PROTO_TOOLCHAIN_ATTR, LABEL)
-                    // TODO(carmi): reinstate mandatoryNativeProviders(ProtoLangToolchainProvider)
+                    // TODO(carmi): reinstate mandatoryBuiltinProviders(ProtoLangToolchainProvider)
                     // once it's in a Bazel release.
                     .legacyAllowAnyFileType()
                     .value(getSpeedProtoToolchainLabel(defaultSpeedProtoToolchainLabel)))
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDebugOutputsInfo.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDebugOutputsInfo.java
index ccda4f6..ddf447c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDebugOutputsInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDebugOutputsInfo.java
@@ -17,8 +17,8 @@
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.apple.AppleDebugOutputsApi;
 import java.util.HashMap;
 import java.util.Map;
@@ -64,8 +64,8 @@
   public static final String STARLARK_NAME = "AppleDebugOutputs";
 
   /** Starlark constructor and identifier for AppleDebugOutputsInfo. */
-  public static final NativeProvider<AppleDebugOutputsInfo> STARLARK_CONSTRUCTOR =
-      new NativeProvider<AppleDebugOutputsInfo>(AppleDebugOutputsInfo.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<AppleDebugOutputsInfo> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<AppleDebugOutputsInfo>(STARLARK_NAME, AppleDebugOutputsInfo.class) {};
 
   private final ImmutableMap<String, Dict<String, Artifact>> outputsMap;
 
@@ -85,10 +85,14 @@
    *     </ul>
    */
   private AppleDebugOutputsInfo(ImmutableMap<String, Dict<String, Artifact>> map) {
-    super(STARLARK_CONSTRUCTOR);
     this.outputsMap = map;
   }
 
+  @Override
+  public BuiltinProvider<AppleDebugOutputsInfo> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   /** Returns the multi-architecture dylib binary that apple_binary created. */
   @Override
   public ImmutableMap<String, Dict<String, Artifact>> getOutputsMap() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDylibBinaryInfo.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDylibBinaryInfo.java
index 8fde971..abf5ad2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDylibBinaryInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDylibBinaryInfo.java
@@ -16,8 +16,8 @@
 
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.apple.AppleDylibBinaryApi;
 
 /**
@@ -38,19 +38,23 @@
   public static final String STARLARK_NAME = "AppleDylibBinary";
 
   /** Starlark constructor and identifier for AppleDylibBinaryInfo. */
-  public static final NativeProvider<AppleDylibBinaryInfo> STARLARK_CONSTRUCTOR =
-      new NativeProvider<AppleDylibBinaryInfo>(AppleDylibBinaryInfo.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<AppleDylibBinaryInfo> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<AppleDylibBinaryInfo>(STARLARK_NAME, AppleDylibBinaryInfo.class) {};
 
   private final Artifact dylibBinary;
   private final ObjcProvider depsObjcProvider;
 
   public AppleDylibBinaryInfo(Artifact dylibBinary,
       ObjcProvider depsObjcProvider) {
-    super(STARLARK_CONSTRUCTOR);
     this.dylibBinary = dylibBinary;
     this.depsObjcProvider = depsObjcProvider;
   }
 
+  @Override
+  public BuiltinProvider<AppleDylibBinaryInfo> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   /**
    * Returns the multi-architecture dylib binary that apple_binary created.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDynamicFrameworkInfo.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDynamicFrameworkInfo.java
index 3a5149d..01c4b7a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDynamicFrameworkInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleDynamicFrameworkInfo.java
@@ -18,8 +18,8 @@
 import com.google.devtools.build.lib.collect.nestedset.Depset;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.apple.AppleDynamicFrameworkInfoApi;
 import javax.annotation.Nullable;
 
@@ -45,9 +45,9 @@
   public static final String STARLARK_NAME = "AppleDynamicFramework";
 
   /** Starlark constructor and identifier for AppleDynamicFrameworkInfo. */
-  public static final NativeProvider<AppleDynamicFrameworkInfo> STARLARK_CONSTRUCTOR =
-      new NativeProvider<AppleDynamicFrameworkInfo>(
-          AppleDynamicFrameworkInfo.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<AppleDynamicFrameworkInfo> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<AppleDynamicFrameworkInfo>(
+          STARLARK_NAME, AppleDynamicFrameworkInfo.class) {};
 
   /** Field name for the dylib binary artifact of the dynamic framework. */
   public static final String DYLIB_BINARY_FIELD_NAME = "binary";
@@ -68,7 +68,6 @@
       ObjcProvider depsObjcProvider,
       NestedSet<String> dynamicFrameworkDirs,
       NestedSet<Artifact> dynamicFrameworkFiles) {
-    super(STARLARK_CONSTRUCTOR);
     this.dylibBinary = dylibBinary;
     this.depsObjcProvider = depsObjcProvider;
     this.dynamicFrameworkDirs = dynamicFrameworkDirs;
@@ -76,6 +75,11 @@
   }
 
   @Override
+  public BuiltinProvider<AppleDynamicFrameworkInfo> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
+  @Override
   public Depset /*<String>*/ getDynamicFrameworkDirs() {
     return Depset.of(Depset.ElementType.STRING, dynamicFrameworkDirs);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleExecutableBinaryInfo.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleExecutableBinaryInfo.java
index d2efddf..0dd66cb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleExecutableBinaryInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleExecutableBinaryInfo.java
@@ -16,8 +16,8 @@
 
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.apple.AppleExecutableBinaryApi;
 
 /**
@@ -39,9 +39,9 @@
   public static final String STARLARK_NAME = "AppleExecutableBinary";
 
   /** Starlark constructor and identifier for AppleExecutableBinaryInfo. */
-  public static final NativeProvider<AppleExecutableBinaryInfo> STARLARK_CONSTRUCTOR =
-      new NativeProvider<AppleExecutableBinaryInfo>(
-          AppleExecutableBinaryInfo.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<AppleExecutableBinaryInfo> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<AppleExecutableBinaryInfo>(
+          STARLARK_NAME, AppleExecutableBinaryInfo.class) {};
 
   private final Artifact appleExecutableBinary;
   private final ObjcProvider depsObjcProvider;
@@ -52,11 +52,15 @@
    */
   public AppleExecutableBinaryInfo(Artifact appleExecutableBinary,
       ObjcProvider depsObjcProvider) {
-    super(STARLARK_CONSTRUCTOR);
     this.appleExecutableBinary = appleExecutableBinary;
     this.depsObjcProvider = depsObjcProvider;
   }
 
+  @Override
+  public BuiltinProvider<AppleExecutableBinaryInfo> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   /**
    * Returns the multi-architecture executable binary that apple_binary created.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleLoadableBundleBinaryInfo.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleLoadableBundleBinaryInfo.java
index a637259..d1cd780 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleLoadableBundleBinaryInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleLoadableBundleBinaryInfo.java
@@ -16,8 +16,8 @@
 
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.starlarkbuildapi.apple.AppleLoadableBundleBinaryApi;
 
 /**
@@ -38,9 +38,9 @@
   public static final String STARLARK_NAME = "AppleLoadableBundleBinary";
 
   /** Starlark constructor and identifier for AppleLoadableBundleBinary. */
-  public static final NativeProvider<AppleLoadableBundleBinaryInfo> STARLARK_CONSTRUCTOR =
-      new NativeProvider<AppleLoadableBundleBinaryInfo>(
-          AppleLoadableBundleBinaryInfo.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<AppleLoadableBundleBinaryInfo> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<AppleLoadableBundleBinaryInfo>(
+          STARLARK_NAME, AppleLoadableBundleBinaryInfo.class) {};
 
   private final Artifact appleLoadableBundleBinary;
   private final ObjcProvider depsObjcProvider;
@@ -51,11 +51,15 @@
    */
   public AppleLoadableBundleBinaryInfo(Artifact appleLoadableBundleBinary,
       ObjcProvider depsObjcProvider) {
-    super(STARLARK_CONSTRUCTOR);
     this.appleLoadableBundleBinary = appleLoadableBundleBinary;
     this.depsObjcProvider = depsObjcProvider;
   }
 
+  @Override
+  public BuiltinProvider<AppleLoadableBundleBinaryInfo> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   /**
    * Returns the multi-architecture binary that apple_binary created.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStarlarkCommon.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStarlarkCommon.java
index 6eaa83b..39fa8e5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStarlarkCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStarlarkCommon.java
@@ -26,7 +26,7 @@
 import com.google.devtools.build.lib.analysis.starlark.StarlarkRuleContext;
 import com.google.devtools.build.lib.collect.nestedset.Depset;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
-import com.google.devtools.build.lib.packages.NativeProvider;
+import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.packages.StarlarkAspect;
@@ -288,7 +288,7 @@
   private StructImpl createAppleBinaryOutputStarlarkStruct(
       AppleBinaryOutput output, StarlarkThread thread) {
     Provider constructor =
-        new NativeProvider<StructImpl>(StructImpl.class, "apple_binary_output") {};
+        new BuiltinProvider<StructImpl>("apple_binary_output", StructImpl.class) {};
     // We have to transform the output group dictionary into one that contains StarlarkValues
     // instead
     // of plain NestedSets because the Starlark caller may want to return this directly from their
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStaticLibraryInfo.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStaticLibraryInfo.java
index 3e69875..91f301d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStaticLibraryInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStaticLibraryInfo.java
@@ -42,17 +42,20 @@
   private final ObjcProvider depsObjcProvider;
 
   /**
-   * Creates a new AppleStaticLibraryInfo provider that propagates the given
-   * {@code apple_static_library} information.
+   * Creates a new AppleStaticLibraryInfo provider that propagates the given {@code
+   * apple_static_library} information.
    */
-  public AppleStaticLibraryInfo(Artifact multiArchArchive,
-      ObjcProvider depsObjcProvider) {
-    super(STARLARK_CONSTRUCTOR);
+  public AppleStaticLibraryInfo(Artifact multiArchArchive, ObjcProvider depsObjcProvider) {
     this.multiArchArchive = multiArchArchive;
     this.depsObjcProvider = depsObjcProvider;
   }
 
   @Override
+  public Provider getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
+  @Override
   public Artifact getMultiArchArchive() {
     return multiArchArchive;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/MultiArchBinarySupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/MultiArchBinarySupport.java
index b3a2ce5..d4b774d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/MultiArchBinarySupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/MultiArchBinarySupport.java
@@ -34,7 +34,6 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.Info;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainProvider;
 import com.google.devtools.build.lib.rules.objc.CompilationSupport.ExtraLinkArgs;
@@ -327,15 +326,6 @@
     return avoidArtifacts.build();
   }
 
-  @Deprecated // Use BuiltinProvider instead.
-  private static <T extends Info> ImmutableList<T> getTypedProviders(
-      Iterable<TransitiveInfoCollection> infoCollections, NativeProvider<T> providerClass) {
-    return Streams.stream(infoCollections)
-        .filter(infoCollection -> infoCollection.get(providerClass) != null)
-        .map(infoCollection -> infoCollection.get(providerClass))
-        .collect(ImmutableList.toImmutableList());
-  }
-
   private static <T extends Info> ImmutableList<T> getTypedProviders(
       Iterable<TransitiveInfoCollection> infoCollections, BuiltinProvider<T> providerClass) {
     return Streams.stream(infoCollections)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProtoProvider.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProtoProvider.java
index e77a5c7..b085253 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProtoProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProtoProvider.java
@@ -18,8 +18,8 @@
 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.packages.BuiltinProvider;
 import com.google.devtools.build.lib.packages.NativeInfo;
-import com.google.devtools.build.lib.packages.NativeProvider;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 /**
@@ -45,8 +45,8 @@
   public static final String STARLARK_NAME = "ObjcProto";
 
   /** Starlark constructor and identifier for AppleExecutableBinaryInfo. */
-  public static final NativeProvider<ObjcProtoProvider> STARLARK_CONSTRUCTOR =
-      new NativeProvider<ObjcProtoProvider>(ObjcProtoProvider.class, STARLARK_NAME) {};
+  public static final BuiltinProvider<ObjcProtoProvider> STARLARK_CONSTRUCTOR =
+      new BuiltinProvider<ObjcProtoProvider>(STARLARK_NAME, ObjcProtoProvider.class) {};
 
   private final NestedSet<Artifact> protoFiles;
   private final NestedSet<Artifact> protobufHeaders;
@@ -58,13 +58,17 @@
       NestedSet<Artifact> portableProtoFilters,
       NestedSet<Artifact> protobufHeaders,
       NestedSet<PathFragment> protobufHeaderSearchPaths) {
-    super(STARLARK_CONSTRUCTOR);
     this.protoFiles = Preconditions.checkNotNull(protoFiles);
     this.portableProtoFilters = Preconditions.checkNotNull(portableProtoFilters);
     this.protobufHeaders = Preconditions.checkNotNull(protobufHeaders);
     this.protobufHeaderSearchPaths = Preconditions.checkNotNull(protobufHeaderSearchPaths);
   }
 
+  @Override
+  public BuiltinProvider<ObjcProtoProvider> getProvider() {
+    return STARLARK_CONSTRUCTOR;
+  }
+
   /** Returns the set of all proto files that the dependencies of this provider has seen. */
   public NestedSet<Artifact> getProtoFiles() {
     return protoFiles;
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 3268de5..3414ca4 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
@@ -33,8 +33,8 @@
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.BuiltinProvider;
+import com.google.devtools.build.lib.packages.BuiltinProvider.WithLegacyStarlarkName;
 import com.google.devtools.build.lib.packages.Info;
-import com.google.devtools.build.lib.packages.NativeProvider.WithLegacyStarlarkName;
 import com.google.devtools.build.lib.packages.semantics.BuildLanguageOptions;
 import com.google.devtools.build.lib.rules.cpp.CcCompilationContext;
 import com.google.devtools.build.lib.rules.cpp.CcLinkingContext;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java
index 243df22..359b4a3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoInfo.java
@@ -78,7 +78,7 @@
       Artifact directDescriptorSet,
       NestedSet<Artifact> transitiveDescriptorSets,
       Location location) {
-    super(PROVIDER, location);
+    super(location);
     this.directProtoSources = directProtoSources;
     this.originalDirectProtoSources = originalDirectProtoSources;
     this.directProtoSourceRoot = directProtoSourceRoot;
@@ -96,6 +96,11 @@
     this.transitiveDescriptorSets = transitiveDescriptorSets;
   }
 
+  @Override
+  public BuiltinProvider<ProtoInfo> getProvider() {
+    return PROVIDER;
+  }
+
   /**
    * The proto source files that are used in compiling this {@code proto_library}.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoLangToolchainRule.java b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoLangToolchainRule.java
index eacaef6..65e27e9 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoLangToolchainRule.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoLangToolchainRule.java
@@ -70,7 +70,7 @@
         .add(
             attr("blacklisted_protos", LABEL_LIST)
                 .allowedFileTypes()
-                .mandatoryNativeProviders(
+                .mandatoryBuiltinProviders(
                     ImmutableList.<Class<? extends TransitiveInfoProvider>>of(FileProvider.class)))
         .requiresConfigurationFragments(ProtoConfiguration.class)
         .advertiseProvider(ProtoLangToolchainProvider.class)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyCcLinkParamsProvider.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyCcLinkParamsProvider.java
index bdadd66..3e5f48c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyCcLinkParamsProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyCcLinkParamsProvider.java
@@ -31,11 +31,15 @@
   private final CcInfo ccInfo;
 
   public PyCcLinkParamsProvider(CcInfo ccInfo) {
-    super(PROVIDER);
     this.ccInfo = CcInfo.builder().setCcLinkingContext(ccInfo.getCcLinkingContext()).build();
   }
 
   @Override
+  public Provider getProvider() {
+    return PROVIDER;
+  }
+
+  @Override
   public CcInfo getCcInfo() {
     return ccInfo;
   }