diff --git a/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java
index eb33eb1..a60fe0d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/EmptyConfiguredTarget.java
@@ -18,12 +18,14 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.InfoInterface;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.skyframe.BuildConfigurationValue;
 import javax.annotation.Nullable;
 
 /** A configured target that is empty. */
+@Immutable // (and Starlark-hashable)
 public class EmptyConfiguredTarget extends AbstractConfiguredTarget {
   public EmptyConfiguredTarget(Label label, BuildConfigurationValue.Key configurationKey) {
     super(label, configurationKey, NestedSetBuilder.emptySet(Order.STABLE_ORDER));
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java
index 35bd929..d83b7cb 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/EnvironmentGroupConfiguredTarget.java
@@ -17,6 +17,7 @@
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.analysis.TargetContext;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.InfoInterface;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
@@ -26,6 +27,7 @@
  * groups are not really first-class Targets.
  */
 @AutoCodec
+@Immutable // (and Starlark-hashable)
 public final class EnvironmentGroupConfiguredTarget extends AbstractConfiguredTarget {
   @AutoCodec.Instantiator
   @AutoCodec.VisibleForSerialization
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
index afc6b96..2dff116 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/FileConfiguredTarget.java
@@ -31,6 +31,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.collect.nestedset.Order;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.InfoInterface;
 import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
 import com.google.devtools.build.lib.packages.Provider;
@@ -42,6 +43,7 @@
  * A ConfiguredTarget for a source FileTarget. (Generated files use a subclass,
  * OutputFileConfiguredTarget.)
  */
+@Immutable // (and Starlark-hashable)
 public abstract class FileConfiguredTarget extends AbstractConfiguredTarget
     implements FileType.HasFileType, LicensesProvider {
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
index 93c9f9f..dfae3b1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/MergedConfiguredTarget.java
@@ -25,6 +25,7 @@
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProviderMap;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProviderMapBuilder;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.InfoInterface;
 import com.google.devtools.build.lib.packages.Provider;
 import com.google.devtools.build.lib.packages.Provider.Key;
@@ -40,6 +41,7 @@
  * <p>This is an ephemeral object created only for the analysis of a single configured target. After
  * that configured target is analyzed, this is thrown away.
  */
+@Immutable // (and Starlark-hashable)
 public final class MergedConfiguredTarget extends AbstractConfiguredTarget {
   private final ConfiguredTarget base;
   private final ImmutableList<ConfiguredAspect> aspects;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java
index bf5df35..6b30c77 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/PackageGroupConfiguredTarget.java
@@ -24,6 +24,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.collect.nestedset.Order;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.InfoInterface;
 import com.google.devtools.build.lib.packages.PackageGroup;
@@ -39,6 +40,7 @@
  * not really first-class Targets.
  */
 @AutoCodec
+@Immutable // (and Starlark-hashable)
 public final class PackageGroupConfiguredTarget extends AbstractConfiguredTarget
     implements PackageSpecificationProvider {
   private static final FileProvider NO_FILES = new FileProvider(
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
index a541872..3defd90 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
@@ -37,6 +37,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.InfoInterface;
 import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.packages.PackageSpecification.PackageGroupContents;
@@ -60,6 +61,7 @@
  * com.google.devtools.build.lib.analysis.RuleConfiguredTargetFactory}.
  */
 @AutoCodec(checkClassExplicitlyAllowed = true)
+@Immutable // (and Starlark-hashable)
 public final class RuleConfiguredTarget extends AbstractConfiguredTarget {
   /**
    * The name of the key for the 'actions' synthesized provider.
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 bc655b9..f515070 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
@@ -452,9 +452,9 @@
 
     /** Adds a direct element, checking that its type is equal to the elements already added. */
     public Builder addDirect(Object x) throws EvalException {
-      // TODO(adonovan): this check causes depset(Target) to fail (see reviewlog).
-      // Investigate how/why user code is exploiting the weak check.
-      // EvalUtils.checkValidDictKey(x);
+      // In case of problems, see b/144992997 or github.com/bazelbuild/bazel/issues/10289.
+      EvalUtils.checkValidDictKey(x);
+
       SkylarkType xt = SkylarkType.of(x);
       this.contentType = checkType(contentType, xt);
       builder.add(x);