diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/FunctionTransitionUtil.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/FunctionTransitionUtil.java
index 29196cb..5f90cb6 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/FunctionTransitionUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/FunctionTransitionUtil.java
@@ -156,7 +156,7 @@
     LinkedHashSet<String> remainingInputs = Sets.newLinkedHashSet(starlarkTransition.getInputs());
 
     try (Mutability mutability = Mutability.create("build_settings")) {
-      Dict<String, Object> dict = Dict.withMutability(mutability);
+      Dict<String, Object> dict = Dict.of(mutability);
 
       // Add native options
       for (Map.Entry<String, OptionInfo> entry : optionInfoMap.entrySet()) {
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 6568ad5..f472a19 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
@@ -144,7 +144,7 @@
     PackageContext context = getContext(thread, loc);
     Collection<Target> targets = context.pkgBuilder.getTargets();
     Mutability mu = thread.mutability();
-    Dict<String, Dict<String, Object>> rules = Dict.withMutability(mu);
+    Dict<String, Dict<String, Object>> rules = Dict.of(mu);
     for (Target t : targets) {
       if (t instanceof Rule) {
         Dict<String, Object> rule = targetDict(t, loc, mu);
@@ -282,7 +282,7 @@
     if (!(target instanceof Rule)) {
       return null;
     }
-    Dict<String, Object> values = Dict.withMutability(mu);
+    Dict<String, Object> values = Dict.of(mu);
 
     Rule rule = (Rule) target;
     AttributeContainer cont = rule.getAttributeContainer();
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 6ef5644..bd0f9e5 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
@@ -371,7 +371,7 @@
               resourceApk.toResourceInfo(ctx.getLabel()),
               resourceApk.toAssetsInfo(ctx.getLabel()),
               resourceApk.toManifestInfo().get()));
-      return Dict.copyOf(/* thread = */ null, builder.build());
+      return Dict.copyOf((Mutability) null, builder.build());
     } catch (RuleErrorException e) {
       throw handleRuleException(errorReporter, e);
     }
@@ -626,7 +626,7 @@
         getJavaInfoForRClassJar(
             resourceApk.getResourceJavaClassJar(), resourceApk.getResourceJavaSrcJar()));
 
-    return Dict.copyOf(/* thread = */ null, builder.build());
+    return Dict.copyOf((Mutability) null, builder.build());
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleSkylarkCommon.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleSkylarkCommon.java
index 4672240..085dc0d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleSkylarkCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleSkylarkCommon.java
@@ -266,7 +266,7 @@
         ImmutableMap.of(
             "binary_provider", output.getBinaryInfoProvider(),
             "debug_outputs_provider", output.getDebugOutputsProvider(),
-            "output_groups", Dict.copyOf(thread, outputGroups));
+            "output_groups", Dict.copyOf(thread.mutability(), outputGroups));
     return SkylarkInfo.createSchemaless(constructor, fields, Location.BUILTIN);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
index b77d39b..ba44c34 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
@@ -175,8 +175,7 @@
       }
       // If there's a kwarg, it's empty.
       if (hasKwargs) {
-        // TODO(bazel-team): create a fresh mutable dict, like Python does
-        arguments[kwargIndex] = Dict.of(thread);
+        arguments[kwargIndex] = Dict.of(thread.mutability());
       }
     } else if (hasKwargs && numNamedParams == 0) {
       // Easy case (2b): there are no named parameters, but there is a **kwargs.
@@ -185,10 +184,10 @@
       // Also note that no named parameters means no mandatory parameters that weren't passed,
       // and no missing optional parameters for which to use a default. Thus, no loops.
       // NB: not 2a means kwarg isn't null
-      arguments[kwargIndex] = Dict.copyOf(thread, kwargs);
+      arguments[kwargIndex] = Dict.copyOf(thread.mutability(), kwargs);
     } else {
       // Hard general case (2c): some keyword arguments may correspond to named parameters
-      Dict<String, Object> kwArg = hasKwargs ? Dict.of(thread) : Dict.empty();
+      Dict<String, Object> kwArg = hasKwargs ? Dict.of(thread.mutability()) : Dict.empty();
 
       // For nicer stabler error messages, start by checking against
       // an argument being provided both as positional argument and as keyword argument.
@@ -227,8 +226,7 @@
         }
       }
       if (hasKwargs) {
-        // TODO(bazel-team): create a fresh mutable dict, like Python does
-        arguments[kwargIndex] = Dict.copyOf(thread, kwArg);
+        arguments[kwargIndex] = Dict.copyOf(thread.mutability(), kwArg);
       }
 
       // Check that all mandatory parameters were filled in general case 2c.
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/CallUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/CallUtils.java
index e28a703..fad3a77 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/CallUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/CallUtils.java
@@ -411,7 +411,7 @@
       builder.add(Tuple.copyOf(extraArgs));
     }
     if (acceptsExtraKwargs) {
-      builder.add(Dict.copyOf(thread, extraKwargs));
+      builder.add(Dict.copyOf(thread.mutability(), extraKwargs));
     }
     appendExtraInterpreterArgs(builder, method, call, call.getLocation(), thread);
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Depset.java b/src/main/java/com/google/devtools/build/lib/syntax/Depset.java
index f515070..2fe96a8 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Depset.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Depset.java
@@ -128,7 +128,7 @@
       }
     } else if (item instanceof Sequence) {
       for (Object x : (Sequence) item) {
-        EvalUtils.checkValidDictKey(x);
+        EvalUtils.checkHashable(x);
         SkylarkType xt = SkylarkType.of(x);
         contentType = checkType(contentType, xt);
         itemsBuilder.add(x);
@@ -453,7 +453,7 @@
     /** Adds a direct element, checking that its type is equal to the elements already added. */
     public Builder addDirect(Object x) throws EvalException {
       // In case of problems, see b/144992997 or github.com/bazelbuild/bazel/issues/10289.
-      EvalUtils.checkValidDictKey(x);
+      EvalUtils.checkHashable(x);
 
       SkylarkType xt = SkylarkType.of(x);
       this.contentType = checkType(contentType, xt);
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 4438dde..bbe71ef 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
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.lib.syntax;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkinterface.Param;
@@ -86,12 +85,6 @@
     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();
-  }
-
   @Override
   public boolean truth() {
     return !isEmpty();
@@ -255,8 +248,10 @@
 
     // All these types and casts are lies.
     Dict<K, V> dict =
-        args instanceof Dict ? (Dict<K, V>) args : getDictFromArgs("update", args, loc, thread);
-    dict = Dict.plus(dict, (Dict<K, V>) kwargs, thread);
+        args instanceof Dict
+            ? (Dict<K, V>) args
+            : getDictFromArgs("update", args, loc, thread.mutability());
+    dict = Dict.plus(dict, (Dict<K, V>) kwargs, thread.mutability());
     putAll(dict, loc);
     return Starlark.NONE;
   }
@@ -305,7 +300,7 @@
     return StarlarkList.wrap(thread.mutability(), array);
   }
 
-  private static final Dict<?, ?> EMPTY = withMutability(Mutability.IMMUTABLE);
+  private static final Dict<?, ?> EMPTY = of(Mutability.IMMUTABLE);
 
   /** Returns an immutable empty dict. */
   // Safe because the empty singleton is immutable.
@@ -314,71 +309,24 @@
     return (Dict<K, V>) EMPTY;
   }
 
-  /** Returns an empty dict with the given {@link Mutability}. */
-  public static <K, V> Dict<K, V> withMutability(@Nullable Mutability mutability) {
-    return new Dict<>(mutability);
-  }
-
-  /**
-   * @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);
-  }
-
-  /** Returns a dict mutable in given environment only. */
+  /** Returns a new empty dict with the specified mutability. */
   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);
-  }
-
-  /**
-   * 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 */
+  /** Returns a new dict with the specified mutability and a single entry. */
   public static <K, V> Dict<K, V> of(@Nullable Mutability mu, K k, V v) {
-    return Dict.<K, V>of(mu).putUnsafe(k, v);
+    return new Dict<K, V>(mu).putUnsafe(k, v);
   }
 
-  /** Returns a dict mutable in given environment only, with two given initial key value pairs. */
+  /** Returns a new dict with the specified mutability and two entries. */
   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);
+    return new Dict<K, V>(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
-  static <K, V> Dict<K, V> copyOf(
-      @Nullable Mutability mutability, Map<? extends K, ? extends V> m) {
-    return Dict.<K, V>withMutability(mutability).putAllUnsafe(m);
-  }
-
-  /**
-   * @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);
+  /** Returns a new dict with the specified mutability containing the entries of {@code m}. */
+  public static <K, V> Dict<K, V> copyOf(@Nullable Mutability mu, Map<? extends K, ? extends V> m) {
+    return new Dict<K, V>(mu).putAllUnsafe(m);
   }
 
   /** Puts the given entry into the dict, without calling {@link #checkMutable}. */
@@ -417,7 +365,7 @@
    */
   public void put(K key, V value, Location loc) throws EvalException {
     checkMutable(loc);
-    EvalUtils.checkValidDictKey(key);
+    EvalUtils.checkHashable(key);
     contents.put(key, value);
   }
 
@@ -433,7 +381,7 @@
     checkMutable(loc);
     for (Map.Entry<KK, VV> e : map.entrySet()) {
       KK k = e.getKey();
-      EvalUtils.checkValidDictKey(k);
+      EvalUtils.checkHashable(k);
       contents.put(k, e.getValue());
     }
   }
@@ -562,16 +510,16 @@
   public final boolean containsKey(Object key, Location loc, StarlarkThread thread)
       throws EvalException {
     if (thread.getSemantics().incompatibleDisallowDictLookupUnhashableKeys()) {
-      EvalUtils.checkValidDictKey(key);
+      EvalUtils.checkHashable(key);
     }
     return this.containsKey(key);
   }
 
-  public static <K, V> Dict<K, V> plus(
+  static <K, V> Dict<K, V> plus(
       Dict<? extends K, ? extends V> left,
       Dict<? extends K, ? extends V> right,
-      @Nullable StarlarkThread thread) {
-    Dict<K, V> result = Dict.of(thread);
+      @Nullable Mutability mu) {
+    Dict<K, V> result = Dict.of(mu);
     result.putAllUnsafe(left);
     result.putAllUnsafe(right);
     return result;
@@ -579,8 +527,7 @@
 
   @SuppressWarnings("unchecked")
   static <K, V> Dict<K, V> getDictFromArgs(
-      String funcname, Object args, Location loc, @Nullable StarlarkThread thread)
-      throws EvalException {
+      String funcname, Object args, Location loc, @Nullable Mutability mu) throws EvalException {
     Iterable<?> seq;
     try {
       seq = EvalUtils.toIterable(args, loc);
@@ -589,7 +536,7 @@
           loc,
           String.format("in %s, got %s, want iterable", funcname, EvalUtils.getDataTypeName(args)));
     }
-    Dict<K, V> result = Dict.of(thread);
+    Dict<K, V> result = Dict.of(mu);
     int pos = 0;
     for (Object item : seq) {
       Iterable<?> seq2;
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 e8811e8..82f615e 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
@@ -441,7 +441,7 @@
       case DICT_EXPR:
         {
           DictExpression dictexpr = (DictExpression) expr;
-          Dict<Object, Object> dict = Dict.of(thread);
+          Dict<Object, Object> dict = Dict.of(thread.mutability());
           Location loc = dictexpr.getLocation();
           for (DictExpression.Entry entry : dictexpr.getEntries()) {
             Object k = eval(thread, entry.getKey());
@@ -610,7 +610,7 @@
 
   private static Object evalComprehension(StarlarkThread thread, Comprehension comp)
       throws EvalException, InterruptedException {
-    final Dict<Object, Object> dict = comp.isDict() ? Dict.of(thread) : null;
+    final Dict<Object, Object> dict = comp.isDict() ? Dict.of(thread.mutability()) : null;
     final ArrayList<Object> list = comp.isDict() ? null : new ArrayList<>();
 
     // Save values of all variables bound in a 'for' clause
@@ -666,7 +666,7 @@
         if (dict != null) {
           DictExpression.Entry body = (DictExpression.Entry) comp.getBody();
           Object k = eval(thread, body.getKey());
-          EvalUtils.checkValidDictKey(k);
+          EvalUtils.checkHashable(k);
           Object v = eval(thread, body.getValue());
           dict.put(k, v, comp.getLocation());
         } else {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index d02ed95..bca1cc9 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -110,19 +110,12 @@
         }
       };
 
-  /**
-   * Checks that an Object is a valid key for a Skylark dict.
-   *
-   * @param o an Object to validate
-   * @throws EvalException if o is not a valid key
-   */
-  static void checkValidDictKey(Object o) throws EvalException {
-    // TODO(bazel-team): check that all recursive elements are both Immutable AND Comparable.
-    if (isHashable(o)) {
-      return;
+  /** Throws EvalException if x is not hashable. */
+  static void checkHashable(Object x) throws EvalException {
+    if (!isHashable(x)) {
+      throw new EvalException(
+          null, Printer.format("unhashable type: '%s'", EvalUtils.getDataTypeName(x)));
     }
-    // Same error message as Python (that makes it a TypeError).
-    throw new EvalException(null, Printer.format("unhashable type: '%r'", o.getClass()));
   }
 
   /**
@@ -477,7 +470,7 @@
         b.put(key, value);
       }
     }
-    return Dict.copyOf(thread, b.build());
+    return Dict.copyOf(thread.mutability(), b.build());
   }
 
   /**
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 47d3682..bb746ec 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
@@ -596,9 +596,11 @@
       useStarlarkThread = true)
   public Dict<?, ?> dict(Object args, Dict<?, ?> kwargs, Location loc, StarlarkThread thread)
       throws EvalException {
-    Dict<?, ?> argsDict =
-        args instanceof Dict ? (Dict) args : Dict.getDictFromArgs("dict", args, loc, thread);
-    return Dict.plus(argsDict, kwargs, thread);
+    Dict<?, ?> dict =
+        args instanceof Dict
+            ? (Dict) args
+            : Dict.getDictFromArgs("dict", args, loc, thread.mutability());
+    return Dict.plus(dict, kwargs, thread.mutability());
   }
 
   @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 976603c..0b99431 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
@@ -57,7 +57,7 @@
   @Override
   public Dict<String, Dict<String, Object>> existingRules(Location loc, StarlarkThread thread)
       throws EvalException, InterruptedException {
-    return Dict.of(thread);
+    return Dict.of(thread.mutability());
   }
 
   @Override
diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkProviderTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkProviderTest.java
index 5272098..6eeba19 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/SkylarkProviderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkProviderTest.java
@@ -22,7 +22,9 @@
 import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.SkylarkProvider.SkylarkKey;
+import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.Printer;
+import com.google.devtools.build.lib.syntax.StarlarkThread;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -134,12 +136,11 @@
   /** Instantiates a {@link SkylarkInfo} with fields a=1, b=2, c=3 (and nothing else). */
   private static SkylarkInfo instantiateWithA1B2C3(SkylarkProvider provider) throws Exception{
     // Code under test begins with the entry point in BaseFunction.
+    StarlarkThread thread =
+        StarlarkThread.builder(Mutability.create("test")).useDefaultSemantics().build();
     Object result =
         provider.call(
-            ImmutableList.of(),
-            ImmutableMap.of("a", 1, "b", 2, "c", 3),
-            /*ast=*/ null,
-            /*thread=*/ null);
+            ImmutableList.of(), ImmutableMap.of("a", 1, "b", 2, "c", 3), /*ast=*/ null, thread);
     assertThat(result).isInstanceOf(SkylarkInfo.class);
     return (SkylarkInfo) result;
   }
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 365b8c6..b242e1c 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
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 import com.google.devtools.build.lib.syntax.EvalUtils.ComparisonException;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
+import javax.annotation.Nullable;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -35,12 +36,12 @@
 @RunWith(JUnit4.class)
 public class EvalUtilsTest extends EvaluationTestCase {
 
-  private static StarlarkList<Object> makeList(StarlarkThread thread) {
-    return StarlarkList.of(thread == null ? null : thread.mutability(), 1, 2, 3);
+  private static StarlarkList<Object> makeList(@Nullable Mutability mu) {
+    return StarlarkList.of(mu, 1, 2, 3);
   }
 
-  private static Dict<Object, Object> makeDict(StarlarkThread thread) {
-    return Dict.of(thread, 1, 1, 2, 2);
+  private static Dict<Object, Object> makeDict(@Nullable Mutability mu) {
+    return Dict.of(mu, 1, 1, 2, 2);
   }
 
   /** MockClassA */
@@ -73,18 +74,17 @@
   public void testDatatypeMutabilityShallow() throws Exception {
     assertThat(EvalUtils.isImmutable(Tuple.of(1, 2, 3))).isTrue();
 
-    // Mutability depends on the environment.
     assertThat(EvalUtils.isImmutable(makeList(null))).isTrue();
     assertThat(EvalUtils.isImmutable(makeDict(null))).isTrue();
-    assertThat(EvalUtils.isImmutable(makeList(thread))).isFalse();
-    assertThat(EvalUtils.isImmutable(makeDict(thread))).isFalse();
+    assertThat(EvalUtils.isImmutable(makeList(thread.mutability()))).isFalse();
+    assertThat(EvalUtils.isImmutable(makeDict(thread.mutability()))).isFalse();
   }
 
   @Test
   public void testDatatypeMutabilityDeep() throws Exception {
-    assertThat(EvalUtils.isImmutable(Tuple.<Object>of(makeList(null)))).isTrue();
+    assertThat(EvalUtils.isImmutable(Tuple.of(makeList(null)))).isTrue();
 
-    assertThat(EvalUtils.isImmutable(Tuple.<Object>of(makeList(thread)))).isFalse();
+    assertThat(EvalUtils.isImmutable(Tuple.of(makeList(thread.mutability())))).isFalse();
   }
 
   @Test
@@ -98,8 +98,8 @@
       Tuple.of("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"),
+      Dict.of(thread.mutability(), "key", 123),
+      Dict.of(thread.mutability(), 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 0685ece..9be6e4a 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
@@ -195,7 +195,7 @@
               final Map<String, Object> kwargs,
               FuncallExpression ast,
               StarlarkThread thread) {
-            return Dict.copyOf(thread, kwargs);
+            return Dict.copyOf(thread.mutability(), kwargs);
           }
         };