diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/ComposingRuleTransitionFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/config/ComposingRuleTransitionFactory.java
index 8f6d2b5..6463077 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/ComposingRuleTransitionFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/ComposingRuleTransitionFactory.java
@@ -20,10 +20,10 @@
 import com.google.devtools.build.lib.analysis.config.transitions.PatchTransition;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.RuleTransitionFactory;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 
-/**
- * A {@link RuleTransitionFactory} that composes other {@link RuleTransitionFactory}s.
- */
+/** A {@link RuleTransitionFactory} that composes other {@link RuleTransitionFactory}s. */
+@AutoCodec
 public class ComposingRuleTransitionFactory implements RuleTransitionFactory {
 
   private final RuleTransitionFactory rtf1;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java
index c45ec3c..e6e6e9c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java
@@ -556,7 +556,8 @@
           RuleClassType type = test ? RuleClassType.TEST : RuleClassType.NORMAL;
           RuleClass parent =
               test
-                  ? getTestBaseRule(SkylarkUtils.getToolsRepository(funcallEnv),
+                  ? getTestBaseRule(
+                      SkylarkUtils.getToolsRepository(funcallEnv),
                       (PatchTransition) SkylarkUtils.getLipoDataTransition(funcallEnv))
                   : (executable ? binaryBaseRule : baseRule);
 
@@ -609,7 +610,9 @@
               .requiresHostConfigurationFragmentsBySkylarkModuleName(
                   hostFragments.getContents(String.class, "host_fragments"));
           builder.setConfiguredTargetFunction(implementation);
-          builder.setRuleDefinitionEnvironment(funcallEnv);
+          builder.setRuleDefinitionEnvironmentLabelAndHashCode(
+              funcallEnv.getGlobals().getTransitiveLabel(),
+              funcallEnv.getTransitiveContentHashCode());
           builder.addRequiredToolchains(collectToolchainLabels(toolchains, ast));
 
           return new SkylarkRuleFunction(builder, type, attributes, ast.getLocation());
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
index ebb131c..6781885 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
@@ -126,8 +126,8 @@
           Builder builder = new Builder("", RuleClassType.WORKSPACE, true);
 
           builder.addOrOverrideAttribute(attr("$local", BOOLEAN).defaultValue(local).build());
-          builder.addOrOverrideAttribute(attr("$environ", STRING_LIST)
-              .defaultValue(environ).build());
+          builder.addOrOverrideAttribute(
+              attr("$environ", STRING_LIST).defaultValue(environ).build());
           BaseRuleClasses.nameAttribute(builder);
           BaseRuleClasses.commonCoreAndSkylarkAttributes(builder);
           builder.add(attr("expect_failure", STRING));
@@ -141,7 +141,9 @@
             }
           }
           builder.setConfiguredTargetFunction(implementation);
-          builder.setRuleDefinitionEnvironment(funcallEnv);
+          builder.setRuleDefinitionEnvironmentLabelAndHashCode(
+              funcallEnv.getGlobals().getTransitiveLabel(),
+              funcallEnv.getTransitiveContentHashCode());
           builder.setWorkspaceOnly();
           return new RepositoryRuleFunction(builder);
         }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java b/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java
index 81dfd14..0147fd1 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java
@@ -29,6 +29,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Runtime;
@@ -75,9 +76,8 @@
     }
   }
 
-  /**
-   * Implicit output functions executing Skylark code.
-   */
+  /** Implicit output functions executing Skylark code. */
+  @AutoCodec
   public static final class SkylarkImplicitOutputsFunctionWithCallback
       extends SkylarkImplicitOutputsFunction {
 
@@ -138,9 +138,8 @@
     }
   }
 
-  /**
-   * Implicit output functions using a simple an output map.
-   */
+  /** Implicit output functions using a simple an output map. */
+  @AutoCodec
   public static final class SkylarkImplicitOutputsFunctionWithMap
       extends SkylarkImplicitOutputsFunction {
 
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 ebb6f12..4795e61 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
@@ -47,7 +47,6 @@
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
 import com.google.devtools.build.lib.syntax.Argument;
 import com.google.devtools.build.lib.syntax.BaseFunction;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.GlobList;
@@ -78,42 +77,47 @@
  * Instances of RuleClass encapsulate the set of attributes of a given "class" of rule, such as
  * <code>cc_binary</code>.
  *
- * <p>This is an instance of the "meta-class" pattern for Rules: we achieve using <i>values</i>
- * what subclasses achieve using <i>types</i>.  (The "Design Patterns" book doesn't include this
- * pattern, so think of it as something like a cross between a Flyweight and a State pattern. Like
- * Flyweight, we avoid repeatedly storing data that belongs to many instances. Like State, we
- * delegate from Rule to RuleClass for the specific behavior of that rule (though unlike state, a
- * Rule object never changes its RuleClass).  This avoids the need to declare one Java class per
- * class of Rule, yet achieves the same behavior.)
+ * <p>This is an instance of the "meta-class" pattern for Rules: we achieve using <i>values</i> what
+ * subclasses achieve using <i>types</i>. (The "Design Patterns" book doesn't include this pattern,
+ * so think of it as something like a cross between a Flyweight and a State pattern. Like Flyweight,
+ * we avoid repeatedly storing data that belongs to many instances. Like State, we delegate from
+ * Rule to RuleClass for the specific behavior of that rule (though unlike state, a Rule object
+ * never changes its RuleClass). This avoids the need to declare one Java class per class of Rule,
+ * yet achieves the same behavior.)
  *
  * <p>The use of a metaclass also allows us to compute a mapping from Attributes to small integers
- * and share this between all rules of the same metaclass.  This means we can save the attribute
+ * and share this between all rules of the same metaclass. This means we can save the attribute
  * dictionary for each rule instance using an array, which is much more compact than a hashtable.
  *
  * <p>Rule classes whose names start with "$" are considered "abstract"; since they are not valid
  * identifiers, they cannot be named in the build language. However, they are useful for grouping
  * related attributes which are inherited.
  *
- * <p>The exact values in this class are important.  In particular:
+ * <p>The exact values in this class are important. In particular:
+ *
  * <ul>
- * <li>Changing an attribute from MANDATORY to OPTIONAL creates the potential for null-pointer
- *     exceptions in code that expects a value.
- * <li>Attributes whose names are preceded by a "$" or a ":" are "hidden", and cannot be redefined
- *     in a BUILD file.  They are a useful way of adding a special dependency. By convention,
- *     attributes starting with "$" are implicit dependencies, and those starting with a ":" are
- *     late-bound implicit dependencies, i.e. dependencies that can only be resolved when the
- *     configuration is known.
- * <li>Attributes should not be introduced into the hierarchy higher then necessary.
- * <li>The 'deps' and 'data' attributes are treated specially by the code that builds the runfiles
- *     tree.  All targets appearing in these attributes appears beneath the ".runfiles" tree; in
- *     addition, "deps" may have rule-specific semantics.
+ *   <li>Changing an attribute from MANDATORY to OPTIONAL creates the potential for null-pointer
+ *       exceptions in code that expects a value.
+ *   <li>Attributes whose names are preceded by a "$" or a ":" are "hidden", and cannot be redefined
+ *       in a BUILD file. They are a useful way of adding a special dependency. By convention,
+ *       attributes starting with "$" are implicit dependencies, and those starting with a ":" are
+ *       late-bound implicit dependencies, i.e. dependencies that can only be resolved when the
+ *       configuration is known.
+ *   <li>Attributes should not be introduced into the hierarchy higher then necessary.
+ *   <li>The 'deps' and 'data' attributes are treated specially by the code that builds the runfiles
+ *       tree. All targets appearing in these attributes appears beneath the ".runfiles" tree; in
+ *       addition, "deps" may have rule-specific semantics.
  * </ul>
  */
 // Non-final only for mocking in tests. Do not subclass!
 @Immutable
+@AutoCodec
 public class RuleClass {
+  @AutoCodec
   static final Function<? super Rule, Map<String, Label>> NO_EXTERNAL_BINDINGS =
       Functions.<Map<String, Label>>constant(ImmutableMap.<String, Label>of());
+
+  @AutoCodec
   static final Function<? super Rule, Set<String>> NO_OPTION_REFERENCE =
       Functions.<Set<String>>constant(ImmutableSet.<String>of());
 
@@ -545,13 +549,14 @@
       }
     }
 
-    /**
-     * A RuleTransitionFactory which always returns the same transition.
-     */
-    private static final class FixedTransitionFactory implements RuleTransitionFactory {
+    /** A RuleTransitionFactory which always returns the same transition. */
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec
+    static final class FixedTransitionFactory implements RuleTransitionFactory {
       private final ConfigurationTransition transition;
 
-      private FixedTransitionFactory(ConfigurationTransition transition) {
+      @AutoCodec.VisibleForSerialization
+      FixedTransitionFactory(ConfigurationTransition transition) {
         this.transition = transition;
       }
 
@@ -597,7 +602,9 @@
         NO_EXTERNAL_BINDINGS;
     private Function<? super Rule, ? extends Set<String>> optionReferenceFunction =
         NO_OPTION_REFERENCE;
-    @Nullable private Environment ruleDefinitionEnvironment = null;
+    /** This field and the next are null iff the rule is native. */
+    @Nullable private Label ruleDefinitionEnvironmentLabel;
+
     @Nullable private String ruleDefinitionEnvironmentHashCode = null;
     private ConfigurationFragmentPolicy.Builder configurationFragmentPolicy =
         new ConfigurationFragmentPolicy.Builder();
@@ -681,8 +688,6 @@
       Preconditions.checkArgument(this.name.isEmpty() || this.name.equals(name));
       type.checkName(name);
       type.checkAttributes(attributes);
-      boolean skylarkExecutable =
-          skylark && (type == RuleClassType.NORMAL || type == RuleClassType.TEST);
       Preconditions.checkState(
           (type == RuleClassType.ABSTRACT)
               == (configuredTargetFactory == null && configuredTargetFunction == null),
@@ -692,8 +697,10 @@
           configuredTargetFactory,
           configuredTargetFunction);
       if (!workspaceOnly) {
-        Preconditions.checkState(skylarkExecutable == (configuredTargetFunction != null));
-        Preconditions.checkState(skylarkExecutable == (ruleDefinitionEnvironment != null));
+        if (skylark) {
+          assertSkylarkRuleClassHasImplementationFunction();
+          assertSkylarkRuleClassHasEnvironmentLabel();
+        }
         Preconditions.checkState(externalBindingsFunction == NO_EXTERNAL_BINDINGS);
       }
       if (type == RuleClassType.PLACEHOLDER) {
@@ -704,7 +711,6 @@
           key,
           type,
           skylark,
-          skylarkExecutable,
           skylarkTestable,
           documented,
           publicByDefault,
@@ -721,13 +727,33 @@
           configuredTargetFunction,
           externalBindingsFunction,
           optionReferenceFunction,
-          ruleDefinitionEnvironment,
+          ruleDefinitionEnvironmentLabel,
           ruleDefinitionEnvironmentHashCode,
           configurationFragmentPolicy.build(),
           supportsConstraintChecking,
           requiredToolchains,
           supportsPlatforms,
-          attributes.values().toArray(new Attribute[0]));
+          attributes.values());
+    }
+
+    private void assertSkylarkRuleClassHasImplementationFunction() {
+      Preconditions.checkState(
+          (type == RuleClassType.NORMAL || type == RuleClassType.TEST)
+              == (configuredTargetFunction != null),
+          "%s %s",
+          type,
+          configuredTargetFunction);
+    }
+
+    private void assertSkylarkRuleClassHasEnvironmentLabel() {
+      Preconditions.checkState(
+          (type == RuleClassType.NORMAL
+                  || type == RuleClassType.TEST
+                  || type == RuleClassType.PLACEHOLDER)
+              == (ruleDefinitionEnvironmentLabel != null),
+          "Concrete Skylark rule classes can't have null labels: %s %s",
+          ruleDefinitionEnvironmentLabel,
+          type);
     }
 
     /**
@@ -1027,18 +1053,9 @@
       return this;
     }
 
-    /** Sets the rule definition environment. Meant for Skylark usage. */
-    public Builder setRuleDefinitionEnvironment(Environment env) {
-      this.ruleDefinitionEnvironment = Preconditions.checkNotNull(env, this.name);
-      this.ruleDefinitionEnvironmentHashCode =
-          this.ruleDefinitionEnvironment.getTransitiveContentHashCode();
-      return this;
-    }
-
-    /** Sets the rule definition environment hash code for deserialized rule classes. */
-    Builder setRuleDefinitionEnvironmentHashCode(String hashCode) {
-      Preconditions.checkState(ruleDefinitionEnvironment == null, ruleDefinitionEnvironment);
-      Preconditions.checkState(type == RuleClassType.PLACEHOLDER, type);
+    /** Sets the rule definition environment label and hash code. Meant for Skylark usage. */
+    public Builder setRuleDefinitionEnvironmentLabelAndHashCode(Label label, String hashCode) {
+      this.ruleDefinitionEnvironmentLabel = Preconditions.checkNotNull(label, this.name);
       this.ruleDefinitionEnvironmentHashCode = Preconditions.checkNotNull(hashCode, this.name);
       return this;
     }
@@ -1175,7 +1192,6 @@
 
   private final RuleClassType type;
   private final boolean isSkylark;
-  private final boolean skylarkExecutable;
   private final boolean skylarkTestable;
   private final boolean documented;
   private final boolean publicByDefault;
@@ -1245,10 +1261,11 @@
   private final Function<? super Rule, ? extends Set<String>> optionReferenceFunction;
 
   /**
-   * The Skylark rule definition environment of this RuleClass.
-   * Null for non Skylark executable RuleClasses.
+   * The Skylark rule definition environment's label and hash code of this RuleClass. Null for non
+   * Skylark executable RuleClasses.
    */
-  @Nullable private final Environment ruleDefinitionEnvironment;
+  @Nullable private final Label ruleDefinitionEnvironmentLabel;
+
   @Nullable private final String ruleDefinitionEnvironmentHashCode;
 
   /**
@@ -1292,7 +1309,6 @@
       String key,
       RuleClassType type,
       boolean isSkylark,
-      boolean skylarkExecutable,
       boolean skylarkTestable,
       boolean documented,
       boolean publicByDefault,
@@ -1309,19 +1325,18 @@
       @Nullable BaseFunction configuredTargetFunction,
       Function<? super Rule, Map<String, Label>> externalBindingsFunction,
       Function<? super Rule, ? extends Set<String>> optionReferenceFunction,
-      @Nullable Environment ruleDefinitionEnvironment,
+      @Nullable Label ruleDefinitionEnvironmentLabel,
       String ruleDefinitionEnvironmentHashCode,
       ConfigurationFragmentPolicy configurationFragmentPolicy,
       boolean supportsConstraintChecking,
       Set<Label> requiredToolchains,
       boolean supportsPlatforms,
-      Attribute... attributes) {
+      Collection<Attribute> attributes) {
     this.name = name;
     this.key = key;
     this.type = type;
     this.isSkylark = isSkylark;
     this.targetKind = name + Rule.targetKindSuffix();
-    this.skylarkExecutable = skylarkExecutable;
     this.skylarkTestable = skylarkTestable;
     this.documented = documented;
     this.publicByDefault = publicByDefault;
@@ -1336,7 +1351,7 @@
     this.configuredTargetFunction = configuredTargetFunction;
     this.externalBindingsFunction = externalBindingsFunction;
     this.optionReferenceFunction = optionReferenceFunction;
-    this.ruleDefinitionEnvironment = ruleDefinitionEnvironment;
+    this.ruleDefinitionEnvironmentLabel = ruleDefinitionEnvironmentLabel;
     this.ruleDefinitionEnvironmentHashCode = ruleDefinitionEnvironmentHashCode;
     validateNoClashInPublicNames(attributes);
     this.attributes = ImmutableList.copyOf(attributes);
@@ -1349,7 +1364,7 @@
 
     // Create the index and collect non-configurable attributes.
     int index = 0;
-    attributeIndex = new HashMap<>(attributes.length);
+    attributeIndex = new HashMap<>(attributes.size());
     ImmutableList.Builder<String> nonConfigurableAttributesBuilder = ImmutableList.builder();
     for (Attribute attribute : attributes) {
       attributeIndex.put(attribute.getName(), index++);
@@ -1360,7 +1375,7 @@
     this.nonConfigurableAttributes = nonConfigurableAttributesBuilder.build();
   }
 
-  private void validateNoClashInPublicNames(Attribute[] attributes) {
+  private void validateNoClashInPublicNames(Iterable<Attribute> attributes) {
     Map<String, Attribute> publicToPrivateNames = new HashMap<>();
     for (Attribute attribute : attributes) {
       String publicName = attribute.getPublicName();
@@ -2117,19 +2132,17 @@
   }
 
   /**
-   * Returns this RuleClass's rule definition environment. Is null for native rules' RuleClass
-   * objects and deserialized Skylark rules. Deserialized rules do provide a hash code encapsulating
-   * their behavior, available at {@link #getRuleDefinitionEnvironmentHashCode}.
+   * For Skylark rule classes, returns this RuleClass's rule definition environment's label, which
+   * is never null. Is null for native rules' RuleClass objects.
    */
   @Nullable
-  public Environment getRuleDefinitionEnvironment() {
-    return ruleDefinitionEnvironment;
+  public Label getRuleDefinitionEnvironmentLabel() {
+    return ruleDefinitionEnvironmentLabel;
   }
 
   /**
-   * Returns the hash code for the RuleClass's rule definition environment. In deserialization,
-   * this RuleClass may not actually contain its environment, in which case the hash code is all
-   * that is available. Will be null for native rules' RuleClass objects.
+   * Returns the hash code for the RuleClass's rule definition environment. Will be null for native
+   * rules' RuleClass objects.
    */
   @Nullable
   public String getRuleDefinitionEnvironmentHashCode() {
@@ -2142,14 +2155,6 @@
   }
 
   /**
-   * Returns true if this RuleClass is an executable Skylark RuleClass (i.e. it is
-   * Skylark and Normal or Test RuleClass).
-   */
-  public boolean isSkylarkExecutable() {
-    return skylarkExecutable;
-  }
-
-  /**
    * Returns true if this RuleClass is Skylark-defined and is subject to analysis-time
    * tests.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleFormatter.java b/src/main/java/com/google/devtools/build/lib/packages/RuleFormatter.java
index a179df0..ce15282 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleFormatter.java
@@ -44,10 +44,7 @@
     if (isSkylark) {
       builder.setSkylarkEnvironmentHashCode(
           Preconditions.checkNotNull(
-              rule.getRuleClassObject()
-                  .getRuleDefinitionEnvironment()
-                  .getTransitiveContentHashCode(),
-              rule));
+              rule.getRuleClassObject().getRuleDefinitionEnvironmentHashCode(), rule));
     }
     for (Attribute attr : rule.getAttributes()) {
       Object rawAttributeValue = rawAttributeMapper.getRawAttributeValue(rule, attr);
@@ -116,4 +113,3 @@
     return null;
   }
 }
-
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
index edb0796..ef5c31a 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
@@ -52,7 +52,6 @@
 import com.google.devtools.build.lib.query2.proto.proto2api.Build.GeneratedFile;
 import com.google.devtools.build.lib.query2.proto.proto2api.Build.QueryResult.Builder;
 import com.google.devtools.build.lib.query2.proto.proto2api.Build.SourceFile;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.Type;
 import java.io.IOException;
 import java.io.OutputStream;
@@ -211,15 +210,15 @@
 
       postProcess(rule, rulePb, serializedAttributes);
 
-      Environment env = rule.getRuleClassObject().getRuleDefinitionEnvironment();
-      if (env != null && includeRuleDefinitionEnvironment()) {
+      String transitiveHashCode = rule.getRuleClassObject().getRuleDefinitionEnvironmentHashCode();
+      if (transitiveHashCode != null && includeRuleDefinitionEnvironment()) {
         // The RuleDefinitionEnvironment is always defined for Skylark rules and
         // always null for non Skylark rules.
         rulePb.addAttribute(
             Build.Attribute.newBuilder()
                 .setName(RULE_IMPLEMENTATION_HASH_ATTR_NAME)
                 .setType(ProtoUtils.getDiscriminatorFromType(Type.STRING))
-                .setStringValue(env.getTransitiveContentHashCode()));
+                .setStringValue(transitiveHashCode));
       }
 
       ImmutableMultimap<Attribute, Label> aspectsDependencies =