Avoid computing and retaining CallableTypes for untyped functions. `TypeTagger` previously constructed a `GeneralCallableType` (which meant constructing temporaries for parameter type lists and mandatoriness sets) for all `def` statements and `lambda` expressions. However, that was a waste and caused GC pressure. We need to read function types only on the following occasions: * During static type checking (`TypeChecker`), for each use of a binding in typed code. We want this to be efficient. * At eval time during dynamic type checking (experimental and disabled by default). We don't particularly care about making it efficient. * After eval, when assigning a type to exported symbols. Here, each function would typically be processed only once (unless exported in multiple struct fields, which would be unusual), so we can tolerate a small CPU overhead per function. We therefore introduce `Types.allAnyFunction()` to conveniently construct types of an functions with unannotated signatures from their rfn. We store the rfn of functions with unannotated signatures in the `TypeTable` to indicate that the symbol has been tagged, but that its type can be computed later on demand. And to avoid having the `TypeChecker` compute this type repeatedly (if an unannotated function is used in typed code), we introduce the new `TypeTable.getAndCacheType()` to cache the type. Also take the opportunity to make `TypeTable`s arrays a bit more lazy and compact. Working towards #27370 PiperOrigin-RevId: 1025872480 Change-Id: I4af6488c6f46dc64d3ca9dd89be08dbeb22f2f9c
diff --git a/src/main/java/net/starlark/java/eval/Eval.java b/src/main/java/net/starlark/java/eval/Eval.java index 1b8b7b3..0395f8e 100644 --- a/src/main/java/net/starlark/java/eval/Eval.java +++ b/src/main/java/net/starlark/java/eval/Eval.java
@@ -241,7 +241,9 @@ rfn.getParameters().size() - (rfn.hasKwargs() ? 1 : 0) - (rfn.hasVarargs() ? 1 : 0); StarlarkFunction fn = fn(fr); - @Nullable CallableType functionType = fn.getChildFunctionType(rfn); + // Used only for dynamic type checking of parameter default values; if there are no type + // annotations on the function's signature, there's nothing to type check. + @Nullable CallableType annotatedFunctionType = fn.getAnnotatedChildFunctionType(rfn); boolean dynamicTypeCheckingEnabled = fr.thread .getSemantics() @@ -257,9 +259,9 @@ Object defaultValue = expr == null ? StarlarkFunction.MANDATORY : eval(fr, expr); defaults[i - (nparams - defaults.length)] = defaultValue; - if (dynamicTypeCheckingEnabled && functionType != null) { + if (dynamicTypeCheckingEnabled && annotatedFunctionType != null) { // Typecheck the default value - StarlarkType parameterType = functionType.getParameterType(i); + StarlarkType parameterType = annotatedFunctionType.getParameterType(i); if (!TypeChecker.isValueSubtypeOf( defaultValue, parameterType, fr.thread.getSemantics(), fr.thread.getTypeContext())) { throw Starlark.errorf(
diff --git a/src/main/java/net/starlark/java/eval/StarlarkFunction.java b/src/main/java/net/starlark/java/eval/StarlarkFunction.java index 86618af..c1956a2 100644 --- a/src/main/java/net/starlark/java/eval/StarlarkFunction.java +++ b/src/main/java/net/starlark/java/eval/StarlarkFunction.java
@@ -41,13 +41,13 @@ public sealed class StarlarkFunction implements StarlarkCallable { final Resolver.Function rfn; - // Types of functions in this module, indexed by their Resolver.Function#getFunctionId(), - // excluding <toplevel>/<expr>. Null if type tagging was not enabled. Note that functions need to - // know both their own type (see getStarlarkType) and the types of their inner functions created - // during evaluation (see getChildFunctionType). We could save a little bit of memory by turning - // this into an `Object typeData` which holds only the function's own type if there are no inner - // functions, and the full functionTypes array otherwise; but the complexity seems not worth it. - @Nullable private final Types.CallableType[] functionTypes; + // Types of functions with annotated signatures in this module (and therefore always excluding + // <toplevel> or <expr>), indexed by their Resolver.Function#getFunctionId(). The size of the + // array may be smaller than the number of functions in the file. Any function whose ID is not + // represented in the array, or whose entry is null, should be considered to have all parameters + // and return type as Any (see Types#allAnyFunction). The array itself is null if type tagging was + // not enabled; and empty if no function in the module has a signature with type annotations. + @Nullable private final Types.CallableType[] annotatedFunctionTypes; private final Module module; // a function closes over its defining module // Index in Module.globals of ith Program global (Resolver.Binding(GLOBAL).index). @@ -79,7 +79,7 @@ checkState(!rfn.isToplevel()); return new StarlarkFunction( rfn, - outerFn.functionTypes, + outerFn.annotatedFunctionTypes, outerFn.module, outerFn.globalIndex, defaultValues, @@ -100,14 +100,14 @@ private StarlarkFunction( Resolver.Function rfn, - @Nullable Types.CallableType[] functionTypes, + @Nullable Types.CallableType[] annotatedFunctionTypes, Module module, int[] globalIndex, Tuple defaultValues, Tuple freevars, SymbolGenerator.Symbol<?> token) { this.rfn = rfn; - this.functionTypes = functionTypes; + this.annotatedFunctionTypes = annotatedFunctionTypes; this.module = module; this.globalIndex = globalIndex; this.defaultValues = defaultValues; @@ -141,11 +141,19 @@ @Override public StarlarkType getStarlarkType(StarlarkSemantics semantics) { - @Nullable StarlarkType functionType = null; - if (functionTypes != null) { - functionType = functionTypes[rfn.getFunctionId()]; + if (annotatedFunctionTypes == null) { + return Types.ANY; } - return functionType != null ? functionType : Types.ANY; + Types.CallableType annotated = getAnnotatedFunctionType(); + return annotated != null ? annotated : Types.allAnyFunction(rfn); + } + + @Nullable + private Types.CallableType getAnnotatedFunctionType() { + int id = rfn.getFunctionId(); + return annotatedFunctionTypes != null && id < annotatedFunctionTypes.length + ? annotatedFunctionTypes[id] + : null; } /** @@ -161,14 +169,21 @@ @Nullable @VisibleForTesting - Types.CallableType[] getFunctionTypes() { - return functionTypes; + Types.CallableType[] getAnnotatedFunctionTypes() { + return annotatedFunctionTypes; } - /** Returns the Starlark type of an inner function instantiated by this function's evaluation. */ + /** + * Returns the Starlark type of an inner function having an annotated signature and instantiated + * by this function's evaluation, or null if type tagging was disabled or the inner function's + * signature doesn't have type annotations. + */ @Nullable - Types.CallableType getChildFunctionType(Resolver.Function childRfn) { - return functionTypes != null ? functionTypes[childRfn.getFunctionId()] : null; + Types.CallableType getAnnotatedChildFunctionType(Resolver.Function childRfn) { + int id = childRfn.getFunctionId(); + return annotatedFunctionTypes != null && id < annotatedFunctionTypes.length + ? annotatedFunctionTypes[id] + : null; } // TODO(adonovan): many functions would be simpler if @@ -614,13 +629,10 @@ thread .getSemantics() .getBool(StarlarkSemantics.EXPERIMENTAL_STARLARK_DYNAMIC_TYPE_CHECKING); - Types.CallableType functionType = null; - if (dynamicTyping - && owner.getStarlarkType(thread.getSemantics()) instanceof Types.CallableType ct) { - functionType = ct; - } - // Argument value dynamic type check, if enabled. + // Used only for dynamic type checking of argument values; if null, there's nothing to type + // check. + Types.CallableType functionType = dynamicTyping ? owner.getAnnotatedFunctionType() : null; if (functionType != null) { for (int i = 0; i < functionType.getNumNonResidualParameters(); i++) { if (locals[i] == null) { @@ -686,7 +698,7 @@ checkArgument(rfn.isToplevel()); super( rfn, - typeTable == null ? null : typeTable.getNonToplevelFunctionTypes(), + typeTable == null ? null : typeTable.getAnnotatedFunctionTypes(), module, globalIndex, /* defaultValues= */ Tuple.empty(), @@ -698,7 +710,10 @@ @Override public StarlarkType getStarlarkType(StarlarkSemantics semantics) { if (typeTable != null) { - return typeTable.getType(rfn); + Types.CallableType type = typeTable.getType(rfn); + if (type != null) { + return type; + } } return Types.ANY; }
diff --git a/src/main/java/net/starlark/java/syntax/DefStatement.java b/src/main/java/net/starlark/java/syntax/DefStatement.java index 99bad3c..9217d35 100644 --- a/src/main/java/net/starlark/java/syntax/DefStatement.java +++ b/src/main/java/net/starlark/java/syntax/DefStatement.java
@@ -77,6 +77,21 @@ return returnType; } + public boolean signatureHasTypeAnnotations() { + if (returnType != null) { + return true; + } + if (!typeParameters.isEmpty()) { + return true; + } + for (Parameter parameter : parameters) { + if (parameter.getType() != null) { + return true; + } + } + return false; + } + void setResolvedFunction(Resolver.Function resolved) { this.resolved = resolved; }
diff --git a/src/main/java/net/starlark/java/syntax/TypeChecker.java b/src/main/java/net/starlark/java/syntax/TypeChecker.java index 5d23487..4f7de58 100644 --- a/src/main/java/net/starlark/java/syntax/TypeChecker.java +++ b/src/main/java/net/starlark/java/syntax/TypeChecker.java
@@ -131,7 +131,7 @@ switch (binding.getScope()) { case UNIVERSAL -> checkNotNull(module.getUniversalSymbolType(binding.getName())); case PREDECLARED -> checkNotNull(module.getPredeclaredSymbolType(binding.getName())); - default -> typeTable.getType(binding); + default -> typeTable.getAndCacheType(binding); }; return type != null ? type : Types.ANY; } @@ -173,12 +173,14 @@ typeTable.getType(lambda.getResolvedFunction()), "type tagger should have set type for lambda expr '%s'", lambda); - if (!originalType.getReturnType().equals(inferedReturnType)) { + if (originalType.getReturnType().equals(inferedReturnType)) { + yield originalType; + } else { // Update the lambda function type with a more precise return type. - typeTable.setType( - lambda.getResolvedFunction(), originalType.withReturnType(inferedReturnType)); + Types.GeneralCallableType updatedType = originalType.withReturnType(inferedReturnType); + typeTable.setAnnotatedType(lambda.getResolvedFunction(), updatedType); + yield updatedType; } - yield typeTable.getType(lambda.getResolvedFunction()); } case ListExpression list -> { List<StarlarkType> elementTypes = new ArrayList<>(); @@ -1087,7 +1089,7 @@ } } - if (lhs instanceof Identifier id && typeTable.getType(id.getBinding()) == null) { + if (lhs instanceof Identifier id && typeTable.getAndCacheType(id.getBinding()) == null) { // If a variable has not been typed, infer its type from the rhs of the first assignment. typeTable.setInferredType(id.getBinding(), rhsType.toLvalue()); } @@ -1387,15 +1389,13 @@ checkState(!functionStack.isEmpty()); FunctionStackEntry functionStackEntry = functionStack.peek(); Resolver.Function function = functionStackEntry.function(); - // May be null if function is the toplevel - @Nullable Types.CallableType callableType = typeTable.getType(function); - if (callableType != null - && !StarlarkType.assignableFrom(callableType.getReturnType(), returnType, typeContext)) { + StarlarkType expectedReturnType = typeTable.getReturnType(function); + if (!StarlarkType.assignableFrom(expectedReturnType, returnType, typeContext)) { errorf( ret.getResult().getStartLocation(), "%s() declares return type '%s' but may return '%s'", function.getName(), - callableType.getReturnType().typeRepr(), + expectedReturnType.typeRepr(), returnType.typeRepr()); } functionStackEntry.returns().add(ret);
diff --git a/src/main/java/net/starlark/java/syntax/TypeTable.java b/src/main/java/net/starlark/java/syntax/TypeTable.java index 27917e3..8fc9d09 100644 --- a/src/main/java/net/starlark/java/syntax/TypeTable.java +++ b/src/main/java/net/starlark/java/syntax/TypeTable.java
@@ -15,6 +15,7 @@ package net.starlark.java.syntax; import static com.google.common.base.Preconditions.checkArgument; +import static com.google.common.base.Preconditions.checkState; import static com.google.common.collect.ImmutableList.toImmutableList; import com.google.common.collect.ImmutableList; @@ -29,6 +30,19 @@ /** * The static type information for a Starlark file. * + * <p>This information comes from the following sources: + * + * <ul> + * <li>Declared types: from type annotations in var and assignment statements (for ordinary + * variables); from function parameter annotations (for parameter variables); and from the + * function signature (possibly annotated) in a def statement (for functions). + * <li>Inferred types: computed by the static type checker. Never supersedes a declared type. + * <li>Loaded exported types: types of symbols that this module {@code load()}s from other + * modules. This is the symbol's declared type in its exporting module; or if there's no + * declared type, it's the *dynamic* type of the symbol after the exporting module's + * evaluation. + * </ul> + * * <p>At first glance, one may think this information ought to be directly embedded in a {@link * Program}'s AST nodes. But storing it separately has some benefits: for one thing, we can do a * second static typechecking pass post-evaluation without having evaluation mutate the AST. And it @@ -38,16 +52,39 @@ * <p>Initialized by {@link TypeTagger} and further refined by {@link TypeChecker}. */ public final class TypeTable { - // Declared types of global bindings. Indexed by the binding's global scope index. - private final StarlarkType[] globalsDeclaredTypes; - // Types of bindings (regardless of scope). Indexed by binding's sequence number. Contains nulls - // for bindings without static type information. - private final StarlarkType[] bindingTypes; + // Empty array singleton for use by getAnnotatedFunctionTypes(). + private static final Types.CallableType[] EMPTY_CALLABLE_ARRAY = new Types.CallableType[0]; + // Number of globals in the program; determined by the resolver. + private final int numGlobals; + // Total number of functions in the program (including toplevel, nested functions, and lambdas); + // determined by the resolver. Equals the max function sequence number + 1. + private final int numFunctions; + + // Declared types of global bindings. Indexed by the binding's global scope index. Elements may be + // * StarlarkType - for non-function symbols having a declared type, and for functions whose + // signature has type annotations; + // * Resolver.Function - for functions with unannotated signatures; + // * null - for non-function symbols without a declared type. + // Lazily initialized by setDeclaredType() / setDeclaredTypeInternal(). + // (Note: unlike for bindingTypes below, here we don't update Resolver.Function values from a + // getter because getters on the globalsDeclaredTypes operate after type checking has finished and + // the type table is frozen.) + @Nullable private Object[] globalsDeclaredTypes; + // Types of bindings (regardless of scope). Indexed by binding's sequence number. Elements may be + // * StarlarkType - for non-function symbols having a declared or inferred type, and for functions + // whose signature has type annotations. + // * Resolver.Function - for functions with unannotated signatures; getAndCacheType() may update + // the latter to the former to cache the Type.untypedFunction() + // * null - for non-function variables without static type information. + private final Object[] bindingTypes; // Type constructor values of bindings, indexed by the binding's sequence number. Sparse because // most bindings are not type constructors; lazily initialized by setTypeConstructor(). @Nullable private LinkedHashMap<Integer, TypeConstructor> typeConstructors; - // Types of functions. Indexed by function's sequence number. - private final Types.GeneralCallableType[] functionTypes; + // Types of functions whose signatures have type annotations. Indexed by function's sequence + // number. Lazily initialized by setAnnotatedFunctionType(). Contains nulls for functions with + // unannotated signatures. Contains a subset of information in bindingTypes, but is helpful for + // retrieval keyed by function. Needed only for StarlarkFunction#getStarlarkType(). + @Nullable private Types.GeneralCallableType[] annotatedFunctionTypes; // Whether a function uses type syntax. Indexed by function's sequence number. private final boolean[] functionsUsingTypeSyntax; @@ -73,9 +110,9 @@ } private TypeTable(int numGlobals, int numBindings, int numFunctions) { - this.globalsDeclaredTypes = new StarlarkType[numGlobals]; - this.bindingTypes = new StarlarkType[numBindings]; - this.functionTypes = new Types.GeneralCallableType[numFunctions]; + this.numGlobals = numGlobals; + this.numFunctions = numFunctions; + this.bindingTypes = new Object[numBindings]; this.functionsUsingTypeSyntax = new boolean[numFunctions]; } @@ -131,15 +168,57 @@ return false; } - /** - * Sets the declared (annotated) type of the given binding. May be called more than once. Null is - * treated is untyped / Any. - */ + /** Sets the declared (annotated) type of the given binding. May be called more than once. */ void setDeclaredType(Resolver.Binding binding, StarlarkType type) { - bindingTypes[binding.getBindingId()] = type; - if (binding.getScope().equals(Resolver.Scope.GLOBAL)) { - globalsDeclaredTypes[binding.getIndex()] = type; + setDeclaredTypeInternal(binding, type); + } + + /** + * Sets the declared type of the given binding to be the callable type (which will be computed on + * demand) of the given function with an unannotated signature. + */ + void setUnannotatedFunctionType(Resolver.Binding binding, Resolver.Function rfn) { + setDeclaredTypeInternal(binding, rfn); + } + + /** + * Sets the declared type of the given binding and its corresponding function whose signature has + * type annotations. + */ + void setAnnotatedFunctionType( + Resolver.Binding binding, Resolver.Function rfn, Types.GeneralCallableType type) { + setDeclaredTypeInternal(binding, type); + if (annotatedFunctionTypes == null && type != null) { + annotatedFunctionTypes = new Types.GeneralCallableType[numFunctions]; } + annotatedFunctionTypes[rfn.getFunctionId()] = type; + } + + /** Clears the declared type of the given binding. */ + void clearDeclaredType(Resolver.Binding binding) { + setDeclaredTypeInternal(binding, null); + } + + /** + * Sets the declared type of the given binding to a {@link StarlarkType} or a {@link + * Resolver.Function} (for callable types of functions with unannotated signatures), or clears the + * declared type (if given null). + */ + private void setDeclaredTypeInternal(Resolver.Binding binding, @Nullable Object typeOrRfn) { + bindingTypes[binding.getBindingId()] = typeOrRfn; + if (binding.getScope().equals(Resolver.Scope.GLOBAL)) { + boolean wantUpdateGlobal = typeOrRfn != null || globalsDeclaredTypes != null; + if (wantUpdateGlobal) { + if (globalsDeclaredTypes == null) { + globalsDeclaredTypes = new Object[numGlobals]; + } + globalsDeclaredTypes[binding.getIndex()] = typeOrRfn; + } + } + } + + boolean hasBindingType(Resolver.Binding binding) { + return bindingTypes[binding.getBindingId()] != null; } /** @@ -151,11 +230,14 @@ } /** - * Sets the type of the given function. May be called more than once. Null is treated is untyped / - * Any. + * Records the type of a function whose signature has type annotations. Doesn't update the binding + * type; the caller must do so by calling {@link #setDeclaredType}. */ - void setType(Resolver.Function function, Types.GeneralCallableType type) { - functionTypes[function.getFunctionId()] = type; + void setAnnotatedType(Resolver.Function function, Types.GeneralCallableType type) { + if (annotatedFunctionTypes == null && type != null) { + annotatedFunctionTypes = new Types.GeneralCallableType[numFunctions]; + } + annotatedFunctionTypes[function.getFunctionId()] = type; } /** @@ -189,19 +271,45 @@ return typeConstructors == null ? null : typeConstructors.get(binding.getBindingId()); } - /** Returns the declared type of the global binding. Null indicates untyped / Any. */ + /** + * Returns the declared type of the global binding, or null if the global binding doesn't have a + * declared type. + * + * <p>Used in the evaluation phase to set the declared type as the exported type in eval.Module. + */ + // TODO: #27370 - Instead of having Eval#assignIdentifier read the declared type and set it on the + // module via the <toplevel> function, pass the list of declared types to eval.Module directly. @Nullable public StarlarkType getGlobalDeclaredType(Resolver.Binding binding) { checkArgument(binding.getScope().equals(Resolver.Scope.GLOBAL)); - return globalsDeclaredTypes[binding.getIndex()]; + if (globalsDeclaredTypes == null) { + return null; + } + int index = binding.getIndex(); + return switch (globalsDeclaredTypes[index]) { + case null -> null; + case StarlarkType type -> type; + case Resolver.Function rfn -> getType(rfn); + default -> + throw new IllegalStateException( + "Unexpected declared type entry: " + globalsDeclaredTypes[index]); + }; } /** - * Returns the type of the binding (whether declared or inferred). Null indicates untyped / Any. + * Returns the type of the binding (whether declared or inferred). Null indicates no static type + * information (during type checking, null means no static type information *yet*). */ @Nullable public StarlarkType getType(Resolver.Binding binding) { - return bindingTypes[binding.getBindingId()]; + int id = binding.getBindingId(); + return switch (bindingTypes[id]) { + case null -> null; + case StarlarkType type -> type; + case Resolver.Function rfn -> getType(rfn); + default -> + throw new IllegalStateException("Unexpected binding type entry: " + bindingTypes[id]); + }; } /** @@ -210,7 +318,57 @@ */ @Nullable public Types.GeneralCallableType getType(Resolver.Function function) { - return functionTypes[function.getFunctionId()]; + if (function.isToplevel()) { + return null; + } + Types.GeneralCallableType annotated = getAnnotatedFunctionType(function); + return annotated != null ? annotated : Types.allAnyFunction(function); + } + + /** Returns the return type of a function. */ + public StarlarkType getReturnType(Resolver.Function function) { + if (function.isToplevel()) { + return Types.ANY; + } + Types.GeneralCallableType annotated = getAnnotatedFunctionType(function); + return annotated != null ? annotated.getReturnType() : Types.ANY; + } + + /** + * Like {@link #getType(Resolver.Binding)}, but caches the type (and therefore, mutates this + * {@link TypeTable}) if it was computed on demand and not yet cached. + * + * <p>Intended to be used by {@link TypeChecker}. Do not call this method after the type table has + * been stored in skyframe. + */ + @Nullable + StarlarkType getAndCacheType(Resolver.Binding binding) { + int id = binding.getBindingId(); + return switch (bindingTypes[id]) { + case null -> null; + case StarlarkType type -> type; + case Resolver.Function rfn -> { + checkState(getAnnotatedFunctionType(rfn) == null); + StarlarkType type = getType(rfn); + if (type != null) { + // Cache the type to avoid recomputing Types.allAnyFunction() + bindingTypes[id] = type; + } + yield type; + } + default -> + throw new IllegalStateException("Unexpected binding type entry: " + bindingTypes[id]); + }; + } + + /** + * Returns the type of a resolved function whose signature has type annotations, or null if the + * signature has no type annotations (or, during type tagging, if the function's type was not set + * yet). + */ + @Nullable + Types.GeneralCallableType getAnnotatedFunctionType(Resolver.Function function) { + return annotatedFunctionTypes == null ? null : annotatedFunctionTypes[function.getFunctionId()]; } /** @@ -249,19 +407,22 @@ } /** - * Returns a newly-allocated array of function types (excluding the <toplevel> function) indexed - * by their {@link Resolver.Function#getFunctionId}. + * Returns an array of function types indexed by their {@link Resolver.Function#getFunctionId}. + * The size of the array may be smaller than the number of functions in the file; any function + * whose ID is not represented in the array, or whose entry in the array is null, should be + * considered to have an unannotated signature (see {@link Types#allAnyFunction}). * * <p>Can only be called after type tagging has finished. */ - public Types.CallableType[] getNonToplevelFunctionTypes() { - if (functionTypes.length == 0) { - return new Types.CallableType[0]; + public Types.CallableType[] getAnnotatedFunctionTypes() { + if (annotatedFunctionTypes == null || annotatedFunctionTypes.length == 0) { + return EMPTY_CALLABLE_ARRAY; } return Arrays.copyOfRange( - functionTypes, + annotatedFunctionTypes, 0, - functionTypes.length - 1, + // Always exclude <toplevel> at index length - 1; it cannot possibly be annotated. + annotatedFunctionTypes.length - 1, // Types.GeneralCallableType is package-private Types.CallableType[].class); }
diff --git a/src/main/java/net/starlark/java/syntax/TypeTagger.java b/src/main/java/net/starlark/java/syntax/TypeTagger.java index 926d9a7..afc7733 100644 --- a/src/main/java/net/starlark/java/syntax/TypeTagger.java +++ b/src/main/java/net/starlark/java/syntax/TypeTagger.java
@@ -23,7 +23,6 @@ import com.google.common.collect.ImmutableMap; import com.google.errorprone.annotations.FormatMethod; import java.util.ArrayDeque; -import java.util.BitSet; import java.util.LinkedHashMap; import java.util.LinkedHashSet; import java.util.Set; @@ -344,7 +343,6 @@ ImmutableList<String> names = resolvedFunction.getParameterNames().subList(0, numNonResidual); // Non-null only if there's at least one non-Any type non-residual parameter. ImmutableList.Builder<StarlarkType> types = null; - BitSet mandatoryIndices = new BitSet(); int nparams = parameters.size(); int numPositionalParameters = 0; @@ -379,10 +377,6 @@ if (types != null) { types.add(paramType); } - - if (param instanceof Parameter.Mandatory) { - mandatoryIndices.set(paramIndex); - } paramIndex++; } @@ -408,28 +402,72 @@ types == null ? null : types.build(), /* numPositionalOnlyParameters= */ 0, numPositionalParameters, - Types.MandatoryParamIndices.of(mandatoryIndices), + Types.MandatoryParamIndices.fromParameters(resolvedFunction), varargsType, kwargsType, returnType); } /** - * Sets an identifier's type. + * Records an identifier's type in the type table. * - * <p>The {@code Binding} on the identifier must have already been set by the resolver. - * (Therefore, this method cannot be called for identifiers that are not symbols, like field names - * or call site keyword arguments.) + * <p>The identifier must be a binding occurrence, and its {@link Resolver.Binding} must have + * already been set by the resolver. (Therefore, this method cannot be called for identifiers that + * are not symbols, like field names or call site keyword arguments.) * * <p>Logs an error if the identifier is not the first binding occurrence of the {@code Binding}. * In this case, the type is not updated. * - * <p>Throws {@link IllegalArgumentException} if this is the first binding occurrence but somehow - * the type is already set. + * <p>For functions, use {@link #setAnnotatedFunctionType} or {@link #setUnannotatedFunctionType}, + * which additionally will in addition associate the type with the {@link Resolver.Function}. + * + * @throws IllegalArgumentException if this is the first binding occurrence but somehow the type + * is already set. */ - private void setType(Node node, Identifier id, StarlarkType type) { - Resolver.Binding binding = id.getBinding(); - checkNotNull(binding, "no binding set on identifier '%s'", id.getName()); + private void setIdentifierType(Node node, Identifier id, StarlarkType type) { + if (!errorIfTypeAlreadySet(node, id)) { + typeTable.setDeclaredType(id.getBinding(), type); + } + } + + /** + * Variant of {@link #setIdentifierType} for the type of a function whose signature has type + * annotations. + * + * <p>Throws {@link IllegalArgumentException} if the type is already set. + */ + private void setAnnotatedFunctionType(DefStatement def, Types.GeneralCallableType type) { + Resolver.Function rfn = def.getResolvedFunction(); + @Nullable StarlarkType prevType = typeTable.getAnnotatedFunctionType(rfn); + if (prevType != null) { + throw new IllegalArgumentException( + String.format( + "Expected type of resolved function %s to be null but was %s", + rfn.getName(), prevType.typeRepr())); + } + if (!errorIfTypeAlreadySet(def, def.getIdentifier())) { + typeTable.setAnnotatedFunctionType(def.getIdentifier().getBinding(), rfn, type); + } + } + + /** + * Variant of {@link #setIdentifierType} for a function whose signature doesn't have type + * annotations. The {@code Callable} type of such a function is computed on demand. + */ + private void setUnannotatedFunctionType(DefStatement def) { + if (!errorIfTypeAlreadySet(def, def.getIdentifier())) { + typeTable.setUnannotatedFunctionType( + def.getIdentifier().getBinding(), def.getResolvedFunction()); + } + } + + /** + * Returns true and logs an error if a previous occurrence of the given symbol has been associated + * with a type or a type constructor; otherwise, returns false. + */ + private boolean errorIfTypeAlreadySet(Node node, Identifier id) { + Resolver.Binding binding = + checkNotNull(id.getBinding(), "no binding set on identifier '%s'", id.getName()); if (binding.getFirst() != id) { if (node instanceof DefStatement) { @@ -454,38 +492,17 @@ } errorIfTypeConstructor(node, id); // We don't have a usable type for this binding. - typeTable.setDeclaredType(binding, null); - return; + typeTable.clearDeclaredType(binding); + return true; } - @Nullable StarlarkType prevType = typeTable.getType(binding); - if (prevType != null) { - throw new IllegalArgumentException( - String.format("Expected type of binding %s to be null but was %s", binding, prevType)); - } - typeTable.setDeclaredType(binding, type); - } - - /** - * Sets a resolved function's type. - * - * <p>Throws {@link IllegalArgumentException} if the type is already set. - */ - private static void setType( - Resolver.Function resolved, Types.GeneralCallableType type, TypeTable typeTable) { - checkNotNull(resolved); - @Nullable StarlarkType prevType = typeTable.getType(resolved); - if (prevType != null) { + if (typeTable.hasBindingType(binding)) { throw new IllegalArgumentException( String.format( - "Expected type of resolved function %s to be null but was %s", - resolved.getName(), prevType.typeRepr())); + "Expected type of binding %s to be null but was %s", + binding, typeTable.getType(binding))); } - typeTable.setType(resolved, type); - } - - private void setType(Resolver.Function resolved, Types.GeneralCallableType type) { - setType(resolved, type, typeTable); + return false; } /** @@ -553,7 +570,7 @@ if (assignment.getType() != null) { setUsesTypeSyntax(); StarlarkType type = extractType(assignment.getType()); - setType(assignment, (Identifier) assignment.getLHS(), type); + setIdentifierType(assignment, (Identifier) assignment.getLHS(), type); } for (Identifier id : Identifier.boundIdentifiers(assignment.getLHS())) { @@ -572,13 +589,13 @@ public void visit(DefStatement def) { Resolver.Function resolvedFunction = def.getResolvedFunction(); functionStack.push(resolvedFunction); - Types.GeneralCallableType type = - createFunctionType(resolvedFunction, def.getParameters(), def.getReturnType()); - setType(resolvedFunction, type); - setType(def, def.getIdentifier(), type); - // Parameter types handled by visit(Parameter). - if (def.getReturnType() != null || !def.getTypeParameters().isEmpty()) { + if (def.signatureHasTypeAnnotations()) { + Types.GeneralCallableType type = + createFunctionType(resolvedFunction, def.getParameters(), def.getReturnType()); + setAnnotatedFunctionType(def, type); setUsesTypeSyntax(); + } else { + setUnannotatedFunctionType(def); } super.visit(def); @@ -600,7 +617,7 @@ type = Types.dict(Types.STR, type); } } - setType(param, param.getIdentifier(), type); + setIdentifierType(param, param.getIdentifier(), type); } super.visit(param); @@ -629,7 +646,13 @@ SpellChecker.didYouMean(originalName, loadedModule.getExports())); continue; } - setType(load, binding.getLocalName(), loadedModule.getExportType(originalName)); + @Nullable StarlarkType type = loadedModule.getExportType(originalName); + if (type != null) { + setIdentifierType(load, binding.getLocalName(), loadedModule.getExportType(originalName)); + } else { + // Even if the export doesn't have a type, verify that the local name wasn't already typed. + errorIfTypeAlreadySet(load, binding.getLocalName()); + } @Nullable TypeConstructor typeConstructor = loadedModule.getExportTypeConstructor(originalName); if (typeConstructor != null) { @@ -656,14 +679,14 @@ extractTypeOrTermEvaluatingToType(node.getDefinition(), typeParams); typeConstructor = new TypeConstructor.Composite(name, typeParams.size(), term); } - setType(node, node.getIdentifier(), Types.TYPE); + setIdentifierType(node, node.getIdentifier(), Types.TYPE); setTypeConstructor(node, node.getIdentifier(), typeConstructor); } @Override public void visit(VarStatement var) { StarlarkType type = extractType(var.getType()); - setType(var, var.getIdentifier(), type); + setIdentifierType(var, var.getIdentifier(), type); setUsesTypeSyntax(); // No need to descend into type expression child. @@ -679,14 +702,7 @@ super.visit(cast); } - @Override - public void visit(LambdaExpression lambda) { - Resolver.Function resolvedFunction = lambda.getResolvedFunction(); - Types.GeneralCallableType type = - createFunctionType(resolvedFunction, lambda.getParameters(), /* returnTypeExpr= */ null); - setType(resolvedFunction, type); - super.visit(lambda); - } + // No visit(LambdaExpression) override: lambda params don't have type annotations. // TODO: #27370 - Figure out the relationship between this visitor and identifiers introduced by // type alias statements. I don't think it's quite correct to say that `type A = B` is annotating
diff --git a/src/main/java/net/starlark/java/syntax/Types.java b/src/main/java/net/starlark/java/syntax/Types.java index 68f9618..9cf4b06 100644 --- a/src/main/java/net/starlark/java/syntax/Types.java +++ b/src/main/java/net/starlark/java/syntax/Types.java
@@ -499,12 +499,16 @@ for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { mask |= 1L << i; } - return INTERNER.intern(new CompactMandatoryParamIndices(mask)); + return ofMask(mask); } // Clone the bitset to prevent mutation of the interned instance. return INTERNER.intern(new BitSetMandatoryParamIndices((BitSet) bitSet.clone())); } + static MandatoryParamIndices ofMask(long mask) { + return mask == 0L ? EMPTY : INTERNER.intern(new CompactMandatoryParamIndices(mask)); + } + static MandatoryParamIndices fromNames( ImmutableList<String> parameterNames, ImmutableSet<String> mandatoryNames) { if (mandatoryNames.isEmpty()) { @@ -519,6 +523,29 @@ return of(bitSet); } + static MandatoryParamIndices fromParameters(Resolver.Function rfn) { + int numNonResidual = rfn.getNumNonResidualParameters(); + ImmutableList<Parameter> params = rfn.getParameters(); + // Minimize temp allocations, since this method is called frequently. + if (numNonResidual <= Long.SIZE) { + long mandatoryMask = 0L; + for (int i = 0; i < numNonResidual; i++) { + if (params.get(i) instanceof Parameter.Mandatory) { + mandatoryMask |= 1L << i; + } + } + return MandatoryParamIndices.ofMask(mandatoryMask); + } else { + BitSet mandatoryBitSet = new BitSet(); + for (int i = 0; i < numNonResidual; i++) { + if (params.get(i) instanceof Parameter.Mandatory) { + mandatoryBitSet.set(i); + } + } + return MandatoryParamIndices.of(mandatoryBitSet); + } + } + /** Returns the total number of mandatory parameters. */ abstract int getNumMandatoryParameters(); @@ -673,6 +700,23 @@ mandatoryParamIndices)); } + /** + * Returns a {@link GeneralCallableType} for a resolved Starlark function whose parameters and + * return value all have type {@link #ANY}. Such a type is determined purely by the names, + * optionality, and keyword-ness/positional-ness of the parameters. + */ + public static GeneralCallableType allAnyFunction(Resolver.Function rfn) { + return generalCallable( + rfn.getParameterNames().subList(0, rfn.getNumNonResidualParameters()), + /* parameterTypesIfNonAny= */ null, + /* numPositionalOnlyParameters= */ 0, + rfn.getNumOrdinaryParameters(), + MandatoryParamIndices.fromParameters(rfn), + rfn.hasVarargs() ? ANY : null, + rfn.hasKwargs() ? ANY : null, + ANY); + } + public static SimpleCallableType simpleCallable( ImmutableList<StarlarkType> parameterTypes, boolean hasVarargsAndKwargs,
diff --git a/src/test/java/net/starlark/java/eval/DynamicTypeCheckTest.java b/src/test/java/net/starlark/java/eval/DynamicTypeCheckTest.java index 4ba712d..7c847bb 100644 --- a/src/test/java/net/starlark/java/eval/DynamicTypeCheckTest.java +++ b/src/test/java/net/starlark/java/eval/DynamicTypeCheckTest.java
@@ -269,9 +269,21 @@ StarlarkSemantics semantics = ev.getStarlarkThread().getSemantics(); // Verify that sibling functions didn't duplicate type data. - assertThat(siblingFn.getFunctionTypes()).isSameInstanceAs(outerFn.getFunctionTypes()); - assertThat(siblingFn.getFunctionTypes()).isSameInstanceAs(middleFn.getFunctionTypes()); - assertThat(siblingFn.getFunctionTypes()).isSameInstanceAs(innerFn.getFunctionTypes()); + assertThat(siblingFn.getAnnotatedFunctionTypes()) + .isSameInstanceAs(outerFn.getAnnotatedFunctionTypes()); + assertThat(siblingFn.getAnnotatedFunctionTypes()) + .isSameInstanceAs(middleFn.getAnnotatedFunctionTypes()); + assertThat(siblingFn.getAnnotatedFunctionTypes()) + .isSameInstanceAs(innerFn.getAnnotatedFunctionTypes()); + + // Verify that annotatedFunctionTypes doesn't include <toplevel>. + assertThat(outerFn.getAnnotatedFunctionTypes()).hasLength(4); + assertThat(outerFn.getAnnotatedFunctionTypes()[innerFn.rfn.getFunctionId()]).isNull(); + assertThat(outerFn.getAnnotatedFunctionTypes()[outerFn.rfn.getFunctionId()]).isNull(); + assertThat(outerFn.getAnnotatedFunctionTypes()[middleFn.rfn.getFunctionId()]) + .isSameInstanceAs(middleFn.getStarlarkType(semantics)); + assertThat(outerFn.getAnnotatedFunctionTypes()[siblingFn.rfn.getFunctionId()]) + .isSameInstanceAs(siblingFn.getStarlarkType(semantics)); assertThat(outerFn.getStarlarkType(semantics).typeRepr()).isEqualTo("<def () -> Any>"); assertThat(middleFn.getStarlarkType(semantics).typeRepr())
diff --git a/src/test/java/net/starlark/java/syntax/TypeTaggerTest.java b/src/test/java/net/starlark/java/syntax/TypeTaggerTest.java index 8daa7e0..b5c3a5b 100644 --- a/src/test/java/net/starlark/java/syntax/TypeTaggerTest.java +++ b/src/test/java/net/starlark/java/syntax/TypeTaggerTest.java
@@ -1117,6 +1117,52 @@ } @Test + public void nonToplevelFunctionTypes_omitsUntypedFunctions() throws Exception { + Result untypedResult = + tagFile( + """ + def outer(): + def inner(): + pass + return inner + + f = lambda x: x + """); + assertThat(untypedResult.typeTable().getAnnotatedFunctionTypes()).isEmpty(); + + Result partiallyTypedResult = + tagFile( + """ + def typed_fn(x: int) -> int: + return x + + def untyped_fn(y): + return lambda z: y + z + """); + DefStatement typedFn = (DefStatement) partiallyTypedResult.file().getStatements().get(0); + DefStatement untypedFn = (DefStatement) partiallyTypedResult.file().getStatements().get(1); + LambdaExpression lambda = + (LambdaExpression) ((ReturnStatement) untypedFn.getBody().get(0)).getResult(); + assertThat( + partiallyTypedResult + .typeTable() + .getAnnotatedFunctionType(typedFn.getResolvedFunction())) + .isEqualTo(partiallyTypedResult.getType(typedFn)); + assertThat( + partiallyTypedResult + .typeTable() + .getAnnotatedFunctionType(untypedFn.getResolvedFunction())) + .isNull(); + assertThat( + partiallyTypedResult.typeTable().getAnnotatedFunctionType(lambda.getResolvedFunction())) + .isNull(); + assertThat(partiallyTypedResult.getType(lambda)).isNotNull(); + assertThat(partiallyTypedResult.typeTable().getAnnotatedFunctionTypes()) + .asList() + .containsExactly(partiallyTypedResult.getType(typedFn), null, null); + } + + @Test public void functionType_sharesParameterNamesAndUntypedParameterTypes() throws Exception { Result result = tagFile(