Reinstate mutable SkylarkDict

Add <String, Object> annotation to optionMap invocation in SkylarkAttr,
to make JDK 1.7 happy.

Give the visible name "aspect" to class SkylarkAspect.

--
MOS_MIGRATED_REVID=113394826

35 files changed, 783 insertions, 458 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index 24bece9edd..6473cdca8e 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -28,6 +28,7 @@ import com.google.devtools.build.lib.shell.ShellUtils;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.util.FileType;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -72,7 +73,8 @@ import javax.annotation.Nullable;
 @SkylarkModule(name = "File",
     doc = "This type represents a file used by the build system. It can be "
         + "either a source file or a derived file produced by a rule.")
-public class Artifact implements FileType.HasFilename, ActionInput, SkylarkValue {
+  public class Artifact
+    implements FileType.HasFilename, ActionInput, SkylarkValue, Comparable<Object> {
 
   /**
    * Compares artifact according to their exec paths. Sorts null values first.
@@ -92,6 +94,15 @@ public class Artifact implements FileType.HasFilename, ActionInput, SkylarkValue
     }
   };
 
+  @Override
+  public int compareTo(Object o) {
+    if (o instanceof Artifact) {
+      return EXEC_PATH_COMPARATOR.compare(this, (Artifact) o);
+    }
+    return EvalUtils.compareByClass(this, o);
+  }
+
+
   /** An object that can expand middleman artifacts. */
   public interface MiddlemanExpander {
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
index b2523de047..7176011b3f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
@@ -25,6 +25,9 @@ import com.google.devtools.build.lib.actions.BaseSpawn;
 import com.google.devtools.build.lib.analysis.actions.FileWriteAction;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
+import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.OS;
 import com.google.devtools.build.lib.util.Pair;
@@ -69,14 +72,14 @@ public final class CommandHelper {
    *  A map of remote path prefixes and corresponding runfiles manifests for tools
    *  used by this rule.
    */
-  private final ImmutableMap<PathFragment, Artifact> remoteRunfileManifestMap;
+  private final SkylarkDict<PathFragment, Artifact> remoteRunfileManifestMap;
 
   /**
    * Use labelMap for heuristically expanding labels (does not include "outs")
    * This is similar to heuristic location expansion in LocationExpander
    * and should be kept in sync.
    */
-  private final ImmutableMap<Label, ImmutableCollection<Artifact>> labelMap;
+  private final SkylarkDict<Label, ImmutableCollection<Artifact>> labelMap;
 
   /**
    * The ruleContext this helper works on
@@ -86,7 +89,7 @@ public final class CommandHelper {
   /**
    * Output executable files from the 'tools' attribute.
    */
-  private final ImmutableList<Artifact> resolvedTools;
+  private final SkylarkList<Artifact> resolvedTools;
 
   /**
    * Creates a {@link CommandHelper}.
@@ -136,21 +139,21 @@ public final class CommandHelper {
       }
     }
 
-    this.resolvedTools = resolvedToolsBuilder.build();
-    this.remoteRunfileManifestMap = remoteRunfileManifestBuilder.build();
+    this.resolvedTools = new MutableList<>(resolvedToolsBuilder.build());
+    this.remoteRunfileManifestMap = SkylarkDict.copyOf(null, remoteRunfileManifestBuilder.build());
     ImmutableMap.Builder<Label, ImmutableCollection<Artifact>> labelMapBuilder =
         ImmutableMap.builder();
     for (Entry<Label, Collection<Artifact>> entry : tempLabelMap.entrySet()) {
       labelMapBuilder.put(entry.getKey(), ImmutableList.copyOf(entry.getValue()));
     }
-    this.labelMap = labelMapBuilder.build();
+    this.labelMap = SkylarkDict.copyOf(null, labelMapBuilder.build());
   }
 
-  public List<Artifact> getResolvedTools() {
+  public SkylarkList<Artifact> getResolvedTools() {
     return resolvedTools;
   }
 
-  public ImmutableMap<PathFragment, Artifact> getRemoteRunfileManifestMap() {
+  public SkylarkDict<PathFragment, Artifact> getRemoteRunfileManifestMap() {
     return remoteRunfileManifestMap;
   }
 
@@ -177,7 +180,8 @@ public final class CommandHelper {
       @Nullable String attribute,
       Boolean supportLegacyExpansion,
       Boolean allowDataInLabel) {
-    LocationExpander expander = new LocationExpander(ruleContext, labelMap, allowDataInLabel);
+    LocationExpander expander = new LocationExpander(
+        ruleContext, ImmutableMap.copyOf(labelMap), allowDataInLabel);
     if (attribute != null) {
       command = expander.expandAttribute(attribute, command);
     } else {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java
index 62e9b614b6..5629c83a60 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java
@@ -14,10 +14,10 @@
 
 package com.google.devtools.build.lib.analysis;
 
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.MakeVariableExpander.ExpansionException;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 
 import java.util.LinkedHashMap;
 import java.util.Map;
@@ -56,13 +56,13 @@ public class ConfigurationMakeVariableContext implements MakeVariableExpander.Co
     return value;
   }
 
-  public ImmutableMap<String, String> collectMakeVariables() {
+  public SkylarkDict<String, String> collectMakeVariables() {
     Map<String, String> map = new LinkedHashMap<>();
     // Collect variables in the reverse order as in lookupMakeVariable
     // because each update is overwriting.
     map.putAll(pkg.getAllMakeVariables(platform));
     map.putAll(globalEnv);
     map.putAll(commandLineEnv);
-    return ImmutableMap.copyOf(map);
+    return SkylarkDict.<String, String>copyOf(null, map);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
index d9c855a32a..c1382c07c2 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.bazel.rules.genrule;
 
 import static com.google.devtools.build.lib.analysis.RunfilesProvider.withData;
 
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
@@ -132,13 +133,13 @@ public class GenRule implements RuleConfiguredTargetFactory {
     ruleContext.registerAction(
         new GenRuleAction(
             ruleContext.getActionOwner(),
-            commandHelper.getResolvedTools(),
+            ImmutableList.copyOf(commandHelper.getResolvedTools()),
             inputs.build(),
             filesToBuild,
             argv,
             env,
             ImmutableMap.copyOf(executionInfo),
-            commandHelper.getRemoteRunfileManifestMap(),
+            ImmutableMap.copyOf(commandHelper.getRemoteRunfileManifestMap()),
             message + ' ' + ruleContext.getLabel()));
 
     RunfilesProvider runfilesProvider = withData(
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index 24eb51429b..8fa921918b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -54,6 +54,7 @@ import com.google.devtools.build.lib.syntax.Identifier;
 import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 import com.google.devtools.build.lib.syntax.Runtime;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
@@ -847,21 +848,23 @@ public final class PackageFactory {
       };
 
   @Nullable
-  static Map<String, Object> callGetRuleFunction(
+  static SkylarkDict<String, Object> callGetRuleFunction(
       String name, FuncallExpression ast, Environment env)
       throws EvalException, ConversionException {
     PackageContext context = getContext(env, ast);
     Target target = context.pkgBuilder.getTarget(name);
 
-    return targetDict(target);
+    return targetDict(target, ast.getLocation(), env);
   }
 
   @Nullable
-  private static Map<String, Object> targetDict(Target target) throws NotRepresentableException {
+  private static SkylarkDict<String, Object> targetDict(
+      Target target, Location loc, Environment env)
+      throws NotRepresentableException, EvalException {
     if (target == null && !(target instanceof Rule)) {
       return null;
     }
-    Map<String, Object> values = new TreeMap<>();
+    SkylarkDict<String, Object> values = SkylarkDict.<String, Object>of(env);
 
     Rule rule = (Rule) target;
     AttributeContainer cont = rule.getAttributeContainer();
@@ -881,7 +884,7 @@ public final class PackageFactory {
         if (val == null) {
           continue;
         }
-        values.put(attr.getName(), val);
+        values.put(attr.getName(), val, loc, env);
       } catch (NotRepresentableException e) {
         throw new NotRepresentableException(
             String.format(
@@ -889,8 +892,8 @@ public final class PackageFactory {
       }
     }
 
-    values.put("name", rule.getName());
-    values.put("kind", rule.getRuleClass());
+    values.put("name", rule.getName(), loc, env);
+    values.put("kind", rule.getRuleClass(), loc, env);
     return values;
   }
 
@@ -1011,18 +1014,21 @@ public final class PackageFactory {
   }
 
 
-  static Map callGetRulesFunction(FuncallExpression ast, Environment env) throws EvalException {
+  static SkylarkDict<String, SkylarkDict<String, Object>> callGetRulesFunction(
+      FuncallExpression ast, Environment env)
+      throws EvalException {
     PackageContext context = getContext(env, ast);
     Collection<Target> targets = context.pkgBuilder.getTargets();
+    Location loc = ast.getLocation();
 
     // Sort by name.
-    Map<String, Map<String, Object>> rules = new TreeMap<>();
+    SkylarkDict<String, SkylarkDict<String, Object>> rules =
+        SkylarkDict.<String, SkylarkDict<String, Object>>of(env);
     for (Target t : targets) {
       if (t instanceof Rule) {
-        Map<String, Object> m = targetDict(t);
+        SkylarkDict<String, Object> m = targetDict(t, loc, env);
         Preconditions.checkNotNull(m);
-
-        rules.put(t.getName(), m);
+        rules.put(t.getName(), m, loc, env);
       }
     }
 
@@ -1335,7 +1341,8 @@ public final class PackageFactory {
   public Preprocessor.Result preprocess(
       PackageIdentifier packageId, Path buildFile, CachingPackageLocator locator)
       throws InterruptedException, IOException {
-    byte[] buildFileBytes = FileSystemUtils.readWithKnownFileSize(buildFile, buildFile.getFileSize());
+    byte[] buildFileBytes =
+        FileSystemUtils.readWithKnownFileSize(buildFile, buildFile.getFileSize());
     Globber globber = createLegacyGlobber(buildFile.getParentDirectory(), packageId, locator);
     try {
       return preprocess(buildFile, packageId, buildFileBytes, globber);
@@ -1669,6 +1676,7 @@ public final class PackageFactory {
     SkylarkSignatureProcessor.configureSkylarkFunctions(PackageFactory.class);
   }
 
+  /** Empty EnvironmentExtension */
   public static class EmptyEnvironmentExtension implements EnvironmentExtension {
     @Override
     public void update(Environment environment) {}
diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java
index dd80289ca5..cecb714ac7 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java
@@ -22,12 +22,11 @@ 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.Runtime;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
 
-import java.util.Map;
-
 /**
  * A class for the Skylark native module.
  */
@@ -50,8 +49,8 @@ public class SkylarkNativeModule {
             + "<li>Matches at least one pattern in <code>include</code>.</li>\n"
             + "<li>Does not match any of the patterns in <code>exclude</code> "
             + "(default <code>[]</code>).</li></ul>\n"
-            + "If the <code>exclude_directories</code> argument is enabled (set to <code>1</code>), "
-            + "files of type directory will be omitted from the results (default <code>1</code>).",
+            + "If the <code>exclude_directories</code> argument is enabled (set to <code>1</code>),"
+            + " files of type directory will be omitted from the results (default <code>1</code>).",
     mandatoryPositionals = {
       @Param(
         name = "include",
@@ -112,12 +111,8 @@ public class SkylarkNativeModule {
         public Object invoke(String name, FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.rule", ast.getLocation());
-          Map<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
-          if (rule != null) {
-            return rule;
-          }
-
-          return Runtime.NONE;
+          SkylarkDict<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
+          return rule == null ? Runtime.NONE : rule;
         }
       };
 
@@ -139,7 +134,7 @@ public class SkylarkNativeModule {
         public Object invoke(String name, FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.existing_rule", ast.getLocation());
-          Map<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
+          SkylarkDict<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
           if (rule != null) {
             return rule;
           }
@@ -152,7 +147,7 @@ public class SkylarkNativeModule {
   @SkylarkSignature(
     name = "rules",
     objectType = SkylarkNativeModule.class,
-    returnType = Map.class,
+    returnType = SkylarkDict.class,
     doc = "Deprecated. Use existing_rules instead.",
     mandatoryPositionals = {},
     useAst = true,
@@ -160,7 +155,8 @@ public class SkylarkNativeModule {
   )
   private static final BuiltinFunction getRules =
       new BuiltinFunction("rules") {
-        public Map<?, ?> invoke(FuncallExpression ast, Environment env)
+        public SkylarkDict<String, SkylarkDict<String, Object>> invoke(
+            FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.rules", ast.getLocation());
           return PackageFactory.callGetRulesFunction(ast, env);
@@ -174,7 +170,7 @@ public class SkylarkNativeModule {
   @SkylarkSignature(
     name = "existing_rules",
     objectType = SkylarkNativeModule.class,
-    returnType = Map.class,
+    returnType = SkylarkDict.class,
     doc =
         "Returns a dict containing all the rules instantiated so far. "
             + "The map key is the name of the rule. The map value is equivalent to the "
@@ -185,7 +181,8 @@ public class SkylarkNativeModule {
   )
   private static final BuiltinFunction existingRules =
       new BuiltinFunction("existing_rules") {
-        public Map<?, ?> invoke(FuncallExpression ast, Environment env)
+        public SkylarkDict<String, SkylarkDict<String, Object>> invoke(
+            FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.existing_rules", ast.getLocation());
           return PackageFactory.callGetRulesFunction(ast, env);
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 aa2fef91d5..6e22fbf269 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
@@ -15,7 +15,6 @@
 package com.google.devtools.build.lib.rules;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.Attribute;
@@ -34,6 +33,7 @@ import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
 import com.google.devtools.build.lib.syntax.Type;
@@ -42,7 +42,6 @@ import com.google.devtools.build.lib.syntax.UserDefinedFunction;
 import com.google.devtools.build.lib.util.FileTypeSet;
 
 import java.util.List;
-import java.util.Map;
 
 /**
  * A helper class to provide Attr module in Skylark.
@@ -106,12 +105,12 @@ public final class SkylarkAttr {
       "the list of allowed values for the attribute. An error is raised if any other "
           + "value is given.";
 
-  private static boolean containsNonNoneKey(Map<String, Object> arguments, String key) {
+  private static boolean containsNonNoneKey(SkylarkDict<String, Object> arguments, String key) {
     return arguments.containsKey(key) && arguments.get(key) != Runtime.NONE;
   }
 
   private static Attribute.Builder<?> createAttribute(
-      Type<?> type, Map<String, Object> arguments, FuncallExpression ast, Environment env)
+      Type<?> type, SkylarkDict<String, Object> arguments, FuncallExpression ast, Environment env)
       throws EvalException, ConversionException {
     // We use an empty name now so that we can set it later.
     // This trick makes sense only in the context of Skylark (builtin rules should not use it).
@@ -192,7 +191,7 @@ public final class SkylarkAttr {
   }
 
   private static Descriptor createAttrDescriptor(
-      Map<String, Object> kwargs, Type<?> type, FuncallExpression ast, Environment env)
+      SkylarkDict<String, Object> kwargs, Type<?> type, FuncallExpression ast, Environment env)
       throws EvalException {
     try {
       return new Descriptor(createAttribute(type, kwargs, ast, env));
@@ -231,15 +230,15 @@ public final class SkylarkAttr {
         public Descriptor invoke(
             Integer defaultInt,
             Boolean mandatory,
-            SkylarkList values,
+            SkylarkList<?> values,
             FuncallExpression ast,
             Environment env)
             throws EvalException {
           // TODO(bazel-team): Replace literal strings with constants.
           env.checkLoadingPhase("attr.int", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
-                  DEFAULT_ARG, defaultInt, MANDATORY_ARG, mandatory, VALUES_ARG, values),
+              EvalUtils.<String, Object>optionMap(
+                  env, DEFAULT_ARG, defaultInt, MANDATORY_ARG, mandatory, VALUES_ARG, values),
               Type.INTEGER,
               ast,
               env);
@@ -276,14 +275,14 @@ public final class SkylarkAttr {
         public Descriptor invoke(
             String defaultString,
             Boolean mandatory,
-            SkylarkList values,
+            SkylarkList<?> values,
             FuncallExpression ast,
             Environment env)
             throws EvalException {
           env.checkLoadingPhase("attr.string", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
-                  DEFAULT_ARG, defaultString, MANDATORY_ARG, mandatory, VALUES_ARG, values),
+              EvalUtils.<String, Object>optionMap(
+                  env, DEFAULT_ARG, defaultString, MANDATORY_ARG, mandatory, VALUES_ARG, values),
               Type.STRING,
               ast,
               env);
@@ -361,7 +360,7 @@ public final class SkylarkAttr {
             Boolean executable,
             Object allowFiles,
             Boolean mandatory,
-            SkylarkList providers,
+            SkylarkList<?> providers,
             Object allowRules,
             Boolean singleFile,
             Object cfg,
@@ -370,7 +369,8 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.label", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
+              EvalUtils.<String, Object>optionMap(
+                  env,
                   DEFAULT_ARG,
                   defaultO,
                   EXECUTABLE_ARG,
@@ -417,7 +417,7 @@ public final class SkylarkAttr {
   private static BuiltinFunction stringList =
       new BuiltinFunction("string_list") {
         public Descriptor invoke(
-            SkylarkList defaultList,
+            SkylarkList<?> defaultList,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -425,8 +425,14 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.string_list", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
-                  DEFAULT_ARG, defaultList, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
+              EvalUtils.<String, Object>optionMap(
+                  env,
+                  DEFAULT_ARG,
+                  defaultList,
+                  MANDATORY_ARG,
+                  mandatory,
+                  NON_EMPTY_ARG,
+                  nonEmpty),
               Type.STRING_LIST,
               ast,
               env);
@@ -457,7 +463,7 @@ public final class SkylarkAttr {
   private static BuiltinFunction intList =
       new BuiltinFunction("int_list") {
         public Descriptor invoke(
-            SkylarkList defaultList,
+            SkylarkList<?> defaultList,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -465,8 +471,14 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.int_list", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
-                  DEFAULT_ARG, defaultList, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
+              EvalUtils.<String, Object>optionMap(
+                  env,
+                  DEFAULT_ARG,
+                  defaultList,
+                  MANDATORY_ARG,
+                  mandatory,
+                  NON_EMPTY_ARG,
+                  nonEmpty),
               Type.INTEGER_LIST,
               ast,
               env);
@@ -547,18 +559,20 @@ public final class SkylarkAttr {
             Object defaultList,
             Object allowFiles,
             Object allowRules,
-            SkylarkList providers,
-            SkylarkList flags,
+            SkylarkList<?> providers,
+            SkylarkList<?> flags,
             Boolean mandatory,
             Boolean nonEmpty,
             Object cfg,
-            SkylarkList aspects,
+            SkylarkList<?> aspects,
             FuncallExpression ast,
             Environment env)
             throws EvalException {
           env.checkLoadingPhase("attr.label_list", ast.getLocation());
-          ImmutableMap<String, Object> kwargs = EvalUtils.optionMap(
-              DEFAULT_ARG, defaultList,
+          SkylarkDict<String, Object> kwargs = EvalUtils.<String, Object>optionMap(
+              env,
+              DEFAULT_ARG,
+              defaultList,
               ALLOW_FILES_ARG,
               allowFiles,
               ALLOW_RULES_ARG,
@@ -576,24 +590,12 @@ public final class SkylarkAttr {
           try {
             Attribute.Builder<?> attribute = createAttribute(
                 BuildType.LABEL_LIST, kwargs, ast, env);
-
-            ImmutableList<SkylarkAspect> skylarkAspects = getSkylarkAspects(aspects);
+            ImmutableList<SkylarkAspect> skylarkAspects =
+                ImmutableList.copyOf(aspects.getContents(SkylarkAspect.class, "aspects"));
             return new Descriptor(attribute, skylarkAspects);
-          } catch (ConversionException e) {
-            throw new EvalException(ast.getLocation(), e.getMessage());
-          }
-        }
-
-        protected ImmutableList<SkylarkAspect> getSkylarkAspects(SkylarkList aspects)
-            throws ConversionException {
-          ImmutableList.Builder<SkylarkAspect> aspectBuilder = ImmutableList.builder();
-          for (Object aspect : aspects) {
-            if (!(aspect instanceof SkylarkAspect)) {
-              throw new ConversionException("Expected a list of aspects for 'aspects'");
-            }
-            aspectBuilder.add((SkylarkAspect) aspect);
+          } catch (EvalException e) {
+            throw new EvalException(ast.getLocation(), e.getMessage(), e);
           }
-          return aspectBuilder.build();
         }
       };
 
@@ -617,7 +619,8 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.bool", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
+              EvalUtils.<String, Object>optionMap(
+                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
               Type.BOOLEAN,
               ast,
               env);
@@ -653,7 +656,8 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.output", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
+              EvalUtils.<String, Object>optionMap(
+                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
               BuildType.OUTPUT,
               ast,
               env);
@@ -694,8 +698,14 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.output_list", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
-                  DEFAULT_ARG, defaultList, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
+              EvalUtils.<String, Object>optionMap(
+                  env,
+                  DEFAULT_ARG,
+                  defaultList,
+                  MANDATORY_ARG,
+                  mandatory,
+                  NON_EMPTY_ARG,
+                  nonEmpty),
               BuildType.OUTPUT_LIST,
               ast,
               env);
@@ -710,7 +720,7 @@ public final class SkylarkAttr {
     objectType = SkylarkAttr.class,
     returnType = Descriptor.class,
     optionalNamedOnly = {
-      @Param(name = DEFAULT_ARG, type = Map.class, defaultValue = "{}", doc = DEFAULT_DOC),
+      @Param(name = DEFAULT_ARG, type = SkylarkDict.class, defaultValue = "{}", doc = DEFAULT_DOC),
       @Param(name = MANDATORY_ARG, type = Boolean.class, defaultValue = "False", doc = MANDATORY_DOC
       ),
       @Param(name = NON_EMPTY_ARG, type = Boolean.class, defaultValue = "False", doc = NON_EMPTY_DOC
@@ -722,7 +732,7 @@ public final class SkylarkAttr {
   private static BuiltinFunction stringDict =
       new BuiltinFunction("string_dict") {
         public Descriptor invoke(
-            Map<?, ?> defaultO,
+            SkylarkDict<?, ?> defaultO,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -730,8 +740,8 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.string_dict", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
-                  DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
+              EvalUtils.<String, Object>optionMap(
+                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
               Type.STRING_DICT,
               ast,
               env);
@@ -746,7 +756,7 @@ public final class SkylarkAttr {
     objectType = SkylarkAttr.class,
     returnType = Descriptor.class,
     optionalNamedOnly = {
-      @Param(name = DEFAULT_ARG, type = Map.class, defaultValue = "{}", doc = DEFAULT_DOC),
+      @Param(name = DEFAULT_ARG, type = SkylarkDict.class, defaultValue = "{}", doc = DEFAULT_DOC),
       @Param(name = MANDATORY_ARG, type = Boolean.class, defaultValue = "False", doc = MANDATORY_DOC
       ),
       @Param(name = NON_EMPTY_ARG, type = Boolean.class, defaultValue = "False", doc = NON_EMPTY_DOC
@@ -758,7 +768,7 @@ public final class SkylarkAttr {
   private static BuiltinFunction stringListDict =
       new BuiltinFunction("string_list_dict") {
         public Descriptor invoke(
-            Map<?, ?> defaultO,
+            SkylarkDict<?, ?> defaultO,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -766,8 +776,8 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.string_list_dict", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(
-                  DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
+              EvalUtils.<String, Object>optionMap(
+                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
               Type.STRING_LIST_DICT,
               ast,
               env);
@@ -796,7 +806,8 @@ public final class SkylarkAttr {
             throws EvalException {
           env.checkLoadingPhase("attr.license", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.optionMap(DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
+              EvalUtils.<String, Object>optionMap(
+                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
               BuildType.LICENSE,
               ast,
               env);
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 bfe75ec7ae..23d6b87b43 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
@@ -69,6 +69,7 @@ import com.google.devtools.build.lib.packages.SkylarkAspectClass;
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.packages.TestSize;
 import com.google.devtools.build.lib.rules.SkylarkAttr.Descriptor;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature.Param;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
@@ -85,6 +86,7 @@ import com.google.devtools.build.lib.syntax.FunctionSignature;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
@@ -224,7 +226,8 @@ public class SkylarkRuleClassFunctions {
             doc = "Whether this rule is a test rule. "
             + "If True, the rule must end with <code>_test</code> (otherwise it must not), "
             + "and there must be an action that generates <code>ctx.outputs.executable</code>."),
-        @Param(name = "attrs", type = Map.class, noneable = true, defaultValue = "None", doc =
+        @Param(name = "attrs", type = SkylarkDict.class, noneable = true, defaultValue = "None",
+            doc =
             "dictionary to declare all the attributes of the rule. It maps from an attribute name "
             + "to an attribute object (see <a href=\"attr.html\">attr</a> module). "
             + "Attributes starting with <code>_</code> are private, and can be used to add "
@@ -233,7 +236,7 @@ public class SkylarkRuleClassFunctions {
             + "<code>deprecation</code>, <code>tags</code>, <code>testonly</code>, and "
             + "<code>features</code> are implicitly added and might be overriden."),
             // TODO(bazel-team): need to give the types of these builtin attributes
-        @Param(name = "outputs", type = Map.class, callbackEnabled = true, noneable = true,
+        @Param(name = "outputs", type = SkylarkDict.class, callbackEnabled = true, noneable = true,
             defaultValue = "None", doc = "outputs of this rule. "
             + "It is a dictionary mapping from string to a template name. "
             + "For example: <code>{\"ext\": \"%{name}.ext\"}</code>. <br>"
@@ -362,7 +365,7 @@ public class SkylarkRuleClassFunctions {
         doc = "List of attribute names.  The aspect propagates along dependencies specified by "
         + " attributes of a target with this name"
       ),
-      @Param(name = "attrs", type = Map.class, noneable = true, defaultValue = "None",
+      @Param(name = "attrs", type = SkylarkDict.class, noneable = true, defaultValue = "None",
         doc = "dictionary to declare all the attributes of the aspect.  "
         + "It maps from an attribute name to an attribute object "
         + "(see <a href=\"attr.html\">attr</a> module). "
@@ -698,6 +701,7 @@ public class SkylarkRuleClassFunctions {
   /**
    * A Skylark value that is a result of 'aspect(..)' function call.
    */
+  @SkylarkModule(name = "aspect", doc = "", documented = false)
   public static final class SkylarkAspect implements SkylarkValue {
     private final BaseFunction implementation;
     private final ImmutableList<String> attributeAspects;
@@ -840,10 +844,12 @@ public class SkylarkRuleClassFunctions {
       return aspectDefinition;
     }
 
+    @Override
     public Label getExtensionLabel() {
       return extensionLabel;
     }
 
+    @Override
     public String getExportedName() {
       return exportedName;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
index c57f48e732..32f812508a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
@@ -52,6 +52,7 @@ import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.FuncallExpression.FuncallException;
 import com.google.devtools.build.lib.syntax.Runtime;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkType;
@@ -152,7 +153,7 @@ public final class SkylarkRuleContext {
 
   private final FragmentCollection hostFragments;
 
-  private final ImmutableMap<String, String> makeVariables;
+  private final SkylarkDict<String, String> makeVariables;
   private final SkylarkRuleAttributesCollection attributesCollection;
   private final SkylarkRuleAttributesCollection ruleAttributesCollection;
 
@@ -517,7 +518,7 @@ public final class SkylarkRuleContext {
 
   @SkylarkCallable(structField = true,
       doc = "Dictionary (String to String) of configuration variables")
-  public ImmutableMap<String, String> var() {
+  public SkylarkDict<String, String> var() {
     return makeVariables;
   }
 
@@ -527,7 +528,7 @@ public final class SkylarkRuleContext {
   }
 
   @SkylarkCallable(doc = "Splits a shell command to a list of tokens.", documented = false)
-  public MutableList tokenize(String optionString) throws FuncallException {
+  public MutableList<String> tokenize(String optionString) throws FuncallException {
     List<String> options = new ArrayList<>();
     try {
       ShellUtils.tokenize(options, optionString);
@@ -544,7 +545,8 @@ public final class SkylarkRuleContext {
           + "Deprecated.",
     documented = false
   )
-  public String expand(@Nullable String expression, SkylarkList artifacts, Label labelResolver)
+  public String expand(
+      @Nullable String expression, SkylarkList<Object> artifacts, Label labelResolver)
       throws EvalException, FuncallException {
     try {
       Map<Label, Iterable<Artifact>> labelMap = new HashMap<>();
@@ -596,7 +598,7 @@ public final class SkylarkRuleContext {
   }
 
   @SkylarkCallable(documented = false)
-  public boolean checkPlaceholders(String template, SkylarkList allowedPlaceholders)
+  public boolean checkPlaceholders(String template, SkylarkList<Object> allowedPlaceholders)
       throws EvalException {
     List<String> actualPlaceHolders = new LinkedList<>();
     Set<String> allowedPlaceholderSet =
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
index 4103b81613..7b69e37684 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
@@ -52,6 +52,7 @@ import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.syntax.Runtime;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
@@ -143,8 +144,8 @@ public class SkylarkRuleImplementationFunctions {
         defaultValue = "None",
         doc =
             "shell command to execute. It is usually preferable to "
-                + "use <code>executable</code> instead. Arguments are available with <code>$1</code>, "
-                + "<code>$2</code>, etc."
+                + "use <code>executable</code> instead. "
+                + "Arguments are available with <code>$1</code>, <code>$2</code>, etc."
       ),
       @Param(
         name = "progress_message",
@@ -163,14 +164,14 @@ public class SkylarkRuleImplementationFunctions {
       ),
       @Param(
         name = "env",
-        type = Map.class,
+        type = SkylarkDict.class,
         noneable = true,
         defaultValue = "None",
         doc = "sets the dictionary of environment variables"
       ),
       @Param(
         name = "execution_requirements",
-        type = Map.class,
+        type = SkylarkDict.class,
         noneable = true,
         defaultValue = "None",
         doc =
@@ -179,7 +180,7 @@ public class SkylarkRuleImplementationFunctions {
       ),
       @Param(
         name = "input_manifests",
-        type = Map.class,
+        type = SkylarkDict.class,
         noneable = true,
         defaultValue = "None",
         doc =
@@ -203,7 +204,7 @@ public class SkylarkRuleImplementationFunctions {
             Boolean useDefaultShellEnv,
             Object envO,
             Object executionRequirementsO,
-            Object inputManifestsO,
+            Object inputManifests,
             Location loc)
             throws EvalException, ConversionException {
           SpawnAction.Builder builder = new SpawnAction.Builder();
@@ -289,14 +290,11 @@ public class SkylarkRuleImplementationFunctions {
                         String.class,
                         "execution_requirements")));
           }
-          if (inputManifestsO != Runtime.NONE) {
+          if (inputManifests instanceof SkylarkDict) {
             for (Map.Entry<PathFragment, Artifact> entry :
-                castMap(
-                        inputManifestsO,
-                        PathFragment.class,
-                        Artifact.class,
-                        "input manifest file map")
-                    .entrySet()) {
+                     ((SkylarkDict<?, ?>) inputManifests)
+                     .getContents(PathFragment.class, Artifact.class, "input manifest file map")
+                     .entrySet()) {
               builder.addInputManifest(entry.getValue(), entry.getKey());
             }
           }
@@ -459,7 +457,7 @@ public class SkylarkRuleImplementationFunctions {
             doc = "the template file"),
         @Param(name = "output", type = Artifact.class,
             doc = "the output file"),
-        @Param(name = "substitutions", type = Map.class,
+        @Param(name = "substitutions", type = SkylarkDict.class,
             doc = "substitutions to make when expanding the template")},
       optionalNamedOnly = {
         @Param(name = "executable", type = Boolean.class,
@@ -467,23 +465,23 @@ public class SkylarkRuleImplementationFunctions {
   private static final BuiltinFunction createTemplateAction =
       new BuiltinFunction("template_action", Arrays.<Object>asList(false)) {
         public TemplateExpansionAction invoke(SkylarkRuleContext ctx,
-            Artifact template, Artifact output, Map<?, ?> substitutionsO, Boolean executable)
+            Artifact template, Artifact output, SkylarkDict<?, ?> substitutions, Boolean executable)
             throws EvalException, ConversionException {
-          ImmutableList.Builder<Substitution> substitutions = ImmutableList.builder();
-          for (Map.Entry<String, String> substitution : castMap(
-              substitutionsO, String.class, String.class, "substitutions").entrySet()) {
+          ImmutableList.Builder<Substitution> substitutionsBuilder = ImmutableList.builder();
+          for (Map.Entry<String, String> substitution : substitutions.getContents(
+              String.class, String.class, "substitutions").entrySet()) {
             // ParserInputSource.create(Path) uses Latin1 when reading BUILD files, which might
             // contain UTF-8 encoded symbols as part of template substitution.
             // As a quick fix, the substitution values are corrected before being passed on.
             // In the long term, fixing ParserInputSource.create(Path) would be a better approach.
-            substitutions.add(Substitution.of(
+            substitutionsBuilder.add(Substitution.of(
                 substitution.getKey(), convertLatin1ToUtf8(substitution.getValue())));
           }
           TemplateExpansionAction action = new TemplateExpansionAction(
               ctx.getRuleContext().getActionOwner(),
               template,
               output,
-              substitutions.build(),
+              substitutionsBuilder.build(),
               executable);
           ctx.getRuleContext().registerAction(action);
           return action;
@@ -574,7 +572,8 @@ public class SkylarkRuleImplementationFunctions {
 
   // TODO(bazel-team): find a better way to typecheck this argument.
   @SuppressWarnings("unchecked")
-  private static Map<Label, Iterable<Artifact>> checkLabelDict(Map<?, ?> labelDict, Location loc)
+  private static Map<Label, Iterable<Artifact>> checkLabelDict(
+      Map<?, ?> labelDict, Location loc)
       throws EvalException {
     for (Map.Entry<?, ?> entry : labelDict.entrySet()) {
       Object key = entry.getKey();
@@ -633,7 +632,7 @@ public class SkylarkRuleImplementationFunctions {
       ),
       @Param(
         name = "make_variables",
-        type = Map.class, // dict(string, string)
+        type = SkylarkDict.class, // dict(string, string)
         noneable = true,
         doc = "make variables to expand, or None"
       ),
@@ -646,7 +645,7 @@ public class SkylarkRuleImplementationFunctions {
       ),
       @Param(
         name = "label_dict",
-        type = Map.class,
+        type = SkylarkDict.class,
         defaultValue = "{}",
         doc =
             "dictionary of resolved labels and the corresponding list of Files "
@@ -658,24 +657,24 @@ public class SkylarkRuleImplementationFunctions {
   private static final BuiltinFunction resolveCommand =
       new BuiltinFunction("resolve_command") {
         @SuppressWarnings("unchecked")
-        public Tuple invoke(
+        public Tuple<Object> invoke(
             SkylarkRuleContext ctx,
             String command,
             Object attributeO,
             Boolean expandLocations,
             Object makeVariablesO,
             SkylarkList tools,
-            Map<?, ?> labelDictM,
+            SkylarkDict<?, ?> labelDict,
             Location loc,
             Environment env)
             throws ConversionException, EvalException {
           Label ruleLabel = ctx.getLabel();
-          Map<Label, Iterable<Artifact>> labelDict = checkLabelDict(labelDictM, loc);
+          Map<Label, Iterable<Artifact>> labelDictM = checkLabelDict(labelDict, loc);
           // The best way to fix this probably is to convert CommandHelper to Skylark.
           CommandHelper helper = new CommandHelper(
               ctx.getRuleContext(),
               tools.getContents(TransitiveInfoCollection.class, "tools"),
-              ImmutableMap.copyOf(labelDict));
+              ImmutableMap.copyOf(labelDictM));
           String attribute = Type.STRING.convertOptional(attributeO, "attribute", ruleLabel);
           if (expandLocations) {
             command = helper.resolveCommandAndExpandLabels(
@@ -689,7 +688,7 @@ public class SkylarkRuleImplementationFunctions {
           List<Artifact> inputs = new ArrayList<>();
           inputs.addAll(helper.getResolvedTools());
           List<String> argv = helper.buildCommandLine(command, inputs, SCRIPT_SUFFIX);
-          return Tuple.of(
+          return Tuple.<Object>of(
               new MutableList(inputs, env),
               new MutableList(argv, env),
               helper.getRemoteRunfileManifestMap());
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java
index 9ceb880118..b5680bf576 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java
@@ -315,7 +315,7 @@ public abstract class AbstractComprehension extends Expression {
 
   @Override
   Object doEval(Environment env) throws EvalException, InterruptedException {
-    OutputCollector collector = createCollector();
+    OutputCollector collector = createCollector(env);
     evalStep(env, collector, 0);
     return collector.getResult(env);
   }
@@ -375,7 +375,7 @@ public abstract class AbstractComprehension extends Expression {
    */
   abstract String printExpressions();
 
-  abstract OutputCollector createCollector();
+  abstract OutputCollector createCollector(Environment env);
 
   /**
    * Add byte code which initializes the collection and returns the variable it is saved in.
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
index 662ac2f259..942bf92657 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
@@ -15,7 +15,6 @@ package com.google.devtools.build.lib.syntax;
 
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Ordering;
 import com.google.common.collect.Sets;
@@ -30,7 +29,6 @@ import com.google.devtools.build.lib.util.Preconditions;
 import net.bytebuddy.implementation.bytecode.StackManipulation;
 
 import java.util.ArrayList;
-import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
@@ -205,7 +203,7 @@ public abstract class BaseFunction implements SkylarkValue {
    */
   public Object[] processArguments(List<Object> args,
       @Nullable Map<String, Object> kwargs,
-      @Nullable Location loc)
+      @Nullable Location loc, @Nullable Environment env)
       throws EvalException {
 
     Object[] arguments = new Object[getArgArraySize()];
@@ -241,7 +239,7 @@ public abstract class BaseFunction implements SkylarkValue {
             Tuple.copyOf(args.subList(numPositionalParams, numPositionalArgs));
         numPositionalArgs = numPositionalParams; // clip numPositionalArgs
       } else {
-        arguments[starParamIndex] = Tuple.EMPTY;
+        arguments[starParamIndex] = Tuple.empty();
       }
     } else if (numPositionalArgs > numPositionalParams) {
       throw new EvalException(loc,
@@ -280,7 +278,7 @@ public abstract class BaseFunction implements SkylarkValue {
       // If there's a kwParam, it's empty.
       if (hasKwParam) {
         // TODO(bazel-team): create a fresh mutable dict, like Python does
-        arguments[kwParamIndex] = ImmutableMap.<String, Object>of();
+        arguments[kwParamIndex] = SkylarkDict.of(env);
       }
     } else if (hasKwParam && numNamedParams == 0) {
       // Easy case (2b): there are no named parameters, but there is a **kwParam.
@@ -288,18 +286,21 @@ public abstract class BaseFunction implements SkylarkValue {
       // Note that *starParam and **kwParam themselves don't count as named.
       // Also note that no named parameters means no mandatory parameters that weren't passed,
       // and no missing optional parameters for which to use a default. Thus, no loops.
-      // TODO(bazel-team): create a fresh mutable dict, like Python does
-      arguments[kwParamIndex] = kwargs; // NB: not 2a means kwarg isn't null
+      // NB: not 2a means kwarg isn't null
+      arguments[kwParamIndex] = SkylarkDict.copyOf(env, kwargs);
     } else {
       // Hard general case (2c): some keyword arguments may correspond to named parameters
-      HashMap<String, Object> kwArg = hasKwParam ? new HashMap<String, Object>() : null;
+      SkylarkDict<String, Object> kwArg = hasKwParam
+          ? SkylarkDict.<String, Object>of(env) : SkylarkDict.<String, Object>empty();
 
       // For nicer stabler error messages, start by checking against
       // an argument being provided both as positional argument and as keyword argument.
       ArrayList<String> bothPosKey = new ArrayList<>();
       for (int i = 0; i < numPositionalArgs; i++) {
         String name = names.get(i);
-        if (kwargs.containsKey(name)) { bothPosKey.add(name); }
+        if (kwargs.containsKey(name)) {
+          bothPosKey.add(name);
+        }
       }
       if (!bothPosKey.isEmpty()) {
         throw new EvalException(loc,
@@ -325,12 +326,12 @@ public abstract class BaseFunction implements SkylarkValue {
             throw new EvalException(loc, String.format(
                 "%s got multiple values for keyword argument '%s'", this, keyword));
           }
-          kwArg.put(keyword, value);
+          kwArg.put(keyword, value, loc, env);
         }
       }
       if (hasKwParam) {
         // TODO(bazel-team): create a fresh mutable dict, like Python does
-        arguments[kwParamIndex] = ImmutableMap.copyOf(kwArg);
+        arguments[kwParamIndex] = SkylarkDict.copyOf(env, kwArg);
       }
 
       // Check that all mandatory parameters were filled in general case 2c.
@@ -436,7 +437,7 @@ public abstract class BaseFunction implements SkylarkValue {
     // ast is null when called from Java (as there's no Skylark call site).
     Location loc = ast == null ? Location.BUILTIN : ast.getLocation();
 
-    Object[] arguments = processArguments(args, kwargs, loc);
+    Object[] arguments = processArguments(args, kwargs, loc, env);
     canonicalizeArguments(arguments, loc);
 
     return call(arguments, ast, env);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
index fc1fe9afbb..a31b037601 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.syntax;
 import static com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils.append;
 
 import com.google.common.base.Strings;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
@@ -37,13 +36,10 @@ import net.bytebuddy.implementation.bytecode.Removal;
 import net.bytebuddy.implementation.bytecode.StackManipulation;
 
 import java.util.ArrayList;
-import java.util.Collection;
 import java.util.Collections;
 import java.util.EnumSet;
 import java.util.IllegalFormatException;
-import java.util.LinkedHashMap;
 import java.util.List;
-import java.util.Map;
 
 /**
  * Syntax node for a binary operator expression.
@@ -108,10 +104,8 @@ public final class BinaryOperatorExpression extends Expression {
         }
       }
       return false;
-    } else if (rval instanceof Collection<?>) {
-      return ((Collection<?>) rval).contains(lval);
-    } else if (rval instanceof Map<?, ?>) {
-      return ((Map<?, ?>) rval).containsKey(lval);
+    } else if (rval instanceof SkylarkDict) {
+      return ((SkylarkDict<?, ?>) rval).containsKey(lval);
     } else if (rval instanceof SkylarkNestedSet) {
       return ((SkylarkNestedSet) rval).expandedSet().contains(lval);
     } else if (rval instanceof String) {
@@ -340,13 +334,8 @@ public final class BinaryOperatorExpression extends Expression {
       return MutableList.concat((MutableList) lval, (MutableList) rval, env);
     }
 
-    if (lval instanceof Map<?, ?> && rval instanceof Map<?, ?>) {
-      Map<?, ?> ldict = (Map<?, ?>) lval;
-      Map<?, ?> rdict = (Map<?, ?>) rval;
-      Map<Object, Object> result = new LinkedHashMap<>(ldict.size() + rdict.size());
-      result.putAll(ldict);
-      result.putAll(rdict);
-      return ImmutableMap.copyOf(result);
+    if (lval instanceof SkylarkDict && rval instanceof SkylarkDict) {
+      return SkylarkDict.plus((SkylarkDict<?, ?>) lval, (SkylarkDict<?, ?>) rval, env);
     }
 
     if (lval instanceof SkylarkClassObject && rval instanceof SkylarkClassObject) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
index c85cc234c8..349e8f53ea 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
@@ -25,10 +25,8 @@ import com.google.devtools.build.lib.syntax.compiler.VariableScope;
 
 import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
 import net.bytebuddy.implementation.bytecode.Duplication;
-import net.bytebuddy.implementation.bytecode.Removal;
 
 import java.util.ArrayList;
-import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 
@@ -51,14 +49,14 @@ public class DictComprehension extends AbstractComprehension {
   }
 
   @Override
-  OutputCollector createCollector() {
-    return new DictOutputCollector();
+  OutputCollector createCollector(Environment env) {
+    return new DictOutputCollector(env);
   }
 
   @Override
   InternalVariable compileInitialization(VariableScope scope, List<ByteCodeAppender> code) {
     InternalVariable dict = scope.freshVariable(ImmutableMap.class);
-    append(code, ByteCodeMethodCalls.BCImmutableMap.builder);
+    append(code, scope.loadEnvironment(), ByteCodeMethodCalls.BCSkylarkDict.of);
     code.add(dict.store());
     return dict;
   }
@@ -75,14 +73,16 @@ public class DictComprehension extends AbstractComprehension {
     code.add(keyExpression.compile(scope, debugInfo));
     append(code, Duplication.SINGLE, EvalUtils.checkValidDictKey);
     code.add(valueExpression.compile(scope, debugInfo));
-    append(code, ByteCodeMethodCalls.BCImmutableMap.Builder.put, Removal.SINGLE);
+    append(code,
+        debugInfo.add(this).loadLocation,
+        scope.loadEnvironment(),
+        ByteCodeMethodCalls.BCSkylarkDict.put);
     return ByteCodeUtils.compoundAppender(code);
   }
 
   @Override
   ByteCodeAppender compileBuilding(VariableScope scope, InternalVariable collection) {
-    return new ByteCodeAppender.Simple(
-        collection.load(), ByteCodeMethodCalls.BCImmutableMap.Builder.build);
+    return new ByteCodeAppender.Simple(collection.load());
   }
 
   /**
@@ -90,23 +90,23 @@ public class DictComprehension extends AbstractComprehension {
    * provides access to the resulting {@link Map}.
    */
   private final class DictOutputCollector implements OutputCollector {
-    private final Map<Object, Object> result;
+    private final SkylarkDict<Object, Object> result;
 
-    DictOutputCollector() {
+    DictOutputCollector(Environment env) {
       // We want to keep the iteration order
-      result = new LinkedHashMap<>();
+      result = SkylarkDict.<Object, Object>of(env);
     }
 
     @Override
     public void evaluateAndCollect(Environment env) throws EvalException, InterruptedException {
       Object key = keyExpression.eval(env);
       EvalUtils.checkValidDictKey(key);
-      result.put(key, valueExpression.eval(env));
+      result.put(key, valueExpression.eval(env), getLocation(), env);
     }
 
     @Override
     public Object getResult(Environment env) throws EvalException {
-      return ImmutableMap.copyOf(result);
+      return result;
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java b/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java
index 8a223ed582..3ab31263f1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java
@@ -16,7 +16,7 @@ package com.google.devtools.build.lib.syntax;
 import static com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils.append;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeMethodCalls;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
 import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
@@ -26,9 +26,7 @@ import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
 import net.bytebuddy.implementation.bytecode.Duplication;
 
 import java.util.ArrayList;
-import java.util.LinkedHashMap;
 import java.util.List;
-import java.util.Map;
 
 /**
  * Syntax node for dictionary literals.
@@ -81,18 +79,17 @@ public class DictionaryLiteral extends Expression {
 
   @Override
   Object doEval(Environment env) throws EvalException, InterruptedException {
-    // We need LinkedHashMap to maintain the order during iteration (e.g. for loops)
-    Map<Object, Object> map = new LinkedHashMap<>();
+    SkylarkDict<Object, Object> dict = SkylarkDict.<Object, Object>of(env);
+    Location loc = getLocation();
     for (DictionaryEntryLiteral entry : entries) {
       if (entry == null) {
-        throw new EvalException(getLocation(), "null expression in " + this);
+        throw new EvalException(loc, "null expression in " + this);
       }
       Object key = entry.key.eval(env);
-      EvalUtils.checkValidDictKey(key);
       Object val = entry.value.eval(env);
-      map.put(key, val);
+      dict.put(key, val, loc, env);
     }
-    return ImmutableMap.copyOf(map);
+    return dict;
   }
 
   @Override
@@ -129,16 +126,18 @@ public class DictionaryLiteral extends Expression {
   @Override
   ByteCodeAppender compile(VariableScope scope, DebugInfo debugInfo) throws EvalException {
     List<ByteCodeAppender> code = new ArrayList<>();
-    append(code, ByteCodeMethodCalls.BCImmutableMap.builder);
-
+    append(code, scope.loadEnvironment());
+    append(code, ByteCodeMethodCalls.BCSkylarkDict.of);
     for (DictionaryEntryLiteral entry : entries) {
+      append(code, Duplication.SINGLE); // duplicate the dict
       code.add(entry.key.compile(scope, debugInfo));
       append(code, Duplication.SINGLE, EvalUtils.checkValidDictKey);
       code.add(entry.value.compile(scope, debugInfo));
-      // add it to the builder which is already on the stack and returns itself
-      append(code, ByteCodeMethodCalls.BCImmutableMap.Builder.put);
+      append(code,
+          debugInfo.add(this).loadLocation,
+          scope.loadEnvironment(),
+          ByteCodeMethodCalls.BCSkylarkDict.put);
     }
-    append(code, ByteCodeMethodCalls.BCImmutableMap.Builder.build);
     return ByteCodeUtils.compoundAppender(code);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index 0d001d3016..c462098373 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -33,7 +33,6 @@ import net.bytebuddy.implementation.bytecode.StackManipulation;
 import java.util.Collection;
 import java.util.List;
 import java.util.Map;
-import java.util.Set;
 
 /**
  * Utilities used by the evaluator.
@@ -83,17 +82,21 @@ public final class EvalUtils {
       try {
         return ((Comparable<Object>) o1).compareTo(o2);
       } catch (ClassCastException e) {
-        try {
-          // Different types -> let the class names decide
-          return o1.getClass().getName().compareTo(o2.getClass().getName());
-        } catch (NullPointerException ex) {
-          throw new ComparisonException(
-              "Cannot compare " + getDataTypeName(o1) + " with " + EvalUtils.getDataTypeName(o2));
-        }
+        return compareByClass(o1, o2);
       }
     }
   };
 
+  public static final int compareByClass(Object o1, Object o2) {
+    try {
+      // Different types -> let the class names decide
+      return o1.getClass().getName().compareTo(o2.getClass().getName());
+    } catch (NullPointerException ex) {
+      throw new ComparisonException(
+          "Cannot compare " + getDataTypeName(o1) + " with " + EvalUtils.getDataTypeName(o2));
+    }
+  }
+
   public static final StackManipulation checkValidDictKey =
       ByteCodeUtils.invoke(EvalUtils.class, "checkValidDictKey", Object.class);
 
@@ -205,30 +208,25 @@ public final class EvalUtils {
    * @return a super-class of c to be used in validation-time type inference.
    */
   public static Class<?> getSkylarkType(Class<?> c) {
-    if (SkylarkList.class.isAssignableFrom(c)) {
+    // TODO(bazel-team): replace these with SkylarkValue-s
+    if (String.class.equals(c)
+        || Boolean.class.equals(c)
+        || Integer.class.equals(c)
+        || Iterable.class.equals(c)
+        || Class.class.equals(c)) {
       return c;
-    } else if (ImmutableList.class.isAssignableFrom(c)) {
-      return ImmutableList.class;
-    } else if (List.class.isAssignableFrom(c)) {
-      return List.class;
-    } else if (Map.class.isAssignableFrom(c)) {
-      return Map.class;
-    } else if (NestedSet.class.isAssignableFrom(c)) {
-      // This could be removed probably
-      return NestedSet.class;
-    } else if (Set.class.isAssignableFrom(c)) {
-      return Set.class;
-    } else {
-      // TODO(bazel-team): also unify all implementations of ClassObject,
-      // that we used to all print the same as "struct"?
-      //
-      // Check if one of the superclasses or implemented interfaces has the SkylarkModule
-      // annotation. If yes return that class.
-      Class<?> parent = getParentWithSkylarkModule(c);
-      if (parent != null) {
-        return parent;
-      }
     }
+    // TODO(bazel-team): also unify all implementations of ClassObject,
+    // that we used to all print the same as "struct"?
+    //
+    // Check if one of the superclasses or implemented interfaces has the SkylarkModule
+    // annotation. If yes return that class.
+    Class<?> parent = getParentWithSkylarkModule(c);
+    if (parent != null) {
+      return parent;
+    }
+    Preconditions.checkArgument(SkylarkValue.class.isAssignableFrom(c),
+        "%s is not allowed as a Skylark value", c);
     return c;
   }
 
@@ -283,8 +281,10 @@ public final class EvalUtils {
       return "int";
     } else if (c.equals(Boolean.class)) {
       return "bool";
-    } else if (Map.class.isAssignableFrom(c)) {
-      return "dict";
+    } else if (List.class.isAssignableFrom(c)) { // This is a Java List that isn't a SkylarkList
+      return "List"; // This case shouldn't happen in normal code, but we keep it for debugging.
+    } else if (Map.class.isAssignableFrom(c)) { // This is a Java Map that isn't a SkylarkDict
+      return "Map"; // This case shouldn't happen in normal code, but we keep it for debugging.
     } else if (BaseFunction.class.isAssignableFrom(c)) {
       return "function";
     } else if (c.equals(SelectorValue.class)) {
@@ -416,8 +416,9 @@ public final class EvalUtils {
   }
 
   /**
-   * Build a map of kwarg arguments from a list, removing null-s or None-s.
+   * Build a SkylarkDict of kwarg arguments from a list, removing null-s or None-s.
    *
+   * @param env the Environment in which this map can be mutated.
    * @param init a series of key, value pairs (as consecutive arguments)
    *   as in {@code optionMap(k1, v1, k2, v2, k3, v3)}
    *   where each key is a String, each value is an arbitrary Objet.
@@ -429,16 +430,16 @@ public final class EvalUtils {
    * Keys cannot be null.
    */
   @SuppressWarnings("unchecked")
-  public static ImmutableMap<String, Object> optionMap(Object... init) {
-    ImmutableMap.Builder<String, Object> b = new ImmutableMap.Builder<>();
+  public static <K, V> SkylarkDict<K, V> optionMap(Environment env, Object... init) {
+    ImmutableMap.Builder<K, V> b = new ImmutableMap.Builder<>();
     Preconditions.checkState(init.length % 2 == 0);
     for (int i = init.length - 2; i >= 0; i -= 2) {
-      String key = (String) Preconditions.checkNotNull(init[i]);
-      Object value = init[i + 1];
+      K key = (K) Preconditions.checkNotNull(init[i]);
+      V value = (V) init[i + 1];
       if (!isNullOrNone(value)) {
         b.put(key, value);
       }
     }
-    return b.build();
+    return SkylarkDict.<K, V>copyOf(env, b.build());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java b/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
index f2543cb581..b858d35ed5 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
@@ -27,7 +27,6 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;
-import java.util.Map;
 import java.util.Set;
 
 import javax.annotation.Nullable;
@@ -150,7 +149,7 @@ public abstract class FunctionSignature implements Serializable {
         parameters.add(Tuple.class);
       }
       if (hasKwArg()) {
-        parameters.add(Map.class);
+        parameters.add(SkylarkDict.class);
       }
 
       return parameters;
@@ -412,7 +411,9 @@ public abstract class FunctionSignature implements Serializable {
         private int j = 0;
 
         public void comma() {
-          if (isMore) { sb.append(", "); }
+          if (isMore) {
+            sb.append(", ");
+          }
           isMore = true;
         }
         public void type(int i) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
index 1f031d9cc2..729dd0c160 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.syntax;
 
 import static com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils.append;
 
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
 import com.google.devtools.build.lib.syntax.compiler.DebugInfo.AstAccessors;
@@ -32,9 +31,7 @@ import java.io.Serializable;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
-import java.util.LinkedHashMap;
 import java.util.List;
-import java.util.Map;
 
 /**
  * Class representing an LValue.
@@ -106,23 +103,20 @@ public class LValue implements Serializable {
 
   // Since dict is still immutable, the expression 'a[x] = b' creates a new dictionary and
   // assigns it to 'a'.
-  // TODO(bazel-team): make dict mutable - this function should be O(1) instead of O(n).
+  @SuppressWarnings("unchecked")
   private static void assignItem(
       Environment env, Location loc, Identifier ident, Object key, Object value)
       throws EvalException, InterruptedException {
     Object o = ident.eval(env);
-    if (!(o instanceof Map)) {
+    if (!(o instanceof SkylarkDict)) {
       throw new EvalException(
           loc,
           "can only assign an element in a dictionary, not in a '"
               + EvalUtils.getDataTypeName(o)
               + "'");
     }
-    Map<?, ?> dict = (Map<?, ?>) o;
-    Map<Object, Object> result = new LinkedHashMap<>(dict.size() + 1);
-    result.putAll(dict);
-    result.put(key, value);
-    env.update(ident.getName(), ImmutableMap.copyOf(result));
+    SkylarkDict<Object, Object> dict = (SkylarkDict<Object, Object>) o;
+    dict.put(key, value, loc, env);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
index 749b056f84..cfcbe12a97 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
@@ -48,7 +48,7 @@ public final class ListComprehension extends AbstractComprehension {
   }
 
   @Override
-  OutputCollector createCollector() {
+  OutputCollector createCollector(Environment env) {
     return new ListOutputCollector();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index b552c1108d..52231c9a92 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -35,13 +35,11 @@ import com.google.devtools.build.lib.syntax.Type.ConversionException;
 import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.Iterator;
-import java.util.LinkedHashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;
-import java.util.TreeMap;
 import java.util.TreeSet;
 import java.util.concurrent.ExecutionException;
 import java.util.regex.Matcher;
@@ -107,7 +105,7 @@ public class MethodLibrary {
         @Param(name = "self", type = String.class, doc = "This string, a separator."),
         @Param(name = "elements", type = SkylarkList.class, doc = "The objects to join.")})
   private static BuiltinFunction join = new BuiltinFunction("join") {
-    public String invoke(String self, SkylarkList elements) throws ConversionException {
+    public String invoke(String self, SkylarkList<?> elements) throws ConversionException {
       return Joiner.on(self).join(elements);
     }
   };
@@ -283,13 +281,13 @@ public class MethodLibrary {
       useEnvironment = true,
       useLocation = true)
   private static BuiltinFunction split = new BuiltinFunction("split") {
-    public MutableList invoke(String self, String sep, Object maxSplitO, Location loc,
+    public MutableList<String> invoke(String self, String sep, Object maxSplitO, Location loc,
         Environment env) throws ConversionException, EvalException {
       int maxSplit = Type.INTEGER.convertOptional(
           maxSplitO, "'split' argument of 'split'", /*label*/null, -2);
       // + 1 because the last result is the remainder, and default of -2 so that after +1 it's -1
       String[] ss = Pattern.compile(sep, Pattern.LITERAL).split(self, maxSplit + 1);
-      return MutableList.of(env, (Object[]) ss);
+      return MutableList.of(env, ss);
     }
   };
 
@@ -308,13 +306,11 @@ public class MethodLibrary {
       useLocation = true)
   private static BuiltinFunction rsplit = new BuiltinFunction("rsplit") {
     @SuppressWarnings("unused")
-    public MutableList invoke(
+    public MutableList<String> invoke(
         String self, String sep, Object maxSplitO, Location loc, Environment env)
         throws ConversionException, EvalException {
       int maxSplit =
           Type.INTEGER.convertOptional(maxSplitO, "'split' argument of 'split'", null, -1);
-      List<String> result;
-
       try {
         return stringRSplit(self, sep, maxSplit, env);
       } catch (IllegalArgumentException ex) {
@@ -335,7 +331,7 @@ public class MethodLibrary {
    * @return A list of words
    * @throws IllegalArgumentException
    */
-  private static MutableList stringRSplit(
+  private static MutableList<String> stringRSplit(
       String input, String separator, int maxSplits, Environment env)
       throws IllegalArgumentException {
     if (separator.isEmpty()) {
@@ -385,7 +381,7 @@ public class MethodLibrary {
       useLocation = true)
   private static BuiltinFunction partition = new BuiltinFunction("partition") {
     @SuppressWarnings("unused")
-    public MutableList invoke(String self, String sep, Location loc, Environment env)
+    public MutableList<String> invoke(String self, String sep, Location loc, Environment env)
         throws EvalException {
       return partitionWrapper(self, sep, true, env, loc);
     }
@@ -405,7 +401,7 @@ public class MethodLibrary {
       useLocation = true)
   private static BuiltinFunction rpartition = new BuiltinFunction("rpartition") {
     @SuppressWarnings("unused")
-    public MutableList invoke(String self, String sep, Location loc, Environment env)
+    public MutableList<String> invoke(String self, String sep, Location loc, Environment env)
         throws EvalException {
       return partitionWrapper(self, sep, false, env, loc);
     }
@@ -423,7 +419,8 @@ public class MethodLibrary {
    * @param loc The location that is used for potential exceptions
    * @return A list with three elements
    */
-  private static MutableList partitionWrapper(String self, String separator, boolean forward,
+  private static MutableList<String> partitionWrapper(
+      String self, String separator, boolean forward,
       Environment env, Location loc) throws EvalException {
     try {
       return new MutableList(stringPartition(self, separator, forward), env);
@@ -652,7 +649,7 @@ public class MethodLibrary {
               doc = "Whether the line breaks should be included in the resulting list.")})
   private static BuiltinFunction splitLines = new BuiltinFunction("splitlines") {
     @SuppressWarnings("unused")
-    public MutableList invoke(String self, Boolean keepEnds) throws EvalException {
+    public MutableList<String> invoke(String self, Boolean keepEnds) throws EvalException {
       List<String> result = new ArrayList<>();
       Matcher matcher = SPLIT_LINES_PATTERN.matcher(self);
       while (matcher.find()) {
@@ -890,13 +887,16 @@ public class MethodLibrary {
           @Param(name = "args", type = SkylarkList.class, defaultValue = "()",
               doc = "List of arguments"),
       },
-      extraKeywords = {@Param(name = "kwargs", doc = "Dictionary of arguments")},
+      extraKeywords = {@Param(name = "kwargs", type = SkylarkDict.class, defaultValue = "{}",
+            doc = "Dictionary of arguments")},
       useLocation = true)
   private static BuiltinFunction format = new BuiltinFunction("format") {
     @SuppressWarnings("unused")
-    public String invoke(String self, SkylarkList args, Map<String, Object> kwargs, Location loc)
+    public String invoke(String self, SkylarkList<Object> args, SkylarkDict<?, ?> kwargs,
+        Location loc)
         throws ConversionException, EvalException {
-      return new FormatParser(loc).format(self, args.getImmutableList(), kwargs);
+      return new FormatParser(loc).format(
+          self, args.getImmutableList(), kwargs.getContents(String.class, Object.class, "kwargs"));
     }
   };
 
@@ -977,8 +977,8 @@ public class MethodLibrary {
   private static BuiltinFunction mutableListSlice =
       new BuiltinFunction("$slice") {
         @SuppressWarnings("unused") // Accessed via Reflection.
-        public MutableList invoke(
-            MutableList self, Object start, Object end, Integer step, Location loc,
+        public MutableList<Object> invoke(
+            MutableList<Object> self, Object start, Object end, Integer step, Location loc,
             Environment env)
             throws EvalException, ConversionException {
           return new MutableList(sliceList(self, start, end, step, loc), env);
@@ -1006,7 +1006,8 @@ public class MethodLibrary {
   private static BuiltinFunction tupleSlice =
       new BuiltinFunction("$slice") {
         @SuppressWarnings("unused") // Accessed via Reflection.
-        public Tuple invoke(Tuple self, Object start, Object end, Integer step, Location loc)
+        public Tuple<Object> invoke(
+            Tuple<Object> self, Object start, Object end, Integer step, Location loc)
             throws EvalException, ConversionException {
           return Tuple.copyOf(sliceList(self, start, end, step, loc));
         }
@@ -1092,7 +1093,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction min = new BuiltinFunction("min") {
     @SuppressWarnings("unused") // Accessed via Reflection.
-    public Object invoke(SkylarkList args, Location loc) throws EvalException {
+    public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
       return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR.reverse(), loc);
     }
   };
@@ -1110,7 +1111,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction max = new BuiltinFunction("max") {
     @SuppressWarnings("unused") // Accessed via Reflection.
-    public Object invoke(SkylarkList args, Location loc) throws EvalException {
+    public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
       return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR, loc);
     }
   };
@@ -1118,7 +1119,7 @@ public class MethodLibrary {
   /**
    * Returns the maximum element from this list, as determined by maxOrdering.
    */
-  private static Object findExtreme(SkylarkList args, Ordering<Object> maxOrdering, Location loc)
+  private static Object findExtreme(SkylarkList<?> args, Ordering<Object> maxOrdering, Location loc)
       throws EvalException {
     // Args can either be a list of elements or a list whose first element is a non-empty iterable
     // of elements.
@@ -1133,7 +1134,7 @@ public class MethodLibrary {
    * This method returns the first element of the list, if that particular element is an
    * Iterable<?>. Otherwise, it will return the entire list.
    */
-  private static Iterable<?> getIterable(SkylarkList list, Location loc) throws EvalException {
+  private static Iterable<?> getIterable(SkylarkList<?> list, Location loc) throws EvalException {
     return (list.size() == 1) ? EvalUtils.toIterable(list.get(0), loc) : list;
   }
 
@@ -1195,7 +1196,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction sorted =
       new BuiltinFunction("sorted") {
-        public MutableList invoke(Object self, Location loc, Environment env)
+        public <E> MutableList<E> invoke(Object self, Location loc, Environment env)
             throws EvalException, ConversionException {
           try {
             return new MutableList(
@@ -1224,10 +1225,10 @@ public class MethodLibrary {
   private static BuiltinFunction reversed =
       new BuiltinFunction("reversed") {
         @SuppressWarnings("unused") // Accessed via Reflection.
-        public MutableList invoke(Object sequence, Location loc, Environment env)
+        public MutableList<?> invoke(Object sequence, Location loc, Environment env)
             throws EvalException {
           // We only allow lists and strings.
-          if (sequence instanceof Map) {
+          if (sequence instanceof SkylarkDict) {
             throw new EvalException(
                 loc, "Argument to reversed() must be a sequence, not a dictionary.");
           } else if (sequence instanceof NestedSet || sequence instanceof SkylarkNestedSet) {
@@ -1254,7 +1255,7 @@ public class MethodLibrary {
     useEnvironment = true)
   private static BuiltinFunction append =
       new BuiltinFunction("append") {
-        public Runtime.NoneType invoke(MutableList self, Object item,
+        public Runtime.NoneType invoke(MutableList<Object> self, Object item,
             Location loc, Environment env) throws EvalException, ConversionException {
           self.add(item, loc, env);
           return Runtime.NONE;
@@ -1273,7 +1274,7 @@ public class MethodLibrary {
     useEnvironment = true)
   private static BuiltinFunction extend =
       new BuiltinFunction("extend") {
-        public Runtime.NoneType invoke(MutableList self, SkylarkList items,
+        public Runtime.NoneType invoke(MutableList<Object> self, SkylarkList<Object> items,
             Location loc, Environment env) throws EvalException, ConversionException {
           self.addAll(items, loc, env);
           return Runtime.NONE;
@@ -1295,7 +1296,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction listIndex =
       new BuiltinFunction("index") {
-        public Integer invoke(MutableList self, Object x, Location loc) throws EvalException {
+        public Integer invoke(MutableList<?> self, Object x, Location loc) throws EvalException {
           int i = 0;
           for (Object obj : self) {
             if (obj.equals(x)) {
@@ -1323,7 +1324,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction listRemove =
       new BuiltinFunction("remove") {
-        public Runtime.NoneType invoke(MutableList self, Object x, Location loc, Environment env)
+        public Runtime.NoneType invoke(MutableList<?> self, Object x, Location loc, Environment env)
             throws EvalException {
           for (int i = 0; i < self.size(); i++) {
             if (self.get(i).equals(x)) {
@@ -1359,7 +1360,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction listPop =
       new BuiltinFunction("pop") {
-        public Object invoke(MutableList self, Object i, Location loc, Environment env)
+        public Object invoke(MutableList<?> self, Object i, Location loc, Environment env)
             throws EvalException {
           int arg = i == Runtime.NONE ? -1 : (Integer) i;
           int index = getListIndex(arg, self.size(), loc);
@@ -1370,14 +1371,14 @@ public class MethodLibrary {
       };
 
   // dictionary access operator
-  @SkylarkSignature(name = "$index", documented = false, objectType = Map.class,
+  @SkylarkSignature(name = "$index", documented = false, objectType = SkylarkDict.class,
       doc = "Looks up a value in a dictionary.",
       mandatoryPositionals = {
-        @Param(name = "self", type = Map.class, doc = "This object."),
+        @Param(name = "self", type = SkylarkDict.class, doc = "This object."),
         @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
       useLocation = true, useEnvironment = true)
   private static BuiltinFunction dictIndexOperator = new BuiltinFunction("$index") {
-    public Object invoke(Map<?, ?> self, Object key,
+      public Object invoke(SkylarkDict<?, ?> self, Object key,
         Location loc, Environment env) throws EvalException, ConversionException {
       if (!self.containsKey(key)) {
         throw new EvalException(loc, Printer.format("Key %r not found in dictionary", key));
@@ -1401,7 +1402,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction listIndexOperator =
       new BuiltinFunction("$index") {
-        public Object invoke(MutableList self, Integer key, Location loc, Environment env)
+        public Object invoke(MutableList<?> self, Integer key, Location loc, Environment env)
             throws EvalException, ConversionException {
           if (self.isEmpty()) {
             throw new EvalException(loc, "List is empty");
@@ -1426,7 +1427,7 @@ public class MethodLibrary {
   )
   private static BuiltinFunction tupleIndexOperator =
       new BuiltinFunction("$index") {
-        public Object invoke(Tuple self, Integer key, Location loc, Environment env)
+        public Object invoke(Tuple<?> self, Integer key, Location loc, Environment env)
             throws EvalException, ConversionException {
           if (self.isEmpty()) {
             throw new EvalException(loc, "tuple is empty");
@@ -1456,62 +1457,61 @@ public class MethodLibrary {
         }
       };
 
-  @SkylarkSignature(name = "values", objectType = Map.class,
+  @SkylarkSignature(name = "values", objectType = SkylarkDict.class,
       returnType = MutableList.class,
       doc = "Returns the list of values. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">"
           + "{2: \"a\", 4: \"b\", 1: \"c\"}.values() == [\"c\", \"a\", \"b\"]</pre>\n",
-      mandatoryPositionals = {@Param(name = "self", type = Map.class, doc = "This dict.")},
+      mandatoryPositionals = {@Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
       useEnvironment = true)
   private static BuiltinFunction values = new BuiltinFunction("values") {
-    public MutableList invoke(Map<?, ?> self,
+    public MutableList<?> invoke(SkylarkDict<?, ?> self,
         Environment env) throws EvalException, ConversionException {
-      // Use a TreeMap to ensure consistent ordering.
-      Map<?, ?> dict = new TreeMap<>(self);
-      return new MutableList(dict.values(), env);
+      return new MutableList(self.values(), env);
     }
   };
 
-  @SkylarkSignature(name = "items", objectType = Map.class,
+  @SkylarkSignature(name = "items", objectType = SkylarkDict.class,
       returnType = MutableList.class,
       doc = "Returns the list of key-value tuples. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">"
           + "{2: \"a\", 4: \"b\", 1: \"c\"}.items() == [(1, \"c\"), (2, \"a\"), (4, \"b\")]"
           + "</pre>\n",
       mandatoryPositionals = {
-        @Param(name = "self", type = Map.class, doc = "This dict.")},
+        @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
       useEnvironment = true)
   private static BuiltinFunction items = new BuiltinFunction("items") {
-    public MutableList invoke(Map<?, ?> self,
+    public MutableList<?> invoke(SkylarkDict<?, ?> self,
         Environment env) throws EvalException, ConversionException {
-      // Use a TreeMap to ensure consistent ordering.
-      Map<?, ?> dict = new TreeMap<>(self);
-      List<Object> list = Lists.newArrayListWithCapacity(dict.size());
-      for (Map.Entry<?, ?> entries : dict.entrySet()) {
+      List<Object> list = Lists.newArrayListWithCapacity(self.size());
+      for (Map.Entry<?, ?> entries : self.entrySet()) {
         list.add(Tuple.of(entries.getKey(), entries.getValue()));
       }
       return new MutableList(list, env);
     }
   };
 
-  @SkylarkSignature(name = "keys", objectType = Map.class,
+  @SkylarkSignature(name = "keys", objectType = SkylarkDict.class,
       returnType = MutableList.class,
       doc = "Returns the list of keys. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">{2: \"a\", 4: \"b\", 1: \"c\"}.keys() == [1, 2, 4]"
           + "</pre>\n",
       mandatoryPositionals = {
-        @Param(name = "self", type = Map.class, doc = "This dict.")},
+        @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
       useEnvironment = true)
-  // Skylark will only call this on a dict; and
-  // allowed keys are all Comparable... if not mutually, it's OK to get a runtime exception.
   private static BuiltinFunction keys = new BuiltinFunction("keys") {
-    public MutableList invoke(Map<Comparable<?>, ?> dict,
+    // Skylark will only call this on a dict; and
+    // allowed keys are all Comparable... if not mutually, it's OK to get a runtime exception.
+    @SuppressWarnings("unchecked")
+    public MutableList<?> invoke(SkylarkDict<?, ?> self,
         Environment env) throws EvalException {
-      return new MutableList(Ordering.natural().sortedCopy(dict.keySet()), env);
+      return new MutableList(
+          Ordering.natural().sortedCopy((Set<Comparable<?>>) (Set<?>) self.keySet()),
+          env);
     }
   };
 
-  @SkylarkSignature(name = "get", objectType = Map.class,
+  @SkylarkSignature(name = "get", objectType = SkylarkDict.class,
       doc = "Returns the value for <code>key</code> if <code>key</code> is in the dictionary, "
           + "else <code>default</code>. If <code>default</code> is not given, it defaults to "
           + "<code>None</code>, so that this method never throws an error.",
@@ -1522,7 +1522,7 @@ public class MethodLibrary {
         @Param(name = "default", defaultValue = "None",
             doc = "The default value to use (instead of None) if the key is not found.")})
   private static BuiltinFunction get = new BuiltinFunction("get") {
-    public Object invoke(Map<?, ?> self, Object key, Object defaultValue) {
+    public Object invoke(SkylarkDict<?, ?> self, Object key, Object defaultValue) {
       if (self.containsKey(key)) {
         return self.get(key);
       }
@@ -1555,7 +1555,7 @@ public class MethodLibrary {
       mandatoryPositionals = {@Param(name = "x", doc = "The object to convert.")},
       useLocation = true, useEnvironment = true)
   private static BuiltinFunction list = new BuiltinFunction("list") {
-    public MutableList invoke(Object x, Location loc, Environment env) throws EvalException {
+    public MutableList<?> invoke(Object x, Location loc, Environment env) throws EvalException {
       return new MutableList(EvalUtils.toCollection(x, loc), env);
     }
   };
@@ -1646,8 +1646,8 @@ public class MethodLibrary {
         @Param(name = "kwargs", doc = "the struct attributes")},
       useLocation = true)
   private static BuiltinFunction struct = new BuiltinFunction("struct") {
-      @SuppressWarnings("unchecked")
-    public SkylarkClassObject invoke(Map<String, Object> kwargs, Location loc)
+    @SuppressWarnings("unchecked")
+    public SkylarkClassObject invoke(SkylarkDict<String, Object> kwargs, Location loc)
         throws EvalException {
       return new SkylarkClassObject(kwargs, loc);
     }
@@ -1684,7 +1684,7 @@ public class MethodLibrary {
 
   @SkylarkSignature(
     name = "dict",
-    returnType = Map.class,
+    returnType = SkylarkDict.class,
     doc =
         "Creates a <a href=\"#modules.dict\">dictionary</a> from an optional positional "
             + "argument and an optional set of keyword arguments. Values from the keyword argument "
@@ -1701,28 +1701,26 @@ public class MethodLibrary {
       ),
     },
     extraKeywords = {@Param(name = "kwargs", doc = "Dictionary of additional entries.")},
-    useLocation = true
+    useLocation = true, useEnvironment = true
   )
   private static final BuiltinFunction dict =
       new BuiltinFunction("dict") {
-        @SuppressWarnings("unused")
-        public Map<Object, Object> invoke(Object args, Map<Object, Object> kwargs, Location loc)
+        public SkylarkDict invoke(Object args, SkylarkDict<String, Object> kwargs,
+            Location loc, Environment env)
             throws EvalException {
-          Map<Object, Object> result =
-              (args instanceof Map<?, ?>)
-                  // Do not remove <Object, Object>: workaround for Java 7 type inference.
-                  ? new LinkedHashMap<Object, Object>((Map<?, ?>) args)
-                  : getMapFromArgs(args, loc);
-          result.putAll(kwargs);
-          return result;
+          SkylarkDict<Object, Object> argsDict = (args instanceof SkylarkDict)
+              ? (SkylarkDict<Object, Object>) args : getDictFromArgs(args, loc, env);
+          return SkylarkDict.plus(argsDict, kwargs, env);
         }
 
-        private Map<Object, Object> getMapFromArgs(Object args, Location loc) throws EvalException {
-          Map<Object, Object> result = new LinkedHashMap<>();
+        private SkylarkDict<Object, Object> getDictFromArgs(
+            Object args, Location loc, Environment env)
+            throws EvalException {
+          SkylarkDict<Object, Object> result = SkylarkDict.of(env);
           int pos = 0;
           for (Object element : Type.OBJECT_LIST.convert(args, "parameter args in dict()")) {
             List<Object> pair = convertToPair(element, pos, loc);
-            result.put(pair.get(0), pair.get(1));
+            result.put(pair.get(0), pair.get(1), loc, env);
             ++pos;
           }
           return result;
@@ -1757,7 +1755,7 @@ public class MethodLibrary {
           + "the input set as well as all additional elements.",
       mandatoryPositionals = {
         @Param(name = "input", type = SkylarkNestedSet.class, doc = "The input set"),
-        @Param(name = "newElements", type = Iterable.class, doc = "The elements to be added")},
+        @Param(name = "new_elements", type = Iterable.class, doc = "The elements to be added")},
       useLocation = true)
   private static final BuiltinFunction union = new BuiltinFunction("union") {
     @SuppressWarnings("unused")
@@ -1776,10 +1774,10 @@ public class MethodLibrary {
       },
       useEnvironment = true)
   private static BuiltinFunction enumerate = new BuiltinFunction("enumerate") {
-    public MutableList invoke(SkylarkList input, Environment env)
+    public MutableList<?> invoke(SkylarkList<?> input, Environment env)
         throws EvalException, ConversionException {
       int count = 0;
-      List<SkylarkList> result = Lists.newArrayList();
+      List<SkylarkList<?>> result = Lists.newArrayList();
       for (Object obj : input) {
         result.add(Tuple.of(count, obj));
         count++;
@@ -1809,7 +1807,7 @@ public class MethodLibrary {
       useLocation = true,
       useEnvironment = true)
   private static final BuiltinFunction range = new BuiltinFunction("range") {
-      public MutableList invoke(Integer startOrStop, Object stopOrNone, Integer step,
+      public MutableList<?> invoke(Integer startOrStop, Object stopOrNone, Integer step,
           Location loc, Environment env)
         throws EvalException, ConversionException {
       int start;
@@ -1847,9 +1845,9 @@ public class MethodLibrary {
   @SkylarkSignature(name = "select",
       doc = "Creates a SelectorValue from the dict parameter.",
       mandatoryPositionals = {
-        @Param(name = "x", type = Map.class, doc = "The parameter to convert.")})
+        @Param(name = "x", type = SkylarkDict.class, doc = "The parameter to convert.")})
   private static final BuiltinFunction select = new BuiltinFunction("select") {
-    public Object invoke(Map<?, ?> dict) throws EvalException {
+    public Object invoke(SkylarkDict<?, ?> dict) throws EvalException {
       return SelectorList
           .of(new SelectorValue(dict));
     }
@@ -1921,7 +1919,7 @@ public class MethodLibrary {
       mandatoryPositionals = {@Param(name = "x", doc = "The object to check.")},
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction dir = new BuiltinFunction("dir") {
-    public MutableList invoke(Object object,
+    public MutableList<?> invoke(Object object,
         Location loc, Environment env) throws EvalException, ConversionException {
       // Order the fields alphabetically.
       Set<String> fields = new TreeSet<>();
@@ -1982,7 +1980,7 @@ public class MethodLibrary {
       extraPositionals = {@Param(name = "args", doc = "The objects to print.")},
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction print = new BuiltinFunction("print") {
-    public Runtime.NoneType invoke(String sep, SkylarkList starargs,
+    public Runtime.NoneType invoke(String sep, SkylarkList<?> starargs,
         Location loc, Environment env) throws EvalException {
       String msg = Joiner.on(sep).join(Iterables.transform(starargs,
               new com.google.common.base.Function<Object, String>() {
@@ -2008,13 +2006,13 @@ public class MethodLibrary {
       extraPositionals = {@Param(name = "args", doc = "lists to zip")},
       returnType = MutableList.class, useLocation = true, useEnvironment = true)
   private static final BuiltinFunction zip = new BuiltinFunction("zip") {
-    public MutableList invoke(SkylarkList args, Location loc, Environment env)
+    public MutableList<?> invoke(SkylarkList<?> args, Location loc, Environment env)
         throws EvalException {
       Iterator<?>[] iterators = new Iterator<?>[args.size()];
       for (int i = 0; i < args.size(); i++) {
         iterators[i] = EvalUtils.toIterable(args.get(i), loc).iterator();
       }
-      List<Tuple> result = new ArrayList<>();
+      List<Tuple<?>> result = new ArrayList<>();
       boolean allHasNext;
       do {
         allHasNext = !args.isEmpty();
@@ -2061,29 +2059,6 @@ public class MethodLibrary {
   )
   static final class StringModule {}
 
-  /**
-   * Skylark Dict module.
-   */
-  @SkylarkModule(name = "dict", doc =
-      "A language built-in type to support dicts. "
-      + "Example of dict literal:<br>"
-      + "<pre class=\"language-python\">d = {\"a\": 2, \"b\": 5}</pre>"
-      + "Use brackets to access elements:<br>"
-      + "<pre class=\"language-python\">e = d[\"a\"]   # e == 2</pre>"
-      + "Dicts support the <code>+</code> operator to concatenate two dicts. In case of multiple "
-      + "keys the second one overrides the first one. Examples:<br>"
-      + "<pre class=\"language-python\">"
-      + "d = {\"a\" : 1} + {\"b\" : 2}   # d == {\"a\" : 1, \"b\" : 2}\n"
-      + "d += {\"c\" : 3}              # d == {\"a\" : 1, \"b\" : 2, \"c\" : 3}\n"
-      + "d = d + {\"c\" : 5}           # d == {\"a\" : 1, \"b\" : 2, \"c\" : 5}</pre>"
-      + "Since the language doesn't have mutable objects <code>d[\"a\"] = 5</code> automatically "
-      + "translates to <code>d = d + {\"a\" : 5}</code>.<br>"
-      + "Iterating on a dict is equivalent to iterating on its keys (in sorted order).<br>"
-      + "Dicts support the <code>in</code> operator, testing membership in the keyset of the dict. "
-      + "Example:<br>"
-      + "<pre class=\"language-python\">\"a\" in {\"a\" : 2, \"b\" : 5}   # evaluates as True"
-      + "</pre>")
-  static final class DictModule {}
 
   static final List<BaseFunction> buildGlobalFunctions =
       ImmutableList.<BaseFunction>of(
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index b24e188f9c..f4b55ad4c4 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
@@ -26,7 +26,6 @@ import net.bytebuddy.implementation.bytecode.StackManipulation;
 
 import java.lang.reflect.Field;
 import java.util.HashMap;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
@@ -120,20 +119,15 @@ public final class Runtime {
    */
   public static void registerFunction(Class<?> nameSpace, BaseFunction function) {
     Preconditions.checkNotNull(nameSpace);
-    // TODO(bazel-team): fix our code so that the two checks below work.
-    // Preconditions.checkArgument(function.getObjectType().equals(nameSpace));
-    // Preconditions.checkArgument(nameSpace.equals(getCanonicalRepresentation(nameSpace)));
-    nameSpace = getCanonicalRepresentation(nameSpace);
+    Preconditions.checkArgument(nameSpace.equals(getCanonicalRepresentation(nameSpace)));
+    Preconditions.checkArgument(
+        getCanonicalRepresentation(function.getObjectType()).equals(nameSpace));
     if (!functions.containsKey(nameSpace)) {
       functions.put(nameSpace, new HashMap<String, BaseFunction>());
     }
     functions.get(nameSpace).put(function.getName(), function);
   }
 
-  static Map<String, BaseFunction> getNamespaceFunctions(Class<?> nameSpace) {
-    return functions.get(getCanonicalRepresentation(nameSpace));
-  }
-
   /**
    * Returns the canonical representation of the given class, i.e. the super class for which any
    * functions were registered.
@@ -143,18 +137,15 @@ public final class Runtime {
    */
   // TODO(bazel-team): make everything a SkylarkValue, and remove this function.
   public static Class<?> getCanonicalRepresentation(Class<?> clazz) {
-    if (SkylarkValue.class.isAssignableFrom(clazz)) {
-      return clazz;
-    }
-    if (Map.class.isAssignableFrom(clazz)) {
-      return MethodLibrary.DictModule.class;
-    }
     if (String.class.isAssignableFrom(clazz)) {
       return MethodLibrary.StringModule.class;
     }
-    Preconditions.checkArgument(
-        !List.class.isAssignableFrom(clazz), "invalid non-SkylarkList list class");
-    return clazz;
+    return EvalUtils.getSkylarkType(clazz);
+  }
+
+
+  static Map<String, BaseFunction> getNamespaceFunctions(Class<?> nameSpace) {
+    return functions.get(getCanonicalRepresentation(nameSpace));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
new file mode 100644
index 0000000000..3a856b23ff
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
@@ -0,0 +1,203 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.syntax;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.syntax.SkylarkMutable.MutableMap;
+
+import java.util.Map;
+import java.util.TreeMap;
+
+import javax.annotation.Nullable;
+
+/**
+ * Skylark Dict module.
+ */
+@SkylarkModule(name = "dict", doc =
+    "A language built-in type to support dicts. "
+    + "Example of dict literal:<br>"
+    + "<pre class=\"language-python\">d = {\"a\": 2, \"b\": 5}</pre>"
+    + "Use brackets to access elements:<br>"
+    + "<pre class=\"language-python\">e = d[\"a\"]   # e == 2</pre>"
+    + "Dicts support the <code>+</code> operator to concatenate two dicts. In case of multiple "
+    + "keys the second one overrides the first one. Examples:<br>"
+    + "<pre class=\"language-python\">"
+    + "d = {\"a\" : 1} + {\"b\" : 2}   # d == {\"a\" : 1, \"b\" : 2}\n"
+    + "d += {\"c\" : 3}              # d == {\"a\" : 1, \"b\" : 2, \"c\" : 3}\n"
+    + "d = d + {\"c\" : 5}           # d == {\"a\" : 1, \"b\" : 2, \"c\" : 5}</pre>"
+    + "Iterating on a dict is equivalent to iterating on its keys (in sorted order).<br>"
+    + "Dicts support the <code>in</code> operator, testing membership in the keyset of the dict. "
+    + "Example:<br>"
+    + "<pre class=\"language-python\">\"a\" in {\"a\" : 2, \"b\" : 5}   # evaluates as True"
+    + "</pre>")
+public final class SkylarkDict<K, V>
+    extends MutableMap<K, V> implements Map<K, V> {
+
+  private TreeMap<K, V> contents = new TreeMap<>(EvalUtils.SKYLARK_COMPARATOR);
+
+  private Mutability mutability;
+
+  @Override
+  public Mutability mutability() {
+    return mutability;
+  }
+
+  private SkylarkDict(@Nullable Environment env) {
+    mutability = env == null ? Mutability.IMMUTABLE : env.mutability();
+  }
+
+  /** @return a dict mutable in given environment only */
+  public static <K, V> SkylarkDict<K, V> of(@Nullable Environment env) {
+    return new SkylarkDict<K, V>(env);
+  }
+
+  /** @return a dict mutable in given environment only, with given initial key and value */
+  public static <K, V> SkylarkDict<K, V> of(@Nullable Environment env, K k, V v) {
+    return SkylarkDict.<K, V>of(env).putUnsafe(k, v);
+  }
+
+  /** @return a dict mutable in given environment only, with two given initial key value pairs */
+  public static <K, V> SkylarkDict<K, V> of(
+      @Nullable Environment env, K k1, V v1, K k2, V v2) {
+    return SkylarkDict.<K, V>of(env).putUnsafe(k1, v1).putUnsafe(k2, v2);
+  }
+
+  /** @return a dict mutable in given environment only, with contents copied from given map */
+  public static <K, V> SkylarkDict<K, V> copyOf(
+      @Nullable Environment env, Map<? extends K, ? extends V> m) {
+    return SkylarkDict.<K, V>of(env).putAllUnsafe(m);
+  }
+
+  private SkylarkDict<K, V> putUnsafe(K k, V v) {
+    contents.put(k, v);
+    return this;
+  }
+
+  private <KK extends K, VV extends V> SkylarkDict putAllUnsafe(Map<KK, VV> m) {
+    for (Map.Entry<KK, VV> e : m.entrySet()) {
+      contents.put(e.getKey(), e.getValue());
+    }
+    return this;
+  }
+
+  /**
+   * The underlying contents is a (usually) mutable data structure.
+   * Read access is forwarded to these contents.
+   * This object must not be modified outside an {@link Environment}
+   * with a correct matching {@link Mutability},
+   * which should be checked beforehand using {@link #checkMutable}.
+   * it need not be an instance of {@link com.google.common.collect.ImmutableMap}.
+   */
+  @Override
+  protected Map<K, V> getContentsUnsafe() {
+    return contents;
+  }
+
+  public void put(K k, V v, Location loc, Environment env) throws EvalException {
+    checkMutable(loc, env);
+    EvalUtils.checkValidDictKey(k);
+    contents.put(k, v);
+  }
+
+  public void putAll(Map<? extends K, ? extends V> m, Location loc, Environment env)
+      throws EvalException {
+    checkMutable(loc, env);
+    putAllUnsafe(m);
+  }
+
+  // Other methods
+  @Override
+  public void write(Appendable buffer, char quotationMark) {
+    Printer.printList(buffer, entrySet(), "{", ", ", "}", null, quotationMark);
+  }
+
+  /**
+   * Cast a {@code SkylarkDict<?>} to a {@code SkylarkDict<K, V>}
+   * after checking its current contents.
+   * @param dict the SkylarkDict to cast
+   * @param keyType the expected class of keys
+   * @param valueType the expected class of values
+   * @param description a description of the argument being converted, or null, for debugging
+   */
+  @SuppressWarnings("unchecked")
+  public static <KeyType, ValueType> SkylarkDict<KeyType, ValueType> castDict(
+      SkylarkDict<?, ?> dict,
+      Class<KeyType> keyType,
+      Class<ValueType> valueType,
+      @Nullable String description)
+      throws EvalException {
+    Object keyDescription = description == null
+        ? null : Printer.formattable("'%s' key", description);
+    Object valueDescription = description == null
+        ? null : Printer.formattable("'%s' value", description);
+    for (Map.Entry<?, ?> e : dict.entrySet()) {
+      SkylarkType.checkType(e.getKey(), keyType, keyDescription);
+      SkylarkType.checkType(e.getValue(), valueType, valueDescription);
+    }
+    return (SkylarkDict<KeyType, ValueType>) dict;
+  }
+
+  /**
+   * Cast a SkylarkDict to a {@code Map<K, V>} after checking its current contents.
+   * Treat None as meaning the empty ImmutableMap.
+   * @param obj the Object to cast. null and None are treated as an empty list.
+   * @param keyType the expected class of keys
+   * @param valueType the expected class of values
+   * @param description a description of the argument being converted, or null, for debugging
+   */
+  public static <K, V> Map<K, V> castSkylarkDictOrNoneToMap(
+      Object obj, Class<K> keyType, Class<V> valueType, @Nullable String description)
+      throws EvalException {
+    if (EvalUtils.isNullOrNone(obj)) {
+      return ImmutableMap.of();
+    }
+    if (obj instanceof SkylarkDict) {
+      return ((SkylarkDict<?, ?>) obj).getContents(keyType, valueType, description);
+    }
+    throw new EvalException(null,
+        Printer.format("Illegal argument: %s is not of expected type dict or NoneType",
+            description == null ? Printer.repr(obj) : String.format("'%s'", description)));
+  }
+
+  /**
+   * Cast a SkylarkDict to a {@code Map<K, V>} after checking its current contents.
+   * @param keyType the expected class of keys
+   * @param valueType the expected class of values
+   * @param description a description of the argument being converted, or null, for debugging
+   */
+  public <KeyType, ValueType> Map<KeyType, ValueType> getContents(
+      Class<KeyType> keyType, Class<ValueType> valueType, @Nullable String description)
+      throws EvalException {
+    return castDict(this, keyType, valueType, description);
+  }
+
+  public static <K, V> SkylarkDict<K, V> plus(
+      SkylarkDict<? extends K, ? extends V> left,
+      SkylarkDict<? extends K, ? extends V> right,
+      @Nullable Environment env) {
+    SkylarkDict<K, V> result = SkylarkDict.<K, V>of(env);
+    result.putAllUnsafe(left);
+    result.putAllUnsafe(right);
+    return result;
+  }
+
+  private static final SkylarkDict<?, ?> EMPTY = of(null);
+
+  public static <K, V> SkylarkDict<K, V> empty() {
+    return (SkylarkDict<K, V>) EMPTY;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
index fddebba162..102cd31dfd 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
@@ -35,13 +35,13 @@ import javax.annotation.Nullable;
  */
 @SkylarkModule(name = "sequence", documented = false,
     doc = "common type of lists and tuples")
-  public abstract class SkylarkList
-    extends MutableCollection<Object> implements List<Object>, RandomAccess {
+  public abstract class SkylarkList<E>
+    extends MutableCollection<E> implements List<E>, RandomAccess {
 
   /**
    * Returns an ImmutableList object with the current underlying contents of this SkylarkList.
    */
-  public abstract ImmutableList<Object> getImmutableList();
+  public abstract ImmutableList<E> getImmutableList();
 
   /**
    * Returns a List object with the current underlying contents of this SkylarkList.
@@ -49,8 +49,7 @@ import javax.annotation.Nullable;
    * Indeed it can sometimes be a {@link GlobList}.
    */
   // TODO(bazel-team): move GlobList out of Skylark, into an extension.
-  @Override
-  public abstract List<Object> getContents();
+  public abstract List<E> getContents();
 
   /**
    * The underlying contents are a (usually) mutable data structure.
@@ -61,7 +60,7 @@ import javax.annotation.Nullable;
    * it need not be an instance of {@link com.google.common.collect.ImmutableList}.
    */
   @Override
-  protected abstract List<Object> getContentsUnsafe();
+  protected abstract List<E> getContentsUnsafe();
 
   /**
    * Returns true if this list is a tuple.
@@ -70,7 +69,7 @@ import javax.annotation.Nullable;
 
   // A SkylarkList forwards all read-only access to the getContentsUnsafe().
   @Override
-  public final Object get(int i) {
+  public final E get(int i) {
     return getContentsUnsafe().get(i);
   }
 
@@ -85,12 +84,12 @@ import javax.annotation.Nullable;
   }
 
   @Override
-  public ListIterator<Object> listIterator() {
+  public ListIterator<E> listIterator() {
     return getContentsUnsafe().listIterator();
   }
 
   @Override
-  public ListIterator<Object> listIterator(int index) {
+  public ListIterator<E> listIterator(int index) {
     return getContentsUnsafe().listIterator(index);
   }
 
@@ -98,28 +97,28 @@ import javax.annotation.Nullable;
   // to prevent subsequent mutation. To get a mutable SkylarkList,
   // use a method that takes an Environment into account.
   @Override
-  public List<Object> subList(int fromIndex, int toIndex) {
+  public List<E> subList(int fromIndex, int toIndex) {
     return getContents().subList(fromIndex, toIndex);
   }
 
   // A SkylarkList disables all direct mutation methods.
   @Override
-  public void add(int index, Object element) {
+  public void add(int index, E element) {
     throw new UnsupportedOperationException();
   }
 
   @Override
-  public boolean addAll(int index, Collection<?> elements) {
+  public boolean addAll(int index, Collection<? extends E> elements) {
     throw new UnsupportedOperationException();
   }
 
   @Override
-  public Object remove(int index) {
+  public E remove(int index) {
     throw new UnsupportedOperationException();
   }
 
   @Override
-  public Object set(int index, Object element) {
+  public E set(int index, E element) {
     throw new UnsupportedOperationException();
   }
 
@@ -155,14 +154,9 @@ import javax.annotation.Nullable;
   public static <TYPE> List<TYPE> castList(
       List<?> list, Class<TYPE> type, @Nullable String description)
       throws EvalException {
+    Object desc = description == null ? null : Printer.formattable("'%s' element", description);
     for (Object value : list) {
-      if (!type.isInstance(value)) {
-        throw new EvalException(null,
-            Printer.format("Illegal argument: expected type %r %sbut got type %s instead",
-                type,
-                description == null ? "" : String.format("for '%s' element ", description),
-                EvalUtils.getDataTypeName(value)));
-      }
+      SkylarkType.checkType(value, type, desc);
     }
     return (List<TYPE>) list;
   }
@@ -181,7 +175,7 @@ import javax.annotation.Nullable;
       return ImmutableList.of();
     }
     if (obj instanceof SkylarkList) {
-      return ((SkylarkList) obj).getContents(type, description);
+      return ((SkylarkList<?>) obj).getContents(type, description);
     }
     throw new EvalException(null,
         Printer.format("Illegal argument: %s is not of expected type list or NoneType",
@@ -218,15 +212,15 @@ import javax.annotation.Nullable;
             + "['a', 'b', 'c', 'd'][3:0:-1]  # ['d', 'c', 'b']</pre>"
             + "Lists are mutable, as in Python."
   )
-  public static final class MutableList extends SkylarkList {
+  public static final class MutableList<E> extends SkylarkList<E> {
 
-    private final ArrayList<Object> contents = new ArrayList<>();
+    private final ArrayList<E> contents = new ArrayList<>();
 
     // Treat GlobList specially: external code depends on it.
     // TODO(bazel-team): make data structures *and binary operators* extensible
     // (via e.g. interface classes for each binary operator) so that GlobList
     // can be implemented outside of the core of Skylark.
-    @Nullable private GlobList<?> globList;
+    @Nullable private GlobList<E> globList;
 
     private final Mutability mutability;
 
@@ -236,11 +230,12 @@ import javax.annotation.Nullable;
      * @param mutability a Mutability context
      * @return a MutableList containing the elements
      */
-    MutableList(Iterable<?> contents, Mutability mutability) {
+    @SuppressWarnings("unchecked")
+    MutableList(Iterable<? extends E> contents, Mutability mutability) {
       super();
       addAllUnsafe(contents);
-      if (contents instanceof GlobList<?>) {
-        globList = (GlobList<?>) contents;
+      if (contents instanceof GlobList) {
+        globList = (GlobList<E>) contents;
       }
       this.mutability = mutability;
     }
@@ -251,7 +246,7 @@ import javax.annotation.Nullable;
      * @param env an Environment from which to inherit Mutability, or null for immutable
      * @return a MutableList containing the elements
      */
-    public MutableList(Iterable<?> contents, @Nullable Environment env) {
+    public MutableList(Iterable<? extends E> contents, @Nullable Environment env) {
       this(contents, env == null ? Mutability.IMMUTABLE : env.mutability());
     }
 
@@ -260,7 +255,7 @@ import javax.annotation.Nullable;
      * @param contents the contents of the list
      * @return an actually immutable MutableList containing the elements
      */
-    public MutableList(Iterable<?> contents) {
+    public MutableList(Iterable<? extends E> contents) {
       this(contents, Mutability.IMMUTABLE);
     }
 
@@ -277,7 +272,7 @@ import javax.annotation.Nullable;
      * @param contents the contents of the list
      * @return a Skylark list containing the specified arguments as elements.
      */
-    public static MutableList of(@Nullable Environment env, Object... contents) {
+    public static <E> MutableList<E> of(@Nullable Environment env, E... contents) {
       return new MutableList(ImmutableList.copyOf(contents), env);
     }
 
@@ -286,8 +281,8 @@ import javax.annotation.Nullable;
      * @param elements the elements to add
      * Assumes that you already checked for Mutability.
      */
-    private void addAllUnsafe(Iterable<?> elements) {
-      for (Object elem : elements) {
+    private void addAllUnsafe(Iterable<? extends E> elements) {
+      for (E elem : elements) {
         contents.add(elem);
       }
     }
@@ -298,7 +293,7 @@ import javax.annotation.Nullable;
       globList = null; // If you're going to mutate it, invalidate the underlying GlobList.
     }
 
-    @Nullable public GlobList<?> getGlobList() {
+    @Nullable public GlobList<E> getGlobList() {
       return globList;
     }
 
@@ -307,15 +302,15 @@ import javax.annotation.Nullable;
      */
     @Override
     @SuppressWarnings("unchecked")
-    public List<Object> getContents() {
+    public List<E> getContents() {
       if (globList != null) {
-        return (List<Object>) (List<?>) globList;
+        return globList;
       }
       return getImmutableList();
     }
 
     @Override
-    protected List<Object> getContentsUnsafe() {
+    protected List<E> getContentsUnsafe() {
       return contents;
     }
 
@@ -336,7 +331,10 @@ import javax.annotation.Nullable;
      * @param env the Environment in which to create a new list
      * @return a new MutableList
      */
-    public static MutableList concat(MutableList left, MutableList right, Environment env) {
+    public static <E> MutableList<E> concat(
+        MutableList<? extends E> left,
+        MutableList<? extends E> right,
+        Environment env) {
       if (left.getGlobList() == null && right.getGlobList() == null) {
         return new MutableList(Iterables.concat(left, right), env);
       }
@@ -350,7 +348,7 @@ import javax.annotation.Nullable;
      * @param loc the Location at which to report any error
      * @param env the Environment requesting the modification
      */
-    public void add(Object element, Location loc, Environment env) throws EvalException {
+    public void add(E element, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
       contents.add(element);
     }
@@ -366,13 +364,14 @@ import javax.annotation.Nullable;
      * @param loc the Location at which to report any error
      * @param env the Environment requesting the modification
      */
-    public void addAll(Iterable<?> elements, Location loc, Environment env) throws EvalException {
+    public void addAll(Iterable<? extends E> elements, Location loc, Environment env)
+        throws EvalException {
       checkMutable(loc, env);
       addAllUnsafe(elements);
     }
 
     @Override
-    public ImmutableList<Object> getImmutableList() {
+    public ImmutableList<E> getImmutableList() {
       return ImmutableList.copyOf(contents);
     }
 
@@ -418,11 +417,11 @@ import javax.annotation.Nullable;
             + "Tuples are immutable, therefore <code>x[1] = \"a\"</code> is not supported."
   )
   @Immutable
-  public static final class Tuple extends SkylarkList {
+  public static final class Tuple<E> extends SkylarkList<E> {
 
-    private final ImmutableList<Object> contents;
+    private final ImmutableList<E> contents;
 
-    private Tuple(ImmutableList<Object> contents) {
+    private Tuple(ImmutableList<E> contents) {
       super();
       this.contents = contents;
     }
@@ -435,14 +434,19 @@ import javax.annotation.Nullable;
     /**
      * THE empty Skylark tuple.
      */
-    public static final Tuple EMPTY = new Tuple(ImmutableList.of());
+    private static final Tuple<?> EMPTY = new Tuple<>(ImmutableList.of());
+
+    @SuppressWarnings("unchecked")
+    public static final <E> Tuple<E> empty() {
+      return (Tuple<E>) EMPTY;
+    }
 
     /**
      * Creates a Tuple from an ImmutableList.
      */
-    public static Tuple create(ImmutableList<Object> contents) {
+    public static<E> Tuple<E> create(ImmutableList<E> contents) {
       if (contents.isEmpty()) {
-        return EMPTY;
+        return empty();
       }
       return new Tuple(contents);
     }
@@ -450,9 +454,8 @@ import javax.annotation.Nullable;
     /**
      * Creates a Tuple from an Iterable.
      */
-    public static Tuple copyOf(Iterable<?> contents) {
-      // Do not remove <Object>: workaround for Java 7 type inference.
-      return create(ImmutableList.<Object>copyOf(contents));
+    public static <E> Tuple<E> copyOf(Iterable<? extends E> contents) {
+      return create(ImmutableList.<E>copyOf(contents));
     }
 
     /**
@@ -460,22 +463,22 @@ import javax.annotation.Nullable;
      * @param elements a variable number of arguments (or an Array of Object-s)
      * @return a Skylark tuple containing the specified arguments as elements.
      */
-    public static Tuple of(Object... elements) {
+    public static <E> Tuple<E> of(E... elements) {
       return Tuple.create(ImmutableList.copyOf(elements));
     }
 
     @Override
-    public ImmutableList<Object> getImmutableList() {
+    public ImmutableList<E> getImmutableList() {
       return contents;
     }
 
     @Override
-    public List<Object> getContents() {
+    public List<E> getContents() {
       return contents;
     }
 
     @Override
-    protected List<Object> getContentsUnsafe() {
+    protected List<E> getContentsUnsafe() {
       return contents;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
index afa107a327..dd9b91a64f 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
@@ -21,6 +21,8 @@ import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
 
 import java.util.Collection;
 import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
 
 import javax.annotation.Nullable;
 
@@ -44,6 +46,11 @@ abstract class SkylarkMutable implements Freezable, SkylarkValue {
   }
 
   @Override
+  public boolean isImmutable() {
+    return !mutability().isMutable();
+  }
+
+  @Override
   public String toString() {
     return Printer.repr(this);
   }
@@ -53,16 +60,6 @@ abstract class SkylarkMutable implements Freezable, SkylarkValue {
     protected MutableCollection() {}
 
     /**
-     * Return the underlying contents of this collection,
-     * that may be of a more specific class with its own methods.
-     * This object MUST NOT be mutated.
-     * If possible, the implementation should make this object effectively immutable,
-     * by throwing {@link UnsupportedOperationException} if attemptedly mutated;
-     * but it need not be an instance of {@link com.google.common.collect.ImmutableCollection}.
-     */
-    public abstract Collection<Object> getContents();
-
-    /**
      * The underlying contents is a (usually) mutable data structure.
      * Read access is forwarded to these contents.
      * This object must not be modified outside an {@link Environment}
@@ -155,4 +152,95 @@ abstract class SkylarkMutable implements Freezable, SkylarkValue {
       return getContentsUnsafe().hashCode();
     }
   }
+
+  abstract static class MutableMap<K, V> extends SkylarkMutable implements Map<K, V> {
+
+    MutableMap() {}
+
+    /**
+     * The underlying contents is a (usually) mutable data structure.
+     * Read access is forwarded to these contents.
+     * This object must not be modified outside an {@link Environment}
+     * with a correct matching {@link Mutability},
+     * which should be checked beforehand using {@link #checkMutable}.
+     */
+    protected abstract Map<K, V> getContentsUnsafe();
+
+    // A SkylarkDict forwards all read-only access to the contents.
+    @Override
+    public final V get(Object key) {
+      return getContentsUnsafe().get(key);
+    }
+
+    @Override
+    public boolean containsKey(Object key) {
+      return getContentsUnsafe().containsKey(key);
+    }
+
+    @Override
+    public boolean containsValue(Object value) {
+      return getContentsUnsafe().containsValue(value);
+    }
+
+    @Override
+      public Set<Map.Entry<K, V>> entrySet() {
+      return getContentsUnsafe().entrySet();
+    }
+
+    @Override
+    public Set<K> keySet() {
+      return getContentsUnsafe().keySet();
+    }
+
+    @Override
+    public Collection<V> values() {
+      return getContentsUnsafe().values();
+    }
+
+    @Override
+    public int size() {
+      return getContentsUnsafe().size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return getContentsUnsafe().isEmpty();
+    }
+
+    // Disable all mutation interfaces without a mutation context.
+
+    @Deprecated
+    @Override
+    public final V put(K key, V value) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final void putAll(Map<? extends K, ? extends V> map) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final V remove(Object key) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final void clear() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      return getContentsUnsafe().equals(o);
+    }
+
+    @Override
+    public int hashCode() {
+      return getContentsUnsafe().hashCode();
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
index b00413c0c8..f3e8c59df2 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
@@ -183,7 +183,7 @@ public final class SkylarkNestedSet implements Iterable<Object>, SkylarkValue {
   private static SkylarkType checkType(SkylarkType builderType, SkylarkType itemType, Location loc)
       throws EvalException {
     if (SkylarkType.intersection(
-        SkylarkType.Union.of(SkylarkType.MAP, SkylarkType.LIST, SkylarkType.STRUCT),
+        SkylarkType.Union.of(SkylarkType.DICT, SkylarkType.LIST, SkylarkType.STRUCT),
         itemType) != SkylarkType.BOTTOM) {
       throw new EvalException(
           loc, String.format("sets cannot contain items of type '%s'", itemType));
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
index 21ea3f8d3d..a90ba7e975 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
@@ -174,8 +174,8 @@ public abstract class SkylarkType implements Serializable {
   /** The FUNCTION type, that contains all functions, otherwise dynamically typed at call-time */
   public static final SkylarkFunctionType FUNCTION = new SkylarkFunctionType("unknown", TOP);
 
-  /** The MAP type, that contains all Map's, and the generic combinator for maps */
-  public static final Simple MAP = Simple.of(Map.class);
+  /** The DICT type, that contains SkylarkDict */
+  public static final Simple DICT = Simple.of(SkylarkDict.class);
 
   /** The SEQUENCE type, that contains lists and tuples */
   // TODO(bazel-team): this was added for backward compatibility with the BUILD language,
@@ -718,7 +718,10 @@ public abstract class SkylarkType implements Serializable {
       return object;
     }
     if (object instanceof List) {
-      return new MutableList((List<?>) object, env);
+      return new MutableList<>((List<?>) object, env);
+    }
+    if (object instanceof Map) {
+      return SkylarkDict.<Object, Object>copyOf(env, (Map<?, ?>) object);
     }
     // TODO(bazel-team): ensure everything is a SkylarkValue at all times.
     // Preconditions.checkArgument(EvalUtils.isSkylarkAcceptable(
@@ -728,4 +731,15 @@ public abstract class SkylarkType implements Serializable {
     //    object.getClass());
     return object;
   }
+
+  public static void checkType(Object object, Class<?> type, @Nullable Object description)
+      throws EvalException {
+    if (!type.isInstance(object)) {
+      throw new EvalException(null,
+          Printer.format("Illegal argument: expected type %r %sbut got type %s instead",
+              type,
+              description == null ? "" : String.format("for %s ", description),
+              EvalUtils.getDataTypeName(object)));
+      }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
index 55e9cc1bf6..28bd503ed5 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
@@ -15,6 +15,9 @@ package com.google.devtools.build.lib.syntax.compiler;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.syntax.Environment;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 
 import net.bytebuddy.implementation.bytecode.StackManipulation;
 
@@ -71,6 +74,21 @@ public class ByteCodeMethodCalls {
   }
 
   /**
+   * Byte code invocations for {@link SkylarkDict}.
+   */
+  public static class BCSkylarkDict {
+    public static final StackManipulation of =
+        ByteCodeUtils.invoke(SkylarkDict.class, "of", Environment.class);
+
+    public static final StackManipulation copyOf =
+        ByteCodeUtils.invoke(SkylarkDict.class, "copyOf", Environment.class, Map.class);
+
+    public static final StackManipulation put =
+        ByteCodeUtils.invoke(SkylarkDict.class, "put",
+            Object.class, Object.class, Location.class, Environment.class);
+  }
+
+  /**
    * Byte code invocations for {@link ImmutableList}.
    */
   public static class BCImmutableList {
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 717a132003..6fedceee06 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
@@ -199,7 +199,7 @@ public class SkylarkRuleClassFunctionsTest extends SkylarkTestCase {
   @Test
   public void testLabelListWithAspectsError() throws Exception {
     checkErrorContains(
-        "Expected a list of aspects for 'aspects'",
+        "Illegal argument: expected type aspect for 'aspects' element but got type int instead",
         "def _impl(target, ctx):",
         "   pass",
         "my_aspect = aspect(implementation = _impl)",
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
index 2fb7db04af..ae3de80459 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
@@ -22,7 +22,6 @@ import static org.junit.Assert.assertSame;
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.FileConfiguredTarget;
@@ -33,6 +32,7 @@ import com.google.devtools.build.lib.rules.SkylarkRuleContext;
 import com.google.devtools.build.lib.rules.java.JavaSourceJarsProvider;
 import com.google.devtools.build.lib.rules.python.PythonSourcesProvider;
 import com.google.devtools.build.lib.skylark.util.SkylarkTestCase;
+import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.testutil.TestConstants;
@@ -544,7 +544,7 @@ public class SkylarkRuleContextTest extends SkylarkTestCase {
   public void testSkylarkRuleContextGetDefaultShellEnv() throws Exception {
     SkylarkRuleContext ruleContext = createRuleContext("//foo:foo");
     Object result = evalRuleContextCode(ruleContext, "ruleContext.configuration.default_shell_env");
-    assertThat(result).isInstanceOf(ImmutableMap.class);
+    assertThat(result).isInstanceOf(SkylarkDict.class);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
index e83651cff0..68178db8ec 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
@@ -37,6 +37,7 @@ import com.google.devtools.build.lib.skylark.util.SkylarkTestCase;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature.Param;
 import com.google.devtools.build.lib.syntax.BuiltinFunction;
+import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
@@ -68,7 +69,8 @@ public class SkylarkRuleImplementationFunctionsTest extends SkylarkTestCase {
     mandatoryPositionals = {@Param(name = "mandatory", doc = "")},
     optionalPositionals = {@Param(name = "optional", doc = "")},
     mandatoryNamedOnly = {@Param(name = "mandatory_key", doc = "")},
-    optionalNamedOnly = {@Param(name = "optional_key", doc = "", defaultValue = "'x'")}
+    optionalNamedOnly = {@Param(name = "optional_key", doc = "", defaultValue = "'x'")},
+    useEnvironment = true
   )
   private BuiltinFunction mockFunc;
 
@@ -121,8 +123,10 @@ public class SkylarkRuleImplementationFunctionsTest extends SkylarkTestCase {
         new BuiltinFunction("mock") {
           @SuppressWarnings("unused")
           public Object invoke(
-              Object mandatory, Object optional, Object mandatoryKey, Object optionalKey) {
+              Object mandatory, Object optional, Object mandatoryKey, Object optionalKey,
+              Environment env) {
             return EvalUtils.optionMap(
+                env,
                 "mandatory",
                 mandatory,
                 "optional",
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
index 4989cbd900..cd0129dd70 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
@@ -26,8 +26,6 @@ import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.util.LinkedHashMap;
-import java.util.Map;
 import java.util.TreeMap;
 
 /**
@@ -37,8 +35,8 @@ import java.util.TreeMap;
 @RunWith(JUnit4.class)
 public class EvalUtilsTest {
 
-  private static Map<Object, Object> makeDict() {
-    return new LinkedHashMap<>();
+  private static SkylarkDict<Object, Object> makeDict() {
+    return SkylarkDict.<Object, Object>of(null);
   }
 
   @Test
@@ -79,7 +77,7 @@ public class EvalUtilsTest {
     map.put("test", 7);
     map.put(-1, 2);
     map.put("4", 6);
-    map.put(2.0, 1);
+    map.put(true, 1);
     map.put(Runtime.NONE, 0);
 
     int expected = 0;
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
index 7a1033838e..4396608f66 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
@@ -259,7 +259,7 @@ public class EvaluationTest extends EvaluationTestCase {
           final Map<String, Object> kwargs,
           FuncallExpression ast,
           Environment env) {
-        return kwargs;
+        return SkylarkDict.copyOf(env, kwargs);
       }
     };
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
index a894ddfe64..7bbe8eafa7 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
@@ -418,8 +418,8 @@ public class MethodLibraryTest extends EvaluationTestCase {
   public void testBuiltinFunctionErrorMessage() throws Exception {
     new BothModesTest()
         .testIfErrorContains(
-            "Method set.union(newElements: Iterable) is not applicable for arguments (string): "
-                + "'newElements' is string, but should be Iterable",
+            "Method set.union(new_elements: Iterable) is not applicable for arguments (string): "
+                + "'new_elements' is string, but should be Iterable",
             "set([]).union('a')")
         .testIfErrorContains(
             "Method string.startswith(sub: string, start: int, end: int or NoneType) is not "
@@ -1347,8 +1347,8 @@ public class MethodLibraryTest extends EvaluationTestCase {
     new BothModesTest()
         .testIfErrorContains("insufficient arguments received by union", "set(['a']).union()")
         .testIfErrorContains(
-            "Method set.union(newElements: Iterable) is not applicable for arguments (string): "
-                + "'newElements' is string, but should be Iterable",
+            "Method set.union(new_elements: Iterable) is not applicable for arguments (string): "
+                + "'new_elements' is string, but should be Iterable",
             "set(['a']).union('b')");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index 6aae5c1b78..7ee189cd9e 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -132,6 +132,7 @@ public class SkylarkEvaluationTest extends EvaluationTest {
     }
   }
 
+  @SkylarkModule(name = "MockClassObject", doc = "", documented = false)
   static final class MockClassObject implements ClassObject {
     @Override
     public Object getValue(String name) {
@@ -835,11 +836,11 @@ public class SkylarkEvaluationTest extends EvaluationTest {
   }
 
   @Test
-  public void testDictAssignmentAsLValueNoSideEffects() throws Exception {
+  public void testDictAssignmentAsLValueSideEffects() throws Exception {
     new SkylarkTest().setUp("def func(d):",
         "  d['b'] = 2",
         "d = {'a' : 1}",
-        "func(d)").testLookup("d", ImmutableMap.of("a", 1));
+        "func(d)").testLookup("d", SkylarkDict.of(null, "a", 1, "b", 2));
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
index 4c6eb6ac63..c44e5c918b 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
@@ -284,7 +284,7 @@ public class ValidationTest extends EvaluationTestCase {
 
   @Test
   public void testParentWithSkylarkModule() throws Exception {
-    Class<?> emptyTupleClass = Tuple.EMPTY.getClass();
+    Class<?> emptyTupleClass = Tuple.empty().getClass();
     Class<?> tupleClass = Tuple.of(1, "a", "b").getClass();
     Class<?> mutableListClass = new MutableList(Tuple.of(1, 2, 3), env).getClass();
 
@@ -311,7 +311,7 @@ public class ValidationTest extends EvaluationTestCase {
   @Test
   public void testSkylarkTypeEquivalence() throws Exception {
     // All subclasses of SkylarkList are made equivalent
-    Class<?> emptyTupleClass = Tuple.EMPTY.getClass();
+    Class<?> emptyTupleClass = Tuple.empty().getClass();
     Class<?> tupleClass = Tuple.of(1, "a", "b").getClass();
     Class<?> mutableListClass = new MutableList(Tuple.of(1, 2, 3), env).getClass();
 
@@ -322,8 +322,14 @@ public class ValidationTest extends EvaluationTestCase {
 
     // Also for ClassObject
     assertThat(SkylarkType.of(ClassObject.SkylarkClassObject.class)).isEqualTo(SkylarkType.STRUCT);
-    // TODO(bazel-team): fix that?
-    assertThat(SkylarkType.of(ClassObject.class)).isNotEqualTo(SkylarkType.STRUCT);
+    try {
+      SkylarkType.of(ClassObject.class);
+      throw new Exception("foo");
+    } catch (Exception e) {
+      assertThat(e.getMessage()).contains(
+          "interface com.google.devtools.build.lib.syntax.ClassObject "
+          + "is not allowed as a Skylark value");
+    }
 
     // Also test for these bazel classes, to avoid some regression.
     // TODO(bazel-team): move to some other place to remove dependency of syntax tests on Artifact?
@@ -342,17 +348,17 @@ public class ValidationTest extends EvaluationTestCase {
     assertThat(SkylarkType.LIST.includes(combo1)).isTrue();
 
     SkylarkType union1 =
-        SkylarkType.Union.of(SkylarkType.MAP, SkylarkType.LIST, SkylarkType.STRUCT);
-    assertThat(union1.includes(SkylarkType.MAP)).isTrue();
+        SkylarkType.Union.of(SkylarkType.DICT, SkylarkType.LIST, SkylarkType.STRUCT);
+    assertThat(union1.includes(SkylarkType.DICT)).isTrue();
     assertThat(union1.includes(SkylarkType.STRUCT)).isTrue();
     assertThat(union1.includes(combo1)).isTrue();
     assertThat(union1.includes(SkylarkType.STRING)).isFalse();
 
     SkylarkType union2 =
         SkylarkType.Union.of(
-            SkylarkType.LIST, SkylarkType.MAP, SkylarkType.STRING, SkylarkType.INT);
+            SkylarkType.LIST, SkylarkType.DICT, SkylarkType.STRING, SkylarkType.INT);
     SkylarkType inter1 = SkylarkType.intersection(union1, union2);
-    assertThat(inter1.includes(SkylarkType.MAP)).isTrue();
+    assertThat(inter1.includes(SkylarkType.DICT)).isTrue();
     assertThat(inter1.includes(SkylarkType.LIST)).isTrue();
     assertThat(inter1.includes(combo1)).isTrue();
     assertThat(inter1.includes(SkylarkType.INT)).isFalse();