Type checker: Add list/dict literal support
This also adds a `Never` bottom type to the hierarchy, and allows unions to be empty (at least internally). The type of an empty list is list[Never], and likewise for dictionaries. (Mypy requires user disambiguation in these types of cases; we may change to that in the future.) `Never` is not made available to user annotations in this CL.
Work toward #28037.
PiperOrigin-RevId: 853386929
Change-Id: Ic5ded1bff44af88c3adb9295b81bf10d4b579d58
diff --git a/src/main/java/net/starlark/java/syntax/TypeChecker.java b/src/main/java/net/starlark/java/syntax/TypeChecker.java
index 2b5ce08..309e5dd 100644
--- a/src/main/java/net/starlark/java/syntax/TypeChecker.java
+++ b/src/main/java/net/starlark/java/syntax/TypeChecker.java
@@ -123,9 +123,27 @@
case INDEX -> {
return inferIndex((IndexExpression) expr);
}
+ case LIST_EXPR -> {
+ var list = (ListExpression) expr;
+ List<StarlarkType> elementTypes = new ArrayList<>();
+ for (Expression element : list.getElements()) {
+ elementTypes.add(infer(element));
+ }
+ return Types.list(Types.union(elementTypes));
+ }
+ case DICT_EXPR -> {
+ var dict = (DictExpression) expr;
+ List<StarlarkType> keyTypes = new ArrayList<>();
+ List<StarlarkType> valueTypes = new ArrayList<>();
+ for (var entry : dict.getEntries()) {
+ keyTypes.add(infer(entry.getKey()));
+ valueTypes.add(infer(entry.getValue()));
+ }
+ return Types.dict(Types.union(keyTypes), Types.union(valueTypes));
+ }
default -> {
- // TODO: #28037 - support binaryop, call, cast, comprehension, conditional, dict_expr,
- // lambda, list, slice, and unaryop expressions.
+ // TODO: #28037 - support binaryop, call, cast, comprehension, conditional,
+ // lambda, slice, and unaryop expressions.
throw new UnsupportedOperationException(
String.format("cannot typecheck %s expression", expr.kind()));
}
diff --git a/src/main/java/net/starlark/java/types/Types.java b/src/main/java/net/starlark/java/types/Types.java
index 09972f6..413385e 100644
--- a/src/main/java/net/starlark/java/types/Types.java
+++ b/src/main/java/net/starlark/java/types/Types.java
@@ -48,6 +48,9 @@
/** The top type of the type hierarchy. */
public static final StarlarkType OBJECT = new ObjectType();
+ /** The bottom type of the type hierarchy. */
+ public static final StarlarkType NEVER = new NeverType();
+
// Primitive types
public static final StarlarkType NONE = new None();
@@ -120,6 +123,23 @@
}
}
+ private static final class NeverType extends StarlarkType {
+ @Override
+ public String toString() {
+ return "Never";
+ }
+
+ @Override
+ public int hashCode() {
+ return NeverType.class.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ return obj instanceof NeverType;
+ }
+ }
+
private static final class None extends StarlarkType {
@Override
public String toString() {
@@ -389,7 +409,7 @@
if (subtypes.size() == 1) {
return subtypes.iterator().next();
} else if (subtypes.isEmpty()) {
- throw new IllegalArgumentException("Empty union!");
+ return Types.NEVER;
}
return new AutoValue_Types_UnionType(subtypes);
}
diff --git a/src/test/java/net/starlark/java/syntax/TypeCheckerTest.java b/src/test/java/net/starlark/java/syntax/TypeCheckerTest.java
index 7eb685e6..f76c542 100644
--- a/src/test/java/net/starlark/java/syntax/TypeCheckerTest.java
+++ b/src/test/java/net/starlark/java/syntax/TypeCheckerTest.java
@@ -446,4 +446,30 @@
t[1] = 123
""");
}
+
+ @Test
+ public void infer_dict() throws Exception {
+ // Empty case.
+ assertTypeGivenDecls("{}", Types.dict(Types.NEVER, Types.NEVER));
+
+ // Homogeneous case.
+ assertTypeGivenDecls("{'a': 1, 'b': 2}", Types.dict(Types.STR, Types.INT));
+
+ // Heterogeneous case.
+ StarlarkType unionType = Types.union(Types.STR, Types.INT);
+ assertTypeGivenDecls("{'a': 'abc', 1: 123}", Types.dict(unionType, unionType));
+ }
+
+ @Test
+ public void infer_list() throws Exception {
+ // Empty case.
+ assertTypeGivenDecls("[]", Types.list(Types.NEVER));
+
+ // Homogeneous case.
+ assertTypeGivenDecls("[1, 2, 3]", Types.list(Types.INT));
+
+ // Heterogeneous case.
+ StarlarkType unionType = Types.union(Types.INT, Types.STR);
+ assertTypeGivenDecls("[1, 'a']", Types.list(unionType));
+ }
}
