Add `TypeChecker.java`, a static type checking visitor
This takes the type annotation information saved in the `Resolver.Binding`s of an AST's `Identifier`s, and validates that the AST uses these types correctly.
The name matches an existing dynamic typechecking file in the `eval/` package, but we can disambiguate that in a future CL. A little stub logic is added to `StarlarkType.java`; in the future we should migrate all the abstract supertype/subtype logic to there.
`Any` is exposed to the user as a valid type annotation identifier.
Work toward #28037.
PiperOrigin-RevId: 846962357
Change-Id: If2abf273c4424814646b82528cd913057e382a85
diff --git a/src/main/java/net/starlark/java/eval/TypeChecker.java b/src/main/java/net/starlark/java/eval/TypeChecker.java
index 9d46311..c3e68e1 100644
--- a/src/main/java/net/starlark/java/eval/TypeChecker.java
+++ b/src/main/java/net/starlark/java/eval/TypeChecker.java
@@ -37,6 +37,7 @@
import net.starlark.java.types.Types.UnionType;
/** Type checker for Starlark types. */
+// TODO: #28043 - Replace or reformulate these using static helpers in StarlarkType.
public final class TypeChecker {
private static boolean isTupleSubtypeOf(TupleType tuple1, TupleType tuple2) {
diff --git a/src/main/java/net/starlark/java/syntax/BUILD b/src/main/java/net/starlark/java/syntax/BUILD
index 214df25..54d84eb 100644
--- a/src/main/java/net/starlark/java/syntax/BUILD
+++ b/src/main/java/net/starlark/java/syntax/BUILD
@@ -64,6 +64,7 @@
"TokenKind.java",
"TypeAliasStatement.java",
"TypeApplication.java",
+ "TypeChecker.java",
"TypeResolver.java",
"UnaryOperatorExpression.java",
"VarStatement.java",
diff --git a/src/main/java/net/starlark/java/syntax/Program.java b/src/main/java/net/starlark/java/syntax/Program.java
index edac73f..183d546 100644
--- a/src/main/java/net/starlark/java/syntax/Program.java
+++ b/src/main/java/net/starlark/java/syntax/Program.java
@@ -112,6 +112,9 @@
}
}
+ // TODO: #28037 - Call the static type checker when --experimental_starlark_type_checking is
+ // enabled. Blocked on having the type checker tolerate all AST nodes.
+
// Extract load statements.
ImmutableList.Builder<String> loads = ImmutableList.builder();
ImmutableList.Builder<Location> loadLocations = ImmutableList.builder();
diff --git a/src/main/java/net/starlark/java/syntax/TypeChecker.java b/src/main/java/net/starlark/java/syntax/TypeChecker.java
new file mode 100644
index 0000000..cfe1a34
--- /dev/null
+++ b/src/main/java/net/starlark/java/syntax/TypeChecker.java
@@ -0,0 +1,173 @@
+// Copyright 2025 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package net.starlark.java.syntax;
+
+import com.google.common.base.Preconditions;
+import com.google.errorprone.annotations.FormatMethod;
+import java.util.List;
+import net.starlark.java.types.StarlarkType;
+import net.starlark.java.types.Types;
+
+/**
+ * A visitor for validating that expressions and statements respect the types of the symbols
+ * appearing within them, as determined by the type resolver.
+ *
+ * <p>Type annotations are not traversed by this visitor.
+ */
+public final class TypeChecker extends NodeVisitor {
+
+ private final List<SyntaxError> errors;
+
+ // Formats and reports an error at the start of the specified node.
+ @FormatMethod
+ private void errorf(Node node, String format, Object... args) {
+ errorf(node.getStartLocation(), format, args);
+ }
+
+ // Formats and reports an error at the specified location.
+ @FormatMethod
+ private void errorf(Location loc, String format, Object... args) {
+ errors.add(new SyntaxError(loc, String.format(format, args)));
+ }
+
+ private TypeChecker(List<SyntaxError> errors) {
+ this.errors = errors;
+ }
+
+ /**
+ * Returns the annotated type of an identifier's symbol, asserting that the binding information is
+ * present.
+ *
+ * <p>If a type is not set on the binding it is taken to be {@code Any}.
+ */
+ // TODO: #27370 - An unannotated variable should either be treated as Any or else inferred from
+ // its first binding occurrence, depending on how the var is introduced and whether it's in typed
+ // code.
+ private StarlarkType getType(Identifier id) {
+ Resolver.Binding binding = id.getBinding();
+ Preconditions.checkNotNull(binding);
+ StarlarkType type = binding.getType();
+ return type != null ? type : Types.ANY;
+ }
+
+ /**
+ * Infers the type of an expression from a bottom-up traversal, relying on type information stored
+ * in identifier bindings by the {@link TypeResolver}.
+ *
+ * <p>May not be called on type expressions (annotations, var statements, type alias statements).
+ */
+ private StarlarkType infer(Expression expr) {
+ switch (expr.kind()) {
+ case IDENTIFIER -> {
+ var id = (Identifier) expr;
+ return switch (id.getName()) {
+ // As a hack, we special-case the names of these universal symbols that should really be
+ // keywords.
+ // TODO: #27728 - Instead of special casing, ensure type information is stored correctly
+ // for the universal/predeclared symbols in the module, and retrieve it from there at type
+ // resolution time. Then here we just need to get it from the binding like anything else.
+ case "True", "False" -> Types.BOOL;
+ case "None" -> Types.NONE;
+ default -> getType(id);
+ };
+ }
+ case STRING_LITERAL -> {
+ return Types.STR;
+ }
+ case INT_LITERAL -> {
+ return Types.INT;
+ }
+ case FLOAT_LITERAL -> {
+ return Types.FLOAT;
+ }
+ default -> {
+ // TODO: #28037 - support binaryop, call, cast, comprehension, conditional, dict_expr, dot,
+ // index, lambda, list, and unaryop expressions.
+ throw new UnsupportedOperationException(
+ String.format("cannot typecheck %s expression", expr.kind()));
+ }
+ }
+ }
+
+ // Expressions should only be visited via infer(), not the visit() dispatch mechanism.
+ // Override visit(Identifier) as a poison pill.
+ @Override
+ public void visit(Identifier id) {
+ throw new AssertionError(
+ String.format(
+ "TypeChecker#visit should not have reached Identifier node '%s'", id.getName()));
+ }
+
+ @Override
+ public void visit(AssignmentStatement assignment) {
+ if (assignment.isAugmented()) {
+ // TODO: #28037 - support this by validating that `lhs <op> rhs` would type check
+ throw new UnsupportedOperationException("cannot typecheck augmented assignment statements");
+ }
+ if (!(assignment.getLHS() instanceof Identifier id)) {
+ // TODO: #28037 - support LHSs containing multiple targets (list expression), field
+ // assignments, and subscript assignments.
+ throw new UnsupportedOperationException(
+ "cannot typecheck assignment statements with anything besides a single identifier on the"
+ + " LHS");
+ }
+ var lhsType = getType(id);
+ // TODO: #27370 - Do bidirectional inference, passing down information about the expected type
+ // from the LHS to the infer() call here, e.g. to construct the type of `[1, 2, 3]` as list[int]
+ // instead of list[object].
+ var rhsType = infer(assignment.getRHS());
+ if (!StarlarkType.assignableFrom(lhsType, rhsType)) {
+ errorf(assignment, "cannot assign type '%s' to '%s'", rhsType, lhsType);
+ }
+ }
+
+ @Override
+ public void visit(ExpressionStatement expr) {
+ // Check constraints in the expression, but ignore the resulting type.
+ // Don't dispatch to it via visit().
+ infer(expr.getExpression());
+ }
+
+ // No need to override visit() for FlowStatement.
+
+ @Override
+ public void visit(LoadStatement load) {
+ // Don't descend into children.
+ }
+
+ @Override
+ public void visit(TypeAliasStatement alias) {
+ // Don't descend into children.
+ }
+
+ @Override
+ public void visit(VarStatement var) {
+ // Don't descend into children.
+ }
+
+ // TODO: #28037 - Support `for`, `def`, `if`, and `return` statements.
+
+ /**
+ * Checks that the given file's AST satisfies the types in the bindings of its identifiers.
+ *
+ * <p>The file must have already been passed through the type resolver without error
+ *
+ * <p>Any type checking errors are appended to the file's errors list.
+ */
+ public static void check(StarlarkFile file) {
+ TypeChecker checker = new TypeChecker(file.errors);
+ checker.visit(file);
+ }
+}
diff --git a/src/main/java/net/starlark/java/syntax/TypeResolver.java b/src/main/java/net/starlark/java/syntax/TypeResolver.java
index 4d26b37..887da2d 100644
--- a/src/main/java/net/starlark/java/syntax/TypeResolver.java
+++ b/src/main/java/net/starlark/java/syntax/TypeResolver.java
@@ -37,7 +37,7 @@
*
* <p>Only a file that has passed the Resolver without errors should be run through this visitor.
*/
-public class TypeResolver extends NodeVisitor {
+public final class TypeResolver extends NodeVisitor {
// TODO: #27728 - Will be used when we support non-universal type symbols.
private final Module module;
diff --git a/src/main/java/net/starlark/java/types/StarlarkType.java b/src/main/java/net/starlark/java/types/StarlarkType.java
index bae9e3c..747bfe2 100644
--- a/src/main/java/net/starlark/java/types/StarlarkType.java
+++ b/src/main/java/net/starlark/java/types/StarlarkType.java
@@ -36,4 +36,29 @@
public List<StarlarkType> getSupertypes() {
return ImmutableList.of();
}
+
+ /**
+ * Returns whether a value of type {@code t2} can be assigned to a value of type {@code t1}.
+ *
+ * <p>In gradual typing terms, {@code t2} must be a "consistent subtype of" {@code t1}. This means
+ * that there is a way to substitute zero or more occurrences of {@code Any} in both terms, such
+ * that {@code t2} becomes a subtype of {@code t1} in the ordinary sense.
+ *
+ * <p>The Python glossary uses the term "assignable [to/from]" for this relation, and
+ * "materialization" to refer to the process of substituting {@code Any}.
+ */
+ // TODO: #28043 - Add support for:
+ // - subtyping (list[int] <= Sequence[int])
+ // - covariance (Sequence[int] <= Sequence[object])
+ // - proper treatment of materializing Any (Sequence[int] <= Sequence[Any])
+ // - transitive application of all of the above, including across unions
+ public static boolean assignableFrom(StarlarkType t1, StarlarkType t2) {
+ if (t1.equals(Types.ANY) || t2.equals(Types.ANY)) {
+ return true;
+ }
+ if (t1.equals(t2)) {
+ return true;
+ }
+ return false;
+ }
}
diff --git a/src/main/java/net/starlark/java/types/Types.java b/src/main/java/net/starlark/java/types/Types.java
index c9dfcc4..2e6014a 100644
--- a/src/main/java/net/starlark/java/types/Types.java
+++ b/src/main/java/net/starlark/java/types/Types.java
@@ -61,6 +61,7 @@
private static ImmutableMap<String, Object> makeTypeUniverse() {
ImmutableMap.Builder<String, Object> env = ImmutableMap.builder();
env //
+ .put("Any", ANY)
.put("None", NONE)
.put("bool", BOOL)
.put("int", INT)
diff --git a/src/test/java/net/starlark/java/syntax/BUILD b/src/test/java/net/starlark/java/syntax/BUILD
index c4ccaa9..6d58f53 100644
--- a/src/test/java/net/starlark/java/syntax/BUILD
+++ b/src/test/java/net/starlark/java/syntax/BUILD
@@ -29,6 +29,7 @@
"ResolverTest.java",
"StarlarkFileTest.java",
"SyntaxTests.java", # (suite)
+ "TypeCheckerTest.java",
"TypeResolverTest.java",
"TypesTest.java",
],
diff --git a/src/test/java/net/starlark/java/syntax/SyntaxTests.java b/src/test/java/net/starlark/java/syntax/SyntaxTests.java
index d51d476..48ffe06 100644
--- a/src/test/java/net/starlark/java/syntax/SyntaxTests.java
+++ b/src/test/java/net/starlark/java/syntax/SyntaxTests.java
@@ -30,6 +30,7 @@
ProgramTest.class,
ResolverTest.class,
StarlarkFileTest.class,
+ TypeCheckerTest.class,
TypeResolverTest.class,
TypesTest.class,
})
diff --git a/src/test/java/net/starlark/java/syntax/TypeCheckerTest.java b/src/test/java/net/starlark/java/syntax/TypeCheckerTest.java
new file mode 100644
index 0000000..e285285
--- /dev/null
+++ b/src/test/java/net/starlark/java/syntax/TypeCheckerTest.java
@@ -0,0 +1,176 @@
+// Copyright 2025 The Bazel Authors. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package net.starlark.java.syntax;
+
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.common.truth.Truth.assertWithMessage;
+import static net.starlark.java.syntax.LexerTest.assertContainsError;
+
+import com.google.common.base.Joiner;
+import net.starlark.java.syntax.Resolver.Module;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+@RunWith(JUnit4.class)
+public final class TypeCheckerTest {
+
+ private final FileOptions.Builder options =
+ FileOptions.builder()
+ .allowTypeSyntax(true)
+ // This lets us construct simpler test cases without wrapper `def` statements.
+ .allowToplevelRebinding(true);
+
+ /**
+ * Throws {@link AssertionError} if a file has errors, with an exception message that includes
+ * {@code what} and the errors.
+ */
+ private void assertNoErrors(String what, StarlarkFile file) {
+ if (!file.ok()) {
+ throw new AssertionError(
+ String.format("Unexpected errors: %s:\n%s", what, Joiner.on("\n").join(file.errors())));
+ }
+ }
+
+ /**
+ * Parses, resolve, and type-resolves a file, then statically typechecks it.
+ *
+ * <p>Asserts that steps before typechecking succeeded, but the typechecking itself may fail. The
+ * resulting errors are available in the returned {@code StarlarkFile}.
+ */
+ private StarlarkFile typecheckFilePossiblyFailing(String... lines) throws Exception {
+ ParserInput input = ParserInput.fromLines(lines);
+ StarlarkFile file = StarlarkFile.parse(input, options.build());
+ assertNoErrors("parsing", file);
+ Module module = Resolver.moduleWithPredeclared();
+ Resolver.resolveFile(file, module);
+ assertNoErrors("resolving", file);
+ TypeResolver.annotateFile(file, module);
+ assertNoErrors("type-resolving", file);
+
+ TypeChecker.check(file);
+ return file;
+ }
+
+ /** As in {@link #typecheckFilePossiblyFailing} but asserts that even type checking succeeded. */
+ private StarlarkFile assertValid(String... lines) throws Exception {
+ StarlarkFile file = typecheckFilePossiblyFailing(lines);
+ assertThat(file.ok()).isTrue();
+ return file;
+ }
+
+ /** Asserts that type checking fails with at least the specified error. */
+ private void assertInvalid(String expectedError, String... lines) throws Exception {
+ StarlarkFile file = typecheckFilePossiblyFailing(lines);
+ assertWithMessage("type checking suceeded unexpectedly").that(file.ok()).isFalse();
+ assertContainsError(file.errors(), expectedError);
+ }
+
+ @Test
+ public void assignment_simple() throws Exception {
+ assertValid(
+ """
+ x: int
+ x = 123
+ """);
+
+ assertInvalid(
+ ":2:1: cannot assign type 'str' to 'int'",
+ """
+ x: int
+ x = "abc"
+ """);
+ }
+
+ @Test
+ public void canLookupIdentifierTypeOnRhs() throws Exception {
+ assertInvalid(
+ ":3:1: cannot assign type 'bool' to 'int'",
+ """
+ x: int
+ y: bool
+ x = y
+ """);
+ }
+
+ @Test
+ public void primitiveTypesAreInferredFromLiteralsAndAreIncompatible() throws Exception {
+ assertInvalid(
+ ":1:1: cannot assign type 'str' to 'bool'",
+ """
+ x: bool = 'abc'
+ """);
+ assertInvalid(
+ ":1:1: cannot assign type 'int' to 'float'",
+ """
+ x: float = 123
+ """);
+ assertInvalid(
+ ":1:1: cannot assign type 'float' to 'None'",
+ """
+ x: None = 1.0
+ """);
+ }
+
+ // TODO: #27728 - We should add a test that the types of universals, and in particular the
+ // keyword-like symbols `None`, `True`, and `False`, are appropriately inferred to have types
+ // None, bool, and bool respectively. This test would have to live in the eval package, since the
+ // universal environment is not available to the syntax/ package.
+
+ @Test
+ public void anyIsCompatibleInEitherDirection() throws Exception {
+ assertValid(
+ """
+ x: int
+ y: Any
+ x = y
+ """);
+ assertValid(
+ """
+ x: Any
+ y: int
+ x = y
+ """);
+ assertValid(
+ """
+ x: Any
+ y: Any
+ x = y
+ """);
+ }
+
+ // TODO: #27370 - The real behavior we want is that an unannotated variable has an inferred type
+ // if it is a non-parameter local variable in typed code, and Any type otherwise.
+ @Test
+ public void unannotatedVarIsAnyType() throws Exception {
+ assertValid(
+ """
+ x: int
+ y = "ignored"
+ x = y
+ """);
+ }
+
+ @Test
+ public void canTolerateIrrelevantStatementTypes() throws Exception {
+ assertValid(
+ """
+ load("...", "B")
+ type A = B
+ B # expression statement
+ """);
+ // TODO: #28037 - Check break/continue, once we support for and def statements
+ }
+}
