# CLAUDE.md

## Project

A Rust implementation of the relational parsing algorithm from Grzegorz Herman,
"Faster general parsing through context-free memoization" (PLDI 2020; earlier
arXiv version: "Relational parsing: a clean, fast parsing strategy for all
context-free languages", arXiv:1902.06591).

The parser is a general context-free parser. Beyond recognition, it is
meant to produce the **full derivation forest** (a shared packed parse
forest), not a single tree. Recognition appears to work (update:
**opus found the recognizer bugs**, and seemed to fix them, see the
design document in tests); **forest construction is wrong**.

Fill in before use:

- Main source files are contained in the sub-crates: [ "graph",
  "receme", "nfa", "chain", "viz", "grammar", "forest", "semiring",
  "graph_macro", "tokens" ], and the top-level crate is mainly for
  making a dynamic module to load as an Emacs library.
- Forest representation is in the "forest" sub-crate, while the
  construction is mainly in the "chain" sub-crate, which is the
  hot-point of the entire crate in my opinion.
- Entry point / CLI: this is intended to be an Emacs dynamic module,
  and should compile to produce a `rep.so` file.
- Paper PDF files are contained in the directory
  "/Users/durand/Desktop/Centre/A propos de programmes/C/parser/references/",
  but there are too many papers to read, so ask me to confirm before
  trying to consult a paper, to save unnecessary tokens.

## The task

Debug forest construction until the parser's forest represents
**exactly** the set of derivation trees of the input, no more and no
fewer, with proper sharing.

Reference cases with hand-verified expected forests and tree sets:
forest-examples.md

## Ground rules

- ONLY MAKE A PLAN FOR ME TO CHANGE.  Do not write or change the files
  here.  I prefer to have this project be fully understood and written
  by me by hand, so unless explicitly requested, no actual change is
  appreciated.
- When some files do get written, they should all sit inside the
  "tests" folder, inside which I permit you to write files.
- Do not weaken, delete, or edit the expected results in
  `forest-examples.md` or in tests to make something pass. If you
  believe a reference case is wrong, stop and explain why with a hand
  derivation.
- Do not change recognition behavior unless you can show a recognition
  bug with a failing test.
- Make minimal, targeted changes. Do not rewrite or restructure large
  parts of the code to fix one bug.
- When the paper's definition is ambiguous or you are unsure how code
  maps to it, say so and ask, rather than guessing silently.
- Every bug you fix gets a regression test that failed before the fix.

## Workflow (follow in order)

### 1. Build a brute-force oracle first

Before touching the parser, write `tests/oracle.rs` (or a
`#[cfg(test)]` module) containing a deliberately naive, obviously
correct enumerator:

- Input: a grammar, a token sequence, and a height bound `h`.
- Output: the set of all derivation trees of height <= h, as canonical
  S-expression strings in the notation used in `forest-examples.md`.
  Height = max number of nonterminal nodes on any root-to-leaf path.
- Method: top-down, try every production for every (symbol, start,
  end) split, memoize nothing clever. Speed is irrelevant (inputs are
  at most ~8 tokens).
- Cycles: the parser represents infinitely many derivations as a cycle
  in the forest (see Case 5 of the reference file). The oracle does
  not prune cyclic derivations; the height bound is what makes it
  terminate.
- Validate the oracle itself against every case in
  `forest-examples.md` before trusting it.
- Make it clear that this enumerator is written by claude code.

### 2. Write an unpacker for the parser's forest

- Add a function `unpack(forest, h)` that expands the parser's forest
  into the same canonical tree-set representation (sorted
  `Vec<String>` or `BTreeSet<String>`), keeping only trees of height
  <= h. Choose alternatives per occurrence of a node, not once per
  node.  The forest may contain cycles, so the height bound is what
  guarantees termination.  Also guard against exponential blowup (bail
  out with a clear error above a tree count limit).
  
  Compare `unpack(forest, h)` with the oracle's output for h = 1, 2,
  3, 4 (and larger for tiny cases).
- This should come inside the above test file.

### 3. Compare, then classify the failure

For each case, diff parser tree set vs oracle tree set. Report which
of these applies, because each points to a different bug class:

- **Missing trees**: lost derivations (alternatives dropped, wrong
  completion or sharing key that merges distinct derivations, nullable
  handling).
- **Extra trees**: spurious derivations (children not covering their
  span, stale or over-shared nodes, memoized result reused in the
  wrong context).
- **Duplicate trees / wrong multiplicity**: the same derivation packed
  twice (identical nodes not shared, or an alternative inserted more
  than once).
- **Right trees, bad size**: forest is correct but not shared properly
  (should be polynomial in n, not exponential).

### 4. Add structural invariant checks

Implement a `validate_forest` function and call it in tests. It should
assert:

- Each node's chosen children cover exactly its span `[start, end]`,
  in order, with no gaps or overlaps.
- Nodes are unique per (symbol, start, end); no duplicate nodes.
- No two packed alternatives of a node are identical.
- Terminal children match the input tokens at their positions.
- Each alternative corresponds to a real production of the grammar.
- Cycles are allowed, but every node on a cycle must have the same
  span `[start, end]`. A cycle through nodes of different spans is a
  bug.
- The forest is finite: node count is polynomial in the input length
  even for cyclic grammars.

### 5. Localize with and without memoization (skipped for now)

My implementation does not handle memoization well yet, so this part
is skipped.

Run every failing case with memoization disabled (add a feature flag
or runtime switch if none exists). If the bug disappears, the
memoization cache key is missing context the result depends on. If it
persists, the bug is in the core algorithm or the forest construction
itself.

### 6. Test layers, in this order

1. Unambiguous, no epsilon.
2. Ambiguous, no epsilon (Cases 1 and 2).
3. Epsilon rules and nullable nonterminals (Cases 3 and 4).
4. Left, right, and hidden left recursion.
5. Cyclic grammars (Case 5).
6. Random small grammars: generate grammars with 1 to 3 nonterminals
   and productions of length at most 3 over a 2-terminal alphabet,
   random inputs up to length 6, and compare against the oracle. Use
   `proptest` or a seeded RNG so failures are reproducible; print the
   grammar and input on failure.

Stop at the first failing layer and fix it before moving on.

## Commands

```
cargo build
cargo test
cargo test -- --nocapture   # to see diffs
cargo clippy -- -D warnings
```

## Reporting

When you finish a debugging step, report briefly:

- The smallest grammar and input that failed.
- Oracle tree set vs parser tree set (the diff).
- The root cause, with the file and line.
- The fix and the regression test added.