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 8965cb5..b429606 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
@@ -77,6 +77,7 @@
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.FileTypeSet;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
@@ -1613,19 +1614,28 @@
       reporter.attributeWarning(attrName, message);
     }
 
-    private void reportBadPrerequisite(Attribute attribute, String targetKind,
-        ConfiguredTarget prerequisite, String reason, boolean isWarning) {
+    private String badPrerequisiteMessage(String targetKind, ConfiguredTarget prerequisite,
+        String reason, boolean isWarning) {
       String msgPrefix = targetKind != null ? targetKind + " " : "";
       String msgReason = reason != null ? " (" + reason + ")" : "";
       if (isWarning) {
-        attributeWarning(attribute.getName(), String.format(
+        return String.format(
             "%s'%s'%s is unexpected here%s; continuing anyway",
             msgPrefix, prerequisite.getLabel(), AliasProvider.printVisibilityChain(prerequisite),
-            msgReason));
+            msgReason);
+      }
+      return String.format(
+          "%s'%s'%s is misplaced here%s", msgPrefix, prerequisite.getLabel(),
+          AliasProvider.printVisibilityChain(prerequisite), msgReason);
+    }
+
+    private void reportBadPrerequisite(Attribute attribute, String targetKind,
+        ConfiguredTarget prerequisite, String reason, boolean isWarning) {
+      String message = badPrerequisiteMessage(targetKind, prerequisite, reason, isWarning);
+      if (isWarning) {
+        attributeWarning(attribute.getName(), message);
       } else {
-        attributeError(attribute.getName(), String.format(
-            "%s'%s'%s is misplaced here%s", msgPrefix, prerequisite.getLabel(),
-            AliasProvider.printVisibilityChain(prerequisite), msgReason));
+        attributeError(attribute.getName(), message);
       }
     }
 
@@ -1803,19 +1813,20 @@
 
     /**
      * Because some rules still have to use allowedRuleClasses to do rule dependency validation.
-     * We implemented the allowedRuleClasses OR mandatoryProvidersList mechanism. Either condition
-     * is satisfied, we consider the dependency valid.
+     * A dependency is valid if it is from a rule in allowedRuledClasses, 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();
-      Boolean allowed = null;
+      HashSet<String> unfulfilledRequirements = new HashSet<>();
 
       if (attribute.getAllowedRuleClassesPredicate() != Predicates.<RuleClass>alwaysTrue()) {
-        allowed = attribute.getAllowedRuleClassesPredicate().apply(ruleClass);
-        if (allowed) {
+        if (attribute.getAllowedRuleClassesPredicate().apply(ruleClass)) {
           return;
         }
+        unfulfilledRequirements.add(badPrerequisiteMessage(prerequisiteTarget.getTargetKind(),
+            prerequisite, "expected " + attribute.getAllowedRuleClassesPredicate(), false));
       }
 
       if (attribute.getAllowedRuleClassesWarningPredicate()
@@ -1828,27 +1839,38 @@
         }
       }
 
-      if (!attribute.getMandatoryNativeProviders().isEmpty()) {
-        String missing = getMissingMandatoryNativeProviders(prerequisite, attribute);
-        if (missing != null) {
-          attributeError(
-              attribute.getName(),
-              "'" + prerequisite.getLabel() + "' does not have mandatory providers: " + missing);
+      // This condition is required; getMissingMandatory[Native]Providers() would be vacuously true
+      // if no providers were mandatory (thus, none are missing), which would cause an early return
+      // below without emitting the error message about the not-allowed rule class if that
+      // requirement was unfulfilled.
+      if (!attribute.getMandatoryNativeProviders().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 provider "
+                  + missingProviders);
+          hadAllMandatoryProviders = false;
+        }
+
+        if (hadAllMandatoryProviders) {
           return;
         }
       }
 
-      if (!attribute.getMandatoryProvidersList().isEmpty()) {
-        String missingMandatoryProviders = getMissingMandatoryProviders(prerequisite, attribute);
-        if (missingMandatoryProviders != null) {
-          attributeError(
-              attribute.getName(),
-              "'" + prerequisite.getLabel() + "' does not have mandatory provider "
-                  + missingMandatoryProviders);
-        }
-      } else if (Boolean.FALSE.equals(allowed)) {
-        reportBadPrerequisite(attribute, prerequisiteTarget.getTargetKind(), prerequisite,
-            "expected " + attribute.getAllowedRuleClassesPredicate(), false);
+      if (!unfulfilledRequirements.isEmpty()) {
+        attributeError(
+            attribute.getName(), StringUtil.joinEnglishList(unfulfilledRequirements, "and"));
       }
     }
 
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 2ac4851..c53b92a 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
@@ -1706,6 +1706,8 @@
     builder.allowedFileTypesForLabels = allowedFileTypesForLabels;
     builder.allowedRuleClassesForLabels = allowedRuleClassesForLabels;
     builder.allowedRuleClassesForLabelsWarning = allowedRuleClassesForLabelsWarning;
+    builder.mandatoryNativeProviders = mandatoryNativeProviders;
+    builder.mandatoryProvidersList = mandatoryProvidersList;
     builder.validityPredicate = validityPredicate;
     builder.condition = condition;
     builder.configTransition = configTransition;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java
index 81c8d9b..e499a3b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcRuleClasses.java
@@ -682,15 +682,8 @@
      */
     static final Iterable<String> ALLOWED_DEPS_RULE_CLASSES =
         ImmutableSet.of(
-            "objc_library",
-            "objc_import",
-            "objc_framework",
-            "objc_proto_library",
-            "j2objc_library",
             "cc_library",
             "cc_inc_library",
-            "ios_framework",
-            "swift_library",
             "experimental_objc_library");
 
     @Override
@@ -736,6 +729,7 @@
               attr("deps", LABEL_LIST)
                   .direct_compile_time_input()
                   .allowedRuleClasses(ALLOWED_DEPS_RULE_CLASSES)
+                  .mandatoryNativeProviders(ObjcProvider.class)
                   .allowedFileTypes())
           /* <!-- #BLAZE_RULE($objc_compiling_rule).ATTRIBUTE(runtime_deps) -->
           The list of framework targets that are late loaded at runtime.  They are included in the
@@ -758,6 +752,7 @@
               attr("non_propagated_deps", LABEL_LIST)
                   .direct_compile_time_input()
                   .allowedRuleClasses(ALLOWED_DEPS_RULE_CLASSES)
+                  .mandatoryNativeProviders(ObjcProvider.class)
                   .allowedFileTypes())
           /* <!-- #BLAZE_RULE($objc_compiling_rule).ATTRIBUTE(defines) -->
            Extra <code>-D</code> flags to pass to the compiler. They should be in