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 543d8e0..9200690 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
@@ -28,6 +28,7 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.util.OS;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -208,7 +209,7 @@
     }
 
     this.resolvedTools = resolvedToolsBuilder.build();
-    this.toolsRunfilesSuppliers = Sequence.createImmutable(toolsRunfilesBuilder.build());
+    this.toolsRunfilesSuppliers = StarlarkList.immutableCopyOf(toolsRunfilesBuilder.build());
     ImmutableMap.Builder<Label, ImmutableCollection<Artifact>> labelMapBuilder =
         ImmutableMap.builder();
     for (Map.Entry<Label, Collection<Artifact>> entry : tempLabelMap.entrySet()) {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
index e9eb04f..38f7ad5 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
@@ -74,6 +74,7 @@
 import com.google.devtools.build.lib.skylarkbuildapi.CommandLineArgsApi;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.LazyString;
 import com.google.devtools.build.lib.util.Pair;
@@ -254,13 +255,13 @@
     for (CommandLineAndParamFileInfo commandLine : commandLines.getCommandLines()) {
       result.add(Args.forRegisteredAction(commandLine, directoryInputs));
     }
-    return Sequence.createImmutable(result.build());
+    return StarlarkList.immutableCopyOf(result.build());
   }
 
   @Override
   public Sequence<String> getSkylarkArgv() throws EvalException {
     try {
-      return Sequence.createImmutable(getArguments());
+      return StarlarkList.immutableCopyOf(getArguments());
     } catch (CommandLineExpansionException exception) {
       throw new EvalException(Location.BUILTIN, exception);
     }
@@ -597,7 +598,6 @@
     }
 
     @Override
-    @SuppressWarnings("unchecked")
     public Iterable<? extends ActionInput> getInputFiles() {
       return inputs;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintCollection.java
index 4982828..9d4bed3 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/platform/ConstraintCollection.java
@@ -38,6 +38,7 @@
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.util.Fingerprint;
 import java.util.Collection;
 import java.util.Map;
@@ -230,7 +231,7 @@
 
   @Override
   public Sequence<ConstraintSettingInfo> constraintSettings() {
-    return Sequence.createImmutable(constraints().keySet());
+    return StarlarkList.immutableCopyOf(constraints().keySet());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkAttributesCollection.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkAttributesCollection.java
index f4ff4a9..b6193a1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkAttributesCollection.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkAttributesCollection.java
@@ -29,8 +29,8 @@
 import com.google.devtools.build.lib.skylarkbuildapi.SkylarkAttributesCollectionApi;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.syntax.EvalException;
-import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.Starlark;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.List;
@@ -212,7 +212,7 @@
       } else if (type == BuildType.LABEL_LIST
           || (type == BuildType.LABEL && a.getTransitionFactory().isSplit())) {
         List<?> allPrereq = context.getRuleContext().getPrerequisites(a.getName(), Mode.DONT_CHECK);
-        attrBuilder.put(skyname, Sequence.createImmutable(allPrereq));
+        attrBuilder.put(skyname, StarlarkList.immutableCopyOf(allPrereq));
       } else if (type == BuildType.LABEL_KEYED_STRING_DICT) {
         ImmutableMap.Builder<TransitiveInfoCollection, String> builder = ImmutableMap.builder();
         Map<Label, String> original = BuildType.LABEL_KEYED_STRING_DICT.cast(val);
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java
index c6f4a2c..9015544 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleContext.java
@@ -211,7 +211,7 @@
             outputs.addOutput(attrName, Starlark.NONE);
           }
         } else if (type == BuildType.OUTPUT_LIST) {
-          outputs.addOutput(attrName, Sequence.createImmutable(artifacts));
+          outputs.addOutput(attrName, StarlarkList.immutableCopyOf(artifacts));
         } else {
           throw new IllegalArgumentException(
               "Type of " + attrName + "(" + type + ") is not output type ");
@@ -444,7 +444,7 @@
           value = splitPrereq.getValue().get(0);
         } else {
           // BuildType.LABEL_LIST
-          value = Sequence.createImmutable(splitPrereq.getValue());
+          value = StarlarkList.immutableCopyOf(splitPrereq.getValue());
         }
 
         if (splitPrereq.getKey().isPresent()) {
@@ -708,7 +708,7 @@
     } catch (TokenizationException e) {
       throw new EvalException(null, e.getMessage() + " while tokenizing '" + optionString + "'");
     }
-    return Sequence.createImmutable(options);
+    return StarlarkList.immutableCopyOf(options);
   }
 
   @Override
@@ -1088,8 +1088,8 @@
             "." + Hashing.murmur3_32().hashUnencodedChars(command).toString() + SCRIPT_SUFFIX);
     List<String> argv = helper.buildCommandLine(command, inputs, constructor);
     return Tuple.<Object>of(
-        StarlarkList.copyOf(thread, inputs),
-        StarlarkList.copyOf(thread, argv),
+        StarlarkList.copyOf(thread.mutability(), inputs),
+        StarlarkList.copyOf(thread.mutability(), argv),
         helper.getToolsRunfilesSuppliers());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContext.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContext.java
index 1b9973f..a253f96 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContext.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContext.java
@@ -53,6 +53,7 @@
 import com.google.devtools.build.lib.syntax.Dict;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics;
@@ -674,7 +675,7 @@
           new IOException("thread interrupted"), Transience.TRANSIENT);
     } catch (IOException e) {
       if (allowFail) {
-        Dict<String, Object> dict = Dict.of(null, "success", false);
+        Dict<String, Object> dict = Dict.of((Mutability) null, "success", false);
         return StructProvider.STRUCT.createStruct(dict, null);
       } else {
         throw new RepositoryFunctionException(e, Transience.TRANSIENT);
@@ -790,7 +791,7 @@
     } catch (IOException e) {
       env.getListener().post(w);
       if (allowFail) {
-        Dict<String, Object> dict = Dict.of(null, "success", false);
+        Dict<String, Object> dict = Dict.of((Mutability) null, "success", false);
         return StructProvider.STRUCT.createStruct(dict, null);
       } else {
         throw new RepositoryFunctionException(e, Transience.TRANSIENT);
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/cpp/BazelCcModule.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/cpp/BazelCcModule.java
index e5c4565..8edcef9 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/cpp/BazelCcModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/cpp/BazelCcModule.java
@@ -34,6 +34,7 @@
 import com.google.devtools.build.lib.skylarkbuildapi.cpp.BazelCcModuleApi;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.syntax.Tuple;
 
@@ -107,7 +108,8 @@
         disallowNopicOutputs,
         /* grepIncludes= */ null,
         /* headersForClifDoNotUseThisParam= */ ImmutableList.of(),
-        Sequence.createImmutable(additionalInputs.getContents(Artifact.class, "additional_inputs")),
+        StarlarkList.immutableCopyOf(
+            additionalInputs.getContents(Artifact.class, "additional_inputs")),
         location,
         /* thread= */ null);
   }
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 f15297b..6568ad5 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
@@ -120,7 +120,7 @@
       throw new EvalException(loc, "illegal argument in call to glob", e);
     }
 
-    return StarlarkList.copyOf(thread, matches);
+    return StarlarkList.copyOf(thread.mutability(), matches);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkData.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkData.java
index 567e99d..dd41b0b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkData.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidSkylarkData.java
@@ -44,8 +44,10 @@
 import com.google.devtools.build.lib.skylarkbuildapi.android.AndroidDataProcessingApi;
 import com.google.devtools.build.lib.syntax.Dict;
 import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.Starlark;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.List;
@@ -209,7 +211,7 @@
     JavaInfo javaInfo =
         getJavaInfoForRClassJar(validated.getClassJar(), validated.getJavaSourceJar());
     return Dict.of(
-        /* thread = */ null,
+        (Mutability) null,
         AndroidResourcesInfo.PROVIDER,
         validated.toProvider(),
         JavaInfo.PROVIDER,
@@ -434,9 +436,9 @@
     return makeBinarySettings(
         ctx,
         Starlark.NONE,
-        Sequence.createImmutable(ImmutableList.of()),
-        Sequence.createImmutable(ImmutableList.of()),
-        Sequence.createImmutable(ImmutableList.of()),
+        StarlarkList.empty(),
+        StarlarkList.empty(),
+        StarlarkList.empty(),
         "auto",
         location,
         thread);
@@ -756,7 +758,7 @@
 
   public static <T extends NativeInfo> Sequence<T> getProviders(
       List<ConfiguredTarget> targets, NativeProvider<T> provider) {
-    return Sequence.createImmutable(
+    return StarlarkList.immutableCopyOf(
         targets.stream()
             .map(target -> target.get(provider))
             .filter(Objects::nonNull)
@@ -765,7 +767,7 @@
 
   protected static <T extends NativeInfo> Sequence<T> getProviders(
       List<ConfiguredTarget> targets, BuiltinProvider<T> provider) {
-    return Sequence.createImmutable(
+    return StarlarkList.immutableCopyOf(
         targets.stream()
             .map(target -> target.get(provider))
             .filter(Objects::nonNull)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ValidatedAndroidResources.java b/src/main/java/com/google/devtools/build/lib/rules/android/ValidatedAndroidResources.java
index 1654063..164065c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ValidatedAndroidResources.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ValidatedAndroidResources.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.rules.android.AndroidConfiguration.AndroidAaptVersion;
 import com.google.devtools.build.lib.skylarkbuildapi.android.ValidatedAndroidDataApi;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import java.util.Objects;
 import java.util.Optional;
 import javax.annotation.Nullable;
@@ -214,7 +215,7 @@
 
   @Override
   public Sequence<Artifact> getResourcesList() {
-    return Sequence.createImmutable(getResources());
+    return StarlarkList.immutableCopyOf(getResources());
   }
 
   public ValidatedAndroidResources filter(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationOutputs.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationOutputs.java
index d021bab..29dfc10 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationOutputs.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationOutputs.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.skylarkbuildapi.cpp.CcCompilationOutputsApi;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import java.util.LinkedHashSet;
 import java.util.Set;
@@ -109,17 +110,17 @@
         thread.getSemantics(),
         location,
         ((Label) thread.getGlobals().getLabel()).getPackageIdentifier().toString());
-    return Sequence.createImmutable(getObjectFiles(usePic));
+    return StarlarkList.immutableCopyOf(getObjectFiles(usePic));
   }
 
   @Override
   public Sequence<Artifact> getSkylarkObjects(Location location) throws EvalException {
-    return Sequence.createImmutable(getObjectFiles(/* usePic= */ false));
+    return StarlarkList.immutableCopyOf(getObjectFiles(/* usePic= */ false));
   }
 
   @Override
   public Sequence<Artifact> getSkylarkPicObjects(Location location) throws EvalException {
-    return Sequence.createImmutable(getObjectFiles(/* usePic= */ true));
+    return StarlarkList.immutableCopyOf(getObjectFiles(/* usePic= */ true));
   }
 
   /** Returns information about bitcode object files resulting from compilation. */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java
index 1885077..e2686ea 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingContext.java
@@ -33,6 +33,7 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.util.Fingerprint;
 import java.util.Arrays;
@@ -199,7 +200,7 @@
 
     @Override
     public Sequence<LibraryToLink> getSkylarkLibrariesToLink(StarlarkThread thread) {
-      return Sequence.createImmutable(getLibraries());
+      return StarlarkList.immutableCopyOf(getLibraries());
     }
 
     public List<LinkOptions> getUserLinkFlags() {
@@ -208,7 +209,7 @@
 
     @Override
     public Sequence<String> getSkylarkUserLinkFlags() {
-      return Sequence.createImmutable(
+      return StarlarkList.immutableCopyOf(
           getUserLinkFlags().stream()
               .map(LinkOptions::get)
               .flatMap(Collection::stream)
@@ -221,7 +222,7 @@
 
     @Override
     public Sequence<Artifact> getSkylarkNonCodeInputs() {
-      return Sequence.createImmutable(getNonCodeInputs());
+      return StarlarkList.immutableCopyOf(getNonCodeInputs());
     }
 
     public List<Linkstamp> getLinkstamps() {
@@ -393,7 +394,7 @@
 
   @Override
   public Sequence<String> getSkylarkUserLinkFlags() {
-    return Sequence.createImmutable(getFlattenedUserLinkFlags());
+    return StarlarkList.immutableCopyOf(getFlattenedUserLinkFlags());
   }
 
   @Override
@@ -402,7 +403,7 @@
     if (thread.getSemantics().incompatibleDepsetForLibrariesToLinkGetter()) {
       return SkylarkNestedSet.of(LibraryToLink.class, getLibraries());
     } else {
-      return Sequence.createImmutable(getLibraries().toList());
+      return StarlarkList.immutableCopyOf(getLibraries().toList());
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcModule.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcModule.java
index f30e154..061d387 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcModule.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcModule.java
@@ -64,6 +64,7 @@
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.Starlark;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.syntax.Tuple;
 import com.google.devtools.build.lib.util.FileTypeSet;
@@ -168,7 +169,7 @@
   @Override
   public Sequence<String> getExecutionRequirements(
       FeatureConfigurationForStarlark featureConfiguration, String actionName) {
-    return Sequence.createImmutable(
+    return StarlarkList.immutableCopyOf(
         featureConfiguration.getFeatureConfiguration().getToolRequirementsForAction(actionName));
   }
 
@@ -190,7 +191,7 @@
       String actionName,
       CcToolchainVariables variables)
       throws EvalException {
-    return Sequence.createImmutable(
+    return StarlarkList.immutableCopyOf(
         featureConfiguration.getFeatureConfiguration().getCommandLine(actionName, variables));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LibraryToLink.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LibraryToLink.java
index 81fb18d..6293890 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LibraryToLink.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LibraryToLink.java
@@ -70,7 +70,7 @@
     if (getObjectFiles() == null) {
       return StarlarkList.empty();
     }
-    return Sequence.createImmutable(getObjectFiles());
+    return StarlarkList.immutableCopyOf(getObjectFiles());
   }
 
   @Nullable
@@ -92,7 +92,7 @@
     if (getPicObjectFiles() == null) {
       return StarlarkList.empty();
     }
-    return Sequence.createImmutable(getPicObjectFiles());
+    return StarlarkList.immutableCopyOf(getPicObjectFiles());
   }
 
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
index f13472d..3e19925 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
@@ -64,6 +64,7 @@
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.LazyString;
 import com.google.devtools.build.lib.view.proto.Deps;
@@ -474,7 +475,7 @@
   @Override
   public Sequence<String> getSkylarkArgv() throws EvalException {
     try {
-      return Sequence.createImmutable(getArguments());
+      return StarlarkList.immutableCopyOf(getArguments());
     } catch (CommandLineExpansionException exception) {
       throw new EvalException(Location.BUILTIN, exception);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java
index 785a056..136d27e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaInfo.java
@@ -43,6 +43,7 @@
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkType;
 import com.google.devtools.build.lib.syntax.Starlark;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import java.util.ArrayList;
 import java.util.List;
@@ -293,7 +294,7 @@
     JavaSourceJarsProvider provider = providers.getProvider(JavaSourceJarsProvider.class);
     ImmutableList<Artifact> sourceJars =
         provider == null ? ImmutableList.of() : provider.getSourceJars();
-    return Sequence.createImmutable(sourceJars);
+    return StarlarkList.immutableCopyOf(sourceJars);
   }
 
   @Override
@@ -313,7 +314,7 @@
 
   @Override
   public Sequence<Artifact> getRuntimeOutputJars() {
-    return Sequence.createImmutable(getDirectRuntimeJars());
+    return StarlarkList.immutableCopyOf(getDirectRuntimeJars());
   }
 
   public ImmutableList<Artifact> getDirectRuntimeJars() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaRuleOutputJarsProvider.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaRuleOutputJarsProvider.java
index c19ffa0..1995870 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaRuleOutputJarsProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaRuleOutputJarsProvider.java
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.skylarkbuildapi.java.JavaRuleOutputJarsProviderApi;
 import com.google.devtools.build.lib.skylarkbuildapi.java.OutputJarApi;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import java.util.Collection;
 import java.util.stream.Collectors;
 import javax.annotation.Nullable;
@@ -88,7 +89,7 @@
     @Nullable
     @Override
     public Sequence<Artifact> getSrcJarsSkylark() {
-      return Sequence.createImmutable(srcJars);
+      return StarlarkList.immutableCopyOf(srcJars);
     }
 
     public Iterable<Artifact> getSrcJars() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainProvider.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainProvider.java
index bad7896..9e70876 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaToolchainProvider.java
@@ -37,6 +37,7 @@
 import com.google.devtools.build.lib.skylarkbuildapi.java.JavaToolchainSkylarkApiProviderApi;
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import java.util.Iterator;
 import javax.annotation.Nullable;
 
@@ -415,7 +416,7 @@
 
   @Override
   public Sequence<String> getSkylarkJvmOptions() {
-    return Sequence.createImmutable(getJvmOptions());
+    return StarlarkList.immutableCopyOf(getJvmOptions());
   }
 
   @Override
@@ -423,5 +424,3 @@
     return SkylarkNestedSet.of(Artifact.class, getTools());
   }
 }
-
-
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
index 44c08ef..b65b5dc 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProvider.java
@@ -44,6 +44,7 @@
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkType;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.Collections;
@@ -665,9 +666,9 @@
   @SuppressWarnings({"rawtypes", "unchecked"})
   public <E> Sequence<E> getDirect(Key<E> key) {
     if (directItems.containsKey(key)) {
-      return Sequence.createImmutable((List) directItems.get(key));
+      return StarlarkList.immutableCopyOf((List) directItems.get(key));
     }
-    return Sequence.createImmutable(ImmutableList.of());
+    return StarlarkList.empty();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Dict.java b/src/main/java/com/google/devtools/build/lib/syntax/Dict.java
index a8d7079..4438dde 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Dict.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Dict.java
@@ -86,6 +86,8 @@
     this.mutability = mutability == null ? Mutability.IMMUTABLE : mutability;
   }
 
+  /** @deprecated use {@code new Dict(thread.mutability())} instead. */
+  @Deprecated
   private Dict(@Nullable StarlarkThread thread) {
     this.mutability = thread == null ? Mutability.IMMUTABLE : thread.mutability();
   }
@@ -267,7 +269,7 @@
               + "{2: \"a\", 4: \"b\", 1: \"c\"}.values() == [\"a\", \"b\", \"c\"]</pre>\n",
       useStarlarkThread = true)
   public StarlarkList<?> invoke(StarlarkThread thread) throws EvalException {
-    return StarlarkList.copyOf(thread, values());
+    return StarlarkList.copyOf(thread.mutability(), values());
   }
 
   @SkylarkCallable(
@@ -317,21 +319,50 @@
     return new Dict<>(mutability);
   }
 
-  /** @return a dict mutable in given environment only */
+  /**
+   * @return a dict mutable in given environment only
+   * @deprecated use {@code of(thread.mutability())} instead.
+   */
+  @Deprecated
   public static <K, V> Dict<K, V> of(@Nullable StarlarkThread thread) {
     return new Dict<>(thread);
   }
 
-  /** @return a dict mutable in given environment only, with given initial key and value */
+  /** Returns a dict mutable in given environment only. */
+  public static <K, V> Dict<K, V> of(@Nullable Mutability mu) {
+    return new Dict<>(mu);
+  }
+
+  /**
+   * Returns a dict mutable in given environment only, with given initial key and value.
+   *
+   * @deprecated use {@code of(thread.mutability(), k, v)} instead.
+   */
+  @Deprecated
   public static <K, V> Dict<K, V> of(@Nullable StarlarkThread thread, K k, V v) {
     return Dict.<K, V>of(thread).putUnsafe(k, v);
   }
 
-  /** @return a dict mutable in given environment only, with two given initial key value pairs */
+  /**
+   * Returns a dict mutable in given environment only, with two given initial key value pairs.
+   *
+   * @deprecated use {@code of(thread.mutability(), k1, v2, k2, v2)}.
+   */
+  @Deprecated
   public static <K, V> Dict<K, V> of(@Nullable StarlarkThread thread, K k1, V v1, K k2, V v2) {
     return Dict.<K, V>of(thread).putUnsafe(k1, v1).putUnsafe(k2, v2);
   }
 
+  /** Returns a dict mutable in given environment only, with given initial key and value */
+  public static <K, V> Dict<K, V> of(@Nullable Mutability mu, K k, V v) {
+    return Dict.<K, V>of(mu).putUnsafe(k, v);
+  }
+
+  /** Returns a dict mutable in given environment only, with two given initial key value pairs. */
+  public static <K, V> Dict<K, V> of(@Nullable Mutability mu, K k1, V v1, K k2, V v2) {
+    return Dict.<K, V>of(mu).putUnsafe(k1, v1).putUnsafe(k2, v2);
+  }
+
   // TODO(bazel-team): Make other methods that take in mutabilities instead of environments, make
   // this method public.
   @VisibleForTesting
@@ -340,7 +371,11 @@
     return Dict.<K, V>withMutability(mutability).putAllUnsafe(m);
   }
 
-  /** @return a dict mutable in given environment only, with contents copied from given map */
+  /**
+   * @return a dict mutable in given environment only, with contents copied from given map
+   * @deprecated use {@code copyOf(thread.mutability(), m)} when available.
+   */
+  @Deprecated
   public static <K, V> Dict<K, V> copyOf(
       @Nullable StarlarkThread thread, Map<? extends K, ? extends V> m) {
     return Dict.<K, V>of(thread).putAllUnsafe(m);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
index bffd0a7..e8811e8 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
@@ -684,7 +684,7 @@
       thread.updateInternal(name, value);
     }
 
-    return comp.isDict() ? dict : StarlarkList.copyOf(thread, list);
+    return comp.isDict() ? dict : StarlarkList.copyOf(thread.mutability(), list);
   }
 
   /** Returns an exception which should be thrown instead of the original one. */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java b/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java
index ff9b4da..ae23070 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Sequence.java
@@ -137,14 +137,4 @@
       throws EvalException {
     return castList(this, type, description);
   }
-
-  /**
-   * Creates an immutable StarlarkList with the given elements.
-   *
-   * <p>The caller must ensure that the elements of {@code contents} are not mutable.
-   */
-  // TODO(adonovan): move to StarlarkList.
-  public static <E> Sequence<E> createImmutable(Iterable<? extends E> contents) {
-    return StarlarkList.copyOf(Mutability.IMMUTABLE, contents);
-  }
 }
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 d276581..b9450e1 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
@@ -439,7 +439,7 @@
   public StarlarkList<Object> toList(Location location, StarlarkThread thread)
       throws EvalException {
     try {
-      return StarlarkList.copyOf(thread, this.toCollection());
+      return StarlarkList.copyOf(thread.mutability(), this.toCollection());
     } catch (NestedSetDepthException exception) {
       throw new EvalException(
           location,
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java
index a85631f..998b302 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkList.java
@@ -114,29 +114,18 @@
   }
 
   /**
-   * Returns a {@code StarlarkList} whose items are given by an iterable and which has the {@link
-   * Mutability} belonging to the given {@link StarlarkThread}. If {@code thread} is null, the list
-   * is immutable.
-   *
-   * @deprecated call {@code copyOf(thread.mutability(), elems)} instead.
+   * Returns an immutable list with the given elements. Equivalent to {@code copyOf(null, elems)}.
    */
-  @Deprecated
-  public static <T> StarlarkList<T> copyOf(
-      @Nullable StarlarkThread thread, Iterable<? extends T> elems) {
-    Mutability mu = thread == null ? null : thread.mutability();
-    return copyOf(mu, elems);
+  public static <T> StarlarkList<T> immutableCopyOf(Iterable<? extends T> elems) {
+    return copyOf(null, elems);
   }
 
   /**
-   * Returns a {@code StarlarkList} with the given items and the {@link Mutability} of the given
-   * {@link StarlarkThread}. If {@code thread} is null, the list is immutable.
-   *
-   * @deprecated call {@code of(thread.mutability(), elems)} instead.
+   * Returns a {@code StarlarkList} with the given items and the {@link Mutability}. If {@code
+   * mutability} is null, the list is immutable.
    */
-  @Deprecated
-  public static <T> StarlarkList<T> of(@Nullable StarlarkThread thread, T... elems) {
-    Mutability mu = thread == null ? null : thread.mutability();
-    return wrap(mu, Arrays.copyOf(elems, elems.length));
+  public static <T> StarlarkList<T> of(@Nullable Mutability mutability, T... elems) {
+    return wrap(mutability, Arrays.copyOf(elems, elems.length));
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java b/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java
index 01781c4..0931fbc 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StringModule.java
@@ -779,7 +779,7 @@
         result.add(line);
       }
     }
-    return Sequence.createImmutable(result);
+    return StarlarkList.immutableCopyOf(result);
   }
 
   @SkylarkCallable(
@@ -967,7 +967,7 @@
     for (char c : self.toCharArray()) {
       builder.add(String.valueOf(c));
     }
-    return Sequence.createImmutable(builder.build());
+    return StarlarkList.immutableCopyOf(builder.build());
   }
 
   @SkylarkCallable(
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeSkylarkNativeModuleApi.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeSkylarkNativeModuleApi.java
index 3d93de1..976603c 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeSkylarkNativeModuleApi.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/FakeSkylarkNativeModuleApi.java
@@ -45,7 +45,7 @@
       Location loc,
       StarlarkThread thread)
       throws EvalException, InterruptedException {
-    return StarlarkList.of(thread);
+    return StarlarkList.of(thread.mutability());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java
index 4a297ef..6b974a7 100644
--- a/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java
+++ b/src/main/java/com/google/devtools/build/skydoc/fakebuildapi/cpp/FakeCcModule.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.skydoc.fakebuildapi.cpp;
 
-import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkbuildapi.FileApi;
@@ -37,6 +36,7 @@
 import com.google.devtools.build.lib.syntax.Dict;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.syntax.Tuple;
 import com.google.devtools.build.skydoc.fakebuildapi.FakeProviderApi;
@@ -81,7 +81,7 @@
   @Override
   public Sequence<String> getExecutionRequirements(
       FeatureConfigurationApi featureConfiguration, String actionName) {
-    return Sequence.createImmutable(ImmutableList.of());
+    return StarlarkList.empty();
   }
 
   @Override
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContextTest.java b/src/test/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContextTest.java
index c7fecbb..667e582 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryContextTest.java
@@ -45,8 +45,9 @@
 import com.google.devtools.build.lib.syntax.Expression;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.FunctionSignature;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInput;
-import com.google.devtools.build.lib.syntax.Sequence;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.testutil.Scratch;
@@ -59,7 +60,6 @@
 import java.io.InputStreamReader;
 import java.nio.charset.StandardCharsets;
 import java.time.Duration;
-import java.util.Arrays;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
@@ -376,7 +376,7 @@
             "$remotable",
             true,
             "exec_properties",
-            Dict.of(null, "OSFamily", "Linux"));
+            Dict.of((Mutability) null, "OSFamily", "Linux"));
 
     RepositoryRemoteExecutor repoRemoteExecutor = Mockito.mock(RepositoryRemoteExecutor.class);
     ExecutionResult executionResult =
@@ -397,7 +397,7 @@
     // Act
     SkylarkExecutionResult skylarkExecutionResult =
         context.execute(
-            Sequence.createImmutable(Arrays.asList("/bin/cmd", "arg1")),
+            StarlarkList.of(/*mutability=*/ null, "/bin/cmd", "arg1"),
             /*timeout=*/ 10,
             /* uncheckedEnvironment=*/ Dict.empty(),
             /* quiet= */ true,
diff --git a/src/test/java/com/google/devtools/build/lib/packages/TargetUtilsTest.java b/src/test/java/com/google/devtools/build/lib/packages/TargetUtilsTest.java
index baa85f4..d140af0 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/TargetUtilsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/TargetUtilsTest.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.packages.util.PackageLoadingTestCase;
 import com.google.devtools.build.lib.syntax.Dict;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Starlark;
 import java.util.Map;
 import org.junit.Test;
@@ -197,12 +198,14 @@
 
     Map<String, String> execInfo =
         TargetUtils.getFilteredExecutionInfo(
-            Dict.of(null, "supports-worker", "1"), noTag, /* allowTagsPropagation */ true);
+            Dict.of((Mutability) null, "supports-worker", "1"),
+            noTag, /* allowTagsPropagation */
+            true);
     assertThat(execInfo).containsExactly("supports-worker", "1");
 
     execInfo =
         TargetUtils.getFilteredExecutionInfo(
-            Dict.of(null, "some-custom-tag", "1", "no-cache", "1"),
+            Dict.of((Mutability) null, "some-custom-tag", "1", "no-cache", "1"),
             noTag,
             /* allowTagsPropagation */ true);
     assertThat(execInfo).containsExactly("no-cache", "1");
@@ -214,7 +217,8 @@
         "tests/BUILD",
         "sh_binary(name = 'tag1', srcs=['sh.sh'], tags=['supports-workers', 'no-cache'])");
     Rule tag1 = (Rule) getTarget("//tests:tag1");
-    Dict<String, String> executionRequirementsUnchecked = Dict.of(null, "no-remote", "1");
+    Dict<String, String> executionRequirementsUnchecked =
+        Dict.of((Mutability) null, "no-remote", "1");
 
     Map<String, String> execInfo =
         TargetUtils.getFilteredExecutionInfo(
@@ -229,7 +233,8 @@
         "tests/BUILD",
         "sh_binary(name = 'tag1', srcs=['sh.sh'], tags=['supports-workers', 'no-cache'])");
     Rule tag1 = (Rule) getTarget("//tests:tag1");
-    Dict<String, String> executionRequirementsUnchecked = Dict.of(null, "no-cache", "1");
+    Dict<String, String> executionRequirementsUnchecked =
+        Dict.of((Mutability) null, "no-cache", "1");
 
     Map<String, String> execInfo =
         TargetUtils.getFilteredExecutionInfo(
@@ -261,7 +266,8 @@
         "tests/BUILD",
         "sh_binary(name = 'tag1', srcs=['sh.sh'], tags=['supports-workers', 'no-cache'])");
     Rule tag1 = (Rule) getTarget("//tests:tag1");
-    Dict<String, String> executionRequirementsUnchecked = Dict.of(null, "no-remote", "1");
+    Dict<String, String> executionRequirementsUnchecked =
+        Dict.of((Mutability) null, "no-remote", "1");
 
     Map<String, String> execInfo =
         TargetUtils.getFilteredExecutionInfo(
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcToolchainConfigureTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcToolchainConfigureTest.java
index 73df135..b670186 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcToolchainConfigureTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcToolchainConfigureTest.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.rules.cpp;
 
 import com.google.devtools.build.lib.packages.util.ResourceLoader;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
 import com.google.devtools.build.lib.testutil.TestConstants;
@@ -28,24 +29,25 @@
 
   @Test
   public void testSplitEscaped() throws Exception {
+    Mutability mu = null;
     newTest()
-        .testExpression("split_escaped('a:b:c', ':')", StarlarkList.of(thread, "a", "b", "c"))
-        .testExpression("split_escaped('a%:b', ':')", StarlarkList.of(thread, "a:b"))
-        .testExpression("split_escaped('a%%b', ':')", StarlarkList.of(thread, "a%b"))
-        .testExpression("split_escaped('a:::b', ':')", StarlarkList.of(thread, "a", "", "", "b"))
-        .testExpression("split_escaped('a:b%:c', ':')", StarlarkList.of(thread, "a", "b:c"))
-        .testExpression("split_escaped('a%%:b:c', ':')", StarlarkList.of(thread, "a%", "b", "c"))
-        .testExpression("split_escaped(':a', ':')", StarlarkList.of(thread, "", "a"))
-        .testExpression("split_escaped('a:', ':')", StarlarkList.of(thread, "a", ""))
-        .testExpression("split_escaped('::a::', ':')", StarlarkList.of(thread, "", "", "a", "", ""))
-        .testExpression("split_escaped('%%%:a%%%%:b', ':')", StarlarkList.of(thread, "%:a%%", "b"))
-        .testExpression("split_escaped('', ':')", StarlarkList.of(thread))
-        .testExpression("split_escaped('%', ':')", StarlarkList.of(thread, "%"))
-        .testExpression("split_escaped('%%', ':')", StarlarkList.of(thread, "%"))
-        .testExpression("split_escaped('%:', ':')", StarlarkList.of(thread, ":"))
-        .testExpression("split_escaped(':', ':')", StarlarkList.of(thread, "", ""))
-        .testExpression("split_escaped('a%%b', ':')", StarlarkList.of(thread, "a%b"))
-        .testExpression("split_escaped('a%:', ':')", StarlarkList.of(thread, "a:"));
+        .testExpression("split_escaped('a:b:c', ':')", StarlarkList.of(mu, "a", "b", "c"))
+        .testExpression("split_escaped('a%:b', ':')", StarlarkList.of(mu, "a:b"))
+        .testExpression("split_escaped('a%%b', ':')", StarlarkList.of(mu, "a%b"))
+        .testExpression("split_escaped('a:::b', ':')", StarlarkList.of(mu, "a", "", "", "b"))
+        .testExpression("split_escaped('a:b%:c', ':')", StarlarkList.of(mu, "a", "b:c"))
+        .testExpression("split_escaped('a%%:b:c', ':')", StarlarkList.of(mu, "a%", "b", "c"))
+        .testExpression("split_escaped(':a', ':')", StarlarkList.of(mu, "", "a"))
+        .testExpression("split_escaped('a:', ':')", StarlarkList.of(mu, "a", ""))
+        .testExpression("split_escaped('::a::', ':')", StarlarkList.of(mu, "", "", "a", "", ""))
+        .testExpression("split_escaped('%%%:a%%%%:b', ':')", StarlarkList.of(mu, "%:a%%", "b"))
+        .testExpression("split_escaped('', ':')", StarlarkList.of(mu))
+        .testExpression("split_escaped('%', ':')", StarlarkList.of(mu, "%"))
+        .testExpression("split_escaped('%%', ':')", StarlarkList.of(mu, "%"))
+        .testExpression("split_escaped('%:', ':')", StarlarkList.of(mu, ":"))
+        .testExpression("split_escaped(':', ':')", StarlarkList.of(mu, "", ""))
+        .testExpression("split_escaped('a%%b', ':')", StarlarkList.of(mu, "a%b"))
+        .testExpression("split_escaped('a%:', ':')", StarlarkList.of(mu, "a:"));
   }
 
   private ModalTestCase newTest(String... skylarkOptions) throws IOException {
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java
index 2f464ae..8dab70b 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.packages.SkylarkProvider.SkylarkKey;
 import com.google.devtools.build.lib.packages.StructImpl;
 import com.google.devtools.build.lib.syntax.Dict;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Sequence;
 import java.util.List;
 import java.util.stream.Collectors;
@@ -132,7 +133,8 @@
         (Sequence<Dict<String, String>>) fooProvider.getValue("envs");
     assertThat(envs)
         .containsExactly(
-            Dict.of(null, "foo", "bar", "pet", "puppy"), Dict.of(null, "pet", "bunny"));
+            Dict.of((Mutability) null, "foo", "bar", "pet", "puppy"),
+            Dict.of((Mutability) null, "pet", "bunny"));
 
     Sequence<Sequence<Artifact>> inputs =
         (Sequence<Sequence<Artifact>>) fooProvider.getValue("inputs");
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 e647599..1f14a23 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
@@ -50,16 +50,17 @@
 import com.google.devtools.build.lib.syntax.Dict;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInput;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.StarlarkFile;
 import com.google.devtools.build.lib.syntax.StarlarkList;
-import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.syntax.SyntaxError;
 import com.google.devtools.build.lib.syntax.Tuple;
 import com.google.devtools.build.lib.testutil.MoreAsserts;
 import com.google.devtools.build.lib.util.FileTypeSet;
 import java.util.Collection;
+import javax.annotation.Nullable;
 import org.junit.Before;
 import org.junit.Rule;
 import org.junit.Test;
@@ -1274,19 +1275,19 @@
     return StructProvider.STRUCT.create(ImmutableMap.of(field, value), "no field '%'");
   }
 
-  private static StructImpl makeBigStruct(StarlarkThread thread) {
+  private static StructImpl makeBigStruct(@Nullable Mutability mu) {
     // struct(a=[struct(x={1:1}), ()], b=(), c={2:2})
     return StructProvider.STRUCT.create(
         ImmutableMap.<String, Object>of(
             "a",
                 StarlarkList.<Object>of(
-                    thread,
+                    mu,
                     StructProvider.STRUCT.create(
-                        ImmutableMap.<String, Object>of("x", Dict.<Object, Object>of(thread, 1, 1)),
+                        ImmutableMap.<String, Object>of("x", Dict.<Object, Object>of(mu, 1, 1)),
                         "no field '%s'"),
                     Tuple.of()),
             "b", Tuple.of(),
-            "c", Dict.<Object, Object>of(thread, 2, 2)),
+            "c", Dict.<Object, Object>of(mu, 2, 2)),
         "no field '%s'");
   }
 
@@ -1295,8 +1296,8 @@
     assertThat(EvalUtils.isImmutable(makeStruct("a", 1))).isTrue();
   }
 
-  private static StarlarkList<Object> makeList(StarlarkThread thread) {
-    return StarlarkList.<Object>of(thread, 1, 2, 3);
+  private static StarlarkList<Object> makeList(@Nullable Mutability mu) {
+    return StarlarkList.<Object>of(mu, 1, 2, 3);
   }
 
   @Test
@@ -1305,9 +1306,10 @@
     assertThat(EvalUtils.isImmutable(makeStruct("a", makeList(null)))).isTrue();
     assertThat(EvalUtils.isImmutable(makeBigStruct(null))).isTrue();
 
-    assertThat(EvalUtils.isImmutable(Tuple.<Object>of(makeList(ev.getStarlarkThread())))).isFalse();
-    assertThat(EvalUtils.isImmutable(makeStruct("a", makeList(ev.getStarlarkThread())))).isFalse();
-    assertThat(EvalUtils.isImmutable(makeBigStruct(ev.getStarlarkThread()))).isFalse();
+    Mutability mu = ev.getStarlarkThread().mutability();
+    assertThat(EvalUtils.isImmutable(Tuple.<Object>of(makeList(mu)))).isFalse();
+    assertThat(EvalUtils.isImmutable(makeStruct("a", makeList(mu)))).isFalse();
+    assertThat(EvalUtils.isImmutable(makeBigStruct(mu))).isFalse();
   }
 
   @Test
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 35020bc..fb134dd 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
@@ -48,6 +48,7 @@
 import com.google.devtools.build.lib.rules.python.PyProviderUtils;
 import com.google.devtools.build.lib.skylark.util.SkylarkTestCase;
 import com.google.devtools.build.lib.syntax.Dict;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.Starlark;
@@ -2174,7 +2175,7 @@
 
     Object substitutionsUnchecked = eval("action.substitutions");
     assertThat(substitutionsUnchecked).isInstanceOf(Dict.class);
-    assertThat(substitutionsUnchecked).isEqualTo(Dict.of(null, "a", "b"));
+    assertThat(substitutionsUnchecked).isEqualTo(Dict.of((Mutability) null, "a", "b"));
   }
 
   private void setUpCoverageInstrumentedTest() throws Exception {
diff --git a/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java b/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java
index a0ee468..4f889ee9 100644
--- a/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java
@@ -42,9 +42,9 @@
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInput;
-import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkFile;
+import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
@@ -366,8 +366,7 @@
             .addScope(
                 Scope.newBuilder()
                     .setName("global")
-                    .addBinding(
-                        getValueProto("x", Sequence.createImmutable(ImmutableList.of(1, 2, 3)))))
+                    .addBinding(getValueProto("x", StarlarkList.of(/*mutability=*/ null, 1, 2, 3))))
             .build());
   }
 
@@ -391,7 +390,7 @@
     Value xValue = frames.getFrame(0).getScope(0).getBinding(0);
 
     assertValuesEqualIgnoringId(
-        xValue, getValueProto("x", Sequence.createImmutable(ImmutableList.of(1, 2, 3))));
+        xValue, getValueProto("x", StarlarkList.of(/*mutability=*/ null, 1, 2, 3)));
 
     List<Value> children = getChildren(xValue);
 
@@ -522,7 +521,7 @@
 
     ListFramesResponse frames = listFrames(threadId);
     assertThat(frames.getFrame(0).getScope(0).getBindingList())
-        .contains(getValueProto("x", Sequence.createImmutable(ImmutableList.of(5, 6))));
+        .contains(getValueProto("x", StarlarkList.of(/*mutability=*/ null, 5, 6)));
   }
 
   @Test
@@ -556,7 +555,7 @@
 
     ListFramesResponse frames = listFrames(threadId);
     assertThat(frames.getFrame(0).getScope(0).getBindingList())
-        .contains(getValueProto("x", Sequence.createImmutable(ImmutableList.of(1, 2, 3, 4))));
+        .contains(getValueProto("x", StarlarkList.of(/*mutability=*/ null, 1, 2, 3, 4)));
   }
 
   @Test
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 95f27fa..365b8c6 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
@@ -36,7 +36,7 @@
 public class EvalUtilsTest extends EvaluationTestCase {
 
   private static StarlarkList<Object> makeList(StarlarkThread thread) {
-    return StarlarkList.of(thread, 1, 2, 3);
+    return StarlarkList.of(thread == null ? null : thread.mutability(), 1, 2, 3);
   }
 
   private static Dict<Object, Object> makeDict(StarlarkThread thread) {
@@ -96,8 +96,8 @@
       Starlark.NONE,
       Tuple.of(1, 2, 3),
       Tuple.of("1", "2", "3"),
-      StarlarkList.of(thread, 1, 2, 3),
-      StarlarkList.of(thread, "1", "2", "3"),
+      StarlarkList.of(thread.mutability(), 1, 2, 3),
+      StarlarkList.of(thread.mutability(), "1", "2", "3"),
       Dict.of(thread, "key", 123),
       Dict.of(thread, 123, "value"),
       StructProvider.STRUCT.create(ImmutableMap.of("key", (Object) "value"), "no field %s"),
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 21a47036..0685ece 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
@@ -283,7 +283,7 @@
     // list
     Object x = eval("[1,2] + [3,4]");
     assertThat((Iterable<Object>) x).containsExactly(1, 2, 3, 4).inOrder();
-    assertThat(x).isEqualTo(StarlarkList.of(thread, 1, 2, 3, 4));
+    assertThat(x).isEqualTo(StarlarkList.of(thread.mutability(), 1, 2, 3, 4));
     assertThat(EvalUtils.isImmutable(x)).isFalse();
 
     // tuple
@@ -475,7 +475,7 @@
   @Test
   public void testListConcatenation() throws Exception {
     newTest()
-        .testExpression("[1, 2] + [3, 4]", StarlarkList.of(thread, 1, 2, 3, 4))
+        .testExpression("[1, 2] + [3, 4]", StarlarkList.of(thread.mutability(), 1, 2, 3, 4))
         .testExpression("(1, 2) + (3, 4)", Tuple.of(1, 2, 3, 4))
         .testIfExactError(
             "unsupported operand type(s) for +: 'list' and 'tuple'", "[1, 2] + (3, 4)")
@@ -485,16 +485,17 @@
 
   @Test
   public void testListMultiply() throws Exception {
+    Mutability mu = thread.mutability();
     newTest()
-        .testExpression("[1, 2, 3] * 1", StarlarkList.of(thread, 1, 2, 3))
-        .testExpression("[1, 2] * 2", StarlarkList.of(thread, 1, 2, 1, 2))
-        .testExpression("[1, 2] * 3", StarlarkList.of(thread, 1, 2, 1, 2, 1, 2))
-        .testExpression("[1, 2] * 4", StarlarkList.of(thread, 1, 2, 1, 2, 1, 2, 1, 2))
-        .testExpression("[8] * 5", StarlarkList.of(thread, 8, 8, 8, 8, 8))
+        .testExpression("[1, 2, 3] * 1", StarlarkList.of(mu, 1, 2, 3))
+        .testExpression("[1, 2] * 2", StarlarkList.of(mu, 1, 2, 1, 2))
+        .testExpression("[1, 2] * 3", StarlarkList.of(mu, 1, 2, 1, 2, 1, 2))
+        .testExpression("[1, 2] * 4", StarlarkList.of(mu, 1, 2, 1, 2, 1, 2, 1, 2))
+        .testExpression("[8] * 5", StarlarkList.of(mu, 8, 8, 8, 8, 8))
         .testExpression("[    ] * 10", StarlarkList.empty())
         .testExpression("[1, 2] * 0", StarlarkList.empty())
         .testExpression("[1, 2] * -4", StarlarkList.empty())
-        .testExpression("2 * [1, 2]", StarlarkList.of(thread, 1, 2, 1, 2))
+        .testExpression("2 * [1, 2]", StarlarkList.of(mu, 1, 2, 1, 2))
         .testExpression("10 * []", StarlarkList.empty())
         .testExpression("0 * [1, 2]", StarlarkList.empty())
         .testExpression("-4 * [1, 2]", StarlarkList.empty());
@@ -569,7 +570,7 @@
   public void testListComprehensionOnDictionaryCompositeExpression() throws Exception {
     new BuildTest()
         .setUp("d = {1:'a',2:'b'}", "l = [d[x] for x in d]")
-        .testLookup("l", StarlarkList.of(thread, "a", "b"));
+        .testLookup("l", StarlarkList.of(thread.mutability(), "a", "b"));
   }
 
   @Test
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 6b8bb04..0ecc3cf 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
@@ -1084,7 +1084,7 @@
             "    modified_list = v + ['extra_string']",
             "  return modified_list",
             "m = func(mock)")
-        .testLookup("m", StarlarkList.of(thread, "b", "c", "extra_string"));
+        .testLookup("m", StarlarkList.of(thread.mutability(), "b", "c", "extra_string"));
   }
 
   @Test
@@ -1555,7 +1555,7 @@
             "  return value",
             "",
             "f()[1] += 1") // `f()` should be called only once here
-        .testLookup("counter", StarlarkList.of(thread, 1));
+        .testLookup("counter", StarlarkList.of(thread.mutability(), 1));
 
     // Check key position.
     new SkylarkTest()
@@ -1568,7 +1568,7 @@
             "  return 1",
             "",
             "value[f()] += 1") // `f()` should be called only once here
-        .testLookup("counter", StarlarkList.of(thread, 1));
+        .testLookup("counter", StarlarkList.of(thread.mutability(), 1));
   }
 
   @Test
@@ -1608,8 +1608,9 @@
             "",
             "f(ordinary)[0] = g(ordinary)[1]",
             "f(augmented)[0] += g(augmented)[1]")
-        .testLookup("ordinary", StarlarkList.of(thread, "g", "f")) // This order is consistent
-        .testLookup("augmented", StarlarkList.of(thread, "f", "g")); // with Python
+        .testLookup(
+            "ordinary", StarlarkList.of(thread.mutability(), "g", "f")) // This order is consistent
+        .testLookup("augmented", StarlarkList.of(thread.mutability(), "f", "g")); // with Python
   }
 
   @Test
@@ -1741,7 +1742,7 @@
   public void testDictAssignmentAsLValueSideEffects() throws Exception {
     new SkylarkTest()
         .setUp("def func(d):", "  d['b'] = 2", "d = {'a' : 1}", "func(d)")
-        .testLookup("d", Dict.of(null, "a", 1, "b", 2));
+        .testLookup("d", Dict.of((Mutability) null, "a", 1, "b", 2));
   }
 
   @Test
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 a404505..da8b41d 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
@@ -155,7 +155,8 @@
 
   @Test
   public void testListConcat() throws Exception {
-    assertThat(eval("[1, 2] + [3, 4]")).isEqualTo(Sequence.createImmutable(Tuple.of(1, 2, 3, 4)));
+    assertThat(eval("[1, 2] + [3, 4]"))
+        .isEqualTo(StarlarkList.of(/*mutability=*/ null, 1, 2, 3, 4));
   }
 
   @Test
@@ -317,7 +318,8 @@
   public void testGetSkylarkType_GivesExpectedClassesForListsAndTuples() throws Exception {
     Class<?> emptyTupleClass = Tuple.empty().getClass();
     Class<?> tupleClass = Tuple.of(1, "a", "b").getClass();
-    Class<?> mutableListClass = StarlarkList.copyOf(thread, Tuple.of(1, 2, 3)).getClass();
+    Class<?> mutableListClass =
+        StarlarkList.copyOf(thread.mutability(), Tuple.of(1, 2, 3)).getClass();
 
     assertThat(EvalUtils.getSkylarkType(mutableListClass)).isEqualTo(StarlarkList.class);
     assertThat(EvalUtils.getSkylarkType(emptyTupleClass)).isEqualTo(Tuple.class);
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java b/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java
index 0d1fafe..20267d9 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java
@@ -58,7 +58,7 @@
     // input1.BUILD contains:
     // x = [1,2,'foo',4] + [1,2, "%s%d" % ('foo', 1)]
     assertThat(thread.moduleLookup("x"))
-        .isEqualTo(Sequence.createImmutable(Tuple.of(1, 2, "foo", 4, 1, 2, "foo1")));
+        .isEqualTo(StarlarkList.of(/*mutability=*/ null, 1, 2, "foo", 4, 1, 2, "foo1"));
   }
 
   @Test