diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index 8afcbb7..1a52b5e 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -241,7 +241,7 @@
 
   private void readObject(ObjectInputStream in) throws IOException {
     try {
-      deserializedPkg = new PackageDeserializer(null, null).deserialize(in);
+      deserializedPkg = new PackageDeserializer().deserialize(in);
     } catch (PackageDeserializationException e) {
       throw new IllegalStateException(e);
     }
@@ -450,7 +450,7 @@
    * though not necessarily: data in a subdirectory of a test package may use a
    * different filename to avoid inadvertently creating a new package.
    */
-  Label getBuildFileLabel() {
+  public Label getBuildFileLabel() {
     return buildFile.getLabel();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageDeserializer.java b/src/main/java/com/google/devtools/build/lib/packages/PackageDeserializer.java
index e4bc250..d5a612e 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageDeserializer.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageDeserializer.java
@@ -34,7 +34,6 @@
 import com.google.devtools.build.lib.syntax.GlobList;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
-import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
@@ -55,11 +54,23 @@
 
   private static final Logger LOG = Logger.getLogger(PackageDeserializer.class.getName());
 
-  // Workaround for Java serialization not allowing to pass in a context manually.
+  /**
+   * Provides the deserializer with tools it needs to build a package from its serialized form.
+   */
+  public interface PackageDeserializationEnvironment {
+
+    /** Converts the serialized package's path string into a {@link Path} object. */
+    Path getPath(String buildFilePath);
+
+    /** Returns a {@link RuleClass} object for the serialized rule. */
+    RuleClass getRuleClass(Build.Rule rulePb, Location ruleLocation);
+  }
+
+  // Workaround for Java serialization making it tough to pass in a deserialization environment
+  // manually.
   // volatile is needed to ensure that the objects are published safely.
-  // TODO(bazel-team): Subclass ObjectOutputStream to pass through environment variables.
-  public static volatile RuleClassProvider defaultRuleClassProvider;
-  public static volatile FileSystem defaultDeserializerFileSystem;
+  // TODO(bazel-team): Subclass ObjectOutputStream to pass this through instead.
+  public static volatile PackageDeserializationEnvironment defaultPackageDeserializationEnvironment;
 
   private class Context {
     private final Package.Builder packageBuilder;
@@ -120,15 +131,9 @@
       }
     }
 
-    void deserializeRule(Build.Rule rulePb)
-        throws PackageDeserializationException {
-      String ruleClassName = rulePb.getRuleClass();
-      RuleClass ruleClass = ruleClassProvider.getRuleClassMap().get(ruleClassName);
-      if (ruleClass == null) {
-        throw new PackageDeserializationException(
-            String.format("Invalid rule class '%s'", ruleClassName));
-      }
-
+    void deserializeRule(Build.Rule rulePb) throws PackageDeserializationException {
+      Location ruleLocation = deserializeLocation(rulePb.getParseableLocation());
+      RuleClass ruleClass = packageDeserializationEnvironment.getRuleClass(rulePb, ruleLocation);
       Map<String, ParsedAttributeValue> attributeValues = new HashMap<>();
       for (Build.Attribute attrPb : rulePb.getAttributeList()) {
         Type<?> type = ruleClass.getAttributeByName(attrPb.getName()).getType();
@@ -136,7 +141,6 @@
       }
 
       Label ruleLabel = deserializeLabel(rulePb.getName());
-      Location ruleLocation = deserializeLocation(rulePb.getParseableLocation());
       try {
         Rule rule = ruleClass.createRuleWithParsedAttributeValues(
             ruleLabel, packageBuilder, ruleLocation, attributeValues,
@@ -150,8 +154,7 @@
     }
   }
 
-  private final FileSystem fileSystem;
-  private final RuleClassProvider ruleClassProvider;
+  private final PackageDeserializationEnvironment packageDeserializationEnvironment;
 
   @Immutable
   private static final class ExplicitLocation extends Location {
@@ -196,15 +199,16 @@
     }
   }
 
-  public PackageDeserializer(FileSystem fileSystem, RuleClassProvider ruleClassProvider) {
-    if (fileSystem == null) {
-      fileSystem = defaultDeserializerFileSystem;
-    }
-    this.fileSystem = Preconditions.checkNotNull(fileSystem);
-    if (ruleClassProvider == null) {
-      ruleClassProvider = defaultRuleClassProvider;
-    }
-    this.ruleClassProvider = Preconditions.checkNotNull(ruleClassProvider);
+  /**
+   * Creates a {@link PackageDeserializer} using {@link #defaultPackageDeserializationEnvironment}.
+   */
+  public PackageDeserializer() {
+    this.packageDeserializationEnvironment = defaultPackageDeserializationEnvironment;
+  }
+
+  public PackageDeserializer(PackageDeserializationEnvironment packageDeserializationEnvironment) {
+    this.packageDeserializationEnvironment =
+        Preconditions.checkNotNull(packageDeserializationEnvironment);
   }
 
   /**
@@ -310,7 +314,7 @@
    */
   private void deserializeInternal(Build.Package packagePb, StoredEventHandler eventHandler,
       Package.Builder builder, InputStream in) throws PackageDeserializationException, IOException {
-    Path buildFile = fileSystem.getPath(packagePb.getBuildFilePath());
+    Path buildFile = packageDeserializationEnvironment.getPath(packagePb.getBuildFilePath());
     Preconditions.checkNotNull(buildFile);
     Context context = new Context(buildFile, builder);
     builder.setFilename(buildFile);
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageSerializer.java b/src/main/java/com/google/devtools/build/lib/packages/PackageSerializer.java
index 16b318cb..4f1a7a3 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageSerializer.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageSerializer.java
@@ -158,6 +158,7 @@
       if (singleAttributeValue != null) {
         attrPb.setStringValue(singleAttributeValue.toString());
       }
+      attrPb.setNodep(type == NODEP_LABEL);
     } else if (type == STRING_LIST || type == LABEL_LIST || type == NODEP_LABEL_LIST
         || type == OUTPUT_LIST || type == DISTRIBUTIONS) {
       for (Object value : values) {
@@ -165,6 +166,7 @@
           attrPb.addStringListValue(entry.toString());
         }
       }
+      attrPb.setNodep(type == NODEP_LABEL_LIST);
     } else if (type == INTEGER_LIST) {
       for (Object value : values) {
         for (Integer entry : (Collection<Integer>) value) {
@@ -393,6 +395,7 @@
     builder.setName(rule.getLabel().toString());
     builder.setRuleClass(rule.getRuleClass());
     builder.setParseableLocation(serializeLocation(rule.getLocation()));
+    builder.setPublicByDefault(rule.getRuleClassObject().isPublicByDefault());
     for (Attribute attribute : rule.getAttributes()) {
       PackageSerializer.addAttributeToProto(builder, attribute,
           getAttributeValues(rule, attribute), rule.getAttributeLocation(attribute.getName()),
diff --git a/src/main/java/com/google/devtools/build/lib/packages/ProtoUtils.java b/src/main/java/com/google/devtools/build/lib/packages/ProtoUtils.java
index 653e283..b566ba7 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/ProtoUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/ProtoUtils.java
@@ -35,11 +35,17 @@
 import static com.google.devtools.build.lib.packages.Type.STRING_LIST_DICT;
 import static com.google.devtools.build.lib.packages.Type.TRISTATE;
 
+import com.google.common.base.Optional;
 import com.google.common.base.Preconditions;
+import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSetMultimap;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.query2.proto.proto2api.Build.Attribute.Discriminator;
 
-import java.util.Map;
+import java.util.Set;
 
 /**
  * Shared code used in proto buffer output for rules and rule classes.
@@ -48,9 +54,13 @@
   /**
    * This map contains all attribute types that are recognized by the protocol
    * output formatter.
+   *
+   * <p>If you modify this map, please ensure that {@link #getTypeFromDiscriminator} can still
+   * resolve a {@link Discriminator} value to exactly one {@link Type} (using an optional nodep
+   * hint, as described below).
    */
-  private static final Map<Type<?>, Discriminator> TYPE_MAP
-      = new ImmutableMap.Builder<Type<?>, Discriminator>()
+  static final ImmutableMap<Type<?>, Discriminator> TYPE_MAP =
+      new ImmutableMap.Builder<Type<?>, Discriminator>()
           .put(INTEGER, Discriminator.INTEGER)
           .put(DISTRIBUTIONS, Discriminator.DISTRIBUTION_SET)
           .put(LABEL, Discriminator.LABEL)
@@ -75,11 +85,71 @@
           .put(STRING_DICT_UNARY, Discriminator.STRING_DICT_UNARY)
           .build();
 
+  static final ImmutableSet<Type<?>> NODEP_TYPES =
+      ImmutableSet.of(NODEP_LABEL, NODEP_LABEL_LIST);
+
+  static final ImmutableSetMultimap<Discriminator, Type<?>> INVERSE_TYPE_MAP =
+      TYPE_MAP.asMultimap().inverse();
+
   /**
    * Returns the appropriate Attribute.Discriminator value from an internal attribute type.
    */
   public static Discriminator getDiscriminatorFromType(Type<?> type) {
-    Preconditions.checkArgument(TYPE_MAP.containsKey(type));
+    Preconditions.checkArgument(TYPE_MAP.containsKey(type), type);
     return TYPE_MAP.get(type);
   }
+
+  /**
+   * Returns the appropriate set of internal attribute types from an Attribute.Discriminator value.
+   */
+  public static ImmutableSet<Type<?>> getTypesFromDiscriminator(Discriminator discriminator) {
+    Preconditions.checkArgument(INVERSE_TYPE_MAP.containsKey(discriminator), discriminator);
+    return INVERSE_TYPE_MAP.get(discriminator);
+  }
+
+  /**
+   * Returns the appropriate internal attribute type from an Attribute.Discriminator value, given
+   * an optional nodeps hint.
+   */
+  public static Type<?> getTypeFromDiscriminator(Discriminator discriminator,
+      Optional<Boolean> nodeps, String ruleClassName, String attrName) {
+    Preconditions.checkArgument(INVERSE_TYPE_MAP.containsKey(discriminator));
+    ImmutableSet<Type<?>> possibleTypes = ProtoUtils.getTypesFromDiscriminator(discriminator);
+    Type<?> preciseType;
+    if (possibleTypes.size() == 1) {
+      preciseType = Iterables.getOnlyElement(possibleTypes);
+    } else {
+      // If there is more than one possible type associated with the discriminator, then the
+      // discriminator must be either Discriminator.STRING or Discriminator.STRING_LIST.
+      //
+      // If it is Discriminator.STRING, then its possible Type<?>s are {NODEP_LABEL, STRING}. The
+      // nodeps hint must be present in order to distinguish between them. If nodeps is true,
+      // then the Type<?> must be NODEP_LABEL, and if false, it must be STRING.
+      //
+      // A similar relation holds for the Discriminator value STRING_LIST, and its possible
+      // Type<?>s {NODEP_LABEL_LIST, STRING_LIST}.
+
+      Preconditions.checkArgument(nodeps.isPresent(),
+          "Nodeps hint is required when discriminator is associated with more than one type."
+              + " Discriminator: \"%s\", Rule class: \"%s\", Attr: \"%s\"", discriminator,
+          ruleClassName, attrName);
+      if (nodeps.get()) {
+        Set<Type<?>> nodepType = Sets.filter(possibleTypes, Predicates.in(NODEP_TYPES));
+        Preconditions.checkState(nodepType.size() == 1,
+            "There should be exactly one NODEP type associated with discriminator \"%s\""
+                + ", but found these: %s. Rule class: \"%s\", Attr: \"%s\"", discriminator,
+            nodepType, ruleClassName, attrName);
+        preciseType = Iterables.getOnlyElement(nodepType);
+      } else {
+        Set<Type<?>> notNodepType =
+            Sets.filter(possibleTypes, Predicates.not(Predicates.in(NODEP_TYPES)));
+        Preconditions.checkState(notNodepType.size() == 1,
+            "There should be exactly one non-NODEP type associated with discriminator \"%s\""
+                + ", but found these: %s. Rule class: \"%s\", Attr: \"%s\"", discriminator,
+            notNodepType, ruleClassName, attrName);
+        preciseType = Iterables.getOnlyElement(notNodepType);
+      }
+    }
+    return preciseType;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index 0286796..e7cbf9e 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -31,6 +31,7 @@
 import com.google.common.collect.Ordering;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.packages.RuleClass.Builder.RuleClassType;
 import com.google.devtools.build.lib.syntax.Argument;
 import com.google.devtools.build.lib.syntax.BaseFunction;
 import com.google.devtools.build.lib.syntax.Environment;
@@ -339,6 +340,29 @@
                 attribute.getName(), attribute.getType());
           }
         }
+      },
+
+      /**
+       * Placeholder rules are only instantiated when packages which refer to non-native rule
+       * classes are deserialized. At this time, non-native rule classes can't be serialized. To
+       * prevent crashes on deserialization, when a package containing a rule with a non-native rule
+       * class is deserialized, the rule is assigned a placeholder rule class. This is compatible
+       * with our limited set of package serialization use cases.
+       *
+       * Placeholder rule class names obey the rule for identifiers.
+       */
+      PLACEHOLDER {
+        @Override
+        public void checkName(String name) {
+          Preconditions.checkArgument(RULE_NAME_PATTERN.matcher(name).matches(), name);
+        }
+
+        @Override
+        public void checkAttributes(Map<String, Attribute> attributes) {
+          // No required attributes; this rule class cannot have the wrong set of attributes now
+          // because, if it did, the rule class would have failed to build before the package
+          // referring to it was serialized.
+        }
       };
 
       /**
@@ -690,6 +714,11 @@
       }
     }
 
+    /** True if the rule class contains an attribute named {@code name}. */
+    public boolean contains(String name) {
+      return attributes.containsKey(name);
+    }
+
     /**
      * Sets the rule implementation function. Meant for Skylark usage.
      */
@@ -789,6 +818,20 @@
     }
   }
 
+  public static Builder createPlaceholderBuilder(final String name, final Location ruleLocation,
+      ImmutableList<RuleClass> parents) {
+    return new Builder(name, RuleClassType.PLACEHOLDER, /*skylark=*/true,
+        parents.toArray(new RuleClass[parents.size()])).factory(
+        new ConfiguredTargetFactory<Object, Object>() {
+          @Override
+          public Object create(Object ruleContext) throws InterruptedException {
+            throw new IllegalStateException(
+                "Cannot create configured targets from rule with placeholder class named \"" + name
+                    + "\" at " + ruleLocation);
+          }
+        });
+  }
+
   private final String name; // e.g. "cc_library"
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
index 1cb405f..f39d292 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
@@ -118,13 +118,15 @@
   });
 
   // TODO(bazel-team): Remove the code duplication (BaseRuleClasses and this class).
-  private static final RuleClass baseRule =
+  /** Parent rule class for non-test Skylark rules. */
+  public static final RuleClass baseRule =
       BaseRuleClasses.commonCoreAndSkylarkAttributes(
           new RuleClass.Builder("$base_rule", RuleClassType.ABSTRACT, true))
           .add(attr("expect_failure", STRING))
           .build();
 
-  private static final RuleClass testBaseRule =
+  /** Parent rule class for test Skylark rules. */
+  public static final RuleClass testBaseRule =
       new RuleClass.Builder("$test_base_rule", RuleClassType.ABSTRACT, true, baseRule)
           .add(attr("size", STRING).value("medium").taggable()
               .nonconfigurable("used in loading phase rule validation logic"))