From fba9a90cfc6aca2a26cce72f55fb261789139781 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 16 Oct 2026 14:01:01 +0800 Subject: new start Now I tested and discussed with claude, and had a working version of this project. The rest is to port the claude version to my own writings. So this serves as the starting point before that attempt. In the new attempt the design is better, and a number of bugs were found and supposedly fixed, so let us see how this goes at the end. --- tests/DESIGN-forest-from-spans.md | 413 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 413 insertions(+) create mode 100644 tests/DESIGN-forest-from-spans.md (limited to 'tests/DESIGN-forest-from-spans.md') 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 `/claude scratch/ws` (build dir +`/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). -- cgit v1.2.3-18-g5258