Skip to content

Incremental: cache type checking per statement in the LSP #1301

Closed

Description

@jsiek

Every LSP re-check type-checks every statement of the user's file, even those unchanged since the last check. After the proof-check cache (checker_cache.py), type checking is the largest remaining per-check cost that does not depend on what changed.

Refs #1213 (iPad app), which wants a check after nearly every edit. Split off from #1218.

Measurements

These are warm lsp.query.check re-checks after inserting blank lines in the middle of the file (no profiler, steady-state runs):

File Total Parse Uniquify type_check_stmt check_proofs (cached)
test/should-validate/doc_reference.pf (489 lines) 0.237 s 0.015 s 0.020 s 0.047 s 0.068 s
test/should-validate/IntTests.pf (216 lines) 0.273 s 0.007 s 0.010 s 0.116 s 0.071 s

type_check_stmt is 20–42% of a re-check. Parse plus uniquify is 6–15%, which is why #1218's statement-level re-parse was dropped.

Proposal

Cache type_check_stmt's result per statement in checker_pipeline.check_deduce. Key it like the check_proofs cache: the statement's structural hash (_hash_ast, which skips locations) plus a fingerprint of the statements it depends on.

Dependencies

Reuse the proof-check cache's dependency tracking: _collect_referenced_names gives the names a statement mentions, _collect_defined_names maps each to the earlier statement that defines it, and _is_global_barrier marks statements that every later one depends on. Since uniquify gives every definition a distinct name, a name identifies one definition. For example, editing double must invalidate t1 but not t2:

fun double(n : Nat) { n + n }
theorem t1: double(1) = 2  proof ... end
theorem t2: all x:Nat. x + 0 = x  proof ... end

Type checking needs two additions:

  1. Overloads. Type checking sees names before overloads are resolved, and OverloadedVar.get_name() returns only the first candidate (abstract_syntax/terms.py, resolved_names[0]). Suppose a file defines fun f(x : Nat) and fun f(x : Int), and a theorem uses f(n). Editing the second f can change which one the theorem resolves to, so the theorem must depend on every name in resolved_names. The proof-check cache doesn't need this, because it runs after type checking, when every name is resolved to one definition.
  2. Lookups by type rather than by name. Type checking finds some declarations by type without naming them. For example, a switch on a UInt finds UIntView by its type. ViewDecl must then be a barrier for this cache, the way ConceptDecl and ModelDecl already are (Geometry roadmap: concepts, models, and where clauses (generic over an interface) #1264).

Also check that type names in annotations (Nat in x : Nat) are collected: _collect_referenced_names only gathers VarRef and PVar nodes.

What makes it harder than the proof-check cache

  • It returns a value. type_check_stmt returns the type-checked statement (overloads resolved, types filled in), which later phases use. So the cache must store and return it, not just a "verified" flag.
  • Locations. The comment above the check_proofs cache in check_deduce notes that the earlier loops' outputs carry Meta locations that matter, e.g. the target hole location goal_at uses. If a statement only moved, the cached output's locations are stale. The cache needs either the location in the key (giving up hits on shifted statements) or a way to re-locate the cached AST.
  • Side effects on env and error_on_next_import, if any, must be replayed on a hit, or such statements excluded.
  • Diagnostics and warnings: as with check_proofs, don't cache a statement whose type check reported one, so it is re-emitted.

Done when

  • Re-checking a file after editing one theorem type-checks only that theorem and the statements that depend on it. A test asserts this through the cache stats (checker_cache.get_cache_stats).
  • test-deduce.py and pytest test/lsp test/unit pass, including goal_at tests on a statement that moved.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions