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 25eea64..11817f5 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
@@ -62,7 +62,7 @@
 
   @VisibleForTesting
   public static final String BAD_SET_TYPE_ERROR =
-      "Value for key %s must be a set of %s, instead found set of %s.";
+      "Value for key %s must be a set of %s, instead found %s.";
 
   @VisibleForTesting
   public static final String BAD_PROVIDERS_ITER_ERROR =
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProviderSkylarkConverters.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProviderSkylarkConverters.java
index 9cbf30c..28df790 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProviderSkylarkConverters.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcProviderSkylarkConverters.java
@@ -107,7 +107,6 @@
       return convertPathFragmentsToSkylark((NestedSet<PathFragment>) javaValue);
     }
 
-    @SuppressWarnings("unchecked")
     @Override
     public NestedSet<?> valueForJava(Key<?> javaKey, Object skylarkValue) throws EvalException {
       NestedSet<String> nestedSet =
@@ -135,7 +134,6 @@
       return SkylarkNestedSet.of(String.class, result.build());
     }
 
-    @SuppressWarnings("unchecked")
     @Override
     public NestedSet<?> valueForJava(Key<?> javaKey, Object skylarkValue) throws EvalException {
       NestedSet<String> nestedSet =
@@ -162,8 +160,7 @@
                 BAD_SET_TYPE_ERROR,
                 keyName,
                 EvalUtils.getDataTypeNameFromClass(expectedSetType),
-                EvalUtils.getDataTypeNameFromClass(
-                    ((SkylarkNestedSet) toCheck).getContentType().getType())),
+                EvalUtils.getDataTypeName(toCheck, /*fullDetails=*/ true)),
             exception);
       }
     } else {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyInfo.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyInfo.java
index 9349ee9..7f641ce 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyInfo.java
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet.TypeException;
+import com.google.devtools.build.lib.syntax.SkylarkType;
 import com.google.devtools.build.lib.syntax.Starlark;
 import java.util.Objects;
 import javax.annotation.Nullable;
@@ -39,13 +40,13 @@
   public static final PyInfoProvider PROVIDER = new PyInfoProvider();
 
   /**
-   * Returns true if the given depset has a content type that is a subtype of the given class, and
-   * has an order compatible with the given order.
+   * Returns true if the given depset has the given content type and order compatible with the given
+   * order.
    */
   private static boolean depsetHasTypeAndCompatibleOrder(
-      SkylarkNestedSet depset, Class<?> clazz, Order order) {
+      SkylarkNestedSet depset, SkylarkType type, Order order) {
     // Work around #7266 by special-casing the empty set in the type check.
-    boolean typeOk = depset.isEmpty() || depset.getContentType().canBeCastTo(clazz);
+    boolean typeOk = depset.isEmpty() || depset.getContentType().equals(type);
     boolean orderOk = depset.getOrder().isCompatible(order);
     return typeOk && orderOk;
   }
@@ -81,12 +82,12 @@
       boolean hasPy3OnlySources) {
     super(PROVIDER, location);
     Preconditions.checkArgument(
-        depsetHasTypeAndCompatibleOrder(transitiveSources, Artifact.class, Order.COMPILE_ORDER));
+        depsetHasTypeAndCompatibleOrder(transitiveSources, Artifact.TYPE, Order.COMPILE_ORDER));
     // TODO(brandjon): PyCommon currently requires COMPILE_ORDER, but we'll probably want to change
     // that to NAIVE_LINK (preorder). In the meantime, order isn't an invariant of the provider
     // itself, so we use STABLE here to accept any order.
     Preconditions.checkArgument(
-        depsetHasTypeAndCompatibleOrder(imports, String.class, Order.STABLE_ORDER));
+        depsetHasTypeAndCompatibleOrder(imports, SkylarkType.STRING, Order.STABLE_ORDER));
     this.transitiveSources = transitiveSources;
     this.usesSharedLibraries = usesSharedLibraries;
     this.imports = imports;
@@ -185,8 +186,7 @@
               ? SkylarkNestedSet.of(String.class, NestedSetBuilder.emptySet(Order.COMPILE_ORDER))
               : (SkylarkNestedSet) importsUncast;
 
-      if (!depsetHasTypeAndCompatibleOrder(
-          transitiveSources, Artifact.class, Order.COMPILE_ORDER)) {
+      if (!depsetHasTypeAndCompatibleOrder(transitiveSources, Artifact.TYPE, Order.COMPILE_ORDER)) {
         throw new EvalException(
             loc,
             String.format(
@@ -194,7 +194,7 @@
                     + "a '%s')",
                 describeType(transitiveSources)));
       }
-      if (!depsetHasTypeAndCompatibleOrder(imports, String.class, Order.STABLE_ORDER)) {
+      if (!depsetHasTypeAndCompatibleOrder(imports, SkylarkType.STRING, Order.STABLE_ORDER)) {
         throw new EvalException(
             loc,
             String.format(
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 b9450e1..7bbef1d 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
@@ -34,14 +34,9 @@
 /**
  * A generic, type-safe {@link NestedSet} wrapper for Skylark.
  *
- * <p>The content type of a {@code SkylarkNestedSet} is the intersection of the {@link SkylarkType}
- * of each of its elements. It is an error if this intersection is {@link SkylarkType#BOTTOM}. An
- * empty set has a content type of {@link SkylarkType#TOP}.
- *
- * <p>It is also an error if this type has a non-bottom intersection with {@link SkylarkType#DICT}
- * or {@link SkylarkType#LIST}, unless the set is empty.
- *
- * <p>TODO(bazel-team): Decide whether this restriction is still useful.
+ * <p>The content type of a non-empty {@code SkylarkNestedSet} is determined by its first element.
+ * All elements must have the same type. An empty depset has type {@code SkylarkType.TOP}, and may
+ * be combined with any other depset.
  */
 @SkylarkModule(
     name = "depset",
@@ -51,8 +46,10 @@
             + " defined traversal order. Commonly used for accumulating data from transitive"
             + " dependencies in rules and aspects. For more information see <a"
             + " href=\"../depsets.md\">here</a>."
-            + " <p>Depsets are not implemented as hash sets and do"
-            + " not support fast membership tests. If you need a general set datatype, you can"
+            + " <p>The elements of a depset must be hashable and all of the same type (as"
+            + " defined by the built-in type(x) function), but depsets are not simply"
+            + " hash sets and do not support fast membership tests."
+            + " If you need a general set datatype, you can"
             + " simulate one using a dictionary where all keys map to <code>True</code>."
             + "<p>Depsets are immutable. They should be created using their <a"
             + " href=\"globals.html#depset\">constructor function</a> and merged or augmented with"
@@ -125,19 +122,15 @@
     if (item instanceof SkylarkNestedSet) {
       SkylarkNestedSet nestedSet = (SkylarkNestedSet) item;
       if (!nestedSet.isEmpty()) {
-        contentType = getTypeAfterInsert(
-            contentType, nestedSet.contentType, /*lastInsertedType=*/ null, loc);
+        contentType = checkType(contentType, nestedSet.contentType, loc);
         transitiveItemsBuilder.add(nestedSet.set);
       }
     } else if (item instanceof Sequence) {
-      SkylarkType lastInsertedType = null;
-      // TODO(bazel-team): we should check ImmutableList here but it screws up genrule at line 43
-      for (Object object : (Sequence) item) {
-        SkylarkType elemType = SkylarkType.of(object);
-        contentType = getTypeAfterInsert(contentType, elemType, lastInsertedType, loc);
-        lastInsertedType = elemType;
-        checkImmutable(object, loc);
-        itemsBuilder.add(object);
+      for (Object x : (Sequence) item) {
+        EvalUtils.checkValidDictKey(x);
+        SkylarkType xt = SkylarkType.of(x);
+        contentType = checkType(contentType, xt, loc);
+        itemsBuilder.add(x);
       }
     } else {
       throw new EvalException(
@@ -197,58 +190,28 @@
     return of(SkylarkType.of(contentType), set);
   }
 
-  private static final SkylarkType DICT_LIST_UNION =
-      SkylarkType.Union.of(SkylarkType.DICT, SkylarkType.LIST);
-
   /**
    * Checks that an item type is allowed in a given set type, and returns the type of a new depset
    * with that item inserted.
    */
-  private static SkylarkType getTypeAfterInsert(
-      SkylarkType depsetType, SkylarkType itemType, SkylarkType lastInsertedType, Location loc)
+  private static SkylarkType checkType(SkylarkType depsetType, SkylarkType itemType, Location loc)
       throws EvalException {
-    if (lastInsertedType != null && lastInsertedType.equals(itemType)) {
-      // Fast path, type shouldn't have changed, so no need to check.
-      // TODO(bazel-team): Make skylark type checking less expensive.
-      return depsetType;
-    }
-
-    // Check not dict or list.
-    if (SkylarkType.intersection(DICT_LIST_UNION, itemType) != SkylarkType.BOTTOM) {
-      throw new EvalException(
-          loc, String.format("depsets cannot contain items of type '%s'", itemType));
-    }
-
-    SkylarkType resultType = SkylarkType.intersection(depsetType, itemType);
-
-    // New depset type should follow the following rules:
-    // 1. Only empty depsets may be of type TOP.
-    // 2. If the previous depset type fully contains the new item type, then the depset type is
-    //    retained.
-    // 3. If the item type fully contains the old depset type, then the depset type becomes the
-    //    item type. (The depset type becomes less strict.)
-    // 4. Otherwise, the insert is invalid.
-    if (depsetType == SkylarkType.TOP) {
-      return resultType;
-    } else if (resultType.equals(itemType)) {
-      return depsetType;
-    } else if (resultType.equals(depsetType)) {
+    // An initially empty depset takes its type from the first element added.
+    // Otherwise, the types of the item and depset must match exactly.
+    //
+    // TODO(adonovan): why is the empty depset TOP, not BOTTOM?
+    // T ^ TOP == TOP, whereas T ^ BOTTOM == T.
+    // This can't be changed without breaking callers of getContentType who
+    // expect to see TOP. Maybe this is minor, but it at least would require
+    // changes to EvalUtils#getDataTypeName so that it
+    // can continue to print "depset of Objects" instead of "depset of EmptyTypes".
+    // Better yet, break the behavior and change it to "empty depset".
+    if (depsetType == SkylarkType.TOP || depsetType.equals(itemType)) {
       return itemType;
-    } else {
-      throw new EvalException(
-          loc,
-          String.format(
-              "cannot add an item of type '%s' to a depset of '%s'", itemType, depsetType));
     }
-  }
-
-  /**
-   * Throws EvalException if a given value is mutable.
-   */
-  private static void checkImmutable(Object o, Location loc) throws EvalException {
-    if (!EvalUtils.isImmutable(o)) {
-      throw new EvalException(loc, "depsets cannot contain mutable items");
-    }
+    throw new EvalException(
+        loc,
+        String.format("cannot add an item of type '%s' to a depset of '%s'", itemType, depsetType));
   }
 
   /**
@@ -275,6 +238,20 @@
   // The precondition ensures generic type safety, and sets are immutable.
   @SuppressWarnings("unchecked")
   public <T> NestedSet<T> getSet(Class<T> type) throws TypeException {
+    // TODO(adonovan): eliminate this function and toCollection in favor of ones
+    // that accept a SkylarkType augmented with a type parameter so that it acts
+    // like a "reified generic": whereas a Class symbol can express only the
+    // top-level value tag, a SkylarkType could express an entire type such as
+    // Set<List<String+Integer>>, and act as a "witness" or existential type to
+    // unlock the untyped nested set. For example:
+    //
+    //  public <T> NestedSet<T> getSet(SkylarkType<NestedSet<T>> witness) throws TypeException {
+    //     if (this.type.matches(witness)) {
+    //         return witness.convert(this);
+    //     }
+    //     throw TypeException;
+    // }
+
     checkHasContentType(type);
     return (NestedSet<T>) set;
   }
@@ -473,8 +450,8 @@
     private final NestedSetBuilder<Object> builder;
     /** Location for error messages */
     private final Location location;
+
     private SkylarkType contentType = SkylarkType.TOP;
-    private SkylarkType lastInsertedType = null;
 
     private Builder(Order order, Location location) {
       this.order = order;
@@ -482,30 +459,22 @@
       this.builder = new NestedSetBuilder<>(order);
     }
 
-    /**
-     * Add a direct element, checking its type to be compatible to already added
-     * elements and transitive sets.
-     */
-    public Builder addDirect(Object direct) throws EvalException {
-      SkylarkType elemType = SkylarkType.of(direct);
-      contentType = getTypeAfterInsert(contentType, elemType, lastInsertedType, location);
-      lastInsertedType = elemType;
-      builder.add(direct);
+    /** Adds a direct element, checking that its type is equal to the elements already added. */
+    public Builder addDirect(Object x) throws EvalException {
+      EvalUtils.checkValidDictKey(x);
+      SkylarkType xt = SkylarkType.of(x);
+      this.contentType = checkType(contentType, xt, location);
+      builder.add(x);
       return this;
     }
 
-    /**
-     * Add a transitive set, checking its content type to be compatible to already added
-     * elements and transitive sets.
-     */
+    /** Adds a transitive set, checking that its type is equal to the elements already added. */
     public Builder addTransitive(SkylarkNestedSet transitive) throws EvalException {
       if (transitive.isEmpty()) {
         return this;
       }
 
-      contentType = getTypeAfterInsert(
-          contentType, transitive.getContentType(), lastInsertedType, this.location);
-      lastInsertedType = transitive.getContentType();
+      this.contentType = checkType(contentType, transitive.getContentType(), location);
 
       if (!order.isCompatible(transitive.getOrder())) {
         throw new EvalException(location,
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
index 7367f40..fe907f3 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
@@ -82,39 +82,37 @@
   // The main primitives to override in subclasses
 
   /** Is the given value an element of this type? By default, no (empty type) */
-  public boolean contains(Object value) {
+  boolean contains(Object value) {
     return false;
   }
 
   /**
    * intersectWith() is the internal method from which function intersection(t1, t2) is computed.
-   * OVERRIDE this method in your classes, but DO NOT TO CALL it: only call intersection().
-   * When computing intersection(t1, t2), whichever type defined before the other
-   * knows nothing about the other and about their intersection, and returns BOTTOM;
-   * the other knows about the former, and returns their intersection (which may be BOTTOM).
-   * intersection() will call in one order then the other, and return whichever answer
-   * isn't BOTTOM, if any. By default, types are disjoint and their intersection is BOTTOM.
+   * OVERRIDE this method in your classes, but DO NOT TO CALL it: only call intersection(). When
+   * computing intersection(t1, t2), whichever type defined before the other knows nothing about the
+   * other and about their intersection, and returns BOTTOM; the other knows about the former, and
+   * returns their intersection (which may be BOTTOM). intersection() will call in one order then
+   * the other, and return whichever answer isn't BOTTOM, if any. By default, types are disjoint and
+   * their intersection is BOTTOM.
    */
   // TODO(bazel-team): should we define and use an Exception instead?
-  protected SkylarkType intersectWith(SkylarkType other) {
+  SkylarkType intersectWith(SkylarkType other) {
     return BOTTOM;
   }
 
   /** @return true if any object of this SkylarkType can be cast to that Java class */
-  public boolean canBeCastTo(Class<?> type) {
+  boolean canBeCastTo(Class<?> type) {
     return SkylarkType.of(type).includes(this);
   }
 
   /** @return the smallest java Class known to contain all elements of this type */
   // Note: most user-code should be using a variant that throws an Exception
   // if the result is Object.class but the type isn't TOP.
-  public Class<?> getType() {
+  Class<?> getType() {
     return Object.class;
   }
 
-  // The actual intersection function for users to use
-
-  public static SkylarkType intersection(SkylarkType t1, SkylarkType t2) {
+  static SkylarkType intersection(SkylarkType t1, SkylarkType t2) {
     if (t1.equals(t2)) {
       return t1;
     }
@@ -126,11 +124,11 @@
     }
   }
 
-  public boolean includes(SkylarkType other) {
+  boolean includes(SkylarkType other) {
     return intersection(this, other).equals(other);
   }
 
-  public SkylarkType getArgType() {
+  SkylarkType getArgType() {
     return TOP;
   }
 
@@ -139,10 +137,10 @@
   // Notable types
 
   /** A singleton for the TOP type, that at analysis time means that any type is possible. */
-  @AutoCodec public static final Simple TOP = new Top();
+  @AutoCodec static final Simple TOP = new Top();
 
   /** A singleton for the BOTTOM type, that contains no element */
-  @AutoCodec public static final Simple BOTTOM = new Bottom();
+  @AutoCodec static final Simple BOTTOM = new Bottom();
 
   /** NONE, the Unit type, isomorphic to Void, except its unique element prints as None */
   // Note that we currently consider at validation time that None is in every type,
@@ -160,71 +158,17 @@
   /** The BOOLEAN type, that contains TRUE and FALSE */
   @AutoCodec public static final Simple BOOL = Simple.forClass(Boolean.class);
 
-  /** The FUNCTION type, that contains all functions, otherwise dynamically typed at call-time */
-  @AutoCodec
-  public static final SkylarkFunctionType FUNCTION = new SkylarkFunctionType("unknown", TOP);
-
   /** The DICT type, that contains Dict */
-  @AutoCodec public static final Simple DICT = Simple.forClass(Dict.class);
-
-  /** The SEQUENCE type, that contains lists and tuples */
-  // TODO(bazel-team): this was added for backward compatibility with the BUILD language,
-  // that doesn't make a difference between list and tuple, so that functions can be declared
-  // that keep not making the difference. Going forward, though, we should investigate whether
-  // we ever want to use this type, and if not, make sure no existing client code uses it.
-  @AutoCodec public static final Simple SEQUENCE = Simple.forClass(Sequence.class);
+  @AutoCodec static final Simple DICT = Simple.forClass(Dict.class);
 
   /** The LIST type, that contains all StarlarkList-s */
-  @AutoCodec public static final Simple LIST = Simple.forClass(StarlarkList.class);
+  @AutoCodec static final Simple LIST = Simple.forClass(StarlarkList.class);
 
   /** The TUPLE type, that contains all Tuple-s */
-  @AutoCodec public static final Simple TUPLE = Simple.forClass(Tuple.class);
-
-  /** The STRING_PAIR type, that contains Tuple-s of size 2 containing only Strings. */
-  @AutoCodec public static final SkylarkType STRING_PAIR = new StringPairType();
-
-  /** The STRING_LIST type, a StarlarkList of strings */
-  @AutoCodec public static final SkylarkType STRING_LIST = Combination.of(LIST, STRING);
-
-  /** The INT_LIST type, a StarlarkList of integers */
-  @AutoCodec public static final SkylarkType INT_LIST = Combination.of(LIST, INT);
+  @AutoCodec static final Simple TUPLE = Simple.forClass(Tuple.class);
 
   /** The SET type, that contains all SkylarkNestedSets, and the generic combinator for them */
-  // TODO(adonovan): eliminate? It appears to be only an optimization.
-  @AutoCodec public static final Simple SET = Simple.forClass(SkylarkNestedSet.class);
-
-  private static class StringPairType extends SkylarkType {
-
-    @Override
-    public boolean contains(Object value) {
-      if (value instanceof Tuple) {
-        Tuple<?> tuple = (Tuple<?>) value;
-        return tuple.size() == 2
-            && tuple.get(0) instanceof String
-            && tuple.get(1) instanceof String;
-      }
-      return false;
-    }
-
-    @Override
-    public Class<?> getType() {
-      return Tuple.class;
-    }
-
-    @Override
-    public String toString() {
-      return "string-pair tuple";
-    }
-
-    @Override
-    protected SkylarkType intersectWith(SkylarkType other) {
-      if (other.equals(this) || other.canBeCastTo(Tuple.class)) {
-        return this;
-      } else {
-        return BOTTOM;
-      }
-    }
-  }
+  @AutoCodec static final Simple SET = Simple.forClass(SkylarkNestedSet.class);
 
   // Common subclasses of SkylarkType
 
@@ -235,10 +179,13 @@
       super(Object.class);
     }
 
-    @Override public boolean contains(Object value) {
+    @Override
+    boolean contains(Object value) {
       return true;
     }
-    @Override public SkylarkType intersectWith(SkylarkType other) {
+
+    @Override
+    SkylarkType intersectWith(SkylarkType other) {
       return other;
     }
     @Override public String toString() {
@@ -253,7 +200,8 @@
       super(Empty.class);
     }
 
-    @Override public SkylarkType intersectWith(SkylarkType other) {
+    @Override
+    SkylarkType intersectWith(SkylarkType other) {
       return this;
     }
     @Override public String toString() {
@@ -270,10 +218,13 @@
       this.type = type;
     }
 
-    @Override public boolean contains(Object value) {
+    @Override
+    boolean contains(Object value) {
       return value != null && type.isInstance(value);
     }
-    @Override public Class<?> getType() {
+
+    @Override
+    Class<?> getType() {
       return type;
     }
     @Override public boolean equals(Object other) {
@@ -289,7 +240,9 @@
     @Override public String toString() {
       return EvalUtils.getDataTypeNameFromClass(type);
     }
-    @Override public boolean canBeCastTo(Class<?> type) {
+
+    @Override
+    boolean canBeCastTo(Class<?> type) {
       return this.type == type || super.canBeCastTo(type);
     }
 
@@ -341,7 +294,7 @@
 
   /** Combination of a generic type and an argument type */
   @AutoCodec
-  public static class Combination extends SkylarkType {
+  static class Combination extends SkylarkType {
     // For the moment, we can only combine a Simple type with a Simple type,
     // and the first one has to be a Java generic class,
     // and in practice actually one of Sequence or SkylarkNestedSet
@@ -355,7 +308,7 @@
     }
 
     @Override
-    public boolean contains(Object value) {
+    boolean contains(Object value) {
       // The empty collection is member of compatible types
       if (value == null || !genericType.contains(value)) {
         return false;
@@ -365,7 +318,9 @@
             || argType.includes(valueArgType);
       }
     }
-    @Override public SkylarkType intersectWith(SkylarkType other) {
+
+    @Override
+    SkylarkType intersectWith(SkylarkType other) {
       // For now, we only accept generics with a single covariant parameter
       if (genericType.equals(other)) {
         return this;
@@ -409,14 +364,17 @@
       // equal underlying types yield the same hashCode
       return 0x20B14A71 + genericType.hashCode() * 1009 + argType.hashCode() * 1013;
     }
-    @Override public Class<?> getType() {
+
+    @Override
+    Class<?> getType() {
       return genericType.getType();
     }
     SkylarkType getGenericType() {
       return genericType;
     }
+
     @Override
-    public SkylarkType getArgType() {
+    SkylarkType getArgType() {
       return argType;
     }
     @Override public String toString() {
@@ -426,7 +384,10 @@
     private static final Interner<Combination> combinationInterner =
         BlazeInterners.newWeakInterner();
 
-    public static SkylarkType of(SkylarkType generic, SkylarkType argument) {
+    // TODO(adonovan): eliminate or rename all the 'of' functions.
+    // This is an abuse of overloading and "static inheritance".
+
+    static SkylarkType of(SkylarkType generic, SkylarkType argument) {
       // assume all combinations with TOP are the same as the simple type, and canonicalize.
       Preconditions.checkArgument(generic instanceof Simple);
       if (argument == TOP) {
@@ -435,14 +396,11 @@
         return combinationInterner.intern(new Combination(generic, argument));
       }
     }
-    public static SkylarkType of(Class<?> generic, Class<?> argument) {
-      return of(Simple.forClass(generic), Simple.forClass(argument));
-    }
   }
 
   /** Union types, used a lot in "dynamic" languages such as Python or Skylark */
   @AutoCodec
-  public static class Union extends SkylarkType {
+  static class Union extends SkylarkType {
     private final ImmutableList<SkylarkType> types;
 
     @VisibleForSerialization
@@ -451,7 +409,7 @@
     }
 
     @Override
-    public boolean contains(Object value) {
+    boolean contains(Object value) {
       for (SkylarkType type : types) {
         if (type.contains(value)) {
           return true;
@@ -483,7 +441,8 @@
     @Override public String toString() {
       return Joiner.on(" or ").join(types);
     }
-    public static List<SkylarkType> addElements(List<SkylarkType> list, SkylarkType type) {
+
+    static List<SkylarkType> addElements(List<SkylarkType> list, SkylarkType type) {
       if (type instanceof Union) {
         list.addAll(((Union) type).types);
       } else if (type != BOTTOM) {
@@ -491,7 +450,9 @@
       }
       return list;
     }
-    @Override public SkylarkType intersectWith(SkylarkType other) {
+
+    @Override
+    SkylarkType intersectWith(SkylarkType other) {
       List<SkylarkType> otherTypes = addElements(new ArrayList<>(), other);
       List<SkylarkType> results = new ArrayList<>();
       for (SkylarkType element : types) {
@@ -501,7 +462,8 @@
       }
       return Union.of(results);
     }
-    public static SkylarkType of(List<SkylarkType> types) {
+
+    static SkylarkType of(List<SkylarkType> types) {
       // When making the union of many types,
       // canonicalize them into elementary (non-Union) types,
       // and then eliminate trivially redundant types from the list.
@@ -541,10 +503,12 @@
         return new Union(ImmutableList.copyOf(canonical));
       }
     }
-    public static SkylarkType of(SkylarkType... types) {
+
+    static SkylarkType of(SkylarkType... types) {
       return of(Arrays.asList(types));
     }
-    public static SkylarkType of(SkylarkType t1, SkylarkType t2) {
+
+    static SkylarkType of(SkylarkType t1, SkylarkType t2) {
       return of(ImmutableList.of(t1, t2));
     }
   }
@@ -553,15 +517,10 @@
   // This function is used to infer the type to use for a SkylarkNestedSet from its first
   // element, but this may be unsound in general (e.g. in the presence of sum types).
   static SkylarkType of(Object object) {
-    SkylarkType type = of(object.getClass());
-    if (type.canBeCastTo(Tuple.class)) {
-      if (STRING_PAIR.contains(object)) {
-        return STRING_PAIR;
-      }
-    }
-    return type;
+    return of(object.getClass());
   }
 
+  /** Returns the type for a Java class. */
   public static SkylarkType of(Class<?> type) {
     if (SkylarkNestedSet.class.isAssignableFrom(type)) { // just an optimization
       return SET;
@@ -575,20 +534,23 @@
   // TODO(adonovan): these functions abuse overloading and look like sum type constructors.
   // Give them better names such as genericOf(generic, argument)? Or rethink the API.
 
-  public static SkylarkType of(SkylarkType t1, SkylarkType t2) {
+  private static SkylarkType of(SkylarkType t1, SkylarkType t2) {
     return Combination.of(t1, t2);
   }
-  public static SkylarkType of(Class<?> t1, Class<?> t2) {
-    return Combination.of(t1, t2);
+
+  /** Returns the type for a Java parameterized type {@code generic<argument>}. */
+  public static SkylarkType of(Class<?> generic, Class<?> argument) {
+    return Combination.of(Simple.forClass(generic), Simple.forClass(argument));
   }
 
   /** A class representing the type of a Skylark function. */
   @AutoCodec
-  public static final class SkylarkFunctionType extends SkylarkType {
+  static final class SkylarkFunctionType extends SkylarkType {
     private final String name;
     @Nullable private final SkylarkType returnType;
 
-    @Override public SkylarkType intersectWith(SkylarkType other) {
+    @Override
+    SkylarkType intersectWith(SkylarkType other) {
       // This gives the wrong result if both return types are incompatibly updated later!
       if (other instanceof SkylarkFunctionType) {
         SkylarkFunctionType fun = (SkylarkFunctionType) other;
@@ -606,7 +568,9 @@
         return BOTTOM;
       }
     }
-    @Override public Class<?> getType() {
+
+    @Override
+    Class<?> getType() {
       return BaseFunction.class;
     }
     @Override public String toString() {
@@ -615,12 +579,12 @@
     }
 
     @Override
-    public boolean contains(Object value) {
+    boolean contains(Object value) {
       // This returns true a bit too much, not looking at the result type.
       return value instanceof BaseFunction;
     }
 
-    public static SkylarkFunctionType of(String name, SkylarkType returnType) {
+    static SkylarkFunctionType of(String name, SkylarkType returnType) {
       return new SkylarkFunctionType(name, returnType);
     }
 
@@ -633,7 +597,7 @@
 
   // Utility functions regarding types
 
-  public static SkylarkType getGenericArgType(Object value) {
+  private static SkylarkType getGenericArgType(Object value) {
     if (value instanceof SkylarkNestedSet) {
       return ((SkylarkNestedSet) value).getContentType();
     } else {
@@ -650,8 +614,9 @@
    * @param format - a format String
    * @param args - arguments to format, in case there's an exception
    */
-  public static <T> T cast(Object value, Class<T> type,
-      Location loc, String format, Object... args) throws EvalException {
+  // TODO(adonovan): irrelevant; eliminate.
+  public static <T> T cast(Object value, Class<T> type, Location loc, String format, Object... args)
+      throws EvalException {
     try {
       return type.cast(value);
     } catch (ClassCastException e) {
diff --git a/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcSkylarkTest.java b/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcSkylarkTest.java
index 41ff8f7..a487583 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcSkylarkTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcSkylarkTest.java
@@ -1025,7 +1025,8 @@
     assertThat(e)
         .hasMessageThat()
         .contains(
-            String.format(AppleSkylarkCommon.BAD_SET_TYPE_ERROR, "library", "File", "string"));
+            String.format(
+                AppleSkylarkCommon.BAD_SET_TYPE_ERROR, "library", "File", "depset of strings"));
   }
 
   @Test
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 1f14a23..ad00cd9 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
@@ -1267,8 +1267,8 @@
 
   @Test
   public void testNsetBadMutableItem() throws Exception {
-    checkEvalErrorContains("depsets cannot contain mutable items", "depset([([],)])");
-    checkEvalErrorContains("depsets cannot contain mutable items", "depset([struct(a=[])])");
+    checkEvalErrorContains("unhashable type: 'tuple'", "depset([([],)])");
+    checkEvalErrorContains("unhashable type: 'struct'", "depset([struct(a=[])])");
   }
 
   private static StructImpl makeStruct(String field, Object value) {
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
index 2139bd6..83d6fec 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
@@ -962,8 +962,7 @@
   @Test
   public void testNsetContainsList() throws Exception {
     setRuleContext(createRuleContext("//foo:foo"));
-    checkEvalErrorContains(
-        "depsets cannot contain items of type 'list'", "depset([[ruleContext.files.srcs]])");
+    checkEvalErrorContains("unhashable type: 'list'", "depset([[ruleContext.files.srcs]])");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
index f4abf4d..ea49524 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
@@ -41,26 +41,19 @@
   }
 
   @Test
-  public void testTuplePairs() throws Exception {
+  public void testTuples() throws Exception {
     exec(
-        // Depsets with tuple-pairs
         "s_one = depset([('1', '2'), ('3', '4')])",
         "s_two = depset(direct = [('1', '2'), ('3', '4'), ('5', '6')])",
         "s_three = depset(transitive = [s_one, s_two])",
         "s_four = depset(direct = [('1', '3')], transitive = [s_one, s_two])",
-        // Depsets with tuple-pairs and non-pair tuples are considered just tuple depsets.
         "s_five = depset(direct = [('1', '3', '5')], transitive = [s_one, s_two])",
         "s_six = depset(transitive = [s_one, s_five])",
         "s_seven = depset(direct = [('1', '3')], transitive = [s_one, s_five])",
-        "s_eight = depset(direct = [(1, 3)], transitive = [s_one, s_two])");
-    assertThat(get("s_one").getContentType()).isEqualTo(SkylarkType.STRING_PAIR);
-    assertThat(get("s_two").getContentType()).isEqualTo(SkylarkType.STRING_PAIR);
-    assertThat(get("s_three").getContentType()).isEqualTo(SkylarkType.STRING_PAIR);
-    assertThat(get("s_four").getContentType()).isEqualTo(SkylarkType.STRING_PAIR);
-
-    assertThat(get("s_five").getContentType()).isEqualTo(SkylarkType.TUPLE);
-    assertThat(get("s_six").getContentType()).isEqualTo(SkylarkType.TUPLE);
-    assertThat(get("s_seven").getContentType()).isEqualTo(SkylarkType.TUPLE);
+        "s_eight = depset(direct = [(1, 3)], transitive = [s_one, s_two])"); // note, tuple of int
+    assertThat(get("s_one").getContentType()).isEqualTo(SkylarkType.TUPLE);
+    assertThat(get("s_two").getContentType()).isEqualTo(SkylarkType.TUPLE);
+    assertThat(get("s_three").getContentType()).isEqualTo(SkylarkType.TUPLE);
     assertThat(get("s_eight").getContentType()).isEqualTo(SkylarkType.TUPLE);
 
     assertThat(get("s_four").getSet(Tuple.class))
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkTypeTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkTypeTest.java
index a30bb36..07b5d02 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkTypeTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkTypeTest.java
@@ -72,10 +72,4 @@
     assertThat(inter.includes(combo)).isTrue();
     assertThat(inter.includes(SkylarkType.INT)).isFalse();
   }
-
-  @Test
-  public void testStringPairTuple() {
-    assertThat(SkylarkType.intersection(SkylarkType.STRING_PAIR, SkylarkType.TUPLE))
-        .isEqualTo(SkylarkType.STRING_PAIR);
-  }
 }