bazel packages: delete NativeProvider, dematerialize StructImpl.provider

This change merges NativeProvider into BuiltinProvider. The two
classes were almost identical.

Also, it removes the StructImpl.provider
field to save one word of space in each instance of NativeInfo.
This requires each subclass to define getProvider,
which is straightforward but leads to a tiresome diff.
(Sadly this doesn't yield tangible space savings; I'm not sure why.)

All the interesting changes are in lib.packages. The rest is repetitive.

This is a small step towards withering StructImpl and StructApi
out of existence.

NO_IFTTT=spurious warning
PiperOrigin-RevId: 341102857
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));
     }