Unify Skylark and BUILD lists

Use SkylarkList everywhere rather than either List or GlobList.
Keep a GlobList underneath a MutableList, where applicable.

--
MOS_MIGRATED_REVID=105864035
diff --git a/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java b/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
index 6d0f904..941849d 100644
--- a/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
+++ b/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
@@ -17,14 +17,13 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Runtime.NoneType;
 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;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
 import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
-import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor.HackHackEitherList;
 
 import java.util.Arrays;
-import java.util.List;
 import java.util.Map;
 
 /**
@@ -55,12 +54,12 @@
       return "<a class=\"anchor\" href=\"string.html\">string</a>";
     } else if (Map.class.isAssignableFrom(type)) {
       return "<a class=\"anchor\" href=\"dict.html\">dict</a>";
-    } else if (Tuple.class.isAssignableFrom(type)) {
+    } else if (type.equals(Tuple.class)) {
       return "<a class=\"anchor\" href=\"list.html\">tuple</a>";
-    } else if (List.class.isAssignableFrom(type) || SkylarkList.class.isAssignableFrom(type)
-        || type == HackHackEitherList.class) {
-      // Annotated Java methods can return simple java.util.Lists (which get auto-converted).
+    } else if (type.equals(MutableList.class)) {
       return "<a class=\"anchor\" href=\"list.html\">list</a>";
+    } else if (type.equals(SkylarkList.class)) {
+      return "<a class=\"anchor\" href=\"list.html\">sequence</a>";
     } else if (type.equals(Void.TYPE) || type.equals(NoneType.class)) {
       return "<a class=\"anchor\" href=\"" + TOP_LEVEL_ID + ".html#None\">None</a>";
     } else if (type.isAnnotationPresent(SkylarkModule.class)) {
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 7fcb29d..11a9772 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
@@ -51,10 +51,11 @@
 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.SkylarkList;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
 import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
-import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor.HackHackEitherList;
 import com.google.devtools.build.lib.syntax.Statement;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
@@ -475,13 +476,13 @@
    * @param async if true, start globs in the background but don't block on their completion.
    *        Only use this for heuristic preloading.
    */
-  @SkylarkSignature(name = "glob", objectType = Object.class, returnType = GlobList.class,
+  @SkylarkSignature(name = "glob", objectType = Object.class, returnType = SkylarkList.class,
       doc = "Returns a list of files that match glob search pattern",
       mandatoryPositionals = {
-        @Param(name = "include", type = HackHackEitherList.class, generic1 = String.class,
+        @Param(name = "include", type = SkylarkList.class, generic1 = String.class,
             doc = "a list of strings specifying patterns of files to include.")},
       optionalPositionals = {
-        @Param(name = "exclude", type = HackHackEitherList.class, generic1 = String.class,
+        @Param(name = "exclude", type = SkylarkList.class, generic1 = String.class,
             defaultValue = "[]",
             doc = "a list of strings specifying patterns of files to exclude."),
         // TODO(bazel-team): migrate all existing code to use boolean instead?
@@ -492,8 +493,8 @@
       new BuiltinFunction.Factory("glob") {
         public BuiltinFunction create(final PackageContext originalContext, final boolean async) {
           return new BuiltinFunction("glob", this) {
-            public GlobList<String> invoke(
-                Object include, Object exclude, Integer excludeDirectories,
+            public SkylarkList invoke(
+                SkylarkList include, SkylarkList exclude, Integer excludeDirectories,
                 FuncallExpression ast, Environment env)
                 throws EvalException, ConversionException, InterruptedException {
               return callGlob(
@@ -503,7 +504,7 @@
         }
       };
 
-  static GlobList<String> callGlob(@Nullable PackageContext originalContext,
+  static SkylarkList callGlob(@Nullable PackageContext originalContext,
       boolean async, Object include, Object exclude, boolean excludeDirs,
       FuncallExpression ast, Environment env)
       throws EvalException, ConversionException, InterruptedException {
@@ -520,16 +521,18 @@
     List<String> includes = Type.STRING_LIST.convert(include, "'glob' argument");
     List<String> excludes = Type.STRING_LIST.convert(exclude, "'glob' argument");
 
+    GlobList<String> globList;
     if (async) {
       try {
         context.globber.runAsync(includes, excludes, excludeDirs);
       } catch (GlobCache.BadGlobException e) {
         // Ignore: errors will appear during the actual evaluation of the package.
       }
-      return GlobList.captureResults(includes, excludes, ImmutableList.<String>of());
+      globList = GlobList.captureResults(includes, excludes, ImmutableList.<String>of());
     } else {
-      return handleGlob(includes, excludes, excludeDirs, context, ast);
+      globList = handleGlob(includes, excludes, excludeDirs, context, ast);
     }
+    return new MutableList(globList, env);
   }
 
   /**
@@ -621,20 +624,21 @@
         @Param(name = "name", type = String.class,
             doc = "The name of the rule."),
         // Both parameter below are lists of label designators
-        @Param(name = "environments", type = HackHackEitherList.class, generic1 = Object.class,
+        @Param(name = "environments", type = SkylarkList.class, generic1 = Object.class,
             doc = "A list of Labels for the environments to be grouped, from the same package."),
-        @Param(name = "defaults", type = HackHackEitherList.class, generic1 = Object.class,
+        @Param(name = "defaults", type = SkylarkList.class, generic1 = Object.class,
             doc = "A list of Labels.")}, // TODO(bazel-team): document what that is
       documented = false, useLocation = true)
   private static final BuiltinFunction.Factory newEnvironmentGroupFunction =
       new BuiltinFunction.Factory("environment_group") {
         public BuiltinFunction create(final PackageContext context) {
           return new BuiltinFunction("environment_group", this) {
-            public Runtime.NoneType invoke(String name, Object environmentsO, Object defaultsO,
+            public Runtime.NoneType invoke(
+                String name, SkylarkList environmentsList, SkylarkList defaultsList,
                 Location loc) throws EvalException, ConversionException {
-              List<Label> environments = BuildType.LABEL_LIST.convert(environmentsO,
+              List<Label> environments = BuildType.LABEL_LIST.convert(environmentsList,
                   "'environment_group argument'", context.pkgBuilder.getBuildFileLabel());
-              List<Label> defaults = BuildType.LABEL_LIST.convert(defaultsO,
+              List<Label> defaults = BuildType.LABEL_LIST.convert(defaultsList,
                   "'environment_group argument'", context.pkgBuilder.getBuildFileLabel());
 
               try {
@@ -659,16 +663,16 @@
   @SkylarkSignature(name = "exports_files", returnType = Runtime.NoneType.class,
       doc = "Declare a set of files as exported",
       mandatoryPositionals = {
-        @Param(name = "srcs", type = HackHackEitherList.class, generic1 = String.class,
+        @Param(name = "srcs", type = SkylarkList.class, generic1 = String.class,
             doc = "A list of strings, the names of the files to export.")},
       optionalPositionals = {
         // TODO(blaze-team): make it possible to express a list of label designators,
         // i.e. a java List or Skylark list of Label or String.
-        @Param(name = "visibility", type = HackHackEitherList.class, noneable = true,
+        @Param(name = "visibility", type = SkylarkList.class, noneable = true,
             defaultValue = "None",
             doc = "A list of Labels specifying the visibility of the exported files "
             + "(defaults to public)"),
-        @Param(name = "licenses", type = HackHackEitherList.class, generic1 = String.class,
+        @Param(name = "licenses", type = SkylarkList.class, generic1 = String.class,
             noneable = true, defaultValue = "None",
             doc = "A list of strings specifying the licenses used in the exported code.")},
       documented = false, useAst = true, useEnvironment = true)
@@ -676,7 +680,8 @@
       new BuiltinFunction.Factory("exports_files") {
         public BuiltinFunction create () {
           return new BuiltinFunction("exports_files", this) {
-            public Runtime.NoneType invoke(Object srcs, Object visibility, Object licenses,
+            public Runtime.NoneType invoke(
+                SkylarkList srcs, Object visibility, Object licenses,
                 FuncallExpression ast, Environment env)
                 throws EvalException, ConversionException {
               return callExportsFiles(srcs, visibility, licenses, ast, env);
@@ -741,16 +746,16 @@
   @SkylarkSignature(name = "licenses", returnType = Runtime.NoneType.class,
       doc = "Declare the license(s) for the code in the current package.",
       mandatoryPositionals = {
-        @Param(name = "license_strings", type = HackHackEitherList.class, generic1 = String.class,
+        @Param(name = "license_strings", type = SkylarkList.class, generic1 = String.class,
             doc = "A list of strings, the names of the licenses used.")},
       documented = false, useLocation = true)
   private static final BuiltinFunction.Factory newLicensesFunction =
       new BuiltinFunction.Factory("licenses") {
         public BuiltinFunction create(final PackageContext context) {
           return new BuiltinFunction("licenses", this) {
-            public Runtime.NoneType invoke(Object licensesO, Location loc) {
+            public Runtime.NoneType invoke(SkylarkList licensesList, Location loc) {
               try {
-                License license = BuildType.LICENSE.convert(licensesO, "'licenses' operand");
+                License license = BuildType.LICENSE.convert(licensesList, "'licenses' operand");
                 context.pkgBuilder.setDefaultLicense(license);
               } catch (ConversionException e) {
                 context.eventHandler.handle(Event.error(loc, e.getMessage()));
@@ -801,11 +806,11 @@
         @Param(name = "name", type = String.class,
             doc = "The name of the rule.")},
       optionalNamedOnly = {
-        @Param(name = "packages", type = HackHackEitherList.class, generic1 = String.class,
+        @Param(name = "packages", type = SkylarkList.class, generic1 = String.class,
             defaultValue = "[]",
             doc = "A list of Strings specifying the packages grouped."),
         // java list or list of label designators: Label or String
-        @Param(name = "includes", type = HackHackEitherList.class, generic1 = Object.class,
+        @Param(name = "includes", type = SkylarkList.class, generic1 = Object.class,
             defaultValue = "[]",
             doc = "A list of Label specifiers for the files to include.")},
       documented = false, useAst = true, useEnvironment = true)
@@ -813,7 +818,7 @@
       new BuiltinFunction.Factory("package_group") {
         public BuiltinFunction create() {
           return new BuiltinFunction("package_group", this) {
-            public Runtime.NoneType invoke(String name, Object packages, Object includes,
+            public Runtime.NoneType invoke(String name, SkylarkList packages, SkylarkList includes,
                 FuncallExpression ast, Environment env) throws EvalException, ConversionException {
               return callPackageFunction(name, packages, includes, ast, env);
             }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index f356f25..6551730 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -44,6 +44,7 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.GlobList;
 import com.google.devtools.build.lib.syntax.Runtime;
+import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -1350,13 +1351,22 @@
 
   private void checkAttrValNonEmpty(
       Rule rule, EventHandler eventHandler, Object attributeValue, Integer attrIndex) {
-    if (attributeValue instanceof List<?>) {
-      Attribute attr = getAttribute(attrIndex);
-      if (attr.isNonEmpty() && ((List<?>) attributeValue).isEmpty()) {
-        rule.reportError(rule.getLabel() + ": non empty " + "attribute '" + attr.getName()
-            + "' in '" + name + "' rule '" + rule.getLabel() + "' has to have at least one value",
-            eventHandler);
-      }
+    List<?> list;
+
+    if (attributeValue instanceof SkylarkList) {
+      list = ((SkylarkList) attributeValue).getList();
+    } else if (attributeValue instanceof List<?>) {
+      list = (List<?>) attributeValue;
+    } else {
+      // TODO(bazel-team): Test maps, not just lists, as being non-empty.
+      return;
+    }
+
+    Attribute attr = getAttribute(attrIndex);
+    if (attr.isNonEmpty() && list.isEmpty()) {
+      rule.reportError(rule.getLabel() + ": non empty " + "attribute '" + attr.getName()
+          + "' in '" + name + "' rule '" + rule.getLabel() + "' has to have at least one value",
+          eventHandler);
     }
   }
 
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 63e1c51..cb30847 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
@@ -18,7 +18,6 @@
 import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
-import com.google.devtools.build.lib.syntax.GlobList;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
@@ -39,7 +38,7 @@
 
   // TODO(bazel-team): shouldn't we return a SkylarkList instead?
   @SkylarkSignature(name = "glob", objectType = SkylarkNativeModule.class,
-      returnType = GlobList.class,
+      returnType = SkylarkList.class,
       doc = "Glob returns a list of every file in the current package that:<ul>\n"
           + "<li>Matches at least one pattern in <code>include</code>.</li>\n"
           + "<li>Does not match any of the patterns in <code>exclude</code> "
@@ -57,7 +56,7 @@
           doc = "A flag whether to exclude directories or not.")},
       useAst = true, useEnvironment = true)
   private static final BuiltinFunction glob = new BuiltinFunction("glob") {
-      public GlobList<String> invoke(
+      public SkylarkList invoke(
           SkylarkList include, SkylarkList exclude,
           Integer excludeDirectories, FuncallExpression ast, Environment env)
           throws EvalException, ConversionException, InterruptedException {
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 5d0e75d..b633ea6 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
@@ -14,8 +14,6 @@
 
 package com.google.devtools.build.lib.rules;
 
-import static com.google.devtools.build.lib.syntax.SkylarkType.castList;
-
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.Attribute;
@@ -40,6 +38,7 @@
 import com.google.devtools.build.lib.syntax.UserDefinedFunction;
 import com.google.devtools.build.lib.util.FileTypeSet;
 
+import java.util.List;
 import java.util.Map;
 
 /**
@@ -123,7 +122,8 @@
       }
     }
 
-    for (String flag : castList(arguments.get(FLAGS_ARG), String.class)) {
+    for (String flag : SkylarkList.castSkylarkListOrNoneToList(
+        arguments.get(FLAGS_ARG), String.class, FLAGS_ARG)) {
       builder.setPropertyFlag(flag);
     }
 
@@ -163,16 +163,19 @@
     Object ruleClassesObj = arguments.get(ALLOW_RULES_ARG);
     if (ruleClassesObj != null && ruleClassesObj != Runtime.NONE) {
       builder.allowedRuleClasses(
-          castList(ruleClassesObj, String.class, "allowed rule classes for attribute definition"));
+          SkylarkList.castSkylarkListOrNoneToList(
+              ruleClassesObj, String.class, "allowed rule classes for attribute definition"));
     }
 
-    Iterable<Object> values = castList(arguments.get(VALUES_ARG), Object.class);
+    List<Object> values = SkylarkList.castSkylarkListOrNoneToList(
+        arguments.get(VALUES_ARG), Object.class, VALUES_ARG);
     if (!Iterables.isEmpty(values)) {
       builder.allowedValues(new AllowedValueSet(values));
     }
 
     if (containsNonNoneKey(arguments, PROVIDERS_ARG)) {
-      builder.mandatoryProviders(castList(arguments.get(PROVIDERS_ARG), String.class));
+      builder.mandatoryProviders(SkylarkList.castSkylarkListOrNoneToList(
+          arguments.get(PROVIDERS_ARG), String.class, PROVIDERS_ARG));
     }
 
     if (containsNonNoneKey(arguments, CONFIGURATION_ARG)) {
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 90d3518..ddfe3ff 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
@@ -21,7 +21,6 @@
 import static com.google.devtools.build.lib.packages.BuildType.LABEL;
 import static com.google.devtools.build.lib.packages.BuildType.LABEL_LIST;
 import static com.google.devtools.build.lib.packages.BuildType.LICENSE;
-import static com.google.devtools.build.lib.syntax.SkylarkType.castList;
 import static com.google.devtools.build.lib.syntax.SkylarkType.castMap;
 import static com.google.devtools.build.lib.syntax.Type.BOOLEAN;
 import static com.google.devtools.build.lib.syntax.Type.INTEGER;
@@ -315,7 +314,8 @@
     }
 
     private void registerRequiredFragments(
-        SkylarkList fragments, SkylarkList hostFragments, RuleClass.Builder builder) {
+        SkylarkList fragments, SkylarkList hostFragments, RuleClass.Builder builder)
+        throws EvalException {
       Map<ConfigurationTransition, ImmutableSet<String>> map = new HashMap<>();
       addFragmentsToMap(map, fragments, NONE); // NONE represents target configuration
       addFragmentsToMap(map, hostFragments, HOST);
@@ -324,9 +324,9 @@
     }
 
     private void addFragmentsToMap(Map<ConfigurationTransition, ImmutableSet<String>> map,
-        SkylarkList fragments, ConfigurationTransition config) {
+        SkylarkList fragments, ConfigurationTransition config) throws EvalException {
       if (!fragments.isEmpty()) {
-        map.put(config, ImmutableSet.copyOf(castList(fragments, String.class)));
+        map.put(config, ImmutableSet.copyOf(fragments.getContents(String.class, "fragments")));
       }
     }
   };
@@ -346,7 +346,7 @@
       };
 
 
-  // This class is needed for testing
+  /** The implementation for the magic function "rule" that creates Skylark rule classes */
   public static final class RuleFunction extends BaseFunction {
     // Note that this means that we can reuse the same builder.
     // This is fine since we don't modify the builder from here.
@@ -442,8 +442,8 @@
       @Param(name = "types", type = SkylarkList.class, generic1 = String.class, defaultValue = "[]",
           doc = "a list of the accepted file extensions")})
   private static final BuiltinFunction fileType = new BuiltinFunction("FileType") {
-      public SkylarkFileType invoke(SkylarkList types) throws ConversionException {
-        return SkylarkFileType.of(castList(types, String.class));
+      public SkylarkFileType invoke(SkylarkList types) throws EvalException {
+        return SkylarkFileType.of(types.getContents(String.class, "types"));
       }
     };
 
@@ -512,7 +512,7 @@
             printSimpleTextMessage(key, item, sb, indent, loc, "list element in struct field");
           }
         } else {
-        printSimpleTextMessage(key, value, sb, indent, loc, "struct field");
+          printSimpleTextMessage(key, value, sb, indent, loc, "struct field");
         }
       }
 
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 8f5cfa6..8e9d13e 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
@@ -49,6 +49,7 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression.FuncallException;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallable;
+import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkType;
@@ -399,14 +400,14 @@
   }
 
   @SkylarkCallable(doc = "Splits a shell command to a list of tokens.", documented = false)
-  public List<String> tokenize(String optionString) throws FuncallException {
+  public MutableList tokenize(String optionString) throws FuncallException {
     List<String> options = new ArrayList<>();
     try {
       ShellUtils.tokenize(options, optionString);
     } catch (TokenizationException e) {
       throw new FuncallException(e.getMessage() + " while tokenizing '" + optionString + "'");
     }
-    return ImmutableList.copyOf(options);
+    return new MutableList(options); // no env is provided, so it's effectively immutable
   }
 
   @SkylarkCallable(doc =
@@ -414,10 +415,10 @@
     + "from definition labels (i.e. the label in the output type attribute) to files. Deprecated.",
       documented = false)
   public String expand(@Nullable String expression,
-      List<Artifact> artifacts, Label labelResolver) throws FuncallException {
+      SkylarkList artifacts, Label labelResolver) throws EvalException, FuncallException {
     try {
       Map<Label, Iterable<Artifact>> labelMap = new HashMap<>();
-      for (Artifact artifact : artifacts) {
+      for (Artifact artifact : artifacts.getContents(Artifact.class, "artifacts")) {
         labelMap.put(artifactLabelMap.get(artifact), ImmutableList.of(artifact));
       }
       return LabelExpander.expand(expression, labelMap, labelResolver);
@@ -465,9 +466,11 @@
   }
 
   @SkylarkCallable(documented = false)
-  public boolean checkPlaceholders(String template, List<String> allowedPlaceholders) {
+  public boolean checkPlaceholders(String template, SkylarkList allowedPlaceholders)
+      throws EvalException {
     List<String> actualPlaceHolders = new LinkedList<>();
-    Set<String> allowedPlaceholderSet = ImmutableSet.copyOf(allowedPlaceholders);
+    Set<String> allowedPlaceholderSet =
+        ImmutableSet.copyOf(allowedPlaceholders.getContents(String.class, "allowed_placeholders"));
     ImplicitOutputsFunction.createPlaceholderSubstitutionFormatString(template, actualPlaceHolders);
     for (String placeholder : actualPlaceHolders) {
       if (!allowedPlaceholderSet.contains(placeholder)) {
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 cecf3f5..56f4c20 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
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.rules;
 
-import static com.google.devtools.build.lib.syntax.SkylarkType.castList;
 import static com.google.devtools.build.lib.syntax.SkylarkType.castMap;
 
 import com.google.common.collect.ImmutableCollection;
@@ -151,10 +150,8 @@
       SpawnAction.Builder builder = new SpawnAction.Builder();
       // TODO(bazel-team): builder still makes unnecessary copies of inputs, outputs and args.
       boolean hasCommand = commandO != Runtime.NONE;
-      Iterable<Artifact> actualInputs = castList(inputs, Artifact.class);
-
-      builder.addInputs(actualInputs);
-      builder.addOutputs(castList(outputs, Artifact.class));
+      builder.addInputs(inputs.getContents(Artifact.class, "inputs"));
+      builder.addOutputs(outputs.getContents(Artifact.class, "outputs"));
       if (hasCommand && arguments.size() > 0) {
         // When we use a shell command, add an empty argument before other arguments.
         //   e.g.  bash -c "cmd" '' 'arg1' 'arg2'
@@ -162,7 +159,7 @@
         // arg1 and arg2 will be $1 and $2, as a user exects.
         builder.addArgument("");
       }
-      builder.addArguments(castList(arguments, String.class));
+      builder.addArguments(arguments.getContents(String.class, "arguments"));
       if (executableO != Runtime.NONE) {
         if (executableO instanceof Artifact) {
           Artifact executable = (Artifact) executableO;
@@ -191,7 +188,7 @@
           if (commandList.size() < 3) {
             throw new EvalException(loc, "'command' list has to be of size at least 3");
           }
-          builder.setShellCommand(castList(commandList, String.class, "command"));
+          builder.setShellCommand(commandList.getContents(String.class, "command"));
         } else {
           throw new EvalException(loc, "expected string or list of strings for "
               + "command instead of " + EvalUtils.getDataTypeName(commandO));
@@ -274,7 +271,7 @@
         Location loc, Environment env) throws EvalException {
       try {
         return new LocationExpander(ctx.getRuleContext(),
-                   makeLabelMap(castList(targets, AbstractConfiguredTarget.class)), false)
+                makeLabelMap(targets.getContents(AbstractConfiguredTarget.class, "targets")), false)
             .expand(input);
       } catch (IllegalStateException ise) {
         throw new EvalException(loc, ise);
@@ -353,8 +350,9 @@
       return Runtime.NONE;
     }
 
-    private NestedSet<Artifact> convertInputs(SkylarkList inputs) {
-      return NestedSetBuilder.<Artifact>compileOrder().addAll(inputs.to(Artifact.class)).build();
+    private NestedSet<Artifact> convertInputs(SkylarkList inputs) throws EvalException {
+      return NestedSetBuilder.<Artifact>compileOrder()
+          .addAll(inputs.getContents(Artifact.class, "inputs")).build();
     }
 
     protected UUID generateUuid(RuleContext ruleContext) {
@@ -486,7 +484,7 @@
         builder.addRunfiles(ctx.getRuleContext(), RunfilesProvider.DEFAULT_RUNFILES);
       }
       if (!files.isEmpty()) {
-        builder.addArtifacts(castList(files, Artifact.class));
+        builder.addArtifacts(files.getContents(Artifact.class, "files"));
       }
       if (transitiveFiles != Runtime.NONE) {
         builder.addTransitiveArtifacts(((SkylarkNestedSet) transitiveFiles).getSet(Artifact.class));
@@ -601,7 +599,7 @@
           // The best way to fix this probably is to convert CommandHelper to Skylark.
           CommandHelper helper = new CommandHelper(
               ctx.getRuleContext(),
-              castList(tools, TransitiveInfoCollection.class),
+              tools.getContents(TransitiveInfoCollection.class, "tools"),
               ImmutableMap.copyOf(labelDict));
           String attribute = Type.STRING.convertOptional(attributeO, "attribute", ruleLabel);
           if (expandLocations) {
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 d4d8f6e..c34ad70 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 @@
 import com.google.common.base.Strings;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
@@ -258,47 +257,18 @@
       return (String) lval + (String) rval;
     }
 
-    // list + list, tuple + tuple (list + tuple, tuple + list => error)
-    if (lval instanceof List<?> && rval instanceof List<?>) {
-      List<?> llist = (List<?>) lval;
-      List<?> rlist = (List<?>) rval;
-      if (EvalUtils.isTuple(llist) != EvalUtils.isTuple(rlist)) {
-        throw new EvalException(getLocation(), "can only concatenate "
-            + EvalUtils.getDataTypeName(llist) + " (not \"" + EvalUtils.getDataTypeName(rlist)
-            + "\") to " + EvalUtils.getDataTypeName(llist));
-      }
-      if (llist instanceof GlobList<?> || rlist instanceof GlobList<?>) {
-        return GlobList.concat(llist, rlist);
-      } else {
-        List<Object> result = Lists.newArrayListWithCapacity(llist.size() + rlist.size());
-        result.addAll(llist);
-        result.addAll(rlist);
-        return EvalUtils.makeSequence(result, EvalUtils.isTuple(llist));
-      }
-    }
-
     if (lval instanceof SelectorValue || rval instanceof SelectorValue
         || lval instanceof SelectorList
         || rval instanceof SelectorList) {
       return SelectorList.concat(getLocation(), lval, rval);
     }
 
-    if ((lval instanceof SkylarkList || lval instanceof List<?>)
-        && ((rval instanceof SkylarkList || rval instanceof List<?>))) {
-      SkylarkList left = (SkylarkList) SkylarkType.convertToSkylark(lval, env);
-      SkylarkList right = (SkylarkList) SkylarkType.convertToSkylark(rval, env);
-      boolean isImmutable = left.isTuple();
-      if (isImmutable != right.isTuple()) {
-        throw new EvalException(getLocation(), "can only concatenate "
-            + EvalUtils.getDataTypeName(left) + " (not \"" + EvalUtils.getDataTypeName(right)
-            + "\") to " + EvalUtils.getDataTypeName(left));
-      }
-      Iterable<Object> concatenated = Iterables.concat(left, right);
-      if (isImmutable) {
-        return Tuple.copyOf(concatenated);
-      } else {
-        return new MutableList(concatenated, env);
-      }
+    if ((lval instanceof Tuple) && (rval instanceof Tuple)) {
+      return Tuple.copyOf(Iterables.concat((Tuple) lval, (Tuple) rval));
+    }
+
+    if ((lval instanceof MutableList) && (rval instanceof MutableList)) {
+      return MutableList.concat((MutableList) lval, (MutableList) rval, env);
     }
 
     if (lval instanceof Map<?, ?> && rval instanceof Map<?, ?>) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
index 9b5b95f..fffad90 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BuiltinFunction.java
@@ -17,7 +17,6 @@
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
-import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor.HackHackEitherList;
 import com.google.devtools.build.lib.syntax.SkylarkType.SkylarkFunctionType;
 
 import java.lang.reflect.InvocationTargetException;
@@ -281,9 +280,6 @@
 
     if (returnType != null) {
       Class<?> type = returnType;
-      if (type == HackHackEitherList.class) {
-        type = Object.class;
-      }
       Class<?> methodReturnType = invokeMethod.getReturnType();
       Preconditions.checkArgument(type == methodReturnType,
           "signature for function %s says it returns %s but its invoke method returns %s",
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
index 82ec917..03bc6ff 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -398,17 +398,6 @@
     return isSkylark;
   }
 
-  /**
-   * Is the caller of the current function executing Skylark code?
-   * @return true if this is skylark was enabled when this code was read.
-   */
-  // TODO(bazel-team): Delete this function.
-  // This function is currently used by MethodLibrary to modify behavior of lists
-  // depending on the Skylark-ness of the code; lists should be unified between the two modes.
-  boolean isCallerSkylark() {
-    return continuation.isSkylark;
-  }
-
   @Override
   public Mutability mutability() {
     // the mutability of the environment is that of its dynamic frame.
@@ -808,11 +797,6 @@
     }
 
     Object value = ext.get(nameInLoadedFile);
-    // TODO(bazel-team): Unify data structures between Skylark and BUILD,
-    // and stop doing the conversions below:
-    if (!isSkylark) {
-      value = SkylarkType.convertFromSkylark(value);
-    }
 
     try {
       update(symbol.getName(), value);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index c1382ca..cbe5564 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -43,12 +43,6 @@
  */
 public final class FuncallExpression extends Expression {
 
-  private static enum ArgConversion {
-    FROM_SKYLARK,
-    TO_SKYLARK,
-    NO_CONVERSION
-  }
-
   /**
    * A value class to store Methods with their corresponding SkylarkCallable annotations.
    * This is needed because the annotation is sometimes in a superclass.
@@ -334,6 +328,7 @@
               + Printer.listString(ImmutableList.copyOf(args), "(", ", ", ")", null));
         }
       }
+      // TODO(bazel-team): get rid of this, by having everyone use the Skylark data structures
       result = SkylarkType.convertToSkylark(result, method, env);
       if (result != null && !EvalUtils.isSkylarkAcceptable(result.getClass())) {
         throw new EvalException(loc, Printer.format(
@@ -444,9 +439,8 @@
 
   @SuppressWarnings("unchecked")
   private void evalArguments(ImmutableList.Builder<Object> posargs, Map<String, Object> kwargs,
-      Environment env, BaseFunction function)
+      Environment env)
       throws EvalException, InterruptedException {
-    ArgConversion conversion = getArgConversion(function);
     ImmutableList.Builder<String> duplicates = new ImmutableList.Builder<>();
     // Iterate over the arguments. We assume all positional arguments come before any keyword
     // or star arguments, because the argument list was already validated by
@@ -454,14 +448,6 @@
     // which should be the only place that build FuncallExpression-s.
     for (Argument.Passed arg : args) {
       Object value = arg.getValue().eval(env);
-      if (conversion == ArgConversion.FROM_SKYLARK) {
-        value = SkylarkType.convertFromSkylark(value);
-      } else if (conversion == ArgConversion.TO_SKYLARK) {
-        // We try to auto convert the type if we can.
-        value = SkylarkType.convertToSkylark(value, env);
-        // We call into Skylark so we need to be sure that the caller uses the appropriate types.
-        SkylarkType.checkTypeAllowedInSkylark(value, getLocation());
-      } // else NO_CONVERSION
       if (arg.isPositional()) {
         posargs.add(value);
       } else if (arg.isStar()) {  // expand the starArg
@@ -514,10 +500,8 @@
         // Add self as an implicit parameter in front.
         posargs.add(objValue);
       }
-      evalArguments(posargs, kwargs, env, function);
-      return convertFromSkylark(
-          function.call(posargs.build(), ImmutableMap.<String, Object>copyOf(kwargs), this, env),
-          env);
+      evalArguments(posargs, kwargs, env);
+      return function.call(posargs.build(), ImmutableMap.<String, Object>copyOf(kwargs), this, env);
     } else if (objValue instanceof ClassObject) {
       Object fieldValue = ((ClassObject) objValue).getValue(func.getName());
       if (fieldValue == null) {
@@ -529,15 +513,13 @@
             getLocation(), String.format("struct field '%s' is not a function", func.getName()));
       }
       function = (BaseFunction) fieldValue;
-      evalArguments(posargs, kwargs, env, function);
-      return convertFromSkylark(
-          function.call(posargs.build(), ImmutableMap.<String, Object>copyOf(kwargs), this, env),
-          env);
+      evalArguments(posargs, kwargs, env);
+      return function.call(posargs.build(), ImmutableMap.<String, Object>copyOf(kwargs), this, env);
     } else if (env.isSkylark()) {
       // Only allow native Java calls when using Skylark
       // When calling a Java method, the name is not in the Environment,
       // so evaluating 'func' would fail.
-      evalArguments(posargs, kwargs, env, null);
+      evalArguments(posargs, kwargs, env);
       Class<?> objClass;
       Object obj;
       if (objValue instanceof Class<?>) {
@@ -579,38 +561,14 @@
     Map<String, Object> kwargs = new HashMap<>();
     if ((funcValue instanceof BaseFunction)) {
       BaseFunction function = (BaseFunction) funcValue;
-      evalArguments(posargs, kwargs, env, function);
-      return convertFromSkylark(
-          function.call(posargs.build(), ImmutableMap.<String, Object>copyOf(kwargs), this, env),
-          env);
+      evalArguments(posargs, kwargs, env);
+      return function.call(posargs.build(), ImmutableMap.<String, Object>copyOf(kwargs), this, env);
     } else {
       throw new EvalException(
           getLocation(), "'" + EvalUtils.getDataTypeName(funcValue) + "' object is not callable");
     }
   }
 
-  protected Object convertFromSkylark(Object returnValue, Environment env) throws EvalException {
-    EvalUtils.checkNotNull(this, returnValue);
-    if (!env.isSkylark()) {
-      // The call happens in the BUILD language. Note that accessing "BUILD language" functions in
-      // Skylark should never happen.
-      return SkylarkType.convertFromSkylark(returnValue);
-    }
-    return returnValue;
-  }
-
-  private ArgConversion getArgConversion(BaseFunction function) {
-    if (function == null) {
-      // It means we try to call a Java function.
-      return ArgConversion.FROM_SKYLARK;
-    }
-    // If we call a UserDefinedFunction we call into Skylark. If we call from Skylark
-    // the argument conversion is invariant, but if we call from the BUILD language
-    // we might need an auto conversion.
-    return function instanceof UserDefinedFunction
-        ? ArgConversion.TO_SKYLARK : ArgConversion.NO_CONVERSION;
-  }
-
   /**
    * Returns the value of the argument 'name' (or null if there is none).
    * This function is used to associate debugging information to rules created by skylark "macros".
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 bfb777e..567fdaf 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
@@ -59,7 +59,7 @@
 
     @Override
     public Object getResult(Environment env) throws EvalException {
-      return env.isSkylark() ? new MutableList(result, env) : result;
+      return new MutableList(result, env);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
index cf620bd..13c4d01 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
@@ -88,11 +88,7 @@
       }
       result.add(expr.eval(env));
     }
-    if (env.isSkylark()) {
-      return isTuple() ? Tuple.copyOf(result) : new MutableList(result, env);
-    } else {
-      return EvalUtils.makeSequence(result, isTuple());
-    }
+    return isTuple() ? Tuple.copyOf(result) : new MutableList(result, env);
   }
 
   @Override
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 e8e8767..62cb8df 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
@@ -14,8 +14,8 @@
 
 package com.google.devtools.build.lib.syntax;
 
-import com.google.common.base.Joiner;
 import com.google.common.base.CharMatcher;
+import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
@@ -27,12 +27,9 @@
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
-import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor.HackHackEitherList;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
 
 import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collection;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.LinkedList;
@@ -52,16 +49,6 @@
 
   private MethodLibrary() {}
 
-  // TODO(bazel-team):
-  // the Build language and Skylark currently have different list types:
-  // the Build language uses plain java List (usually ArrayList) which is mutable and accepts
-  // any argument, whereas Skylark uses SkylarkList which is immutable and accepts only
-  // arguments of the same kind. Some methods below use HackHackEitherList as a magic marker
-  // to indicate that either kind of lists is used depending on the evaluation context.
-  // It might be a good idea to either have separate methods for the two languages where it matters,
-  // or to unify the two languages so they use the same data structure (which might require
-  // updating all existing clients).
-
   // Convert string index in the same way Python does.
   // If index is negative, starts from the end.
   // If index is outside bounds, it is restricted to the valid range.
@@ -114,11 +101,10 @@
           + "<pre class=\"language-python\">\"|\".join([\"a\", \"b\", \"c\"]) == \"a|b|c\"</pre>",
       mandatoryPositionals = {
         @Param(name = "self", type = String.class, doc = "This string, a separator."),
-        @Param(name = "elements", type = HackHackEitherList.class, doc = "The objects to join.")})
+        @Param(name = "elements", type = SkylarkList.class, doc = "The objects to join.")})
   private static BuiltinFunction join = new BuiltinFunction("join") {
-    public String invoke(String self, Object elements) throws ConversionException {
-      List<?> seq = Type.OBJECT_LIST.convert(elements, "'join.elements' argument");
-      return Joiner.on(self).join(seq);
+    public String invoke(String self, SkylarkList elements) throws ConversionException {
+      return Joiner.on(self).join(elements);
     }
   };
 
@@ -281,7 +267,7 @@
   };
 
   @SkylarkSignature(name = "split", objectType = StringModule.class,
-      returnType = HackHackEitherList.class,
+      returnType = MutableList.class,
       doc = "Returns a list of all the words in the string, using <code>sep</code>  "
           + "as the separator, optionally limiting the number of splits to <code>maxsplit</code>.",
       mandatoryPositionals = {
@@ -293,18 +279,18 @@
       useEnvironment = true,
       useLocation = true)
   private static BuiltinFunction split = new BuiltinFunction("split") {
-    public Object invoke(String self, String sep, Object maxSplitO, Location loc,
+    public MutableList 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 convert(Arrays.<String>asList(ss), env);
+      return MutableList.of(env, (Object[]) ss);
     }
   };
 
   @SkylarkSignature(name = "rsplit", objectType = StringModule.class,
-      returnType = HackHackEitherList.class,
+      returnType = MutableList.class,
       doc = "Returns a list of all the words in the string, using <code>sep</code>  "
           + "as the separator, optionally limiting the number of splits to <code>maxsplit</code>. "
           + "Except for splitting from the right, this method behaves like split().",
@@ -318,19 +304,18 @@
       useLocation = true)
   private static BuiltinFunction rsplit = new BuiltinFunction("rsplit") {
     @SuppressWarnings("unused")
-    public Object invoke(String self, String sep, Object maxSplitO, Location loc, Environment env)
+    public MutableList 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 {
-        result = stringRSplit(self, sep, maxSplit);
+        return stringRSplit(self, sep, maxSplit, env);
       } catch (IllegalArgumentException ex) {
         throw new EvalException(loc, ex);
       }
-
-      return convert(result, env);
     }
   };
 
@@ -346,7 +331,8 @@
    * @return A list of words
    * @throws IllegalArgumentException
    */
-  private static List<String> stringRSplit(String input, String separator, int maxSplits)
+  private static MutableList stringRSplit(
+      String input, String separator, int maxSplits, Environment env)
       throws IllegalArgumentException {
     if (separator.isEmpty()) {
       throw new IllegalArgumentException("Empty separator");
@@ -378,11 +364,11 @@
       result.addFirst(input.substring(0, remainingLength));
     }
 
-    return result;
+    return new MutableList(result, env);
   }
 
   @SkylarkSignature(name = "partition", objectType = StringModule.class,
-      returnType = HackHackEitherList.class,
+      returnType = MutableList.class,
       doc = "Splits the input string at the first occurrence of the separator "
           + "<code>sep</code> and returns the resulting partition as a three-element "
           + "list of the form [substring_before, separator, substring_after].",
@@ -395,14 +381,14 @@
       useLocation = true)
   private static BuiltinFunction partition = new BuiltinFunction("partition") {
     @SuppressWarnings("unused")
-    public Object invoke(String self, String sep, Location loc, Environment env)
+    public MutableList invoke(String self, String sep, Location loc, Environment env)
         throws EvalException {
       return partitionWrapper(self, sep, true, env, loc);
     }
   };
 
   @SkylarkSignature(name = "rpartition", objectType = StringModule.class,
-      returnType = HackHackEitherList.class,
+      returnType = MutableList.class,
       doc = "Splits the input string at the last occurrence of the separator "
           + "<code>sep</code> and returns the resulting partition as a three-element "
           + "list of the form [substring_before, separator, substring_after].",
@@ -415,7 +401,7 @@
       useLocation = true)
   private static BuiltinFunction rpartition = new BuiltinFunction("rpartition") {
     @SuppressWarnings("unused")
-    public Object invoke(String self, String sep, Location loc, Environment env)
+    public MutableList invoke(String self, String sep, Location loc, Environment env)
         throws EvalException {
       return partitionWrapper(self, sep, false, env, loc);
     }
@@ -433,10 +419,10 @@
    * @param loc The location that is used for potential exceptions
    * @return A list with three elements
    */
-  private static Object partitionWrapper(String self, String separator, boolean forward,
+  private static MutableList partitionWrapper(String self, String separator, boolean forward,
       Environment env, Location loc) throws EvalException {
     try {
-      return convert(stringPartition(self, separator, forward), env);
+      return new MutableList(stringPartition(self, separator, forward), env);
     } catch (IllegalArgumentException ex) {
       throw new EvalException(loc, ex);
     }
@@ -445,7 +431,7 @@
   /**
    * Splits the input string at the {first|last} occurrence of the given separator
    * and returns the resulting partition as a three-tuple of Strings, contained
-   * in a {@code List}.
+   * in a {@code MutableList}.
    *
    * <p>If the input string does not contain the separator, the tuple will
    * consist of the original input string and two empty strings.
@@ -742,16 +728,16 @@
           @Param(name = "self", type = String.class, doc = "This string."),
       },
       extraPositionals = {
-          @Param(name = "args", type = HackHackEitherList.class, defaultValue = "[]",
+          @Param(name = "args", type = SkylarkList.class, defaultValue = "()",
               doc = "List of arguments"),
       },
       extraKeywords = {@Param(name = "kwargs", doc = "Dictionary of arguments")},
       useLocation = true)
   private static BuiltinFunction format = new BuiltinFunction("format") {
     @SuppressWarnings("unused")
-    public String invoke(String self, Object args, Map<String, Object> kwargs, Location loc)
+    public String invoke(String self, SkylarkList args, Map<String, Object> kwargs, Location loc)
         throws ConversionException, EvalException {
-      return new FormatParser(loc).format(self, Type.OBJECT_LIST.convert(args, "format"), kwargs);
+      return new FormatParser(loc).format(self, args.getList(), kwargs);
     }
   };
 
@@ -790,20 +776,6 @@
     }
   };
 
-  @SkylarkSignature(name = "$slice", objectType = List.class,
-      documented = false,
-      mandatoryPositionals = {
-        @Param(name = "self", type = List.class, doc = "This list or tuple."),
-        @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
-        @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
-      doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.")
-  private static BuiltinFunction listSlice = new BuiltinFunction("$slice") {
-    public Object invoke(List<Object> self, Integer left, Integer right)
-        throws EvalException, ConversionException {
-      return sliceList(self, left, right);
-    }
-  };
-
   @SkylarkSignature(name = "$slice", objectType = MutableList.class, returnType = MutableList.class,
       documented = false,
       mandatoryPositionals = {
@@ -813,11 +785,11 @@
       doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.",
       useEnvironment = true)
   private static BuiltinFunction mutableListSlice = new BuiltinFunction("$slice") {
-      public MutableList invoke(MutableList self, Integer left, Integer right,
-          Environment env) throws EvalException, ConversionException {
-        return new MutableList(sliceList(self.getList(), left, right), env);
-      }
-    };
+    public MutableList invoke(MutableList self, Integer left, Integer right,
+        Environment env) throws EvalException, ConversionException {
+      return new MutableList(sliceList(self.getList(), left, right), env);
+    }
+  };
 
   @SkylarkSignature(name = "$slice", objectType = Tuple.class, returnType = Tuple.class,
       documented = false,
@@ -846,7 +818,7 @@
   // supported list methods
   @SkylarkSignature(
     name = "sorted",
-    returnType = HackHackEitherList.class,
+    returnType = MutableList.class,
     doc =
         "Sort a collection. Elements are sorted first by their type, "
             + "then by their value (in ascending order).",
@@ -856,46 +828,19 @@
   )
   private static BuiltinFunction sorted =
       new BuiltinFunction("sorted") {
-        public Object invoke(Object self, Location loc, Environment env)
+        public MutableList invoke(Object self, Location loc, Environment env)
             throws EvalException, ConversionException {
           try {
-            Collection<?> col =
-                Ordering.from(EvalUtils.SKYLARK_COMPARATOR)
-                    .sortedCopy(EvalUtils.toCollection(self, loc));
-            return convert(col, env);
+            return new MutableList(
+                Ordering.from(EvalUtils.SKYLARK_COMPARATOR).sortedCopy(
+                    EvalUtils.toCollection(self, loc)),
+                env);
           } catch (EvalUtils.ComparisonException e) {
             throw new EvalException(loc, e);
           }
         }
       };
 
-  // This function has a SkylarkSignature but is only used by the Build language, not Skylark.
-  @SkylarkSignature(
-    name = "append",
-    objectType = List.class,
-    returnType = Runtime.NoneType.class,
-    documented = false,
-    doc = "Adds an item to the end of the list.",
-    mandatoryPositionals = {
-      // we use List rather than SkylarkList because this is actually for use *outside* Skylark
-      @Param(name = "self", type = List.class, doc = "This list."),
-      @Param(name = "item", type = Object.class, doc = "Item to add at the end.")
-    },
-    useLocation = true,
-    useEnvironment = true)
-  private static BuiltinFunction append =
-      new BuiltinFunction("append") {
-        public Runtime.NoneType invoke(List<Object> self, Object item,
-            Location loc, Environment env) throws EvalException, ConversionException {
-          if (EvalUtils.isTuple(self)) {
-            throw new EvalException(loc,
-                "function 'append' is not defined on object of type 'Tuple'");
-          }
-          self.add(item);
-          return Runtime.NONE;
-        }
-      };
-
   @SkylarkSignature(
     name = "append",
     objectType = MutableList.class,
@@ -908,7 +853,7 @@
     },
     useLocation = true,
     useEnvironment = true)
-  private static BuiltinFunction skylarkAppend =
+  private static BuiltinFunction append =
       new BuiltinFunction("append") {
         public Runtime.NoneType invoke(MutableList self, Object item,
             Location loc, Environment env) throws EvalException, ConversionException {
@@ -917,32 +862,6 @@
         }
       };
 
-  // This function has a SkylarkSignature but is only used by the Build language, not Skylark.
-  @SkylarkSignature(
-    name = "extend",
-    objectType = List.class,
-    returnType = Runtime.NoneType.class,
-    documented = false,
-    doc = "Adds all items to the end of the list.",
-    mandatoryPositionals = {
-      // we use List rather than SkylarkList because this is actually for use *outside* Skylark
-      @Param(name = "self", type = List.class, doc = "This list."),
-      @Param(name = "items", type = List.class, doc = "Items to add at the end.")},
-    useLocation = true,
-    useEnvironment = true)
-  private static BuiltinFunction skylarkExtend =
-      new BuiltinFunction("extend") {
-        public Runtime.NoneType invoke(List<Object> self, List<Object> items,
-            Location loc, Environment env) throws EvalException, ConversionException {
-          if (EvalUtils.isTuple(self)) {
-            throw new EvalException(loc,
-                "function 'extend' is not defined on object of type 'Tuple'");
-          }
-          self.addAll(items);
-          return Runtime.NONE;
-        }
-      };
-
   @SkylarkSignature(
     name = "extend",
     objectType = MutableList.class,
@@ -970,7 +889,7 @@
         @Param(name = "self", type = Map.class, doc = "This object."),
         @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
       useLocation = true)
-  private static BuiltinFunction indexOperator = new BuiltinFunction("$index") {
+  private static BuiltinFunction dictIndexOperator = new BuiltinFunction("$index") {
     public Object invoke(Map<?, ?> self, Object key,
         Location loc) throws EvalException, ConversionException {
       if (!self.containsKey(key)) {
@@ -987,7 +906,7 @@
         @Param(name = "self", type = MutableList.class, doc = "This list."),
         @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
       useLocation = true)
-  private static BuiltinFunction mutableListIndexOperator = new BuiltinFunction("$index") {
+  private static BuiltinFunction listIndexOperator = new BuiltinFunction("$index") {
       public Object invoke(MutableList self, Object key,
           Location loc) throws EvalException, ConversionException {
         if (self.isEmpty()) {
@@ -1000,7 +919,7 @@
 
   // tuple access operator
   @SkylarkSignature(name = "$index", documented = false, objectType = Tuple.class,
-      doc = "Returns the nth element of a list.",
+      doc = "Returns the nth element of a tuple.",
       mandatoryPositionals = {
         @Param(name = "self", type = Tuple.class, doc = "This tuple."),
         @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
@@ -1009,31 +928,13 @@
       public Object invoke(Tuple self, Object key,
           Location loc) throws EvalException, ConversionException {
         if (self.isEmpty()) {
-          throw new EvalException(loc, "Tuple is empty");
+          throw new EvalException(loc, "tuple is empty");
         }
         int index = getListIndex(key, self.size(), loc);
         return self.getList().get(index);
       }
     };
 
-  // list access operator
-  @SkylarkSignature(name = "$index", documented = false, objectType = List.class,
-      doc = "Returns the nth element of a list.",
-      mandatoryPositionals = {
-        @Param(name = "self", type = List.class, doc = "This object."),
-        @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
-      useLocation = true)
-  private static BuiltinFunction listIndexOperator = new BuiltinFunction("$index") {
-    public Object invoke(List<?> self, Object key,
-        Location loc) throws EvalException, ConversionException {
-      if (self.isEmpty()) {
-        throw new EvalException(loc, "List is empty");
-      }
-      int index = getListIndex(key, self.size(), loc);
-      return self.get(index);
-    }
-  };
-
   @SkylarkSignature(name = "$index", documented = false, objectType = String.class,
       doc = "Returns the nth element of a string.",
       mandatoryPositionals = {
@@ -1049,58 +950,57 @@
   };
 
   @SkylarkSignature(name = "values", objectType = Map.class,
-      returnType = HackHackEitherList.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.")},
-      useLocation = true, useEnvironment = true)
+      useEnvironment = true)
   private static BuiltinFunction values = new BuiltinFunction("values") {
-    public Object invoke(Map<?, ?> self,
-        Location loc, Environment env) throws EvalException, ConversionException {
+    public MutableList invoke(Map<?, ?> self,
+        Environment env) throws EvalException, ConversionException {
       // Use a TreeMap to ensure consistent ordering.
       Map<?, ?> dict = new TreeMap<>(self);
-      return convert(dict.values(), env);
+      return new MutableList(dict.values(), env);
     }
   };
 
   @SkylarkSignature(name = "items", objectType = Map.class,
-      returnType = HackHackEitherList.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.")},
-      useLocation = true, useEnvironment = true)
+      useEnvironment = true)
   private static BuiltinFunction items = new BuiltinFunction("items") {
-    public Object invoke(Map<?, ?> self,
-        Location loc, Environment env) throws EvalException, ConversionException {
+    public MutableList invoke(Map<?, ?> 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<?> item = ImmutableList.of(entries.getKey(), entries.getValue());
-        list.add(env.isCallerSkylark() ? Tuple.copyOf(item) : item);
+        list.add(Tuple.of(entries.getKey(), entries.getValue()));
       }
-      return convert(list, env);
+      return new MutableList(list, env);
     }
   };
 
   @SkylarkSignature(name = "keys", objectType = Map.class,
-      returnType = HackHackEitherList.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.")},
-      useLocation = true, useEnvironment = true)
+      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 Object invoke(Map<Comparable<?>, ?> dict,
-        Location loc, Environment env) throws EvalException {
-      return convert(Ordering.natural().sortedCopy(dict.keySet()), env);
+    public MutableList invoke(Map<Comparable<?>, ?> dict,
+        Environment env) throws EvalException {
+      return new MutableList(Ordering.natural().sortedCopy(dict.keySet()), env);
     }
   };
 
@@ -1123,17 +1023,6 @@
     }
   };
 
-  // TODO(bazel-team): Use the same type for both Skylark and BUILD files.
-  @SuppressWarnings("unchecked")
-  private static Iterable<Object> convert(Collection<?> list, Environment env)
-      throws EvalException {
-    if (env.isCallerSkylark()) {
-      return new MutableList(list, env);
-    } else {
-      return Lists.newArrayList(list);
-    }
-  }
-
   // unary minus
   @SkylarkSignature(name = "-", returnType = Integer.class,
       documented = false,
@@ -1350,29 +1239,28 @@
     }
   };
 
-  @SkylarkSignature(name = "enumerate", returnType = HackHackEitherList.class,
+  @SkylarkSignature(name = "enumerate", returnType = MutableList.class,
       doc = "Returns a list of pairs (two-element tuples), with the index (int) and the item from"
           + " the input list.\n<pre class=\"language-python\">"
           + "enumerate([24, 21, 84]) == [(0, 24), (1, 21), (2, 84)]</pre>\n",
       mandatoryPositionals = {
-        @Param(name = "list", type = HackHackEitherList.class, doc = "input list")
+        @Param(name = "list", type = SkylarkList.class, doc = "input list")
       },
-      useLocation = true,
       useEnvironment = true)
   private static BuiltinFunction enumerate = new BuiltinFunction("enumerate") {
-    public Object invoke(Object input, Location loc, Environment env)
+    public MutableList invoke(SkylarkList input, Environment env)
         throws EvalException, ConversionException {
       int count = 0;
       List<SkylarkList> result = Lists.newArrayList();
-      for (Object obj : Type.OBJECT_LIST.convert(input, "input")) {
+      for (Object obj : input) {
         result.add(Tuple.of(count, obj));
         count++;
       }
-      return convert(result, env);
+      return new MutableList(result, env);
     }
   };
 
-  @SkylarkSignature(name = "range", returnType = HackHackEitherList.class,
+  @SkylarkSignature(name = "range", returnType = MutableList.class,
       doc = "Creates a list where items go from <code>start</code> to <code>stop</code>, using a "
           + "<code>step</code> increment. If a single argument is provided, items will "
           + "range from 0 to that element."
@@ -1393,8 +1281,8 @@
       useLocation = true,
       useEnvironment = true)
   private static final BuiltinFunction range = new BuiltinFunction("range") {
-      public Object invoke(Integer startOrStop, Object stopOrNone, Integer step, Location loc,
-          Environment env)
+      public MutableList invoke(Integer startOrStop, Object stopOrNone, Integer step,
+          Location loc, Environment env)
         throws EvalException, ConversionException {
       int start;
       int stop;
@@ -1420,7 +1308,7 @@
           start += step;
         }
       }
-      return convert(result, env);
+      return new MutableList(result, env);
     }
   };
 
@@ -1499,13 +1387,13 @@
     }
   };
 
-  @SkylarkSignature(name = "dir", returnType = SkylarkList.class,
+  @SkylarkSignature(name = "dir", returnType = MutableList.class,
       doc = "Returns a list strings: the names of the attributes and "
           + "methods of the parameter object.",
       mandatoryPositionals = {@Param(name = "x", doc = "The object to check.")},
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction dir = new BuiltinFunction("dir") {
-    public SkylarkList invoke(Object object,
+    public MutableList invoke(Object object,
         Location loc, Environment env) throws EvalException, ConversionException {
       // Order the fields alphabetically.
       Set<String> fields = new TreeSet<>();
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 6f597cf..67b7db6 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
@@ -14,8 +14,8 @@
 
 package com.google.devtools.build.lib.syntax;
 
-import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.Mutability.Freezable;
@@ -47,6 +47,15 @@
   public abstract ImmutableList<Object> getImmutableList();
 
   /**
+   * Returns a List object with the current underlying contents of this SkylarkList.
+   * This object must not be modified, but may not be an ImmutableList.
+   * It may notably be a GlobList, where appropriate.
+   */
+  // TODO(bazel-team): move GlobList out of Skylark, into an extension,
+  // and maybe get rid of this method?
+  public abstract List<Object> getContents();
+
+  /**
    * Returns true if this list is a tuple.
    */
   public abstract boolean isTuple();
@@ -99,17 +108,61 @@
     return getClass().hashCode() + 31 * getList().hashCode();
   }
 
+  /**
+   * Cast a {@code List<?>} to a {@code List<T>} after checking its current contents.
+   * @param list the List to cast
+   * @param type the expected class of elements
+   * @param description a description of the argument being converted, or null, for debugging
+   */
   @SuppressWarnings("unchecked")
-  public <T> Iterable<T> to(Class<T> type) {
-    for (Object value : getList()) {
-      Preconditions.checkArgument(
-          type.isInstance(value),
-          Printer.formattable("list element %r is not of type %r", value, type));
+  public static <TYPE> List<TYPE> castList(
+      List<?> list, Class<TYPE> type, @Nullable String description)
+      throws EvalException {
+    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)));
+      }
     }
-    return (Iterable<T>) this;
+    return (List<TYPE>) list;
   }
 
   /**
+   * Cast a SkylarkList to a {@code List<T>} after checking its current contents.
+   * Treat None as meaning the empty List.
+   * @param obj the Object to cast. null and None are treated as an empty list.
+   * @param type the expected class of elements
+   * @param description a description of the argument being converted, or null, for debugging
+   */
+  public static <TYPE> List<TYPE> castSkylarkListOrNoneToList(
+      Object obj, Class<TYPE> type, @Nullable String description)
+      throws EvalException {
+    if (EvalUtils.isNullOrNone(obj)) {
+      return ImmutableList.of();
+    }
+    if (obj instanceof SkylarkList) {
+      return ((SkylarkList) obj).getContents(type, description);
+    }
+    throw new EvalException(null,
+        Printer.format("Illegal argument: %s is not of expected type list or NoneType",
+            description == null ? Printer.repr(obj) : String.format("'%s'", description)));
+  }
+
+  /**
+   * Cast the SkylarkList object into a List of the given type.
+   * @param type the expected class of elements
+   * @param description a description of the argument being converted, or null, for debugging
+   */
+  public <TYPE> List<TYPE> getContents(Class<TYPE> type, @Nullable String description)
+      throws EvalException {
+    return castList(getContents(), type, description);
+  }
+
+
+  /**
    * A class for mutable lists.
    */
   @SkylarkModule(name = "list",
@@ -126,6 +179,12 @@
 
     private final ArrayList<Object> 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;
+
     private final Mutability mutability;
 
     /**
@@ -137,6 +196,9 @@
     MutableList(Iterable<?> contents, Mutability mutability) {
       super();
       addAll(contents);
+      if (contents instanceof GlobList<?>) {
+        globList = (GlobList<?>) contents;
+      }
       this.mutability = mutability;
     }
 
@@ -160,6 +222,16 @@
     }
 
     /**
+     * Builds a Skylark list (actually immutable) from a variable number of arguments.
+     * @param env an Environment from which to inherit Mutability, or null for immutable
+     * @param contents the contents of the list
+     * @return a Skylark list containing the specified arguments as elements.
+     */
+    public static MutableList of(Environment env, Object... contents) {
+      return new MutableList(ImmutableList.copyOf(contents), env);
+    }
+
+    /**
      * Adds one element at the end of the MutableList.
      * @param element the element to add
      */
@@ -183,6 +255,48 @@
       } catch (MutabilityException ex) {
         throw new EvalException(loc, ex);
       }
+      globList = null; // If you're going to mutate it, invalidate the underlying GlobList.
+    }
+
+    @Nullable public GlobList<?> getGlobList() {
+      return globList;
+    }
+
+    /**
+     * @return the GlobList if there is one, otherwise an Immutable copy of the regular contents.
+     */
+    @Override
+    @SuppressWarnings("unchecked")
+    public List<Object> getContents() {
+      if (globList != null) {
+        return (List<Object>) (List<?>) globList;
+      }
+      return getImmutableList();
+    }
+
+    /**
+     * @return the GlobList if there is one, otherwise the regular contents.
+     */
+    private List<?> getContentsUnsafe() {
+      if (globList != null) {
+        return globList;
+      }
+      return contents;
+    }
+
+    /**
+     * Concatenate two MutableList
+     * @param left the start of the new list
+     * @param right the end of the new list
+     * @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) {
+      if (left.getGlobList() == null && right.getGlobList() == null) {
+        return new MutableList(Iterables.concat(left, right), env);
+      }
+      return new MutableList(GlobList.concat(
+          left.getContentsUnsafe(), right.getContentsUnsafe()), env);
     }
 
     /**
@@ -304,6 +418,11 @@
     }
 
     @Override
+    public List<Object> getContents() {
+      return contents;
+    }
+
+    @Override
     public boolean isTuple() {
       return true;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
index 6b96dac..44f9783 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
@@ -115,18 +115,6 @@
   }
 
   /**
-   * Fake class to use in SkylarkSignature annotations to indicate that either List or SkylarkList
-   * may be used, depending on whether the Build language or Skylark is being evaluated.
-   */
-  // TODO(bazel-team): either make SkylarkList a subclass of List (mutable or immutable throwing
-  // runtime exceptions), or have the Build language use immutable SkylarkList, but either way,
-  // do away with this hack.
-  public static class HackHackEitherList {
-    private HackHackEitherList() { }
-  }
-
-
-  /**
    * Configures the parameter of this Skylark function using the annotation.
    */
   // TODO(bazel-team): Maybe have the annotation be a string representing the
@@ -146,18 +134,8 @@
       return new Parameter.Star<>(null);
     }
     if (param.type() != Object.class) {
-      if (param.type() == HackHackEitherList.class) {
-        // NB: a List in the annotation actually indicates either a List or a SkylarkList
-        // and we trust the BuiltinFunction to do the enforcement.
-        // For automatic document generation purpose, we lie and just say it's a list;
-        // hopefully user code should never be exposed to the java List case
-        officialType = SkylarkType.of(SkylarkList.class, param.generic1());
-        enforcedType = SkylarkType.Union.of(
-            SkylarkType.of(List.class),
-            SkylarkType.of(SkylarkList.class, param.generic1()));
-        Preconditions.checkArgument(enforcedType instanceof SkylarkType.Union);
-      } else if (param.generic1() != Object.class) {
-        // Otherwise, we will enforce the proper parametric type for Skylark list and set objects
+      if (param.generic1() != Object.class) {
+        // Enforce the proper parametric type for Skylark list and set objects
         officialType = SkylarkType.of(param.type(), param.generic1());
         enforcedType = officialType;
       } else {
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 f79b129..190dfb1 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
@@ -644,34 +644,6 @@
     }
   }
 
-  /** Cast a SkylarkList object into an Iterable of the given type. Treat null as empty List */
-  public static <TYPE> Iterable<TYPE> castList(Object obj, final Class<TYPE> type) {
-    if (obj == null) {
-      return ImmutableList.of();
-    }
-    return ((SkylarkList) obj).to(type);
-  }
-
-  /** Cast a List or SkylarkList object into an Iterable of the given type. null means empty List */
-  public static <TYPE> Iterable<TYPE> castList(
-      Object obj, final Class<TYPE> type, final String what) throws EvalException {
-    if (obj == null) {
-      return ImmutableList.of();
-    }
-    List<TYPE> results = new ArrayList<>();
-    for (Object object : com.google.devtools.build.lib.syntax.Type.LIST.convert(obj, what)) {
-      try {
-        results.add(type.cast(object));
-      } catch (ClassCastException e) {
-        throw new EvalException(null, String.format(
-            "Illegal argument: expected %s type for '%s' but got %s instead",
-            EvalUtils.getDataTypeNameFromClass(type), what,
-            EvalUtils.getDataTypeName(object)));
-      }
-    }
-    return results;
-  }
-
   /**
    * Cast a Map object into an Iterable of Map entries of the given key, value types.
    * @param obj the Map object, where null designates an empty map
@@ -749,17 +721,4 @@
     }
     return object;
   }
-
-  /**
-   * Converts object from a Skylark-compatible wrapper type to its original type.
-   */
-  public static Object convertFromSkylark(Object value) {
-    if (value instanceof MutableList) {
-      return new ArrayList<>(((MutableList) value).getList());
-    } else if (value instanceof Tuple) {
-      return ((Tuple) value).getImmutableList();
-    } else {
-      return value;
-    }
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Type.java b/src/main/java/com/google/devtools/build/lib/syntax/Type.java
index e876781..a3d348c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Type.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Type.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.util.LoggingUtil;
 import com.google.devtools.build.lib.util.StringCanonicalizer;
 
@@ -558,11 +559,20 @@
         }
         ++index;
       }
+      // We preserve GlobList-s so they can make it to attributes;
+      // some external code relies on attributes preserving this information.
+      // TODO(bazel-team): somehow make Skylark extensible enough that
+      // GlobList support can be wholly moved out of Skylark into an extension.
       if (x instanceof GlobList<?>) {
         return new GlobList<>(((GlobList<?>) x).getCriteria(), result);
-      } else {
-        return result;
       }
+      if (x instanceof MutableList) {
+        GlobList<?> globList = ((MutableList) x).getGlobList();
+        if (globList != null) {
+          return new GlobList<>(globList.getCriteria(), result);
+        }
+      }
+      return result;
     }
 
     @Override
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 c753d68..f97c452 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
@@ -310,7 +310,7 @@
   public void testCreateSpawnActionBadGenericArg() throws Exception {
     checkErrorContains(
         createRuleContext("//foo:foo"),
-        "Illegal argument in call to action: list element \"a\" is not of type File",
+        "Illegal argument: expected type File for 'outputs' element but got type string instead",
         "l = ['a', 'b']",
         "ruleContext.action(",
         "  outputs = l,",
@@ -552,7 +552,7 @@
 
   public void testRunfilesBadListGenericType() throws Exception {
     checkErrorContains(
-        "Illegal argument in call to runfiles: list element \"some string\" is not of type File",
+        "Illegal argument: expected type File for 'files' element but got type string instead",
         "ruleContext.runfiles(files = ['some string'])");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java b/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java
index b036e5a..85880c7 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/BuildFileASTTest.java
@@ -1,4 +1,4 @@
-// Copyright 2006-2015 Google Inc. All Rights Reserved.
+// Copyright 2006 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.
@@ -23,6 +23,8 @@
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventCollector;
 import com.google.devtools.build.lib.packages.CachingPackageLocator;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.vfs.Path;
@@ -32,7 +34,6 @@
 import org.junit.runners.JUnit4;
 
 import java.io.IOException;
-import java.util.Arrays;
 
 /**
  * Unit tests for BuildFileAST.
@@ -78,8 +79,8 @@
     //
     // input1.BUILD contains:
     // x = [1,2,'foo',4] + [1,2, "%s%d" % ('foo', 1)]
-    assertEquals(Arrays.<Object>asList(1, 2, "foo", 4, 1, 2, "foo1"),
-                 env.lookup("x"));
+    assertEquals(new MutableList(Tuple.of(1, 2, "foo", 4, 1, 2, "foo1")),
+        env.lookup("x"));
   }
 
   @Test
@@ -94,7 +95,7 @@
     BuildFileAST buildfile = BuildFileAST.parseBuildFile(buildFile, getEventHandler(), false);
 
     assertFalse(buildfile.exec(env, getEventHandler()));
-    Event e = assertContainsEvent("unsupported operand type(s) for +: 'int' and 'List'");
+    Event e = assertContainsEvent("unsupported operand type(s) for +: 'int' and 'list'");
     assertEquals(4, e.getLocation().getStartLineAndColumn().getLine());
   }
 
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 9e9b0c0..3816c4b 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
@@ -18,8 +18,9 @@
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
 import com.google.devtools.build.lib.testutil.TestMode;
 
@@ -28,7 +29,6 @@
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.util.Arrays;
 import java.util.Collections;
 import java.util.List;
 import java.util.Map;
@@ -324,15 +324,15 @@
     // list
     Object x = eval("[1,2] + [3,4]");
     assertThat((Iterable<Object>) x).containsExactly(1, 2, 3, 4).inOrder();
-    assertEquals(Arrays.asList(1, 2, 3, 4), x);
+    assertEquals(MutableList.of(env, 1, 2, 3, 4), x);
     assertFalse(EvalUtils.isImmutable(x));
 
     // tuple
     x = eval("(1,2) + (3,4)");
-    assertEquals(Arrays.asList(1, 2, 3, 4), x);
+    assertEquals(Tuple.of(1, 2, 3, 4), x);
     assertTrue(EvalUtils.isImmutable(x));
 
-    checkEvalError("can only concatenate Tuple (not \"List\") to Tuple",
+    checkEvalError("unsupported operand type(s) for +: 'tuple' and 'list'",
         "(1,2) + [3,4]"); // list + tuple
   }
 
@@ -392,8 +392,8 @@
 
   @Test
   public void testListComprehensionsMultipleVariables() throws Exception {
-    newTest().testEval("[x + y for x, y in [(1, 2), (3, 4)]]", "[3, 7]").testEval(
-        "[z + t for (z, t) in [[1, 2], [3, 4]]]", "[3, 7]");
+    newTest().testEval("[x + y for x, y in [(1, 2), (3, 4)]]", "[3, 7]")
+        .testEval("[z + t for (z, t) in [[1, 2], [3, 4]]]", "[3, 7]");
   }
 
   @Test
@@ -510,10 +510,12 @@
   @Test
   public void testListConcatenation() throws Exception {
     newTest()
-        .testStatement("[1, 2] + [3, 4]", Arrays.asList(1, 2, 3, 4))
-        .testStatement("(1, 2) + (3, 4)", ImmutableList.of(1, 2, 3, 4))
-        .testIfExactError("can only concatenate List (not \"Tuple\") to List", "[1, 2] + (3, 4)")
-        .testIfExactError("can only concatenate Tuple (not \"List\") to Tuple", "(1, 2) + [3, 4]");
+        .testStatement("[1, 2] + [3, 4]", MutableList.of(env, 1, 2, 3, 4))
+        .testStatement("(1, 2) + (3, 4)", Tuple.of(1, 2, 3, 4))
+        .testIfExactError("unsupported operand type(s) for +: 'list' and 'tuple'",
+            "[1, 2] + (3, 4)")
+        .testIfExactError("unsupported operand type(s) for +: 'tuple' and 'list'",
+            "(1, 2) + [3, 4]");
   }
 
   @SuppressWarnings("unchecked")
@@ -552,7 +554,7 @@
   public void testListComprehensionOnDictionaryCompositeExpression() throws Exception {
     new BuildTest()
         .setUp("d = {1:'a',2:'b'}", "l = [d[x] for x in d]")
-        .testLookup("l", ImmutableList.of("a", "b"));
+        .testLookup("l", MutableList.of(env, "a", "b"));
   }
 
   @Test
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 7c0828b..86e8d8f 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
@@ -20,6 +20,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
 
 import org.junit.Before;
@@ -27,8 +28,6 @@
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.util.Arrays;
-
 /**
  * Tests for MethodLibrary.
  */
@@ -915,9 +914,9 @@
 
   @Test
   public void testEnumerateBadArg() throws Exception {
-    // TODO(bazel-team): unify BUILD List and Skylark list, and get rid of this ugly message.
     new BothModesTest().testIfErrorContains(
-        "expected List or sequence for 'list' while calling enumerate but got string instead: a",
+        "Method enumerate(list: sequence) is not applicable for arguments (string): "
+        + "'list' is string, but should be sequence",
         "enumerate('a')");
   }
 
@@ -925,18 +924,18 @@
   public void testPyListAppend() throws Exception {
     new BuildTest()
         .setUp("FOO = ['a', 'b']", "FOO.append('c')")
-        .testLookup("FOO", Arrays.asList("a", "b", "c"))
+        .testLookup("FOO", MutableList.of(env, "a", "b", "c"))
         .testIfErrorContains(
-            "function 'append' is not defined on object of type 'Tuple'", "(1, 2).append(3)");
+            "function append is not defined on object of type 'tuple'", "(1, 2).append(3)");
   }
 
   @Test
   public void testPyListExtend() throws Exception {
     new BuildTest()
         .setUp("FOO = ['a', 'b']", "FOO.extend(['c', 'd'])")
-        .testLookup("FOO", Arrays.asList("a", "b", "c", "d"))
+        .testLookup("FOO", MutableList.of(env, "a", "b", "c", "d"))
         .testIfErrorContains(
-            "function 'extend' is not defined on object of type 'Tuple'", "(1, 2).extend([3, 4])");
+            "function extend is not defined on object of type 'tuple'", "(1, 2).extend([3, 4])");
   }
 
   @Test
@@ -944,7 +943,7 @@
     new BuildTest()
         .setUp("cc_binary = (['hello.cc'])")
         .testIfErrorContains(
-            "'List' object is not callable",
+            "'list' object is not callable",
             "cc_binary(name = 'hello', srcs=['hello.cc'], malloc = '//base:system_malloc')");
   }
 
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 f956f94..eb0f095 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
@@ -917,7 +917,7 @@
 
   @Test
   public void testListAnTupleConcatenationDoesNotWorkInSkylark() throws Exception {
-    new SkylarkTest().testIfExactError("can only concatenate list (not \"tuple\") to list",
+    new SkylarkTest().testIfExactError("unsupported operand type(s) for +: 'list' and 'tuple'",
         "[1, 2] + (3, 4)");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
index 7fdff2b..d553464 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
@@ -46,6 +46,7 @@
   @Test
   public void testListEmpty() throws Exception {
     assertThat(eval("8 if [1, 2, 3] else 9")).isEqualTo(8);
+    assertThat(eval("8 if [] else 9")).isEqualTo(9);
   }
 
   @Test