1 files changed, 174 insertions, 0 deletions
diff --git a/CLAUDE.md b/CLAUDE.md
new file mode 100644
index 0000000..c6f838c
--- /dev/null
+++ b/CLAUDE.md
@@ -0,0 +1,174 @@
+# 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.