R170: Left-Recursion Member Memoization

The rules of a left-recursion cycle other than its leader are memoized, so a member reached from several call sites at one position is evaluated once instead of once per call.

Mechanism and Invariants

The result of a call of a rule of a cycle is a function of the growths of its cycle in progress at its position, its context: the leaders that grow there and the seeds they have reached. A call records what its result depended on: the seeds it read, each by an identity that equal step results of a leader share; the outcome of each lookahead whose evaluation read a seed, in place of those seeds; and the leaders that grew at the position (the present set, one bit per leader). A result that read no seed and observed no lookahead goes to the memo with its present set and answers any call whose context it includes. Any other result is kept in the table of its context, which lasts while the first growth there lasts, and answers a call in a context with the same present set where the seeds it read have the same identities and the lookaheads it observed have the same outcomes. A growth in a context memoizes its steps the same way and records runs of steps that read only its own seed as jumps. Leaders grow from failure; a call of a leader that grows at its position reads the seed. No dependent result reaches the memo of a Document, so later parses reuse only results that depend on the rule, the position and the variables. The transient policy applies to members.

Scope and State

All six backends and Documents. A transient member, one called from a single place, is not memoized in ordinary parses.

Reference Control

DisableMemo disables memoization of members and other rules together. Tests compare the engine with its internal parse option ContextMemoOff, which evaluates every call in a context again.

Evidence and Implementation

Evidence record: 130.

Source owners: the check of the front end's check package (the memo flags and the cycle numbers), CallBegin and CallEnd with the engine's context state, GrowBegin with the engine's dependency memo, the dependency memo of the generated Go runtime and its calls and growths, the call protocol in Exec IR with its context and growth operations, which the operations package of Exec IR declares, Parser.ctxEnter and the growths of the TypeScript runtime.

Related mechanisms: R020, R120.

Optimization Catalog