Use RequiredProviders to validate rule prerequisites in RuleContext.

We now use a unified way to check provider requirements everywhere.

Reland of https://github.com/bazelbuild/bazel/commit/c32e1b1efcd703b3780de47fba62974123593d71.

RELNOTES: None.
PiperOrigin-RevId: 164038621
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java
index deee99a..235dc37 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AbstractConfiguredTarget.java
@@ -104,12 +104,6 @@
   @Override
   public Object getValue(String name) {
     switch (name) {
-      case FILES_FIELD:
-      case DEFAULT_RUNFILES_FIELD:
-      case DATA_RUNFILES_FIELD:
-      case FilesToRunProvider.SKYLARK_NAME:
-        // Standard fields should be proxied to their default provider object
-        return getDefaultProvider().getValue(name);
       case LABEL_FIELD:
         return getLabel();
       default:
@@ -205,7 +199,18 @@
     if (OutputGroupProvider.SKYLARK_NAME.equals(providerKey)) {
       return get(OutputGroupProvider.SKYLARK_CONSTRUCTOR);
     }
-    return rawGetSkylarkProvider(providerKey);
+    switch (providerKey) {
+      case FILES_FIELD:
+      case DEFAULT_RUNFILES_FIELD:
+      case DATA_RUNFILES_FIELD:
+      case FilesToRunProvider.SKYLARK_NAME:
+        // Standard fields should be proxied to their default provider object
+        return getDefaultProvider().getValue(providerKey);
+      case OutputGroupProvider.SKYLARK_NAME:
+        return get(OutputGroupProvider.SKYLARK_CONSTRUCTOR);
+      default:
+        return rawGetSkylarkProvider(providerKey);
+    }
   }
 
   /** Implement in subclasses to get a skylark provider for a given {@code providerKey}. */
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 771189a..de978e0 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -70,18 +70,17 @@
 import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.packages.PackageSpecification;
 import com.google.devtools.build.lib.packages.RawAttributeMapper;
+import com.google.devtools.build.lib.packages.RequiredProviders;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.packages.RuleErrorConsumer;
-import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.rules.AliasProvider;
 import com.google.devtools.build.lib.rules.MakeVariableProvider;
 import com.google.devtools.build.lib.rules.fileset.FilesetProvider;
 import com.google.devtools.build.lib.shell.ShellUtils;
-import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.syntax.Type.LabelClass;
@@ -1975,154 +1974,101 @@
       }
     }
 
-    private String getMissingMandatoryProviders(ConfiguredTarget prerequisite, Attribute attribute){
-      ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList =
-          attribute.getMandatoryProvidersList();
-      if (mandatoryProvidersList.isEmpty()) {
-        return null;
-      }
-      List<List<String>> missingProvidersList = new ArrayList<>();
-      for (ImmutableSet<SkylarkProviderIdentifier> providers : mandatoryProvidersList) {
-        List<String> missing = new ArrayList<>();
-        for (SkylarkProviderIdentifier provider : providers) {
-          // A rule may require a built-in provider that is always implicitly provided, e.g. "files"
-          ImmutableSet<String> availableKeys =
-              ImmutableSet.copyOf(((ClassObject) prerequisite).getKeys());
-          if ((prerequisite.get(provider) == null)
-              && !(provider.isLegacy() && availableKeys.contains(provider.getLegacyId()))) {
-            missing.add(provider.toString());
-          }
-        }
-        if (missing.isEmpty()) {
-          return null;
-        } else {
-          missingProvidersList.add(missing);
-        }
-      }
-      StringBuilder missingProviders = new StringBuilder();
-      Joiner joinProvider = Joiner.on("', '");
-      for (List<String> providers : missingProvidersList) {
-        if (missingProviders.length() > 0) {
-          missingProviders.append(" or ");
-        }
-        missingProviders.append((providers.size() > 1) ? "[" : "")
-                        .append("'");
-        joinProvider.appendTo(missingProviders, providers);
-        missingProviders.append("'")
-                        .append((providers.size() > 1) ? "]" : "");
-      }
-      return missingProviders.toString();
-    }
-
-    private String getMissingMandatoryNativeProviders(
-        ConfiguredTarget prerequisite, Attribute attribute) {
-      List<ImmutableList<Class<? extends TransitiveInfoProvider>>> mandatoryProvidersList =
-          attribute.getMandatoryNativeProvidersList();
-      if (mandatoryProvidersList.isEmpty()) {
-        return null;
-      }
-      List<List<String>> missingProvidersList = new ArrayList<>();
-      for (ImmutableList<Class<? extends TransitiveInfoProvider>> providers
-          : mandatoryProvidersList) {
-        List<String> missing = new ArrayList<>();
-        for (Class<? extends TransitiveInfoProvider> provider : providers) {
-          if (prerequisite.getProvider(provider) == null) {
-            missing.add(provider.getSimpleName());
-          }
-        }
-        if (missing.isEmpty()) {
-          return null;
-        } else {
-          missingProvidersList.add(missing);
-        }
-      }
-      StringBuilder missingProviders = new StringBuilder();
-      Joiner joinProvider = Joiner.on(", ");
-      for (List<String> providers : missingProvidersList) {
-        if (missingProviders.length() > 0) {
-          missingProviders.append(" or ");
-        }
-        missingProviders.append((providers.size() > 1) ? "[" : "");
-        joinProvider.appendTo(missingProviders, providers);
-        missingProviders.append((providers.size() > 1) ? "]" : "");
-      }
-      return missingProviders.toString();
-    }
-
     /**
-     * Because some rules still have to use allowedRuleClasses to do rule dependency validation.
-     * A dependency is valid if it is from a rule in allowedRuleClasses, OR if all of the providers
-     * in mandatoryNativeProviders AND mandatoryProvidersList are provided by the target.
+     * Because some rules still have to use allowedRuleClasses to do rule dependency validation. A
+     * dependency is valid if it is from a rule in allowedRuledClasses, OR if all of the providers
+     * in requiredProviders are provided by the target.
      */
     private void validateRuleDependency(ConfiguredTarget prerequisite, Attribute attribute) {
-      Target prerequisiteTarget = prerequisite.getTarget();
-      RuleClass ruleClass = ((Rule) prerequisiteTarget).getRuleClassObject();
-      String notAllowedRuleClassesMessage = null;
 
+      Set<String> unfulfilledRequirements = new LinkedHashSet<>();
+      if (checkRuleDependencyClass(prerequisite, attribute, unfulfilledRequirements)) {
+        return;
+      }
+
+      if (checkRuleDependencyClassWarnings(prerequisite, attribute)) {
+        return;
+      }
+
+      if (checkRuleDependencyMandatoryProviders(prerequisite, attribute, unfulfilledRequirements)) {
+        return;
+      }
+
+      // not allowed rule class and some mandatory providers missing => reject.
+      if (!unfulfilledRequirements.isEmpty()) {
+        attributeError(
+            attribute.getName(), StringUtil.joinEnglishList(unfulfilledRequirements, "and"));
+      }
+    }
+
+    /** Check if prerequisite should be allowed based on its rule class. */
+    private boolean checkRuleDependencyClass(
+        ConfiguredTarget prerequisite, Attribute attribute, Set<String> unfulfilledRequirements) {
       if (attribute.getAllowedRuleClassesPredicate() != Predicates.<RuleClass>alwaysTrue()) {
-        if (attribute.getAllowedRuleClassesPredicate().apply(ruleClass)) {
+        if (attribute
+            .getAllowedRuleClassesPredicate()
+            .apply(((Rule) prerequisite.getTarget()).getRuleClassObject())) {
           // prerequisite has an allowed rule class => accept.
-          return;
+          return true;
         }
         // remember that the rule class that was not allowed;
         // but maybe prerequisite provides required providers? do not reject yet.
-        notAllowedRuleClassesMessage =
+        unfulfilledRequirements.add(
             badPrerequisiteMessage(
-                prerequisiteTarget.getTargetKind(),
+                prerequisite.getTarget().getTargetKind(),
                 prerequisite,
                 "expected " + attribute.getAllowedRuleClassesPredicate(),
-                false);
+                false));
       }
+      return false;
+    }
 
-      if (attribute.getAllowedRuleClassesWarningPredicate().apply(ruleClass)) {
+    /**
+     * Check if prerequisite should be allowed with warning based on its rule class.
+     *
+     * <p>If yes, also issues said warning.
+     */
+    private boolean checkRuleDependencyClassWarnings(
+        ConfiguredTarget prerequisite, Attribute attribute) {
+      if (attribute
+          .getAllowedRuleClassesWarningPredicate()
+          .apply(((Rule) prerequisite.getTarget()).getRuleClassObject())) {
         Predicate<RuleClass> allowedRuleClasses = attribute.getAllowedRuleClassesPredicate();
-        reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisite,
+        reportBadPrerequisite(
+            attribute,
+            prerequisite.getTarget().getTargetKind(),
+            prerequisite,
             allowedRuleClasses == Predicates.<RuleClass>alwaysTrue()
                 ? null
                 : "expected " + allowedRuleClasses,
             true);
         // prerequisite has a rule class allowed with a warning => accept, emitting a warning.
-        return;
+        return true;
+      }
+      return false;
+    }
+
+    /** Check if prerequisite should be allowed based on required providers on the attribute. */
+    private boolean checkRuleDependencyMandatoryProviders(
+        ConfiguredTarget prerequisite, Attribute attribute, Set<String> unfulfilledRequirements) {
+      RequiredProviders requiredProviders = attribute.getRequiredProviders();
+
+      if (requiredProviders.acceptsAny()) {
+        // If no required providers specified, we do not know if we should accept.
+        return false;
       }
 
-      // If we get here, we have no allowed rule class.
-      // If mandatory providers are specified, try them.
-      Set<String> unfulfilledRequirements = new LinkedHashSet<>();
-      if (!attribute.getMandatoryNativeProvidersList().isEmpty()
-          || !attribute.getMandatoryProvidersList().isEmpty()) {
-        boolean hadAllMandatoryProviders = true;
-
-        String missingNativeProviders = getMissingMandatoryNativeProviders(prerequisite, attribute);
-        if (missingNativeProviders != null) {
-          unfulfilledRequirements.add(
-              "'" + prerequisite.getLabel() + "' does not have mandatory providers: "
-                  + missingNativeProviders);
-          hadAllMandatoryProviders = false;
-        }
-
-        String missingProviders = getMissingMandatoryProviders(prerequisite, attribute);
-        if (missingProviders != null) {
-          unfulfilledRequirements.add(
-              "'" + prerequisite.getLabel() + "' does not have mandatory providers: "
-                  + missingProviders);
-          hadAllMandatoryProviders = false;
-        }
-
-        if (hadAllMandatoryProviders) {
-          // all mandatory providers are present => accept.
-          return;
-        }
+      if (prerequisite.satisfies(requiredProviders)) {
+        return true;
       }
 
-      // not allowed rule class and some mandatory providers missing => reject.
-      if (notAllowedRuleClassesMessage != null) {
-        unfulfilledRequirements.add(notAllowedRuleClassesMessage);
-      }
+      unfulfilledRequirements.add(
+          String.format(
+              "'%s' does not have mandatory providers: %s",
+              prerequisite.getLabel(),
+              prerequisite.missingProviders(requiredProviders).getDescription()));
 
-      if (!unfulfilledRequirements.isEmpty()) {
-        attributeError(
-            attribute.getName(), StringUtil.joinEnglishList(unfulfilledRequirements, "and"));
-      }
+      return false;
     }
 
     private void validateDirectPrerequisite(Attribute attribute, ConfiguredTarget prerequisite) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java
index b174a47..b3b4894 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TransitiveInfoCollection.java
@@ -16,6 +16,7 @@
 
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.packages.RequiredProviders;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.syntax.SkylarkIndexable;
@@ -79,4 +80,25 @@
    * <b>null</b>.</p>
    */
   @Nullable BuildConfiguration getConfiguration();
+
+  /**
+   * Checks whether this {@link TransitiveInfoCollection} satisfies given {@link RequiredProviders}.
+   */
+  default boolean satisfies(RequiredProviders providers) {
+    return providers.isSatisfiedBy(
+        aClass -> getProvider(aClass.asSubclass(TransitiveInfoProvider.class)) != null,
+        id -> this.get(id) != null);
+  }
+
+  /**
+   * Returns providers that this {@link TransitiveInfoCollection} misses from a given {@link
+   * RequiredProviders}.
+   *
+   * <p>If none are missing, returns {@link RequiredProviders} that accept any set of providers.
+   */
+  default RequiredProviders missingProviders(RequiredProviders providers) {
+    return providers.getMissing(
+        aClass -> getProvider(aClass.asSubclass(TransitiveInfoProvider.class)) != null,
+        id -> this.get(id) != null);
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelPrerequisiteValidator.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelPrerequisiteValidator.java
index bb2456c..f1d7dff 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelPrerequisiteValidator.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/BazelPrerequisiteValidator.java
@@ -14,16 +14,14 @@
 
 package com.google.devtools.build.lib.bazel.rules;
 
-import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.lib.analysis.PackageSpecificationProvider;
 import com.google.devtools.build.lib.analysis.RuleContext;
-import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.NonconfigurableAttributeMapper;
 import com.google.devtools.build.lib.packages.PackageGroup;
 import com.google.devtools.build.lib.packages.RawAttributeMapper;
+import com.google.devtools.build.lib.packages.RequiredProviders;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.rules.AliasProvider;
@@ -77,15 +75,10 @@
     }
 
     if (prerequisiteTarget instanceof PackageGroup) {
-      ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
-          mandatoryNativeProviders =
-              RawAttributeMapper.of(rule)
-                  .getAttributeDefinition(attrName)
-                  .getMandatoryNativeProvidersList();
+      RequiredProviders requiredProviders =
+          RawAttributeMapper.of(rule).getAttributeDefinition(attrName).getRequiredProviders();
       boolean containsPackageSpecificationProvider =
-          mandatoryNativeProviders
-              .stream()
-              .anyMatch(list -> list.contains(PackageSpecificationProvider.class));
+          requiredProviders.getDescription().contains("PackageSpecificationProvider");
       // TODO(plf): Add the PackageSpecificationProvider to the 'visibility' attribute.
       if (!attrName.equals("visibility") && !containsPackageSpecificationProvider) {
         context.reportError(
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 bcf6341..bd36056 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
@@ -457,10 +457,8 @@
     private Predicate<AttributeMap> condition;
     private Set<PropertyFlag> propertyFlags = EnumSet.noneOf(PropertyFlag.class);
     private PredicateWithMessage<Object> allowedValues = null;
-    private ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList =
-        ImmutableList.<ImmutableSet<SkylarkProviderIdentifier>>of();
-    private ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
-        mandatoryNativeProvidersList = ImmutableList.of();
+    private RequiredProviders.Builder requiredProvidersBuilder =
+        RequiredProviders.acceptAnyBuilder();
     private HashMap<String, RuleAspect<?>> aspects = new LinkedHashMap<>();
 
     /**
@@ -956,11 +954,11 @@
      * #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
-     * continues without error. Else the build fails during analysis.
+     * allowedRuleClasses()) and they fulfill {@link #getRequiredProviders()}}, 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 #getRequiredProviders()} 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.
@@ -978,12 +976,10 @@
         Iterable<? extends Iterable<Class<? extends TransitiveInfoProvider>>> providersList) {
       Preconditions.checkState(type.getLabelClass() == LabelClass.DEPENDENCY,
           "must be a label-valued type");
-      ImmutableList.Builder<ImmutableList<Class<? extends TransitiveInfoProvider>>> listBuilder
-          = ImmutableList.builder();
+
       for (Iterable<Class<? extends TransitiveInfoProvider>> providers : providersList) {
-        listBuilder.add(ImmutableList.<Class<? extends TransitiveInfoProvider>>copyOf(providers));
+        this.requiredProvidersBuilder.addNativeSet(ImmutableSet.copyOf(providers));
       }
-      this.mandatoryNativeProvidersList = listBuilder.build();
       return this;
     }
 
@@ -1005,12 +1001,9 @@
         Iterable<? extends Iterable<SkylarkProviderIdentifier>> providersList){
       Preconditions.checkState(type.getLabelClass() == LabelClass.DEPENDENCY,
           "must be a label-valued type");
-      ImmutableList.Builder<ImmutableSet<SkylarkProviderIdentifier>> listBuilder
-          = ImmutableList.builder();
       for (Iterable<SkylarkProviderIdentifier> providers : providersList) {
-        listBuilder.add(ImmutableSet.copyOf(providers));
+        this.requiredProvidersBuilder.addSkylarkSet(ImmutableSet.copyOf(providers));
       }
-      this.mandatoryProvidersList = listBuilder.build();
       return this;
     }
 
@@ -1181,8 +1174,7 @@
           validityPredicate,
           condition,
           allowedValues,
-          mandatoryProvidersList,
-          mandatoryNativeProvidersList,
+          requiredProvidersBuilder.build(),
           ImmutableList.copyOf(aspects.values()));
     }
   }
@@ -1795,10 +1787,7 @@
 
   private final PredicateWithMessage<Object> allowedValues;
 
-  private final ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList;
-
-  private final ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
-      mandatoryNativeProvidersList;
+  private final RequiredProviders requiredProviders;
 
   private final ImmutableList<RuleAspect<?>> aspects;
 
@@ -1828,9 +1817,7 @@
       ValidityPredicate validityPredicate,
       Predicate<AttributeMap> condition,
       PredicateWithMessage<Object> allowedValues,
-      ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList,
-      ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
-          mandatoryNativeProvidersList,
+      RequiredProviders requiredProviders,
       ImmutableList<RuleAspect<?>> aspects) {
     Preconditions.checkNotNull(configTransition);
     Preconditions.checkArgument(
@@ -1864,8 +1851,7 @@
     this.validityPredicate = validityPredicate;
     this.condition = condition;
     this.allowedValues = allowedValues;
-    this.mandatoryProvidersList = mandatoryProvidersList;
-    this.mandatoryNativeProvidersList = mandatoryNativeProvidersList;
+    this.requiredProviders = requiredProviders;
     this.aspects = aspects;
   }
 
@@ -2064,17 +2050,8 @@
     return allowedRuleClassesForLabelsWarning;
   }
 
-  /**
-   * Returns the list of sets of mandatory Skylark providers.
-   */
-  public ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> getMandatoryProvidersList() {
-    return mandatoryProvidersList;
-  }
-
-  /** Returns the list of lists of mandatory native providers. */
-  public ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
-      getMandatoryNativeProvidersList() {
-    return mandatoryNativeProvidersList;
+  public RequiredProviders getRequiredProviders() {
+    return requiredProviders;
   }
 
   public FileTypeSet getAllowedFileTypesPredicate() {
@@ -2233,8 +2210,7 @@
     builder.allowedFileTypesForLabels = allowedFileTypesForLabels;
     builder.allowedRuleClassesForLabels = allowedRuleClassesForLabels;
     builder.allowedRuleClassesForLabelsWarning = allowedRuleClassesForLabelsWarning;
-    builder.mandatoryNativeProvidersList = mandatoryNativeProvidersList;
-    builder.mandatoryProvidersList = mandatoryProvidersList;
+    builder.requiredProvidersBuilder = requiredProviders.copyAsBuilder();
     builder.validityPredicate = validityPredicate;
     builder.condition = condition;
     builder.configTransition = configTransition;
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 23dc9b8..5b494b7 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
@@ -13,13 +13,14 @@
 // limitations under the License.
 package com.google.devtools.build.lib.packages;
 
-import com.google.common.base.Predicate;
-import com.google.common.base.Predicates;
+import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Preconditions;
+import java.util.function.Function;
+import java.util.function.Predicate;
+import javax.annotation.Nullable;
 
 /**
  * Represents a constraint on a set of providers required by a dependency (of a rule
@@ -52,6 +53,10 @@
    */
   private final ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> skylarkProviders;
 
+  public String getDescription() {
+    return constraint.getDescription(this);
+  }
+
   /**
    * Represents one of the constraints as desctibed in {@link RequiredProviders}
    */
@@ -59,8 +64,10 @@
     /** Accept any dependency */
     ANY {
       @Override
-      public boolean satisfies(AdvertisedProviderSet advertisedProviderSet,
-          RequiredProviders requiredProviders) {
+      public boolean satisfies(
+          AdvertisedProviderSet advertisedProviderSet,
+          RequiredProviders requiredProviders,
+          Builder missing) {
         return true;
       }
 
@@ -68,15 +75,28 @@
       public boolean satisfies(
           Predicate<Class<?>> hasNativeProvider,
           Predicate<SkylarkProviderIdentifier> hasSkylarkProvider,
-          RequiredProviders requiredProviders) {
+          RequiredProviders requiredProviders,
+          Builder missingProviders) {
         return true;
       }
+
+      @Override
+      Builder copyAsBuilder(RequiredProviders providers) {
+        return acceptAnyBuilder();
+      }
+
+      @Override
+      public String getDescription(RequiredProviders providers) {
+        return "no providers required";
+      }
     },
     /** Accept no dependency */
     NONE {
       @Override
-      public boolean satisfies(AdvertisedProviderSet advertisedProviderSet,
-          RequiredProviders requiredProviders) {
+      public boolean satisfies(
+          AdvertisedProviderSet advertisedProviderSet,
+          RequiredProviders requiredProviders,
+          Builder missing) {
         return false;
       }
 
@@ -84,56 +104,124 @@
       public boolean satisfies(
           Predicate<Class<?>> hasNativeProvider,
           Predicate<SkylarkProviderIdentifier> hasSkylarkProvider,
-          RequiredProviders requiredProviders) {
+          RequiredProviders requiredProviders,
+          Builder missingProviders) {
         return false;
       }
+
+      @Override
+      Builder copyAsBuilder(RequiredProviders providers) {
+        return acceptNoneBuilder();
+      }
+
+      @Override
+      public String getDescription(RequiredProviders providers) {
+        return "no providers accepted";
+      }
     },
+
     /** Accept a dependency that has all providers from one of the sets. */
     RESTRICTED {
       @Override
-      public boolean satisfies(Predicate<Class<?>> hasNativeProvider,
+      public boolean satisfies(
+          final AdvertisedProviderSet advertisedProviderSet,
+          RequiredProviders requiredProviders,
+          Builder missing) {
+        if (advertisedProviderSet.canHaveAnyProvider()) {
+          return true;
+        }
+        return satisfies(
+            advertisedProviderSet.getNativeProviders()::contains,
+            advertisedProviderSet.getSkylarkProviders()::contains,
+            requiredProviders,
+            missing);
+      }
+
+      @Override
+      public boolean satisfies(
+          Predicate<Class<?>> hasNativeProvider,
           Predicate<SkylarkProviderIdentifier> hasSkylarkProvider,
-          RequiredProviders requiredProviders) {
+          RequiredProviders requiredProviders,
+          Builder missingProviders) {
         for (ImmutableSet<Class<?>> nativeProviderSet : requiredProviders.nativeProviders) {
-          if (Iterables.all(nativeProviderSet, hasNativeProvider)) {
+          if (nativeProviderSet.stream().allMatch(hasNativeProvider)) {
             return true;
           }
+
+          // Collect missing providers
+          if (missingProviders != null) {
+            missingProviders.addNativeSet(
+                nativeProviderSet
+                    .stream()
+                    .filter(hasNativeProvider.negate())
+                    .collect(ImmutableSet.toImmutableSet()));
+          }
         }
 
         for (ImmutableSet<SkylarkProviderIdentifier> skylarkProviderSet
             : requiredProviders.skylarkProviders) {
-          if (Iterables.all(skylarkProviderSet, hasSkylarkProvider)) {
+          if (skylarkProviderSet.stream().allMatch(hasSkylarkProvider)) {
             return true;
           }
+          // Collect missing providers
+          if (missingProviders != null) {
+            missingProviders.addSkylarkSet(
+                skylarkProviderSet
+                    .stream()
+                    .filter(hasSkylarkProvider.negate())
+                    .collect(ImmutableSet.toImmutableSet()));
+          }
         }
         return false;
       }
+
+      @Override
+      Builder copyAsBuilder(RequiredProviders providers) {
+        Builder result = acceptAnyBuilder();
+        for (ImmutableSet<Class<?>> nativeProviderSet : providers.nativeProviders) {
+          result.addNativeSet(nativeProviderSet);
+        }
+        for (ImmutableSet<SkylarkProviderIdentifier> skylarkProviderSet :
+            providers.skylarkProviders) {
+          result.addSkylarkSet(skylarkProviderSet);
+        }
+        return result;
+      }
+
+      @Override
+      public String getDescription(RequiredProviders providers) {
+        StringBuilder result = new StringBuilder();
+        describe(result, providers.nativeProviders, Class::getSimpleName);
+        describe(result, providers.skylarkProviders, id -> "'" + id.toString() + "'");
+        return result.toString();
+      }
     };
 
     /** Checks if {@code advertisedProviderSet} satisfies these {@code RequiredProviders} */
-    public boolean satisfies(final AdvertisedProviderSet advertisedProviderSet,
-        RequiredProviders requiredProviders) {
-      if (advertisedProviderSet.canHaveAnyProvider()) {
-        return true;
-      }
-      return satisfies(
-          aClass -> advertisedProviderSet.getNativeProviders().contains(aClass),
-          Predicates.in(advertisedProviderSet.getSkylarkProviders()),
-          requiredProviders);
-    }
+    public abstract boolean satisfies(
+        AdvertisedProviderSet advertisedProviderSet,
+        RequiredProviders requiredProviders,
+        Builder missing);
 
     /**
      * Checks if a set of providers encoded by predicates {@code hasNativeProviders} and {@code
      * hasSkylarkProvider} satisfies these {@code RequiredProviders}
      */
-    abstract boolean satisfies(Predicate<Class<?>> hasNativeProvider,
+    abstract boolean satisfies(
+        Predicate<Class<?>> hasNativeProvider,
         Predicate<SkylarkProviderIdentifier> hasSkylarkProvider,
-        RequiredProviders requiredProviders);
+        RequiredProviders requiredProviders,
+        @Nullable Builder missingProviders);
+
+    abstract Builder copyAsBuilder(RequiredProviders providers);
+
+    /** Returns a string describing the providers that can be presented to the user. */
+    abstract String getDescription(RequiredProviders providers);
   }
 
   /** Checks if {@code advertisedProviderSet} satisfies this {@code RequiredProviders} instance. */
   public boolean isSatisfiedBy(AdvertisedProviderSet advertisedProviderSet) {
-    return constraint.satisfies(advertisedProviderSet, this);
+    return constraint.satisfies(advertisedProviderSet, this, null);
   }
 
   /**
@@ -143,7 +231,40 @@
   public boolean isSatisfiedBy(
       Predicate<Class<?>> hasNativeProvider,
       Predicate<SkylarkProviderIdentifier> hasSkylarkProvider) {
-    return constraint.satisfies(hasNativeProvider, hasSkylarkProvider, this);
+    return constraint.satisfies(hasNativeProvider, hasSkylarkProvider, this, null);
+  }
+
+  /**
+   * Returns providers that are missing. If none are missing, returns {@code RequiredProviders} that
+   * accept anything.
+   */
+  public RequiredProviders getMissing(
+      Predicate<Class<?>> hasNativeProvider,
+      Predicate<SkylarkProviderIdentifier> hasSkylarkProvider) {
+    Builder builder = acceptAnyBuilder();
+    if (constraint.satisfies(hasNativeProvider, hasSkylarkProvider, this, builder)) {
+      // Ignore all collected missing providers.
+      return acceptAnyBuilder().build();
+    }
+    return builder.build();
+  }
+
+  /**
+   * Returns providers that are missing. If none are missing, returns {@code RequiredProviders} that
+   * accept anything.
+   */
+  public RequiredProviders getMissing(AdvertisedProviderSet set) {
+    Builder builder = acceptAnyBuilder();
+    if (constraint.satisfies(set, this, builder)) {
+      // Ignore all collected missing providers.
+      return acceptAnyBuilder().build();
+    }
+    return builder.build();
+  }
+
+  /** Returns true if this {@code RequiredProviders} instance accept any set of providers. */
+  public boolean acceptsAny() {
+    return constraint.equals(Constraint.ANY);
   }
 
 
@@ -161,6 +282,22 @@
     this.skylarkProviders = skylarkProviders;
   }
 
+  /** Helper method to describe lists of sets of things. */
+  private static <T> void describe(
+      StringBuilder result,
+      ImmutableList<ImmutableSet<T>> listOfSets,
+      Function<T, String> describeOne) {
+    Joiner joiner = Joiner.on(", ");
+    for (ImmutableSet<T> ids : listOfSets) {
+      if (result.length() > 0) {
+        result.append(" or ");
+      }
+      result.append((ids.size() > 1) ? "[" : "");
+      joiner.appendTo(result, ids.stream().map(describeOne).iterator());
+      result.append((ids.size() > 1) ? "]" : "");
+    }
+  }
+
   /**
    * A builder for {@link RequiredProviders} that accepts any dependency
    * unless restriction provider sets are added.
@@ -177,6 +314,11 @@
     return new Builder(true);
   }
 
+  /** Returns a Builder initialized to the same value as this {@code RequiredProvider} */
+  public Builder copyAsBuilder() {
+    return constraint.copyAsBuilder(this);
+  }
+
   /** A builder for {@link RequiredProviders} */
   public static class Builder {
     private final ImmutableList.Builder<ImmutableSet<Class<?>>> nativeProviders;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
index d3a2110..1951610 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
@@ -276,7 +276,11 @@
       SkylarkType.checkType(obj, SkylarkList.class, PROVIDERS_ARG);
       ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> providersList = buildProviderPredicate(
           (SkylarkList<?>) obj, PROVIDERS_ARG, ast.getLocation());
-      builder.mandatoryProvidersList(providersList);
+
+      // If there is at least one empty set, there is no restriction.
+      if (providersList.stream().noneMatch(ImmutableSet::isEmpty)) {
+        builder.mandatoryProvidersList(providersList);
+      }
     }
 
     if (containsNonNoneKey(arguments, CONFIGURATION_ARG)) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index aa960a8..1b783b9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -15,7 +15,6 @@
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Joiner;
-import com.google.common.base.Predicate;
 import com.google.common.base.Supplier;
 import com.google.common.base.Verify;
 import com.google.common.base.VerifyException;
@@ -43,7 +42,6 @@
 import com.google.devtools.build.lib.analysis.MergedConfiguredTarget.DuplicateException;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
-import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
@@ -67,7 +65,6 @@
 import com.google.devtools.build.lib.packages.RawAttributeMapper;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
-import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.skyframe.AspectFunction.AspectCreationException;
@@ -988,20 +985,7 @@
     if (!aspect.getDefinition().applyToFiles() && !(dep.getTarget() instanceof Rule)) {
       return false;
     }
-    return aspect.getDefinition().getRequiredProviders().isSatisfiedBy(
-        new Predicate<Class<?>>() {
-          @Override
-          public boolean apply(Class<?> provider) {
-            return dep.getProvider(provider.asSubclass(TransitiveInfoProvider.class)) != null;
-          }
-        },
-        new Predicate<SkylarkProviderIdentifier>() {
-          @Override
-          public boolean apply(SkylarkProviderIdentifier skylarkProviderIdentifier) {
-            return dep.get(skylarkProviderIdentifier) != null;
-          }
-        }
-    );
+    return dep.satisfies(aspect.getDefinition().getRequiredProviders());
   }
 
   /**
diff --git a/src/test/java/com/google/devtools/build/lib/packages/RequiredProvidersTest.java b/src/test/java/com/google/devtools/build/lib/packages/RequiredProvidersTest.java
index e86cc41..489303f 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/RequiredProvidersTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/RequiredProvidersTest.java
@@ -16,7 +16,6 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
-import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
@@ -31,6 +30,9 @@
  */
 @RunWith(JUnit4.class)
 public class RequiredProvidersTest {
+
+  private static final String NO_PROVIDERS_REQUIRED = "no providers required";
+
   private static final class P1 {}
   private static final class P2 {}
   private static final class P3 {}
@@ -59,10 +61,11 @@
       RequiredProviders requiredProviders) {
     boolean result = requiredProviders.isSatisfiedBy(providers);
 
-    assertThat(requiredProviders.isSatisfiedBy(
-        Predicates.in(providers.getNativeProviders()),
-        Predicates.in(providers.getSkylarkProviders())
-    )).isEqualTo(result);
+    assertThat(
+            requiredProviders.isSatisfiedBy(
+                providers.getNativeProviders()::contains,
+                providers.getSkylarkProviders()::contains))
+        .isEqualTo(result);
     return result;
   }
 
@@ -108,32 +111,31 @@
         .addNative(P1.class)
         .addNative(P2.class)
         .build();
-    assertThat(validateNative(providerSet, ImmutableSet.<Class<?>>of(P1.class, P2.class)))
+    assertThat(
+            validateNative(providerSet, NO_PROVIDERS_REQUIRED, ImmutableSet.of(P1.class, P2.class)))
         .isTrue();
   }
 
   @Test
   public void nativeProvidersBranchMatch() {
     assertThat(
-        validateNative(
-          AdvertisedProviderSet.builder()
-              .addNative(P1.class)
-              .build(),
-          ImmutableSet.<Class<?>>of(P1.class),
-          ImmutableSet.<Class<?>>of(P2.class)
-        )).isTrue();
+            validateNative(
+                AdvertisedProviderSet.builder().addNative(P1.class).build(),
+                NO_PROVIDERS_REQUIRED,
+                ImmutableSet.<Class<?>>of(P1.class),
+                ImmutableSet.<Class<?>>of(P2.class)))
+        .isTrue();
   }
 
   @Test
   public void nativeProvidersNoMatch() {
     assertThat(
-        validateNative(
-            AdvertisedProviderSet.builder()
-                .addNative(P3.class)
-                .build(),
-            ImmutableSet.<Class<?>>of(P1.class),
-            ImmutableSet.<Class<?>>of(P2.class)
-        )).isFalse();
+            validateNative(
+                AdvertisedProviderSet.builder().addNative(P3.class).build(),
+                "P1 or P2",
+                ImmutableSet.<Class<?>>of(P1.class),
+                ImmutableSet.<Class<?>>of(P2.class)))
+        .isFalse();
   }
 
   @Test
@@ -143,53 +145,75 @@
         .addSkylark(ID_NATIVE)
         .addSkylark(ID_SKYLARK)
         .build();
-    assertThat(validateSkylark(providerSet,
-        ImmutableSet.of(
-            ID_LEGACY, ID_SKYLARK, ID_NATIVE)))
+    assertThat(
+            validateSkylark(
+                providerSet,
+                NO_PROVIDERS_REQUIRED,
+                ImmutableSet.of(ID_LEGACY, ID_SKYLARK, ID_NATIVE)))
         .isTrue();
   }
 
   @Test
   public void skylarkProvidersBranchMatch() {
     assertThat(
-        validateSkylark(
-            AdvertisedProviderSet.builder()
-                .addSkylark(ID_LEGACY)
-                .build(),
-            ImmutableSet.of(ID_LEGACY),
-            ImmutableSet.of(ID_NATIVE)
-        )).isTrue();
+            validateSkylark(
+                AdvertisedProviderSet.builder().addSkylark(ID_LEGACY).build(),
+                NO_PROVIDERS_REQUIRED,
+                ImmutableSet.of(ID_LEGACY),
+                ImmutableSet.of(ID_NATIVE)))
+        .isTrue();
   }
 
   @Test
   public void skylarkProvidersNoMatch() {
     assertThat(
-        validateSkylark(
-            AdvertisedProviderSet.builder()
-                .addSkylark(ID_SKYLARK)
-                .build(),
-            ImmutableSet.of(ID_LEGACY),
-            ImmutableSet.of(ID_NATIVE)
-        )).isFalse();
+            validateSkylark(
+                AdvertisedProviderSet.builder().addSkylark(ID_SKYLARK).build(),
+                "'p_legacy' or 'p_native'",
+                ImmutableSet.of(ID_LEGACY),
+                ImmutableSet.of(ID_NATIVE)))
+        .isFalse();
+  }
+
+  @Test
+  public void checkDescriptions() {
+    assertThat(RequiredProviders.acceptAnyBuilder().build().getDescription())
+        .isEqualTo("no providers required");
+    assertThat(RequiredProviders.acceptNoneBuilder().build().getDescription())
+        .isEqualTo("no providers accepted");
+    assertThat(
+            RequiredProviders.acceptAnyBuilder()
+                .addSkylarkSet(ImmutableSet.of(ID_LEGACY, ID_SKYLARK))
+                .addSkylarkSet(ImmutableSet.of(ID_SKYLARK))
+                .addNativeSet(ImmutableSet.of(P1.class, P2.class))
+                .build()
+                .getDescription())
+        .isEqualTo("[P1, P2] or ['p_legacy', 'p_skylark'] or 'p_skylark'");
   }
 
   @SafeVarargs
-  private static boolean validateNative(AdvertisedProviderSet providerSet,
-      ImmutableSet<Class<?>>... sets) {
+  private static boolean validateNative(
+      AdvertisedProviderSet providerSet, String missing, ImmutableSet<Class<?>>... sets) {
     Builder anyBuilder = RequiredProviders.acceptAnyBuilder();
     Builder noneBuilder = RequiredProviders.acceptNoneBuilder();
     for (ImmutableSet<Class<?>> set : sets) {
       anyBuilder.addNativeSet(set);
       noneBuilder.addNativeSet(set);
     }
-    boolean result = satisfies(providerSet, anyBuilder.build());
-    assertThat(satisfies(providerSet, noneBuilder.build())).isEqualTo(result);
+    RequiredProviders rpStartingFromAny = anyBuilder.build();
+    boolean result = satisfies(providerSet, rpStartingFromAny);
+    assertThat(rpStartingFromAny.getMissing(providerSet).getDescription()).isEqualTo(missing);
+
+    RequiredProviders rpStaringFromNone = noneBuilder.build();
+    assertThat(satisfies(providerSet, rpStaringFromNone)).isEqualTo(result);
+    assertThat(rpStaringFromNone.getMissing(providerSet).getDescription()).isEqualTo(missing);
     return result;
   }
 
   @SafeVarargs
   private static boolean validateSkylark(
       AdvertisedProviderSet providerSet,
+      String missing,
       ImmutableSet<SkylarkProviderIdentifier>... sets) {
     Builder anyBuilder = RequiredProviders.acceptAnyBuilder();
     Builder noneBuilder = RequiredProviders.acceptNoneBuilder();
@@ -197,8 +221,14 @@
       anyBuilder.addSkylarkSet(set);
       noneBuilder.addSkylarkSet(set);
     }
-    boolean result = satisfies(providerSet, anyBuilder.build());
-    assertThat(satisfies(providerSet, noneBuilder.build())).isEqualTo(result);
+
+    RequiredProviders rpStartingFromAny = anyBuilder.build();
+    boolean result = satisfies(providerSet, rpStartingFromAny);
+    assertThat(rpStartingFromAny.getMissing(providerSet).getDescription()).isEqualTo(missing);
+
+    RequiredProviders rpStaringFromNone = noneBuilder.build();
+    assertThat(satisfies(providerSet, rpStaringFromNone)).isEqualTo(result);
+    assertThat(rpStaringFromNone.getMissing(providerSet).getDescription()).isEqualTo(missing);
     return result;
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
index b346a60..71e084d 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
@@ -711,7 +711,7 @@
         "main_rule = rule(implementation = rule_impl, attrs = {",
         "    'deps': attr.label_list(providers = [",
         "        'files', 'data_runfiles', 'default_runfiles',",
-        "        'files_to_run', 'label', 'output_groups',",
+        "        'files_to_run', 'output_groups',",
         "    ])",
         "})");
     scratch.file(
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
index 5c32321..c212605 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
@@ -249,8 +249,18 @@
         buildAttribute("a1",
             "b = provider()",
             "attr.label_list(allow_files = True, providers = ['a', b])");
-    assertThat(attr.getMandatoryProvidersList())
-        .containsExactly(ImmutableSet.of(legacy("a"), declared("b")));
+    assertThat(attr.getRequiredProviders().isSatisfiedBy(set(legacy("a"), declared("b")))).isTrue();
+    assertThat(attr.getRequiredProviders().isSatisfiedBy(set(legacy("a")))).isFalse();
+  }
+
+  @Test
+  public void testAttrWithProvidersOneEmpty() throws Exception {
+    Attribute attr =
+        buildAttribute(
+            "a1",
+            "b = provider()",
+            "attr.label_list(allow_files = True, providers = [['a', b],[]])");
+    assertThat(attr.getRequiredProviders().acceptsAny()).isTrue();
   }
 
   @Test
@@ -259,9 +269,17 @@
         buildAttribute("a1",
             "b = provider()",
             "attr.label_list(allow_files = True, providers = [['a', b], ['c']])");
-    assertThat(attr.getMandatoryProvidersList()).containsExactly(
-        ImmutableSet.of(legacy("a"), declared("b")),
-        ImmutableSet.of(legacy("c")));
+    assertThat(attr.getRequiredProviders().isSatisfiedBy(set(legacy("a"), declared("b")))).isTrue();
+    assertThat(attr.getRequiredProviders().isSatisfiedBy(set(legacy("c")))).isTrue();
+    assertThat(attr.getRequiredProviders().isSatisfiedBy(set(legacy("a")))).isFalse();
+  }
+
+  private static AdvertisedProviderSet set(SkylarkProviderIdentifier... ids) {
+    AdvertisedProviderSet.Builder builder = AdvertisedProviderSet.builder();
+    for (SkylarkProviderIdentifier id : ids) {
+      builder.addSkylark(id);
+    }
+    return builder.build();
   }
 
   private void checkAttributeError(String expectedMessage, String... lines) throws Exception {
@@ -425,12 +443,9 @@
 
   private static final RuleClass.ConfiguredTargetFactory<Object, Object>
       DUMMY_CONFIGURED_TARGET_FACTORY =
-      new RuleClass.ConfiguredTargetFactory<Object, Object>() {
-        @Override
-        public Object create(Object ruleContext) throws InterruptedException {
-          throw new IllegalStateException();
-        }
-      };
+          ruleContext -> {
+            throw new IllegalStateException();
+          };
 
   private RuleClass ruleClass(String name) {
     return new RuleClass.Builder(name, RuleClassType.NORMAL, false)