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(