perf(prediction): add an opt-in full-context DFA with caller-context edges

[tinovyatkin]

Source

Tunnel Vision's optimized fork can cache full-context (LL) prediction in the
decision DFA, not only local-context (SLL) prediction:

• Optimized fork: Full context DFA
• enable_global_context_dfa and its memory warning
• Full-context start-state and caller-context traversal
• Context-sensitive DFA edges
• DFAState context symbols and context-edge map

The fork maintains a separate full-context start state and incrementally follows
caller return states through context edges before taking the next token edge.
It is disabled by default because retained states, configurations, and contexts
can grow substantially.

Applicability

Applicable. The Rust runtime already performs full-context prediction and
owns compact learned-DFA/context storage, but its
ParserDfa
contains only SLL token edges plus local/precedence start states. The
adaptive_predict_full_context
path rebuilds and simulates LL configurations rather than learning
caller-context edges.

#207 added a narrower bounded replay memo for predicate-free full-context
resolutions. A full-context DFA is complementary: it can retain intermediate LL
states and context transitions, and it should be evaluated as an opt-in
alternative rather than silently duplicating both caches.

This is source-level applicability research only; no speedup is claimed without
future measurement.

Proposed work

• Add an opt-in, default-off full-context DFA mode.
• Represent full-context start states and caller-context edges with compact IDs
  in the existing hot/cold DFA architecture; do not introduce per-state object
  maps.
• Consume interned caller return states incrementally, matching the fork's
  context-symbol/context-edge model.
• Define bounded retention and expose state/context-edge memory statistics.
• Specify interaction with perf(prediction): memoize full-context LL resolutions by interned context — repeated SLL-conflict retries dominate ambiguous-grammar parses #207's replay memo: select, compose with a proven
  bound, or replace it, but do not retain two unaccounted caches for the same
  work.
• Preserve precedence DFA, predicates, exact ambiguity diagnostics, shared-store
  import/remapping, and clear_dfa() behavior.

Acceptance criteria

• The option is disabled by default and has a documented memory tradeoff.
• Repeated identical LL predictions can hit learned full-context states
  without re-running the complete LL closure.
• Caller contexts that share a prefix reuse context edges; distinct contexts
  cannot alias.
• Cache clearing and shared prediction-store import preserve ContextId
  ownership invariants.
• ANTLR runtime conformance remains green with zero skipped cases.

[tinovyatkin]

Follow-up: prefer automatic per-decision admission

The default-off discussion exposes a usability problem: a global switch asks
users to predict runtime context reuse and memory growth from application
behavior they generally cannot observe. We have the source grammar and ATN at
generation time, so codegen should contribute a recommendation, but a
grammar-only on/off decision is still insufficient.

What codegen can determine

Codegen can classify each decision rather than treating the entire grammar as
one unit:

• Never eligible: complete LL(1) decisions, and complete fixed-lookahead
  decisions when that optimization is enabled, cannot reach adaptive
  prediction and therefore cannot benefit from a full-context DFA. The
  existing decision classifier
  already proves this category.
• Candidate: a bounded SLL/configuration exploration can look for reachable
  conflicts which may require full-context prediction. This is stronger than
  merely treating every non-LL(1) decision as a candidate: many adaptive
  decisions resolve with additional token lookahead and never need LL.
• Memory-risk signal: recursion, the number of distinct incoming rule-call
  follow states, and caller-context fan-out can estimate whether retained
  context edges are likely to diversify. The grammar frontend already records
  recursive components
  and owns the rule call graph.
• Conditional/unknown: predicates, precedence-sensitive paths, or an
  exhausted analysis budget should prevent a strong static recommendation
  rather than silently imply safety.

These results should extend
decisions.json
with per-decision full-context-DFA eligibility and the reason/risk signal.

What codegen cannot determine

The actual payoff depends on the entry rule, input distribution, frequency of
LL retries, repetition of caller contexts, parser lifetime, and the
application's memory limit. The same grammar can be a one-shot CLI parser or a
long-lived service processing millions of structurally similar documents.
Source analysis cannot choose correctly for both.

Recommendation

Expose Off | Auto | On, with Auto as the default, and apply it per
decision:

1. Codegen emits a compact eligibility bitset plus diagnostic manifest data.
2. An eligible decision starts without a full-context DFA.
3. The runtime observes a small admission window of full-context retries,
   closure work, and caller-context reuse.
4. It promotes only decisions that show repeated expensive LL work with useful
   reuse. There is already a runtime precedent for
   work-density-based automatic routing,
   and the perf instrumentation already tracks
   per-decision retry and memo behavior.
5. Per-decision and parser-wide state/context-edge budgets bound retention.
   Once a budget is reached, learned entries remain usable but misses fall
   back to ordinary LL without further growth.
6. Promotion replaces or disables perf(prediction): memoize full-context LL resolutions by interned context — repeated SLL-conflict retries dominate ambiguous-grammar parses #207's replay memo for that decision; the
   two caches must not duplicate retention.

User guidance then becomes straightforward:

• Auto: normal default; no full-context storage is allocated until a
  decision demonstrates likely benefit.
• Off: applications requiring a strict no-cache policy or the smallest
  predictable memory footprint.
• On: forced experimentation, benchmarking, or an already-profiled LL-heavy
  workload, still subject to hard retention budgets.

I recommend replacing the current acceptance criterion "disabled by default"
with default automatic admission plus explicit Off and On overrides. The
feature remains cold/off initially, but users no longer need to understand
ANTLR prediction internals to receive the optimization where it is justified.