[perf][feature] Precomputed reference index — make CodeLens counts / FAR O(1) lookups instead of per-request searches

[msarson]

Goal

Make reference counts (and eventually Find-All-References / "who calls X") O(refs) lookups instead of per-request searches. After #188 the per-method CodeLens cost is dominated by the reference search scanning the file set on every count (~1–2s/method). A precomputed symbol → [reference sites] index turns each count into a map lookup, independent of how many methods a file has.

This is Mark's proposal (2026-06-07): "build a list of the methods in some graph, then just analyze references to those methods — would work well with procedure implementations as well."

Why it's feasible now

• [perf] Large-file LSP freeze: DocumentStructure.process() O(S×T) + reference search re-tokenizes files (5–12s event-loop blocks) #188 made tokenizing a file cheap (~0.8s, cached cross-call via TokenCache.getTokensForClosedFile) — so a one-pass build over the solution is affordable, where before it would've taken minutes.
• Building blocks already exist: FileRelationshipGraph (file edges), StructureDeclarationIndexer (declarations), DocumentStructure.procedureIndex (per-file decl index), and the resolution logic in ReferencesProvider / MemberLocatorService / CallSiteArgumentClassifier.

Data structure

class ReferenceIndex {
  // symbolKey → reference sites across the whole solution
  private bySymbol: Map<string, ReferenceSite[]>;
  // file uri → the symbolKeys it contributes sites to (for incremental invalidation)
  private byFile: Map<string, Set<string>>;
  count(symbolKey): number;        // O(1)
  references(symbolKey): ReferenceSite[];
  reindexFile(uri, sites): void;   // remove old contributions of uri, add new
  removeFile(uri): void;
  isReady(): boolean;
}
ReferenceSite = { uri, line, character };

symbolKey (normalized identity — must mirror how references resolve):

• Global procedure: proc:<name>
• Class method: method:<class>.<method>
• Interface method impl: method:<class>.<iface>.<method> (or fold to the iface method)
• Class type: type:<name>
  Start name-level (no overload-signature discrimination); add signature precision in a later phase (reuse [#120 follow-up] DefinitionProvider / MethodHoverResolver / ImplementationProvider still route through legacy selectBestOverload — type-aware findOverloadByArgClassifications not wired in #125/[#125 follow-up] Pattern A extension: arg-classification wire-up to SELF/PARENT/chained/cross-file paths in Def/Hover/Impl #127 CallSiteArgumentClassifier).

Phasing (each independently shippable, behaviour-preserving)

• Phase 1 — substrate. ReferenceIndex class + a pure extractReferenceSites(tokens, uri, resolve) that walks call/dot-access/type-usage sites and yields {symbolKey, site}. Unit-tested in isolation. Not wired to anything → zero behaviour risk.
• Phase 2 — build + wire counts. Build the index at solutionReady (one pass over solution files, cheap tokens, yield per file per [perf][umbrella] Yield + honor cancellation across hot LSP search loops (WorkspaceSymbol, Implementation, overload/include walks) #187). Point onCodeLensResolve at index.count(key) with fallback to the live FAR when the index isn't ready or misses (so it's never wrong, only faster). Measure.
• Phase 3 — incremental. On didChangeContent, reindexFile(changedUri) (using byFile to drop stale contributions) instead of the current global codeLensGeneration bump; refresh CodeLens.
• Phase 4 — precision + reuse. Overload-signature discrimination; let FAR / "who calls X" read from the index too.

Correctness guardrails

• Phase 2 keeps the live FAR as the fallback/source of truth; the index is a cache. Compare index counts vs FAR counts in tests on disk fixtures before trusting it.
• Symbol-identity must match FAR's resolution or counts drift — pin with tests that assert index.count(sym) === provideReferences(sym).length on representative fixtures.
• mtime/byFile invalidation so external edits don't serve stale counts (same discipline as getTokensForClosedFile).

Cross-ref

• [perf] Large-file LSP freeze: DocumentStructure.process() O(S×T) + reference search re-tokenizes files (5–12s event-loop blocks) #188 (token caching + O(T) process — the substrate this builds on)
• [perf][umbrella] Yield + honor cancellation across hot LSP search loops (WorkspaceSymbol, Implementation, overload/include walks) #187 (yield/cancel in scans — reuse cooperativeCheckpoint for the build pass)
• [perf] Reference-count CodeLens runs Find-All-References per visible method — sluggish on large classes; add setting + cache #185 (the CodeLens setting + count cache this supersedes)
• Resolution substrate: ReferencesProvider, MemberLocatorService, CallSiteArgumentClassifier ([#120 follow-up] DefinitionProvider / MethodHoverResolver / ImplementationProvider still route through legacy selectBestOverload — type-aware findOverloadByArgClassifications not wired in #125/[#125 follow-up] Pattern A extension: arg-classification wire-up to SELF/PARENT/chained/cross-file paths in Def/Hover/Impl #127/[#127 follow-up] Cross-file overload resolution must walk MEMBER → PROGRAM → INCLUDE chain (not just current file's INCLUDEs) #128)

[msarson]

Shipped a phase of #189 in PR #208 (merge commit 423b6b2):\n\n- Added background precompute of CodeLens reference counts at solutionReady.\n- Warmed the existing declaration-keyed cache across solution source files.\n- Kept onCodeLensResolve behavior-safe via existing live FAR fallback.\n- Added referencesCodeLensEnabled toggle handling to clear/rebuild precompute state.\n\nIssue remains open for later phases (incremental reindex/rebuild strategy and broader FAR reuse).

[msarson]

Closed via the delivered #189 increments now merged to version-0.9.9:\n\n- Phase 1 substrate: ReferenceIndex data structure + unit tests (ReferenceIndex.test.ts)\n- Phase 2 build/warm path: background precompute of declaration-keyed CodeLens reference cache at solution-ready\n- Phase 2 invalidation: per-file cache eviction (no more global CodeLens count invalidation on any edit)\n- Phase 4 initial FAR reuse: onReferences now does an O(1) declaration-path cache lookup using CodeLens metadata, with live ReferencesProvider fallback preserved for correctness\n\nLatest FAR cache fast-path merge: PR #222\nChangelog update: PR #223\n\nThis closes the issue goal of moving CodeLens counts and declaration-driven FAR off per-request full scans onto precomputed lookups, while retaining behavior-safe fallback paths.