path: root/tests/DESIGN-forest-from-spans.md

# Design: exact recognizer and forest from facts

Written by Claude Code (Opus).  This is the plan to follow; the source
changes are for the user to write by hand.  Claims are marked MEASURED
(shown by a run in the scratch copy), READ (read from the code) or
INFERRED.

## 1. Goal and approach

The parser's forest must represent exactly the derivation trees of the
input.  The approach:

- **Part A, an exact recognizer.**  Fix five recognizer bugs (section 3).
  Recognition alone must be right and fast; it is also the base of Part
  B.
- **Part B, the forest from facts.**  While recognizing, record facts
  `(X, i, j)` ("the nonterminal `X` derives `input[i..j]`").  After the
  input, build the forest top-down from `(S, 0, n)` using only the facts,
  the grammar and the input (section 4).  The forest is then a function
  of a set of facts: it does not depend on the order in which edges are
  processed.  Extra facts are harmless, because every forest node is
  checked down to terminals and ε, so correctness reduces to "no fact is
  missing", which the tests check against the oracle.

The current incremental forest code (`insert_item` and everything under
it) is replaced, not repaired.  MEASURED: its result depends on the hash
order of `Edge` (`labels_of` iterates a hash map,
`graph/src/labelled/double.rs:20`).

Everything in this document is prototyped and verified in the scratch
copy (section 7).  No step needs further research.

## 2. How the recognizer works (READ, partly INFERRED)

From `chain/src/default.rs` (`derive`, `generate_edges`, `extend`),
`chain/src/lib.rs` (`Collapsed`, `chain`) and
`chain/src/atom/default.rs` (`from_grammar`).

- **Chain graph.** A graph-structured stack.  An edge `(label, target)`
  out of a node means: "inside a nonterminal invocation (a *frame*), the
  atom NFA is in state `label`; when the frame completes, continue with
  the edges of `target`".
- **Nodes never change.**  `DLGraph::extend`
  (`graph/src/labelled/double.rs:395`) builds a node whole from edges
  whose targets are older nodes.  Nothing adds edges to a node later.
- **NFA states.** NFA nodes `2·pos` and `2·pos+1` belong to rule
  position `pos`; `get_rule_num(pos)` is the nonterminal owning it.
  **These states are shared by all nonterminals** (MEASURED): for
  `S -> X d; X -> Y c; Y -> a`, the state `Y -> a ·` has the edge
  `c -> X -> Y c ·` in every frame.  Virtual nodes `[nt]^t` come after
  all positions.  Within one frame the NFA runs through left-corner
  chains, so every nonterminal completed inside a frame starts at the
  frame's start.
- **Calls.** A nonterminal in a non-leading position starts a new frame
  at the current position `p`.  `derive` groups all callers of one
  virtual node (`add_second_layer`); `Collapsed` then creates one
  *second-layer* node `M` with their continuations, and the edge
  `(v, M)`.
- **Pops.** A transition to an accepting state "pulls in" the target's
  edges: the frame completes and the caller continues.  Reaching the end
  of a rule with nothing after it (an *empty node*) gives no real edge,
  only an *imaginary* edge `Im(target)` that carries acceptance.
- **Tail calls.** If the caller has nothing left after the call, no node
  is kept for it.  So the target of an edge does not tell where its frame
  started (for `S -> a S | a` every edge points to the root).

## 3. Part A: recognizer bugs and fixes

Each bug has a test in `tests/oracle.rs` (section 6).

### 3.1 Add `Edge::frame_nt`

The nonterminal of the edge's frame, part of `Eq` and `Hash`.  Needed by
3.4 and 3.5.

| Edge | `frame_nt` |
|---|---|
| Continuing edge made by `generate_edges` (`Edge::new(atom_child, …)`) | the `frame_nt` of the edge it comes from |
| Edge into a new frame: `Collapsed`, label = virtual node `[nt]^t` | `nt` |
| Edge into a new frame: the tail-call edge `Edge::new(virtual_node, …)` in `derive` | `non` |
| Pulled-in edge | its own |
| Initial edge from `unit` | the start symbol |

### 3.2 `DefaultChain::extend` decides acceptance from the first label

- **Bug:** the loop over the new node's labels (hash order) stops at the
  first label: "not accepting" if none of its targets accepts,
  "accepting" if the label accepts.  The result depends on the order.
- **Fix:** the node accepts iff some accepting label has an accepting
  target.
- Latent today; it shows once edges with the same label are not merged
  (3.1).

### 3.3 Moves into rules outside the frame

- **Bug:** because states are shared, inside a frame of `T` the end of
  `T` continues into `E -> E + · T` (`T` is a left corner of `E`).
  - `S -> b | a; A -> A S A | eps` accepts `a b b b`.
  - `E -> E + T | T; T -> T * n | n` on `n + n + … + n`: every `+`
    leaves a phantom `E` inside a `T` frame; maximum node degree 21 at 41
    tokens, total edges quadratic (MEASURED).
- **Fix:** inside a frame of `X`, allow a transition `label -> a` only if
  `a` is not a rule position, or the nonterminal owning `a`
  (`get_rule_num(a/2)`) is in `LC*(X)`.
  - `LC*(X)`: `X` itself, and for every rule `X -> Y1 … Ym` and every `k`
    such that `Y1 … Y(k-1)` are nullable and `Yk` is a nonterminal,
    everything in `LC*(Yk)`.  Compute it once from the grammar (a boolean
    matrix in the grammar or the atom).
  - Apply it to the atom children in the main loop of `derive`, and in
    the fact recording (4.3).  Checking the target state is enough
    (INFERRED): a composed edge climbs only through left corners of the
    target's nonterminal, which are then in `LC*(X)` too.
- With the fix the expression grammar has maximum degree 2 and linear
  edges (MEASURED).

### 3.4 Acceptance is one flag per state

- **Bugs:**
  - `S -> X d; X -> Y c; Y -> a` accepts `a c`: `X -> Y c ·` accepts
    because `X` ends there, and that flag also ends the frame of `S`.
  - `S -> A A; A -> a | eps` rejects `a`: the virtual node `[S]^a`
    ignores its left-linearly expanded children ("should not affect the
    nullability" block in `chain/src/atom/default.rs`).  Also
    `S -> Y; Y -> A | B; A -> x; B -> x` on `x`, and
    `S -> A; A -> B C; B -> x | eps; C -> y | eps` on `x`.
- **Fix:** acceptance relative to the frame's nonterminal.
  - In `DefaultAtom::from_grammar`, before the closure, compute for every
    nonterminal `x` the NFA nodes that reach the end of `x` (node
    `accumulators[x] + 1`) through nullable edges: the same propagation
    loop as `accepting_vec`, seeded with that one node.  Store it as
    `acc_by_nt[x][node]`.
  - `is_accepting_in(x, node)`: `acc_by_nt[x][node]` for a node of a rule
    position; `accepting_vec[node]` for other nodes (end of rules,
    virtual nodes).
  - `generate_edges` takes `frame_nt` and uses
    `is_accepting_in(frame_nt, atom_child)` for the edge's `accepting`
    flag and for pulling in the target's edges.
  - The virtual node `[nt]^t` accepts iff some child, left-linear or not,
    has `acc_by_nt[nt][child]`.

### 3.5 Imaginary edges are ignored next to real edges

- **Bug:** `Chain::chain` calls `update_epsilon` only when the new node
  has no real edges, and `Collapsed` keeps only the real edges of a
  second-layer group.  So a completion exactly at the end of a rule
  (`Im(target)`) is lost when other edges exist.  Hidden today by the
  global acceptance of 3.4: with 3.4 alone, `S -> B a; B -> a B | eps`
  rejects `a a`.
- **Fix:** in `chain`, always call `update_epsilon` (it only ever sets
  acceptance to true); in `Collapsed`, after creating `M`, call
  `update_epsilon(M, …)` with the group's imaginary edges.  Do 3.4 and
  3.5 in the same change.

### 3.6 Reduction lists lose nonterminals (needed by Part B)

- **Bug:** `transform_label_null_epsilon` (`grammar/src/lib.rs`) keeps
  one list per pair of states: the longest, and on composition only the
  second edge's list plus the end crossed in the middle.
  `S -> Y c; Y -> A | B; A -> x; B -> x` on `x c` loses `B[0,1]`.
- **Fix:** keep, per pair of NFA states, the *union* of all nonterminals
  ended on any path (a reduction set): during the closure, union the
  sets of both composed edges and the end crossed in the middle; when the
  atom builds a virtual node, copy the union onto the virtual node's
  edges.  Keep the lists while the old forest code still uses them.

## 4. Part B: the forest

### 4.1 Start sets (only when a forest is requested)

Edges do not carry their start.  A side table maps each chain edge
`(node, label, target, frame_nt)` to the set of starts of its frame,
filled when the node is created, from edges of older nodes:

| New edge | Its start set |
|---|---|
| continuing edge `(a, target)` from the edge `e` | `starts(e)` |
| pulled-in edge copied from node `c` | the set of that edge in `c` |
| edge into a new frame (`(v, M)`, tail-call edge `(v, target)`) | `{p}` |
| edges of a second-layer node `M` | by the same rules |
| initial edge from `unit` | `{0}` |

Edges that merge in `extend` take the union of their sets.

**Why this is exact (READ, MEASURED).**  A node is built whole from
older nodes and never changes, and all callers of one call are grouped
before `M` is created.  So no start can reach an edge after the edge's
successors exist.  Keep the check "every real edge has a non-empty set"
as a debug assertion.  If nodes are ever shared across positions
(memoization), this argument must be redone.

### 4.2 Facts recorded while reading token `t` at position `p`

For every edge `e = (label, children)` of the current node, and every
transition `label -> a` on `t` or on a call `Non(non)` with `t` in
FIRST(non), after the left-corner filter (3.3):

- **E1, inner completions.**  For every `X` in the reduction set of
  `(label, a)` (3.6) and every `s` in `starts(e)`: `(X, s, p)`.
- **E2, frame completion after a terminal.**  If `t` is read and
  `is_accepting_in(e.frame_nt, a)`:
  - for every `s` in `starts(e)`: `(e.frame_nt, s, p+1)`, and the *head
    event* `(H, s, p+1)` with `H = get_rule_num(a / 2)`;
  - walk down the stack: for every child node of `e`, every edge `l` of
    it with `is_accepting_in(l.frame_nt, l.label)` completes too; record
    the same for `l` with its start set, and continue from `l`'s targets.
- **E3, calls.**
  - Every call: the single-token event `(t, p)`, standing for
    `(X, p, p+1)` for every `X` that derives exactly `t` (precompute per
    terminal from the grammar).
  - If the virtual node `v` accepts: `(non, p, p+1)`.
  - If `a` also accepts for the caller's frame: as E2 with `e`.
- **E4, tail calls.**  If `a` is an empty node: for every `s` in
  `starts(e)`, the link `(p → s, e.frame_nt, H = get_rule_num(a/2))`.

Facts with `i == j` are not recorded: nullability comes from the
grammar.  Facts are not closed during the parse (4.3).

### 4.3 Building the forest top-down

- **`closed(j)`**: the facts ending at `j` (E1-E3, single-token events
  expanded), closed
  - *upward*: a head event `(H, i, j)` also gives `(Y, i, j)` for every
    `Y` reachable from `H` through rules `Y -> α H β` with `α`, `β`
    nullable;
  - *through tail links*: if a fact in `closed(j)` has start `p` and a
    link starts at `p`, add `(caller_nt, caller_start, j)` and the upward
    closure of `H` at `(caller_start, j)`; repeat.

  Compute `closed(j)` once per `j`, on the first demand.  Closing all
  facts eagerly would be quadratic on right recursion (`S -> a S | eps`:
  3240 facts at 80 tokens, against 80 needed; MEASURED).
- **Allowed keys.**  `(Y, k, l)` is allowed if `k < l` and `(Y, k)` is in
  `closed(l)`, or `k == l` and `Y` is nullable.
- **Alternatives of `(X, i, j)`.**  For each production `X -> Y1 … Ym`,
  find split points from right to left: `Ym` ends at `j` (a terminal
  equal to `input[j-1]`, or an allowed key `(Ym, k, j)`), then `Y(m-1)`
  ends at `k`, and so on; `Y1` must start at `i`.  An ε production is the
  alternative with `m = 0` and `i == j`.  Right to left makes every query
  "facts ending at `k`", the unit of the lazy closure.
- **Visit** from `(S, 0, n)`, computing the alternatives of each key
  reached.  This gives a finite graph of keys and alternatives.
- **Productive keys**: least fixpoint on that graph (a key is productive
  if one of its alternatives has only productive key children).  Cycles
  over equal spans (Case 5) are kept; keys with no finite derivation are
  dropped.
- **The forest**: the productive keys reachable from `(S, 0, n)` through
  productive alternatives.  If `(S, 0, n)` is not productive there is no
  root.  After Part A this agrees with `chain.epsilon()`; keep a debug
  assertion.

### 4.4 Output format

The format `unpack` in `tests/oracle.rs` reads:

- one nonterminal node per key, `start = i`, `end = Some(j)`;
- one alternative: a plain node whose children are, in order, one
  `Rule(slot)` wrapper per symbol of the production, each wrapper with
  exactly one child;
- several alternatives: a packed node with one cloned node per
  alternative;
- an ε alternative: a nonterminal node with no children;
- terminal leaves shared per position, wrappers per `(slot, start, end)`;
- `slot` is the atom's position number (`print_rule_positions`);
- check with `validate_forest`.

### 4.5 Why this is exact (INFERRED from the construction)

- **No extra trees:** every node is checked down to terminals and ε.
- **No missing trees:** if the facts cover the oracle, every node of
  every tree is a productive key with that alternative, reached from the
  root.
- **No duplicates:** alternatives are unique per (production, splits),
  nodes per key.

### 4.6 Cost

- **Recognition alone:** no side table, no facts.  The fixes of Part A
  make the chain smaller where states leaked between frames.
- **Recording:** O(edges + start-set entries + facts E1-E3).
- **Forest:** about the facts in the visited `closed(j)` plus the
  alternatives built.
- **Measured sizes** (scratch, all fixes):

  | Grammar | tokens | chain edges | max degree | start-set entries | facts needed | keys visited |
  |---|---|---|---|---|---|---|
  | `S -> a S \| eps` | 80 | 81 | 1 | 80 | 80 | 81 |
  | `S -> S a \| a` | 80 | 81 | 1 | 80 | 79 | 80 |
  | `S -> a S b \| eps` | 80 | 119 | 1 | 119 | 78 | 41 |
  | `E -> E + T \| T; T -> T * n \| n` | 79 | 158 | 2 | 155 | 119 | 80 |
  | `S -> S S \| a` | 80 | 6401 | 80 | 6242 | 3240 | 3240 |

  Linear for the first four (also at 20 and 40 tokens); quadratic for
  `S -> S S | a`, whose forest has n²/2 keys anyway.
- **Flat output:** a node may have O(n^(m-1)) alternatives for a
  production of length m.  Binarised nodes `(slot, i, k)` would give
  O(n³) but need `unpack` changes; later.

## 5. Plan

Each step has a test that fails before it and passes after it.

### Part A: exact recognizer

1. **Recognition gate**: port the scratch recognition check into
   `tests/oracle.rs`.  On the hand cases and the random grammars, "the
   recognizer accepts" must equal exact derivability (no height bound).
   It fails today.
2. **`extend` acceptance** (3.2).
3. **`Edge::frame_nt`** (3.1).
4. **Left-corner filter** (3.3).
5. **Frame-relative acceptance and imaginary edges** (3.4 and 3.5, one
   change).
6. **Gate passes** with zero mismatches; all recognition tests pass.
   Time the recognizer on long inputs before and after Part A (only
   chain size has been measured so far).

### Part B: forest

7. **Reduction sets** (3.6).
8. **Start-set side table** (4.1), only when a forest is requested.
9. **Record facts E1-E4** (4.2).
10. **Facts gate**: port `probe_facts` from scratch into
    `tests/oracle.rs` as real tests on the hand cases and random
    grammars.  A test-only eager closure of the recorded facts must
    satisfy "no missing fact" and "derivable from facts == exactly
    derivable".  This checks the recording alone.
11. **Top-down forest in `end_of_input`** (4.3, 4.4), with the chain run
    with `no_item = true`.  Compare the forest with the oracle on the
    same cases.  Delete `insert_item` and the old forest code once the
    suite passes.
12. **Full suite**, including layers 3 to 6 and every regression test
    (they compare derivation sets, so they stay valid).
13. **Later:** binarised nodes, memoization (redo 4.1's argument),
    incremental reparsing from the saved chain node at an edit point
    (facts and start sets before it stay valid).

## 6. Tests

In `tests/oracle.rs` (and the scratch copy):

| Test | Today | After |
|---|---|---|
| `open_recognition_nullable_rest_of_virtual_node` | fails | passes after step 5 |
| `open_recognition_inner_rule_end_is_not_frame_end` | fails | passes after step 5 |
| `open_recognition_unreachable_rule_accepts_too_much` | fails | passes after step 5 |
| `open_recognition_expression_grammar_node_degree_stays_bounded` | fails (degree 21) | passes after step 4 |
| `guard_recognition_rule_end_completion_next_to_other_edges` | passes | must keep passing; fails if 3.4 is done without 3.5 |

**The 9 forest tests that fail today** (`layer3_case_3`,
`layer3_case_4`, `layer3_nullable_in_the_middle`,
`layer4_hidden_left_recursion`, `layer5_case_5a`, `layer5_case_5c`,
`layer5_case_5d`, `layer5_highly_ambiguous_with_epsilon`,
`open_indirect_left_recursion`) fail in the old forest code.  Part A
does not change them (MEASURED).  The top-down prototype gives exactly
the oracle's trees on every grammar and input of those tests (MEASURED,
height 5), so they are expected to pass after step 11.  If one does not,
the step 10 tests tell whether the recording or the construction is
wrong.

## 7. Evidence (MEASURED in scratch, recognizer run with `no_item = true`)

With all fixes, start sets in a side table and `frame_nt` on edges:

- **27 hand cases** (right, left, hidden, indirect and nested left
  recursion; `S S`, `S S S`, `S S | S a`, `E + E`, `E + T / T * n`;
  nullable rules; the cyclic grammars of Case 5; unit chains through two
  nonterminals; 8-11-token ambiguous inputs) and **1194 random grammars**
  (the layer-6 generator, six seeds, height 4):
  - recognition equals exact derivability (no false acceptance or
    rejection);
  - no fact missing; "derivable from facts" equals exact derivability;
  - every real edge has a non-empty start set;
  - the top-down construction's trees equal the oracle's.
- With the fixes on, the old forest code's suite results do not change.
- Tree sets were compared at oracle height 4 to 6; recognition and
  derivability exactly.

## 8. Open points

- That a pulled-in edge keeps the start set and frame nonterminal of its
  own frame is INFERRED from the code and supported by the measurements,
  not proven; the step 10 tests guard it.
- The empty input is not supported by the test harness yet; `(S, 0, 0)`
  must be allowed when `S` is nullable.

## 9. Scratch reference

The scratch copy `<repo>/claude scratch/ws` (build dir
`<repo>/claude scratch/target`) holds the prototypes.  It is not the
user's tree: it also contains obsolete forest edits and `NOFIX_*`
switches, which must not be ported.  The prototypes are probes that
mirror `derive` in a separate pass; the real code should record inside
the actual edge generation.

| What | Where (scratch) | Switch |
|---|---|---|
| `Edge::frame_nt` | `chain/src/lib.rs` | `PROBE_START=1 NO_START=1` |
| 3.2 `extend` | `chain/src/default.rs` | `FIX_EXTEND=1` |
| 3.3 left-corner filter (`lc_ok`) | `chain/src/default.rs`; table from the test via `LC_TABLE` | `FIX_LC=1` |
| 3.4 `acc_by_nt`, `is_accepting_in` | `chain/src/atom/default.rs` | `FIX_FACC=1` |
| 3.5 imaginary edges | `chain/src/lib.rs` (`Collapsed`, `chain`) | `FIX_IMAG=1` |
| 3.6 reduction sets | `grammar/src/lib.rs` (`reduction_sets`) | `FIX_REDSET=1` |
| 4.1 start sets (`resolve_origins`, `orig`) and 4.2 facts | `chain/src/default.rs` | `ORIGINS=1` |
| 4.3 top-down prototype | `tests/oracle.rs`, test `probe_facts` | `PF_TOPDOWN=1` |

Full configuration:
`env PROBE_START=1 NO_START=1 ORIGINS=1 FIX_REDSET=1 FIX_EXTEND=1 FIX_LC=1 FIX_FACC=1 FIX_IMAG=1 PF_TOPDOWN=1`
(write the switches literally; zsh does not split `env $v`).
`probe_facts` options: `PF_GRAMMAR`/`PF_INPUT` (one case),
`PF_RANDOM=n` with `REP_SEED`, `PF_NOORACLE=1` (sizes only).
`probe_atom` prints the atom NFA of `PF_GRAMMAR`.  Recognition tests run
with `FIX_LC` need `LC_TABLE` by hand (`"0,1;1"` for the expression
grammar).