Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 2 additions & 1 deletion CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -10,8 +10,9 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
### Breaking changes

- **File format v8** (#287, #371). Index keys now include the encoded value and the assert/retract flag. A v7 file (written by v2.x) is re-indexed and upgraded to v8 the first time it is opened; the upgrade is one-way and v2.x cannot open a v8 file (`STG-006`). Bindings users get this upgrade silently on open.
- **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones; checkpoints still rewrite all four indexes until copy-on-write insert lands (PR 4). Files written by a v3.0.0 development build before this change fail with `STG-032`.
- **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones. Files written by a v3.0.0 development build before this change fail with `STG-032`.
- **Covering indexes with dictionary-coded keys** (v8 storage format, PR 3 of 5; #433). Every index entry now holds the whole fact as a byte-comparable key, so a query reads only index pages, never a separate fact page. Entities and idents (attribute names and keyword values) get sequential internal ids from a dictionary stored in the file, and strings longer than 64 bytes are stored once in value pages and deduplicated. Fact pages are gone. A file with 100,000 facts (10 attributes per entity) takes 88 bytes per fact, down from 314. Facts from committed data now come back in internal-id order (entity, then attribute) rather than insertion or UUID order; query results are sets, and code that relied on an order must sort. New codes `STG-036` (dictionary entry missing) and `STG-037` (one transaction with two timestamps: a checkpoint or v7 upgrade refuses to change a stored timestamp). Files written by a v3.0.0 development build before this change fail with `STG-032`.
- **Checkpoints cost what changed, not the size of the database** (v8 storage format, PR 4 of 5; #434). A checkpoint now inserts copy-on-write: it rewrites only the index leaves that receive new facts and their paths to the root, and reuses pages freed by earlier checkpoints through a free list it reads and extends only as far as it needs. A checkpoint after one new fact takes 3.1 ms on a 10,000-fact file and 3.3 ms on a 100,000-fact file (it took 15.5 ms and 43 ms before, and grew with the file). One new fact at 100,000 facts writes 16 pages. The `checkpoint()` and `wal_checkpoint_threshold` docs now describe this cost.
- **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit.
- **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed.

Expand Down
13 changes: 8 additions & 5 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -111,7 +111,7 @@ cargo run < demos/demo_negation.txt
- `index.rs`: pending (uncheckpointed) EAVT/AEVT keys over UUIDs and strings, `encode_value`
- `keys.rs`: byte-comparable v8 keys (FDB integers, value tags, `tx↓`, FOREVER), DICT keys, `MAX_VALUE_BYTES`, `MAX_IDENT_BYTES`
- `node.rs`: prefix-compressed leaf and shortest-separator internal node codecs
- `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `rebuild_btree_incremental`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`)
- `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`)
- `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building)
- `value_pages.rs`: append-only value pages for strings over 64 bytes
- `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`)
Expand Down Expand Up @@ -182,15 +182,18 @@ Sidecar: <db>.wal — v2 header records the base generation; CRC32-protected e
Covering indexes: every index entry is a whole fact as a byte-comparable key
(`e a v tx↓ vf vt op` in EAVT order), with entities and idents as sequential ids from
the DICT tree, assigned at checkpoint. Strings over 64 bytes live once in value pages.
Committed scans return facts in id order. A checkpoint writes only pages the active
meta does not reference, syncs, then writes the other meta page and syncs, so a crash
at any point keeps the previous checkpoint.
Committed scans return facts in id order. A checkpoint is copy-on-write: it rewrites
only touched leaves and their paths (`btree::cow_insert`), takes pages from the free
list lazily and pushes freed ones (`PageAllocator::from_chain` / `finish_free_list`),
so its cost follows the change. It writes only pages the active meta does not
reference, syncs, then writes the other meta page and syncs, so a crash at any point
keeps the previous checkpoint.
Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are rejected
(STG-028). Design: `docs/superpowers/specs/2026-10-05-v8-storage-format-design.md`.

## Test Coverage

**1226 tests** (1218 passing, 8 ignored; unit + integration + doc).
**1230 tests** (1222 passing, 8 ignored; unit + integration + doc).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1226 tests
cargo test # run 1230 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
4 changes: 2 additions & 2 deletions docs/TEST_COVERAGE.md
Original file line number Diff line number Diff line change
Expand Up @@ -4,9 +4,9 @@

**Verified**: 2026-10-05 with `cargo test --quiet`

**Result**: 1,218 passing tests and 8 ignored tests (1,226 total)
**Result**: 1,222 passing tests and 8 ignored tests (1,230 total)

This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445).
This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445).

### Covered Areas

Expand Down
Loading
Loading