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 235dc37..deee99a 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,6 +104,12 @@
   @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:
@@ -199,18 +205,7 @@
     if (OutputGroupProvider.SKYLARK_NAME.equals(providerKey)) {
       return get(OutputGroupProvider.SKYLARK_CONSTRUCTOR);
     }
-    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);
-    }
+    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 de978e0..771189a 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,17 +70,18 @@
 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;
@@ -1974,101 +1975,154 @@
       }
     }
 
-    /**
-     * 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) {
-
-      Set<String> unfulfilledRequirements = new LinkedHashSet<>();
-      if (checkRuleDependencyClass(prerequisite, attribute, unfulfilledRequirements)) {
-        return;
+    private String getMissingMandatoryProviders(ConfiguredTarget prerequisite, Attribute attribute){
+      ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList =
+          attribute.getMandatoryProvidersList();
+      if (mandatoryProvidersList.isEmpty()) {
+        return null;
       }
-
-      if (checkRuleDependencyClassWarnings(prerequisite, attribute)) {
-        return;
+      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);
+        }
       }
-
-      if (checkRuleDependencyMandatoryProviders(prerequisite, attribute, unfulfilledRequirements)) {
-        return;
+      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) ? "]" : "");
       }
-
-      // not allowed rule class and some mandatory providers missing => reject.
-      if (!unfulfilledRequirements.isEmpty()) {
-        attributeError(
-            attribute.getName(), StringUtil.joinEnglishList(unfulfilledRequirements, "and"));
-      }
+      return missingProviders.toString();
     }
 
-    /** Check if prerequisite should be allowed based on its rule class. */
-    private boolean checkRuleDependencyClass(
-        ConfiguredTarget prerequisite, Attribute attribute, Set<String> unfulfilledRequirements) {
+    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.
+     */
+    private void validateRuleDependency(ConfiguredTarget prerequisite, Attribute attribute) {
+      Target prerequisiteTarget = prerequisite.getTarget();
+      RuleClass ruleClass = ((Rule) prerequisiteTarget).getRuleClassObject();
+      String notAllowedRuleClassesMessage = null;
+
       if (attribute.getAllowedRuleClassesPredicate() != Predicates.<RuleClass>alwaysTrue()) {
-        if (attribute
-            .getAllowedRuleClassesPredicate()
-            .apply(((Rule) prerequisite.getTarget()).getRuleClassObject())) {
+        if (attribute.getAllowedRuleClassesPredicate().apply(ruleClass)) {
           // prerequisite has an allowed rule class => accept.
-          return true;
+          return;
         }
         // remember that the rule class that was not allowed;
         // but maybe prerequisite provides required providers? do not reject yet.
-        unfulfilledRequirements.add(
+        notAllowedRuleClassesMessage =
             badPrerequisiteMessage(
-                prerequisite.getTarget().getTargetKind(),
+                prerequisiteTarget.getTargetKind(),
                 prerequisite,
                 "expected " + attribute.getAllowedRuleClassesPredicate(),
-                false));
+                false);
       }
-      return false;
-    }
 
-    /**
-     * 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())) {
+      if (attribute.getAllowedRuleClassesWarningPredicate().apply(ruleClass)) {
         Predicate<RuleClass> allowedRuleClasses = attribute.getAllowedRuleClassesPredicate();
-        reportBadPrerequisite(
-            attribute,
-            prerequisite.getTarget().getTargetKind(),
-            prerequisite,
+        reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisite,
             allowedRuleClasses == Predicates.<RuleClass>alwaysTrue()
                 ? null
                 : "expected " + allowedRuleClasses,
             true);
         // prerequisite has a rule class allowed with a warning => accept, emitting a warning.
-        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;
+        return;
       }
 
-      if (prerequisite.satisfies(requiredProviders)) {
-        return true;
+      // 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;
+        }
       }
 
-      unfulfilledRequirements.add(
-          String.format(
-              "'%s' does not have mandatory providers: %s",
-              prerequisite.getLabel(),
-              prerequisite.missingProviders(requiredProviders).getDescription()));
+      // not allowed rule class and some mandatory providers missing => reject.
+      if (notAllowedRuleClassesMessage != null) {
+        unfulfilledRequirements.add(notAllowedRuleClassesMessage);
+      }
 
-      return false;
+      if (!unfulfilledRequirements.isEmpty()) {
+        attributeError(
+            attribute.getName(), StringUtil.joinEnglishList(unfulfilledRequirements, "and"));
+      }
     }
 
     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 b3b4894..b174a47 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,7 +16,6 @@
 
 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;
@@ -80,25 +79,4 @@
    * <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 f1d7dff..bb2456c 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,14 +14,16 @@
 
 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;
@@ -75,10 +77,15 @@
     }
 
     if (prerequisiteTarget instanceof PackageGroup) {
-      RequiredProviders requiredProviders =
-          RawAttributeMapper.of(rule).getAttributeDefinition(attrName).getRequiredProviders();
+      ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
+          mandatoryNativeProviders =
+              RawAttributeMapper.of(rule)
+                  .getAttributeDefinition(attrName)
+                  .getMandatoryNativeProvidersList();
       boolean containsPackageSpecificationProvider =
-          requiredProviders.getDescription().contains("PackageSpecificationProvider");
+          mandatoryNativeProviders
+              .stream()
+              .anyMatch(list -> list.contains(PackageSpecificationProvider.class));
       // 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 bd36056..bcf6341 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,8 +457,10 @@
     private Predicate<AttributeMap> condition;
     private Set<PropertyFlag> propertyFlags = EnumSet.noneOf(PropertyFlag.class);
     private PredicateWithMessage<Object> allowedValues = null;
-    private RequiredProviders.Builder requiredProvidersBuilder =
-        RequiredProviders.acceptAnyBuilder();
+    private ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList =
+        ImmutableList.<ImmutableSet<SkylarkProviderIdentifier>>of();
+    private ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
+        mandatoryNativeProvidersList = ImmutableList.of();
     private HashMap<String, RuleAspect<?>> aspects = new LinkedHashMap<>();
 
     /**
@@ -954,11 +956,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 #getRequiredProviders()}}, the build continues
-     * without error. Else the build fails during analysis.
+     * allowedRuleClasses()) and they fulfill {@link #getMandatoryNativeProvidersList()}}, 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 #getRequiredProviders()} build without error.
+     * <p>If neither this nor {@link #allowedRuleClassesForLabels} is set, only rules that
+     * fulfill {@link #getMandatoryNativeProvidersList()} 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.
@@ -976,10 +978,12 @@
         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) {
-        this.requiredProvidersBuilder.addNativeSet(ImmutableSet.copyOf(providers));
+        listBuilder.add(ImmutableList.<Class<? extends TransitiveInfoProvider>>copyOf(providers));
       }
+      this.mandatoryNativeProvidersList = listBuilder.build();
       return this;
     }
 
@@ -1001,9 +1005,12 @@
         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) {
-        this.requiredProvidersBuilder.addSkylarkSet(ImmutableSet.copyOf(providers));
+        listBuilder.add(ImmutableSet.copyOf(providers));
       }
+      this.mandatoryProvidersList = listBuilder.build();
       return this;
     }
 
@@ -1174,7 +1181,8 @@
           validityPredicate,
           condition,
           allowedValues,
-          requiredProvidersBuilder.build(),
+          mandatoryProvidersList,
+          mandatoryNativeProvidersList,
           ImmutableList.copyOf(aspects.values()));
     }
   }
@@ -1787,7 +1795,10 @@
 
   private final PredicateWithMessage<Object> allowedValues;
 
-  private final RequiredProviders requiredProviders;
+  private final ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList;
+
+  private final ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
+      mandatoryNativeProvidersList;
 
   private final ImmutableList<RuleAspect<?>> aspects;
 
@@ -1817,7 +1828,9 @@
       ValidityPredicate validityPredicate,
       Predicate<AttributeMap> condition,
       PredicateWithMessage<Object> allowedValues,
-      RequiredProviders requiredProviders,
+      ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> mandatoryProvidersList,
+      ImmutableList<ImmutableList<Class<? extends TransitiveInfoProvider>>>
+          mandatoryNativeProvidersList,
       ImmutableList<RuleAspect<?>> aspects) {
     Preconditions.checkNotNull(configTransition);
     Preconditions.checkArgument(
@@ -1851,7 +1864,8 @@
     this.validityPredicate = validityPredicate;
     this.condition = condition;
     this.allowedValues = allowedValues;
-    this.requiredProviders = requiredProviders;
+    this.mandatoryProvidersList = mandatoryProvidersList;
+    this.mandatoryNativeProvidersList = mandatoryNativeProvidersList;
     this.aspects = aspects;
   }
 
@@ -2050,8 +2064,17 @@
     return allowedRuleClassesForLabelsWarning;
   }
 
-  public RequiredProviders getRequiredProviders() {
-    return requiredProviders;
+  /**
+   * 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 FileTypeSet getAllowedFileTypesPredicate() {
@@ -2210,7 +2233,8 @@
     builder.allowedFileTypesForLabels = allowedFileTypesForLabels;
     builder.allowedRuleClassesForLabels = allowedRuleClassesForLabels;
     builder.allowedRuleClassesForLabelsWarning = allowedRuleClassesForLabelsWarning;
-    builder.requiredProvidersBuilder = requiredProviders.copyAsBuilder();
+    builder.mandatoryNativeProvidersList = mandatoryNativeProvidersList;
+    builder.mandatoryProvidersList = mandatoryProvidersList;
     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 5b494b7..23dc9b8 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,14 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.lib.packages;
 
-import com.google.common.base.Joiner;
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
 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
@@ -53,10 +52,6 @@
    */
   private final ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> skylarkProviders;
 
-  public String getDescription() {
-    return constraint.getDescription(this);
-  }
-
   /**
    * Represents one of the constraints as desctibed in {@link RequiredProviders}
    */
@@ -64,10 +59,8 @@
     /** Accept any dependency */
     ANY {
       @Override
-      public boolean satisfies(
-          AdvertisedProviderSet advertisedProviderSet,
-          RequiredProviders requiredProviders,
-          Builder missing) {
+      public boolean satisfies(AdvertisedProviderSet advertisedProviderSet,
+          RequiredProviders requiredProviders) {
         return true;
       }
 
@@ -75,28 +68,15 @@
       public boolean satisfies(
           Predicate<Class<?>> hasNativeProvider,
           Predicate<SkylarkProviderIdentifier> hasSkylarkProvider,
-          RequiredProviders requiredProviders,
-          Builder missingProviders) {
+          RequiredProviders requiredProviders) {
         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,
-          Builder missing) {
+      public boolean satisfies(AdvertisedProviderSet advertisedProviderSet,
+          RequiredProviders requiredProviders) {
         return false;
       }
 
@@ -104,124 +84,56 @@
       public boolean satisfies(
           Predicate<Class<?>> hasNativeProvider,
           Predicate<SkylarkProviderIdentifier> hasSkylarkProvider,
-          RequiredProviders requiredProviders,
-          Builder missingProviders) {
+          RequiredProviders requiredProviders) {
         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(
-          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,
+      public boolean satisfies(Predicate<Class<?>> hasNativeProvider,
           Predicate<SkylarkProviderIdentifier> hasSkylarkProvider,
-          RequiredProviders requiredProviders,
-          Builder missingProviders) {
+          RequiredProviders requiredProviders) {
         for (ImmutableSet<Class<?>> nativeProviderSet : requiredProviders.nativeProviders) {
-          if (nativeProviderSet.stream().allMatch(hasNativeProvider)) {
+          if (Iterables.all(nativeProviderSet, 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 (skylarkProviderSet.stream().allMatch(hasSkylarkProvider)) {
+          if (Iterables.all(skylarkProviderSet, 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 abstract boolean satisfies(
-        AdvertisedProviderSet advertisedProviderSet,
-        RequiredProviders requiredProviders,
-        Builder missing);
+    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);
+    }
 
     /**
      * 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,
-        @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);
+        RequiredProviders requiredProviders);
   }
 
   /** Checks if {@code advertisedProviderSet} satisfies this {@code RequiredProviders} instance. */
   public boolean isSatisfiedBy(AdvertisedProviderSet advertisedProviderSet) {
-    return constraint.satisfies(advertisedProviderSet, this, null);
+    return constraint.satisfies(advertisedProviderSet, this);
   }
 
   /**
@@ -231,40 +143,7 @@
   public boolean isSatisfiedBy(
       Predicate<Class<?>> hasNativeProvider,
       Predicate<SkylarkProviderIdentifier> hasSkylarkProvider) {
-    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);
+    return constraint.satisfies(hasNativeProvider, hasSkylarkProvider, this);
   }
 
 
@@ -282,22 +161,6 @@
     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.
@@ -314,11 +177,6 @@
     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 1951610..d3a2110 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,11 +276,7 @@
       SkylarkType.checkType(obj, SkylarkList.class, PROVIDERS_ARG);
       ImmutableList<ImmutableSet<SkylarkProviderIdentifier>> providersList = buildProviderPredicate(
           (SkylarkList<?>) obj, PROVIDERS_ARG, ast.getLocation());
-
-      // If there is at least one empty set, there is no restriction.
-      if (providersList.stream().noneMatch(ImmutableSet::isEmpty)) {
-        builder.mandatoryProvidersList(providersList);
-      }
+      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 1b783b9..aa960a8 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,6 +15,7 @@
 
 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;
@@ -42,6 +43,7 @@
 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;
@@ -65,6 +67,7 @@
 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;
@@ -985,7 +988,20 @@
     if (!aspect.getDefinition().applyToFiles() && !(dep.getTarget() instanceof Rule)) {
       return false;
     }
-    return dep.satisfies(aspect.getDefinition().getRequiredProviders());
+    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;
+          }
+        }
+    );
   }
 
   /**