diff options
Diffstat (limited to 'tests/DESIGN-forest-from-spans.md')
| -rw-r--r-- | tests/DESIGN-forest-from-spans.md | 413 |
1 files changed, 413 insertions, 0 deletions
diff --git a/tests/DESIGN-forest-from-spans.md b/tests/DESIGN-forest-from-spans.md new file mode 100644 index 0000000..8ff81d4 --- /dev/null +++ b/tests/DESIGN-forest-from-spans.md @@ -0,0 +1,413 @@ +# 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). |