From 2e21b9bcd179465a507921ddc6c103ac4f5fa025 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Mon, 21 Sep 2026 20:23:07 +0530 Subject: [PATCH 01/21] docs: design spec for index key value collision (#371, #287) Co-Authored-By: Claude Sonnet 5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- ...-09-21-index-key-value-collision-design.md | 123 ++++++++++++++++++ 1 file changed, 123 insertions(+) create mode 100644 docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md diff --git a/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md b/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md new file mode 100644 index 000000000..95e08a8d8 --- /dev/null +++ b/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md @@ -0,0 +1,123 @@ +# Index key value collision (#371, #287) — Design + +**Date**: 2026-09-21 +**Issues**: #371 (same-transaction multi-valued facts read back as one value), #287 (`EavtKey`/`AevtKey` carry no value bytes) +**Target**: file format v8, v3.0.0 milestone + +## Problem + +When one `transact` writes two values of the same attribute for one entity, both facts share +`(entity, attribute, valid_from, valid_to, tx_count)`. Two layers then discard one of them: + +1. **Index keys.** `EavtKey` and `AevtKey` have no value bytes. Colliding entries overwrite each + other in the pending `BTreeMap`s. At checkpoint, `build_sorted_index_entries` sorts them with + `sort_unstable_by`, so which colliding entry survives can differ between EAVT and AEVT. + Reads through the two paths can return different values for the same entity. +2. **Query-time dedup.** `selective_fact_fetch` (`src/query/datalog/executor.rs`) dedups fetched + facts on `(entity, attribute, tx_count, asserted)`. That key has no value either, so even with + correct indexes it keeps only the first of the colliding facts. For a batched retract, the + second retraction never reaches `net_asserted_facts`, so its assertion is never cancelled. + +A full scan (no bound entity or attribute) reads the fact pages directly and returns both values, +which is why the paths disagree. + +## Scope + +In scope: + +- Add value bytes and `asserted` to `EavtKey` and `AevtKey`. +- Add `asserted` to `AvetKey` and `VaetKey`. Both already distinguish different values (AVET has + `value_bytes`, VAET has the ref target), but an assertion and a retraction of the same value at + the same `tx_count` share a key. This is inferred from the key definitions; a test written first + must demonstrate it before the change is applied. +- File format v7 → v8, with migration. +- Add value bytes to the `seen` key in `selective_fact_fetch`. + +Out of scope: + +- Dropping v1–v6 migration code (a separate PR at v3.0.0 cut time). v1–v6 migrations stay and + chain into v8. +- Version bump, tag, and release. +- The `seen` set in `executor.rs` `Or`-branch evaluation. It keys on bound values and is not + affected. + +## Design + +### Key layout + +The new fields are appended to the end of each key, so the existing sort prefix and range-scan +order are unchanged. + +| Key | Order (v8) | +|------|-----------------------------------------------------------------------------| +| EAVT | entity, attribute, valid_from, valid_to, tx_count, **value_bytes, asserted** | +| AEVT | attribute, entity, valid_from, valid_to, tx_count, **value_bytes, asserted** | +| AVET | attribute, value_bytes, valid_from, valid_to, entity, tx_count, **asserted** | +| VAET | ref_target, attribute, valid_from, valid_to, source_entity, tx_count, **asserted** | + +`value_bytes` is `encode_value(&fact.value)`, as AVET already uses. + +Range bounds (`get_facts_by_entity`, `get_facts_by_attribute`, `lookup_eavt_*`, `lookup_aevt_*`, +and B+tree range tests) use `value_bytes: vec![]` and `asserted: false` as the minimum. Existing +upper bounds are exclusive next-entity or next-attribute keys, so they need only the same minimum +values. Inclusive upper bounds built from `tx_count: u64::MAX` (`lookup_eavt_entity_attr`) cannot +name a maximal `value_bytes`, so they would drop entries whose `tx_count` is `u64::MAX`. Those +helpers are rewritten as exclusive bounds on the next attribute, and a unit test covers the edge. + +Alternative rejected: placing `value_bytes` directly after the attribute, as AVET does. It changes +the sort order and hurts temporal range scans on entity and attribute. + +### Query-time dedup + +`selective_fact_fetch` `seen` key becomes +`(entity, attribute, tx_count, asserted, encode_value(&value))`. Both the entity-driven and +attribute-driven loops use it. + +### Format v8 and migration + +- `FORMAT_VERSION` becomes 8. The 84-byte header layout is unchanged; only `version` differs. +- On open, a v7 header forces the existing `needs_rebuild` path in `PersistentFactStorage::load`. + That path re-reads packed fact pages with real `FactRef`s (`read_all_with_refs`), rebuilds all + four B+trees with the new keys, and writes a v8 header. Fact pages are not modified. +- Idempotent under crash: the rebuild overwrites index pages before writing the header. A crash in + between leaves a v7 header whose index checksum no longer matches, so the next open rebuilds + again. +- `FileHeader::validate` still rejects versions above `FORMAT_VERSION` (`STG-006`). +- Header checksum validation applies to `version >= 7` as today. + +## Testing + +Regression tests are written first and shown failing before any fix: + +1. Issue reproduction: two values of one attribute in one transact; read through EAVT, AEVT and + full scan; after checkpoint and reopen; over several graph shapes (filler entities with two + attributes each). All three paths return both values. +2. Batched retract of both values, then checkpoint and reopen: no path returns either value. +3. Same value asserted and retracted in one `WriteTransaction`: both facts survive in all four + indexes (demonstrates the `asserted` collision, then the fix). +4. v7 → v8 migration: build a v7 fixture containing colliding values (from the current code, before + the change), open with the new code, assert v8 header and correct reads. +5. Unit tests: key ordering, range-bound minima, `encode_value` in the key, `selective_fact_fetch` + dedup with two values sharing everything but the value. +6. Update existing assertions on `FORMAT_VERSION == 7` and header version. + +Tests follow the project convention: no `{:?}` of `Result`/`Fact`/`Value` in assert messages. + +## Documentation and process + +- Update `CHANGELOG.md`, `ROADMAP.md` (move #287 work out of planned scope), `README.md` if it + cites the format version, `docs/TEST_COVERAGE.md`, `CLAUDE.md` (test count, format version), and + wiki `Architecture.md` (key layout, format v8). Wiki is committed and pushed separately. +- PR closes #371 and #287 only. No version bump or tag in this PR. +- Work in worktree `.worktrees/fix-371-index-value-collision`, branch + `fix/371-index-value-collision`. Own the PR until CI is green; do not merge without explicit + confirmation. + +## Risks + +- Larger keys (value bytes) increase index size and lower B+tree fanout for EAVT/AEVT. Measure + file size and benchmark impact on the existing suite before claiming no regression. +- Long string values inflate keys. The existing `MAX_FACT_BYTES` bound applies to facts; check + whether a key can exceed the B+tree node page size and, if so, decide on truncation with a + fact-page tiebreak or a size error. +- v8 files are unreadable by v2.x. This is the intended breaking change for v3.0.0. From c1e45aba824d7940770efc9230f11554a60e6c95 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 09:10:28 +0530 Subject: [PATCH 02/21] =?UTF-8?q?docs:=20revise=20#371=20spec=20after=20re?= =?UTF-8?q?view=20=E2=80=94=20legacy=20decoders,=20forced=20rebuild=20for?= =?UTF-8?q?=20v6/v7,=20fixtures?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- ...-09-21-index-key-value-collision-design.md | 102 +++++++++++++----- 1 file changed, 75 insertions(+), 27 deletions(-) diff --git a/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md b/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md index 95e08a8d8..aa23a80d1 100644 --- a/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md +++ b/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md @@ -36,7 +36,7 @@ In scope: Out of scope: - Dropping v1–v6 migration code (a separate PR at v3.0.0 cut time). v1–v6 migrations stay and - chain into v8. + chain into v8, with the changes under "Legacy decoders" below that keep them working. - Version bump, tag, and release. - The `seen` set in `executor.rs` `Or`-branch evaluation. It keys on bound values and is not affected. @@ -60,9 +60,11 @@ order are unchanged. Range bounds (`get_facts_by_entity`, `get_facts_by_attribute`, `lookup_eavt_*`, `lookup_aevt_*`, and B+tree range tests) use `value_bytes: vec![]` and `asserted: false` as the minimum. Existing upper bounds are exclusive next-entity or next-attribute keys, so they need only the same minimum -values. Inclusive upper bounds built from `tx_count: u64::MAX` (`lookup_eavt_entity_attr`) cannot -name a maximal `value_bytes`, so they would drop entries whose `tx_count` is `u64::MAX`. Those -helpers are rewritten as exclusive bounds on the next attribute, and a unit test covers the edge. +values. `lookup_eavt_entity`, `lookup_eavt_entity_attr` and similar `Indexes` helpers build +upper bounds from `u64::MAX` sentinels (and one from a `"zzz…"` attribute). With `value_bytes` +appended, an inclusive `tx_count: u64::MAX` bound no longer covers every key, so these helpers +switch to the exclusive next-entity / next-attribute bound that `graph/storage.rs` already uses. +Several are `#[allow(dead_code)]`; if unused outside tests they are removed instead. Alternative rejected: placing `value_bytes` directly after the attribute, as AVET does. It changes the sort order and hurts temporal range scans on entity and attribute. @@ -76,30 +78,72 @@ attribute-driven loops use it. ### Format v8 and migration - `FORMAT_VERSION` becomes 8. The 84-byte header layout is unchanged; only `version` differs. -- On open, a v7 header forces the existing `needs_rebuild` path in `PersistentFactStorage::load`. - That path re-reads packed fact pages with real `FactRef`s (`read_all_with_refs`), rebuilds all - four B+trees with the new keys, and writes a v8 header. Fact pages are not modified. -- Idempotent under crash: the rebuild overwrites index pages before writing the header. A crash in - between leaves a v7 header whose index checksum no longer matches, so the next open rebuilds - again. -- `FileHeader::validate` still rejects versions above `FORMAT_VERSION` (`STG-006`). -- Header checksum validation applies to `version >= 7` as today. +- Keys are postcard-encoded in B+tree pages. Postcard is not self-describing, so a v6 or v7 key + cannot be decoded as a v8 key. Every code path that decodes on-disk keys (`OnDiskIndexReader` + range scans, `stream_all_entries` in `save()`) must therefore never see a pre-v8 tree. +- On open, any header with `version < 8` that has B+tree index roots (v6 and v7) forces the + existing `needs_rebuild` path in `PersistentFactStorage::load`, before the index reader is wired + and before any `save()`. That path re-reads packed fact pages with real `FactRef`s + (`read_all_with_refs`), rebuilds all four B+trees with v8 keys, and writes a v8 header + (`FileHeader::new()` already uses `FORMAT_VERSION`). Fact pages are not modified. +- Crash safety: the rebuild overwrites index pages first and writes the header last. A crash in + between leaves a header with `version < 8`, so the next open rebuilds again. This rests on the + version check, not on the index checksum. +- `FileHeader::validate` still rejects versions above `FORMAT_VERSION` (`STG-006`), so v2.x opening + a v8 file fails cleanly. The upgrade is one-way and happens on first open; the CHANGELOG must say + so, since bindings users (e.g. temporal_reasoning) get the upgrade silently on open. +- WAL entries carry facts, not index keys, so a sidecar WAL on a v7 file replays unchanged after + the rebuild. +- The browser backend (`src/browser/mod.rs`, `import_graph`) uses the same + `PersistentFactStorage::load`, so it gets the migration with no separate code. + +### Legacy decoders + +The v5 → v6 migration (`migrate_v5_to_v6`) reads v5 paged-blob indexes with +`btree::read_*_index`, which postcard-decode into the current `EavtKey`/`AevtKey`/`AvetKey`/ +`VaetKey`. Changing those structs silently breaks v5 migration. The same function also builds +keys by hand when it rebuilds from facts. + +- `use_old_indexes` in `migrate_v5_to_v6` is removed: v5 indexes lack value bytes and cannot be + converted into v8 keys, so v5 migration always rebuilds from fact pages. +- The legacy `btree::read_*_index` / `write_*_index` functions then have no production caller. + They keep their own frozen `v7`-layout key types (private to `btree.rs`) so their unit tests keep + exercising the old byte layout; they are deleted in the v1–v6 cleanup PR. +- All hand-built key literals (`persistent_facts.rs` v5 path, `build_sorted_index_entries`, + `Indexes::insert`, `graph/storage.rs` range bounds, tests) go through one constructor per key + type (`EavtKey::from_fact` etc.) so a future field change cannot miss a site. +- Verify during planning that the v4 one-per-page path (`load_one_per_page_legacy` → `save()`) + and the v1 → v2 path never have non-zero B+tree roots when `save()` streams them. ## Testing Regression tests are written first and shown failing before any fix: -1. Issue reproduction: two values of one attribute in one transact; read through EAVT, AEVT and - full scan; after checkpoint and reopen; over several graph shapes (filler entities with two - attributes each). All three paths return both values. +1. Issue reproduction: two values of one attribute in one transact; read through EAVT + (`[:e :attr ?v]`), AEVT (`[?e :attr ?v]`) and full scan (`[?e ?a ?v]`), in three states: + before checkpoint (pending `BTreeMap`s), after reopen without checkpoint (WAL replay), and after + checkpoint and reopen (on-disk B+tree). Run over several graph shapes, including filler entities + with two attributes each, which is what made EAVT and AEVT disagree in the issue. All paths + return both values in all states. 2. Batched retract of both values, then checkpoint and reopen: no path returns either value. -3. Same value asserted and retracted in one `WriteTransaction`: both facts survive in all four - indexes (demonstrates the `asserted` collision, then the fix). -4. v7 → v8 migration: build a v7 fixture containing colliding values (from the current code, before - the change), open with the new code, assert v8 header and correct reads. -5. Unit tests: key ordering, range-bound minima, `encode_value` in the key, `selective_fact_fetch` - dedup with two values sharing everything but the value. -6. Update existing assertions on `FORMAT_VERSION == 7` and header version. +3. Same value asserted and retracted in one `WriteTransaction` with the same valid window: all + four indexes keep both facts. This test must fail on the current code first; if it cannot be + made to fail, `asserted` is not added to AVET/VAET and the spec is revised. +4. v7 → v8 migration, from real v7 files written by v2.0.0 code: + - The existing `tests/fixtures/compat.graph` is v7. Its native test + (`tests/cross_platform_compat_test.rs`) and browser test (`src/browser/mod.rs`) now cover + the migration path; add assertions that the header is v8 after open and that a second open + does not rebuild. + - Add a second fixture with colliding values, generated on `main` (v2.0.0) with the existing + `generate_compat_fixture` example pattern. After migration, both values read back through + all paths. The generation steps are recorded in the fixture's test doc comment. +5. v5 migration still works after the key change (existing v5 tests), now always rebuilding. +6. Maximum-size value: a fact whose value is near `MAX_FACT_BYTES` checkpoints and reads back + through all four indexes. AVET already stores full value bytes today, so this is not a new + risk class, but EAVT/AEVT separators in internal nodes now carry values too. +7. Unit tests: key ordering, range-bound minima, per-key constructors, and `selective_fact_fetch` + dedup with two facts that differ only in value. +8. Update existing assertions on `FORMAT_VERSION == 7` and header version 7. Tests follow the project convention: no `{:?}` of `Result`/`Fact`/`Value` in assert messages. @@ -115,9 +159,13 @@ Tests follow the project convention: no `{:?}` of `Result`/`Fact`/`Value` in ass ## Risks -- Larger keys (value bytes) increase index size and lower B+tree fanout for EAVT/AEVT. Measure - file size and benchmark impact on the existing suite before claiming no regression. -- Long string values inflate keys. The existing `MAX_FACT_BYTES` bound applies to facts; check - whether a key can exceed the B+tree node page size and, if so, decide on truncation with a - fact-page tiebreak or a size error. +- Larger EAVT/AEVT keys lower B+tree fanout and grow the file. Measure file size and run the + benchmark suite (`cargo bench`, not `cargo test --release`) against `main` before claiming no + regression, and record the numbers in the PR. +- Oversized entries: `build_btree` writes one entry per page when an entry exceeds the fill + threshold, but an entry larger than a page would overflow `write_leaf_page`. Facts are capped at + `MAX_FACT_BYTES` and AVET entries already carry full value bytes, so EAVT/AEVT entries have the + same bound as AVET today. Test 6 confirms this rather than assuming it. +- `encode_value` in the `selective_fact_fetch` dedup key allocates per fetched fact. Acceptable + for correctness; note it in the benchmark comparison. - v8 files are unreadable by v2.x. This is the intended breaking change for v3.0.0. From 008524d0fcc4455b694468bffa06f553e742c8a7 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 09:26:08 +0530 Subject: [PATCH 03/21] =?UTF-8?q?docs:=20#371=20spec=20=E2=80=94=20support?= =?UTF-8?q?=20only=20v7=20as=20legacy=20format,=20drop=20v1=E2=80=93v6?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- ...-09-21-index-key-value-collision-design.md | 56 +++++++++---------- 1 file changed, 28 insertions(+), 28 deletions(-) diff --git a/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md b/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md index aa23a80d1..cde3736a7 100644 --- a/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md +++ b/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md @@ -30,13 +30,14 @@ In scope: `value_bytes`, VAET has the ref target), but an assertion and a retraction of the same value at the same `tx_count` share a key. This is inferred from the key definitions; a test written first must demonstrate it before the change is applied. -- File format v7 → v8, with migration. +- File format v7 → v8, with migration. v7 (the format written by v2.0.0) is the only older + format still supported. +- Dropping support for formats v1–v6, as the v3.0.0 file-format policy in `ROADMAP.md` requires. + Doing it here avoids adapting v5 migration code to the new key types only to delete it. - Add value bytes to the `seen` key in `selective_fact_fetch`. Out of scope: -- Dropping v1–v6 migration code (a separate PR at v3.0.0 cut time). v1–v6 migrations stay and - chain into v8, with the changes under "Legacy decoders" below that keep them working. - Version bump, tag, and release. - The `seen` set in `executor.rs` `Or`-branch evaluation. It keys on bound values and is not affected. @@ -78,16 +79,15 @@ attribute-driven loops use it. ### Format v8 and migration - `FORMAT_VERSION` becomes 8. The 84-byte header layout is unchanged; only `version` differs. -- Keys are postcard-encoded in B+tree pages. Postcard is not self-describing, so a v6 or v7 key +- Keys are postcard-encoded in B+tree pages. Postcard is not self-describing, so a v7 key cannot be decoded as a v8 key. Every code path that decodes on-disk keys (`OnDiskIndexReader` range scans, `stream_all_entries` in `save()`) must therefore never see a pre-v8 tree. -- On open, any header with `version < 8` that has B+tree index roots (v6 and v7) forces the - existing `needs_rebuild` path in `PersistentFactStorage::load`, before the index reader is wired - and before any `save()`. That path re-reads packed fact pages with real `FactRef`s - (`read_all_with_refs`), rebuilds all four B+trees with v8 keys, and writes a v8 header - (`FileHeader::new()` already uses `FORMAT_VERSION`). Fact pages are not modified. +- On open, a v7 header forces the existing `needs_rebuild` path in `PersistentFactStorage::load`, + before the index reader is wired and before any `save()`. That path re-reads packed fact pages + with real `FactRef`s (`read_all_with_refs`), rebuilds all four B+trees with v8 keys, and writes + a v8 header (`FileHeader::new()` already uses `FORMAT_VERSION`). Fact pages are not modified. - Crash safety: the rebuild overwrites index pages first and writes the header last. A crash in - between leaves a header with `version < 8`, so the next open rebuilds again. This rests on the + between leaves a v7 header, so the next open rebuilds again. This rests on the version check, not on the index checksum. - `FileHeader::validate` still rejects versions above `FORMAT_VERSION` (`STG-006`), so v2.x opening a v8 file fails cleanly. The upgrade is one-way and happens on first open; the CHANGELOG must say @@ -97,23 +97,22 @@ attribute-driven loops use it. - The browser backend (`src/browser/mod.rs`, `import_graph`) uses the same `PersistentFactStorage::load`, so it gets the migration with no separate code. -### Legacy decoders - -The v5 → v6 migration (`migrate_v5_to_v6`) reads v5 paged-blob indexes with -`btree::read_*_index`, which postcard-decode into the current `EavtKey`/`AevtKey`/`AvetKey`/ -`VaetKey`. Changing those structs silently breaks v5 migration. The same function also builds -keys by hand when it rebuilds from facts. - -- `use_old_indexes` in `migrate_v5_to_v6` is removed: v5 indexes lack value bytes and cannot be - converted into v8 keys, so v5 migration always rebuilds from fact pages. -- The legacy `btree::read_*_index` / `write_*_index` functions then have no production caller. - They keep their own frozen `v7`-layout key types (private to `btree.rs`) so their unit tests keep - exercising the old byte layout; they are deleted in the v1–v6 cleanup PR. -- All hand-built key literals (`persistent_facts.rs` v5 path, `build_sorted_index_entries`, - `Indexes::insert`, `graph/storage.rs` range bounds, tests) go through one constructor per key - type (`EavtKey::from_fact` etc.) so a future field change cannot miss a site. -- Verify during planning that the v4 one-per-page path (`load_one_per_page_legacy` → `save()`) - and the v1 → v2 path never have non-zero B+tree roots when `save()` streams them. +### Dropping v1–v6 + +- `FileHeader::validate` rejects versions below 7 with a new error code (next free `STG-0xx`), + whose text names the version found and says the file must first be opened with Minigraf v2.x to + upgrade it to v7. Versions above 8 keep `STG-006`, whose text changes from + `supported: 1-{}` to `supported: 7-{}`. Both are added to `docs/ERROR_REFERENCE.md`. +- Removed: `src/storage/btree.rs` (v5 paged-blob indexes), `migrate_v1_to_v2`, + `migrate_v5_to_v6`, `load_one_per_page_legacy`, the `fact_page_format` one-per-page branch in + `load`, and the pre-v7 branches of header parsing and checksum handling (the `version >= 6`, + `version >= 7` and fact-pages-only checksum fallbacks). Their tests go with them. +- Kept: every v7 read path, since v7 is still opened (and migrated). +- All hand-built key literals (`build_sorted_index_entries`, `Indexes::insert`, + `graph/storage.rs` range bounds, tests) go through one constructor per key type + (`EavtKey::from_fact` etc.) so a future field change cannot miss a site. +- Planning must list every removed function and test, and confirm nothing else reaches the removed + code (fuzz targets, examples, benches, bindings). ## Testing @@ -137,7 +136,8 @@ Regression tests are written first and shown failing before any fix: - Add a second fixture with colliding values, generated on `main` (v2.0.0) with the existing `generate_compat_fixture` example pattern. After migration, both values read back through all paths. The generation steps are recorded in the fixture's test doc comment. -5. v5 migration still works after the key change (existing v5 tests), now always rebuilding. +5. Files with versions 1–6 fail to open with the new error code; files with version 9 fail with + `STG-006`. Neither is modified on disk. 6. Maximum-size value: a fact whose value is near `MAX_FACT_BYTES` checkpoints and reads back through all four indexes. AVET already stores full value bytes today, so this is not a new risk class, but EAVT/AEVT separators in internal nodes now carry values too. From dbf27abe0812409b8b47ead948871eb282796296 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 11:48:34 +0530 Subject: [PATCH 04/21] docs: implementation plan for #371/#287 (file format v8) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- .../2026-09-24-index-key-value-collision.md | 1120 +++++++++++++++++ 1 file changed, 1120 insertions(+) create mode 100644 docs/superpowers/plans/2026-09-24-index-key-value-collision.md diff --git a/docs/superpowers/plans/2026-09-24-index-key-value-collision.md b/docs/superpowers/plans/2026-09-24-index-key-value-collision.md new file mode 100644 index 000000000..ad0a8ad1c --- /dev/null +++ b/docs/superpowers/plans/2026-09-24-index-key-value-collision.md @@ -0,0 +1,1120 @@ +# Index Key Value Collision (#371, #287) Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Two values of one attribute written in one transaction are both stored, indexed and returned by every query path; file format moves to v8 with v7 auto-migration; v1–v6 are no longer readable. + +**Architecture:** Append `value_bytes` + `asserted` to `EavtKey`/`AevtKey` and `asserted` to `AvetKey`/`VaetKey` (sort prefix unchanged). All key construction goes through per-key constructors. A v7 file is always sent down the existing index-rebuild path on open, which writes v8 B+trees and a v8 header. The query-time dedup key in `selective_fact_fetch` gains the encoded value. v1–v6 headers are rejected with a new `STG-028`. + +**Tech Stack:** Rust (MSRV 1.89), postcard, cargo test / clippy / fmt, cargo bench (criterion). + +**Spec:** `docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md` + +## Global Constraints + +- Work only in worktree `.worktrees/fix-371-index-value-collision`, branch `fix/371-index-value-collision`. +- Never use `{:?}` of `Result`, `Fact`, `Value`, `EdnValue` or anything holding a `Uuid` in `assert!`/`assert_eq!` messages (CodeQL `rust/cleartext-logging`). Use plain strings, `unwrap`/`expect`, or count/bool asserts. +- Do not run `cargo test --release` (release profile is `panic = "abort"`); use `cargo bench` for performance. +- Every commit message ends with: + ``` + Co-Authored-By: Claude Opus 5.5 + Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ + ``` +- Commits and the PR reference `#371` and `#287`; only the PR body uses closing keywords (`Closes #371`, `Closes #287`). +- No version bump, no tag, no `release.yml` edits (cargo-dist owns it). +- New error code: `STG-028`. Retired codes: `STG-003`, `STG-004` (never reused). +- `FORMAT_VERSION = 8`, new `MIN_FORMAT_VERSION = 7`. +- The pre-push hook runs fmt + clippy + test; CI's clippy may be newer than local — run `cargo clippy --all-targets --all-features -- -D warnings` before pushing. + +## Key finding from planning (read before Task 3/4) + +On-disk B+trees are built from sorted `Vec`s (`build_sorted_index_entries` + `merge_sorted_vecs`), not `BTreeMap`s, so after a checkpoint **both** colliding entries are already on disk today. The value loss after checkpoint comes from the `selective_fact_fetch` dedup (Task 4); the EAVT/AEVT disagreement comes from `sort_unstable_by` putting the two equal-keyed entries in different orders, so "first seen" differs. The pending in-memory `BTreeMap`s (before checkpoint) lose a value through key overwrite (Task 3). Tests in each task target the state that task fixes. + +## File map + +| File | Change | +|------|--------| +| `tests/fixtures/v7_multivalue.graph` | New: v7 file with colliding values, generated by current (v2.0.0-format) code in Task 1 | +| `src/storage/mod.rs` | `FORMAT_VERSION` 8, `MIN_FORMAT_VERSION` 7, header parse/validate for v7+ only, drop `FACT_PAGE_FORMAT_ONE_PER_PAGE`, `pub mod btree` removed | +| `src/storage/btree.rs` | Deleted | +| `src/storage/persistent_facts.rs` | Remove v1/v5/one-per-page migrations and their tests; forced rebuild for `version < FORMAT_VERSION`; constructors in `build_sorted_index_entries` | +| `src/error.rs`, `docs/ERROR_REFERENCE.md` | Add `STG-028`, retire `STG-003`/`STG-004`, reword `STG-005`/`STG-006` | +| `src/storage/index.rs` | New key fields, constructors, `take_while` lookups, `max_uuid`/`lookup_eavt_entity_attr` removed | +| `src/graph/storage.rs` | Range bounds via constructors | +| `src/storage/btree_v6.rs` | Test key literals via helper | +| `src/query/datalog/executor.rs` | `selective_fact_fetch` dedup key includes value bytes | +| `tests/multi_value_test.rs` | New: issue regression (3 states), batched retract, max-size value, fixture migration | +| `tests/migration_matrix_test.rs`, `tests/btree_v6_test.rs`, `tests/wal_test.rs`, `tests/error_codes_storage_test.rs`, `tests/cross_platform_compat_test.rs`, `src/browser/mod.rs` | Legacy-version tests become rejection tests; v7 fixture tests assert v8 after open | +| `examples/generate_compat_fixture.rs` | Doc: `compat.graph` is the frozen v7 fixture; do not regenerate | +| `CHANGELOG.md`, `ROADMAP.md`, `CLAUDE.md`, `README.md`, `docs/TEST_COVERAGE.md`, `.wiki/Architecture.md` | Doc sync (Task 6) | + +--- + +### Task 1: Generate the v7 multi-value fixture (before any code change) + +The fixture must be produced by today's v7 writer, so this runs first on unmodified code. + +**Files:** +- Create: `tests/fixtures/v7_multivalue.graph` +- Scratch (not committed): `examples/gen_v7_multivalue.rs` + +**Interfaces:** +- Produces: `tests/fixtures/v7_multivalue.graph` — v7 file, one checkpoint, no WAL. Contents: `[:t/x :kind :k/a] [:t/x :kind :k/b] [:t/x :note "two"]` plus 30 filler entities `:t/f-` each with `:kind :k/c` and `:note "f"`, all in **one** transact. Then a second transact `[:t/y :tag :g/a] [:t/y :tag :g/b]` followed by a batched retract `[[:t/y :tag :g/a] [:t/y :tag :g/b]]`, then checkpoint. + +- [ ] **Step 1: Confirm the code is unmodified v7** + +Run: `git diff main --stat -- src` → Expected: no output. `grep -n "FORMAT_VERSION: u32" src/storage/mod.rs` → `= 7`. + +- [ ] **Step 2: Write the scratch generator** + +`examples/gen_v7_multivalue.rs`: +```rust +fn main() -> anyhow::Result<()> { + use std::path::PathBuf; + let dir = PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("tests/fixtures"); + let tmp = dir.join("v7_multivalue.graph.tmp"); + let _ = std::fs::remove_file(&tmp); + let _ = std::fs::remove_file(dir.join("v7_multivalue.graph.tmp.wal")); + + let db = minigraf::Minigraf::open(&tmp)?; + let mut facts = vec![ + "[:t/x :kind :k/a]".to_string(), + "[:t/x :kind :k/b]".to_string(), + r#"[:t/x :note "two"]"#.to_string(), + ]; + for i in 0..30 { + facts.push(format!("[:t/f-{i} :kind :k/c]")); + facts.push(format!(r#"[:t/f-{i} :note "f"]"#)); + } + db.execute(&format!("(transact [{}])", facts.join(" ")))?; + db.execute("(transact [[:t/y :tag :g/a] [:t/y :tag :g/b]])")?; + db.execute("(retract [[:t/y :tag :g/a] [:t/y :tag :g/b]])")?; + db.checkpoint()?; + drop(db); + let _ = std::fs::remove_file(dir.join("v7_multivalue.graph.tmp.wal")); + std::fs::rename(&tmp, dir.join("v7_multivalue.graph"))?; + Ok(()) +} +``` + +- [ ] **Step 3: Generate and verify it is v7** + +Run: `cargo run --example gen_v7_multivalue && xxd -l 8 tests/fixtures/v7_multivalue.graph` +Expected: `4d47 5246 0700 0000` (magic `MGRF`, version 7). No `.wal` sidecar left in `tests/fixtures/`. + +- [ ] **Step 4: Delete the scratch generator, commit the fixture** + +```bash +rm examples/gen_v7_multivalue.rs +git add tests/fixtures/v7_multivalue.graph +git commit -m "test: add v7 fixture with same-transaction multi-valued facts (#371, #287) + +Generated by the v7 writer at 84bf375 (v2.0.0 format). Generator source is +recorded in tests/multi_value_test.rs. + +" +``` +(The generator source from Step 2 is pasted verbatim into the doc comment of the fixture test in Task 5.) + +--- + +### Task 2: Drop support for file formats v1–v6 + +Still `FORMAT_VERSION = 7` after this task. All tests pass at the end. + +**Files:** +- Modify: `src/storage/mod.rs` (constants ~48–52, `from_bytes` ~180–285, `validate` ~288, header tests ~370–631) +- Delete: `src/storage/btree.rs`; remove `pub mod btree;` from `src/storage/mod.rs:9` +- Modify: `src/storage/persistent_facts.rs` (imports lines 9–15; `load` 207–447; delete `load_one_per_page_legacy` 449–492, `migrate_v1_to_v2` 494–568, `migrate_v5_to_v6` 570–~820; tests) +- Modify: `src/error.rs` (enum ~142–166, `REGISTRY` ~790–940, exhaustive match ~1720–1750, `ALL` list ~1910–1940) +- Modify: `docs/ERROR_REFERENCE.md` (table ~112–138, sections ~1677–1745, add STG-028 section after STG-027 ~1984) +- Modify: `tests/migration_matrix_test.rs`, `tests/btree_v6_test.rs:110-157`, `tests/wal_test.rs:~730-790`, `tests/error_codes_storage_test.rs` + +**Interfaces:** +- Produces: `pub const MIN_FORMAT_VERSION: u32 = 7;` in `crate::storage`; `ErrorCode::Stg028` with args `(found_version, MIN_FORMAT_VERSION)`. + +- [ ] **Step 1: Write failing rejection tests** + +Replace `v3_empty_migrates_without_error` in `tests/migration_matrix_test.rs` with: +```rust +/// Formats v1–v6 are no longer readable (v3.0.0 file-format policy). Opening +/// one must fail with STG-028 and must not modify the file. +#[test] +fn pre_v7_versions_are_rejected_with_stg_028() { + for version in 1u32..=6 { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("old.graph"); + let mut page = vec![0u8; PAGE_SIZE]; + page[0..4].copy_from_slice(&MAGIC_NUMBER); + page[4..8].copy_from_slice(&version.to_le_bytes()); + page[8..16].copy_from_slice(&1u64.to_le_bytes()); // page_count = 1 + std::fs::write(&path, &page).unwrap(); + + let err = match Minigraf::open(&path) { + Ok(_) => panic!("pre-v7 file must not open"), + Err(e) => e, + }; + assert_eq!(err.code(), "STG-028", "pre-v7 file must fail with STG-028"); + assert!( + err.to_string().contains("v2.x"), + "STG-028 message must tell the user how to upgrade" + ); + assert_eq!( + std::fs::read(&path).unwrap(), + page, + "rejected file must be left unmodified" + ); + } +} +``` +Add to `unsupported_version_fails_loudly` after the `is_err` assert: +```rust + assert_eq!(result.err().unwrap().code(), "STG-006"); +``` + +- [ ] **Step 2: Run to confirm failure** + +Run: `cargo test --test migration_matrix_test` +Expected: `pre_v7_versions_are_rejected_with_stg_028` FAILS (v1–v6 currently migrate); compile error for `Stg028` is NOT expected since the test only uses the code string. + +- [ ] **Step 3: Add STG-028, retire STG-003/004, reword STG-005/006 in `src/error.rs`** + +- Enum: remove `Stg003`, `Stg004`; add `Stg028` after `Stg027`. +- `REGISTRY`: delete the `Stg003` and `Stg004` rows; change the `Stg005` and `Stg006` rows and add `Stg028`: +```rust + ( + ErrorCode::Stg005, + "STG-005", + "Invalid header: expected 84 bytes, got {}", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg006, + "STG-006", + "Unsupported format version: {} (supported: 7-{})", + ErrorCategory::Storage, + ), +``` +```rust + ( + ErrorCode::Stg028, + "STG-028", + "Format version {} is no longer supported (oldest supported: {}). Open the file once with Minigraf v2.x to upgrade it to format v7, then open it with this version.", + ErrorCategory::Storage, + ), +``` +- Exhaustive `match` in `every_error_code_variant_has_a_registry_entry` and the `ALL` array: remove `Stg003`/`Stg004`, add `Stg028` after `Stg027`. + +- [ ] **Step 4: Update `docs/ERROR_REFERENCE.md`** + +- Table: delete the `STG-003` and `STG-004` rows; change `STG-005` row to `| STG-005 | Invalid header too short | Storage |`; add `| STG-028 | Format version no longer supported | Storage |` after `STG-027`. +- Directly under the table add the paragraph: + `Retired codes: STG-003 and STG-004 (pre-v7 header sizes) were retired in v3.0.0, when formats v1–v6 stopped being readable. Retired codes are never reused.` +- Delete the `### STG-003 …` and `### STG-004 …` sections. +- Replace the STG-005 section with: +```markdown +### STG-005 Invalid header too short + +**Error text**: `Invalid header: expected 84 bytes, got {}` + +**Cause**: The file declares a supported format version (7 or later) but is shorter than the 84-byte header. The file is truncated. + +**Resolution**: +- Restore from backup. If the file is newly created, delete it. See the [file format section in README](../README.md#file-format). +``` +- STG-006 section: change the Error text line to `` **Error text**: `Unsupported format version: {} (supported: 7-{})` ``. +- Add after the STG-027 section: +```markdown +### STG-028 Format version no longer supported + +**Error text**: `Format version {} is no longer supported (oldest supported: {}). Open the file once with Minigraf v2.x to upgrade it to format v7, then open it with this version.` + +**Cause**: The file was last written by Minigraf v1.x or earlier in a format older than v7. Minigraf v3.0.0 and later read only format v7 (written by v2.x) and v8. + +**Resolution**: +- Open the file once with Minigraf v2.x, which upgrades it to format v7, then open it with this version. The file is not modified by the failed open. + +**Scenario**: A `.graph` file created with Minigraf v1.x and never opened with v2.x. +``` + +- [ ] **Step 5: Header parsing and validation in `src/storage/mod.rs`** + +After `pub const FORMAT_VERSION: u32 = 7;` add: +```rust +/// Oldest file format version this library reads. Older files must first be +/// opened with Minigraf v2.x, which upgrades them to v7 (see STG-028). +pub const MIN_FORMAT_VERSION: u32 = 7; +``` +Delete `FACT_PAGE_FORMAT_ONE_PER_PAGE` (and its doc comment) and `pub mod btree;`. + +Replace `from_bytes` body from `let version = read_u32_le(bytes, 4)?;` to the end of the `header_checksum` computation with: +```rust + let version = read_u32_le(bytes, 4)?; + if version < MIN_FORMAT_VERSION { + bail_coded!(ErrorCode::Stg028, version, MIN_FORMAT_VERSION); + } + if bytes.len() < 84 { + bail_coded!(ErrorCode::Stg005, bytes.len()); + } + let page_count = read_u64_le(bytes, 8)?; + let node_count = read_u64_le(bytes, 16)?; + let last_checkpointed_tx_count = read_u64_le(bytes, 24)?; + let fact_page_count = read_u64_le(bytes, 72)?; + let header_checksum = read_u32_le(bytes, 80)?; +``` +(Keep the final `Ok(FileHeader { … })` as is.) Update the doc comment to: `Accepts only v7+ (84-byte) headers; older versions fail with STG-028.` Keep the `bytes.len() < 64` → `Stg001` check before reading the version. + +In `validate`: +```rust + if self.version < MIN_FORMAT_VERSION { + bail_coded!(ErrorCode::Stg028, self.version, MIN_FORMAT_VERSION); + } + if self.version > FORMAT_VERSION { + bail_coded!(ErrorCode::Stg006, self.version, FORMAT_VERSION); + } +``` +Update field doc comments that say "zero-initialised when reading v5/v6 or older headers" to drop that clause. + +Header unit tests in `src/storage/mod.rs`: delete `test_file_header_from_bytes_v3_accepted`, `test_file_header_v6_reads_header_checksum_zero`, `test_validate_accepts_versions_1_to_7`, `test_file_header_from_bytes_truncated_v4_rejected`, `test_file_header_v5_fact_page_format_roundtrip`, `test_v4_header_reads_fact_page_format_zero`, `test_validate_accepts_version_5`, `from_bytes_v4_too_short_returns_stg_003`, `from_bytes_v6_too_short_returns_stg_004`. Add: +```rust + #[test] + fn from_bytes_pre_v7_returns_stg_028() { + for version in 1u32..=6 { + let mut bytes = FileHeader::new().to_bytes(); + bytes[4..8].copy_from_slice(&version.to_le_bytes()); + let err = FileHeader::from_bytes(&bytes).expect_err("pre-v7 header must be rejected"); + assert_eq!(crate::error::code_of(&err), "STG-028"); + } + } + + #[test] + fn validate_pre_v7_returns_stg_028() { + let mut h = FileHeader::new(); + h.version = 6; + let err = h.validate().expect_err("v6 must be rejected"); + assert_eq!(crate::error::code_of(&err), "STG-028"); + } +``` +Before writing these, check how the existing `from_bytes_v7_too_short_returns_stg_005` test extracts the code (around line 623) and use the same helper instead of `crate::error::code_of` if it differs. + +- [ ] **Step 6: Remove legacy load paths in `src/storage/persistent_facts.rs`** + +- Imports: delete line 9 (`use crate::storage::btree::{…}`). +- In `load`: delete the `version < 2` and `version == 5` branches and the `fact_page_format == 0 || … ONE_PER_PAGE` block (`load_one_per_page_legacy` call through `return Ok(())`). Delete the now-unused `let fact_page_format = header.fact_page_format;`. Change `if header.version >= 7 && header.header_checksum != 0` (two places) to `if header.header_checksum != 0`. Change `let num_fact_pages = if header.version >= 6 && header.fact_page_count > 0` to `if header.fact_page_count > 0`. +- Delete `load_one_per_page_legacy`, `migrate_v1_to_v2`, `migrate_v5_to_v6` entirely. +- Tests: delete `make_v1_backend`, `test_migrate_v1_to_v2_assigns_defaults`, `test_migrate_v1_tx_counter_set_correctly`, `test_v4_database_migrates_to_v5_on_open`, `test_v6_migration_from_v5_unit`, `test_v6_migration_crash_safe_unit`. Replace `test_v5_migration_large_page_count_does_not_hang` (keep its fuzz-artifact doc paragraph, add one line: "Since v3.0.0 a v5 header is rejected before any page is touched.") with the same header bytes and: +```rust + let err = match PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256) { + Ok(_) => panic!("v5 header must be rejected"), + Err(e) => e, + }; + assert!(err.to_string().contains("no longer supported"), "must fail with STG-028"); +``` +- If `read_all_from_pages` in `packed_pages.rs` is now used only by `CommittedFactLoaderImpl::stream_all` (line ~89), leave it. + +- [ ] **Step 7: Rework legacy integration tests** + +- `tests/btree_v6_test.rs` (the v5 test around lines 110–157): replace with a test that writes the same v5 header, asserts `OpenOptions::new().path(&path).open()` fails with code `STG-028`, and that the file bytes are unchanged. Rename to `test_v5_file_is_rejected`. +- `tests/wal_test.rs` (v2 file test around 730–790): replace the body after building the v2 page with an assert that `Minigraf::open(&db_path)` fails with code `STG-028`. Rename the test by replacing `v2` upgrade wording with `test_v2_file_is_rejected`. +- `tests/error_codes_storage_test.rs`: add +```rust +#[test] +fn open_pre_v7_version_returns_stg_028() { + let dir = scratch_dir("pre_v7"); + let path = dir.join("db.graph"); + write_file(&path, &header_page(|b| { + b[4..8].copy_from_slice(&6u32.to_le_bytes()); // version = 6 + })); + let err = match Minigraf::open(&path) { + Ok(_) => panic!("opening a v6 file should fail"), + Err(e) => e, + }; + assert_eq!(err.code(), "STG-028"); +} +``` +(Match the imports/helpers already at the top of that file.) + +- [ ] **Step 8: Run the full suite** + +Run: `cargo test 2>&1 | tail -30` +Expected: all pass, including `registry_matches_error_reference_doc_bidirectionally`. Also run `cargo build --features browser --target wasm32-unknown-unknown` only if the target is installed (`rustup target list --installed | grep wasm32`); otherwise note it for CI. + +Also: `grep -rn "btree::\|Stg003\|Stg004\|ONE_PER_PAGE\|migrate_v" src tests fuzz benches examples` → Expected: no hits. + +- [ ] **Step 9: Commit** + +```bash +git add -A src tests docs/ERROR_REFERENCE.md +git commit -m "feat!: drop support for file formats v1–v6 (#287) + +Formats older than v7 now fail to open with STG-028, which tells the user +to open the file once with v2.x. Removes the v1→v2, one-per-page and +v5→v6 migrations and the legacy v5 B+tree module. STG-003/STG-004 are +retired. + +" +``` + +--- + +### Task 3: v8 index keys, constructors, forced v7 rebuild + +**Files:** +- Modify: `src/storage/index.rs` (keys 99–144, `Indexes::insert` 169–217, lookups 219–320, tests) +- Modify: `src/storage/persistent_facts.rs` (`build_sorted_index_entries` 1173–1260, `load` `needs_rebuild`, tests asserting version 7) +- Modify: `src/graph/storage.rs:615-760` (`get_facts_by_entity`, `get_facts_by_attribute` bounds) +- Modify: `src/storage/btree_v6.rs` tests (key literals at ~815, 1084–1330) +- Modify: `src/storage/mod.rs` (`FORMAT_VERSION = 8`, tests `test_format_version_is_7`, `test_validate_accepts_version_7`, `test_new_header_has_version_7`, `*_v7*` names/asserts) +- Modify: `tests/cross_platform_compat_test.rs`, `examples/generate_compat_fixture.rs` (doc), `src/browser/mod.rs` test + +**Interfaces:** +- Consumes: `MIN_FORMAT_VERSION` (Task 2). +- Produces (in `crate::storage::index`): + - `EavtKey { entity, attribute, valid_from, valid_to, tx_count, value_bytes: Vec, asserted: bool }` + - `AevtKey { attribute, entity, valid_from, valid_to, tx_count, value_bytes: Vec, asserted: bool }` + - `AvetKey { …existing…, asserted: bool }` (last field) + - `VaetKey { …existing…, asserted: bool }` (last field) + - `EavtKey::from_fact(&Fact) -> EavtKey`, `EavtKey::entity_start(EntityId) -> EavtKey` + - `AevtKey::from_fact(&Fact) -> AevtKey`, `AevtKey::attribute_start(&str) -> AevtKey` + - `AvetKey::from_fact(&Fact) -> AvetKey` + - `VaetKey::from_fact(&Fact) -> Option` (`None` unless value is `Value::Ref`) + +- [ ] **Step 1: Write failing unit tests in `src/storage/index.rs` tests module** + +```rust + fn fact_at(entity: Uuid, attr: &str, value: Value, asserted: bool) -> Fact { + let mut f = Fact::with_valid_time(entity, attr.to_string(), value, 100, 7, 100, VALID_TIME_FOREVER); + f.asserted = asserted; + f + } + + /// #371: two values of one attribute in one transaction must both be indexed. + #[test] + fn same_tx_multi_value_keeps_both_entries_in_all_indexes() { + let e = Uuid::from_u128(1); + let t1 = Uuid::from_u128(10); + let t2 = Uuid::from_u128(11); + let mut idx = Indexes::new(); + idx.insert(&fact_at(e, ":kind", Value::Ref(t1), true), FactRef { page_id: 0, slot_index: 0 }); + idx.insert(&fact_at(e, ":kind", Value::Ref(t2), true), FactRef { page_id: 0, slot_index: 1 }); + assert_eq!(idx.lookup_eavt_entity(e).len(), 2, "EAVT must keep both values"); + assert_eq!(idx.lookup_aevt_attr(":kind").len(), 2, "AEVT must keep both values"); + assert_eq!(idx.eavt.len(), 2); + assert_eq!(idx.aevt.len(), 2); + assert_eq!(idx.avet.len(), 2); + assert_eq!(idx.vaet.len(), 2); + } + + /// An assertion and a retraction of the same value at the same tx_count + /// must not collide in any index. + #[test] + fn same_tx_assert_and_retract_keep_both_entries_in_all_indexes() { + let e = Uuid::from_u128(1); + let t = Uuid::from_u128(10); + let mut idx = Indexes::new(); + idx.insert(&fact_at(e, ":kind", Value::Ref(t), true), FactRef { page_id: 0, slot_index: 0 }); + idx.insert(&fact_at(e, ":kind", Value::Ref(t), false), FactRef { page_id: 0, slot_index: 1 }); + assert_eq!(idx.eavt.len(), 2, "EAVT must keep assert and retract"); + assert_eq!(idx.aevt.len(), 2, "AEVT must keep assert and retract"); + assert_eq!(idx.avet.len(), 2, "AVET must keep assert and retract"); + assert_eq!(idx.vaet.len(), 2, "VAET must keep assert and retract"); + } + + #[test] + fn lookups_do_not_leak_neighbouring_entities_or_attributes() { + let (a, b) = (Uuid::from_u128(1), Uuid::from_u128(2)); + let mut idx = Indexes::new(); + idx.insert(&fact_at(a, ":x", Value::Integer(1), true), FactRef { page_id: 0, slot_index: 0 }); + idx.insert(&fact_at(b, ":x", Value::Integer(1), true), FactRef { page_id: 0, slot_index: 1 }); + idx.insert(&fact_at(a, ":xy", Value::Integer(1), true), FactRef { page_id: 0, slot_index: 2 }); + assert_eq!(idx.lookup_eavt_entity(a).len(), 2); + assert_eq!(idx.lookup_aevt_attr(":x").len(), 2); + assert_eq!(idx.lookup_avet_attr_value(":x", &Value::Integer(1)).len(), 2); + } + + #[test] + fn entity_and_attribute_start_keys_sort_before_every_matching_key() { + let e = Uuid::from_u128(5); + let f = fact_at(e, ":a", Value::Null, false); + assert!(EavtKey::entity_start(e) <= EavtKey::from_fact(&f)); + assert!(AevtKey::attribute_start(":a") <= AevtKey::from_fact(&f)); + assert!(EavtKey::entity_start(Uuid::from_u128(6)) > EavtKey::from_fact(&f)); + } +``` +Also add to `src/storage/persistent_facts.rs` tests (pending state, fails today via `BTreeMap` overwrite): +```rust + #[test] + fn same_tx_multi_value_visible_through_entity_and_attribute_lookups_before_save() { + let pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + let e = Uuid::from_u128(42); + pfs.storage() + .transact( + vec![ + (e, ":kind".to_string(), Value::Keyword(":k/a".to_string())), + (e, ":kind".to_string(), Value::Keyword(":k/b".to_string())), + ], + None, + ) + .unwrap(); + assert_eq!(pfs.storage().get_facts_by_entity(&e).unwrap().len(), 2); + assert_eq!(pfs.storage().get_facts_by_attribute(&":kind".to_string()).unwrap().len(), 2); + } +``` + +- [ ] **Step 2: Run to confirm failure** + +Run: `cargo test --lib storage::index 2>&1 | tail -20` → Expected: compile errors for `entity_start`/`attribute_start`/`from_fact`. Temporarily comment out `entity_and_attribute_start_keys_sort_before_every_matching_key` and re-run: the two collision tests FAIL (len 1 ≠ 2). Run `cargo test --lib same_tx_multi_value_visible_through` → FAILS. Uncomment afterwards. + +- [ ] **Step 3: New key fields and constructors in `src/storage/index.rs`** + +Replace the four key structs' doc comments and add fields at the end: +```rust +/// EAVT: sort by (Entity, Attribute, ValidFrom, ValidTo, TxCount, ValueBytes, Asserted) +/// +/// `value_bytes` and `asserted` come last so entity/attribute range scans keep +/// their order; they keep facts that differ only in value or assert/retract +/// from colliding (#371, #287). +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] +pub struct EavtKey { + pub entity: EntityId, + pub attribute: Attribute, + pub valid_from: i64, + pub valid_to: i64, + pub tx_count: u64, + pub value_bytes: Vec, + pub asserted: bool, +} +``` +Same pattern for `AevtKey` (doc: `(Attribute, Entity, ValidFrom, ValidTo, TxCount, ValueBytes, Asserted)`), and append `pub asserted: bool,` to `AvetKey` and `VaetKey` with `, Asserted` appended in their sort-order doc lines. + +Add constructors: +```rust +impl EavtKey { + pub fn from_fact(f: &Fact) -> Self { + EavtKey { + entity: f.entity, + attribute: f.attribute.clone(), + valid_from: f.valid_from, + valid_to: f.valid_to, + tx_count: f.tx_count, + value_bytes: encode_value(&f.value), + asserted: f.asserted, + } + } + + /// Smallest possible key for `entity`: every EAVT key of that entity sorts at or after it. + pub fn entity_start(entity: EntityId) -> Self { + EavtKey { + entity, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + value_bytes: Vec::new(), + asserted: false, + } + } +} + +impl AevtKey { + pub fn from_fact(f: &Fact) -> Self { + AevtKey { + attribute: f.attribute.clone(), + entity: f.entity, + valid_from: f.valid_from, + valid_to: f.valid_to, + tx_count: f.tx_count, + value_bytes: encode_value(&f.value), + asserted: f.asserted, + } + } + + /// Smallest possible key for `attribute`. + pub fn attribute_start(attribute: &str) -> Self { + AevtKey { + attribute: attribute.to_string(), + entity: EntityId::nil(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + value_bytes: Vec::new(), + asserted: false, + } + } +} + +impl AvetKey { + pub fn from_fact(f: &Fact) -> Self { + AvetKey { + attribute: f.attribute.clone(), + value_bytes: encode_value(&f.value), + valid_from: f.valid_from, + valid_to: f.valid_to, + entity: f.entity, + tx_count: f.tx_count, + asserted: f.asserted, + } + } +} + +impl VaetKey { + /// `None` unless the fact's value is a `Value::Ref` (only refs are VAET-indexed). + pub fn from_fact(f: &Fact) -> Option { + match &f.value { + Value::Ref(target) => Some(VaetKey { + ref_target: *target, + attribute: f.attribute.clone(), + valid_from: f.valid_from, + valid_to: f.valid_to, + source_entity: f.entity, + tx_count: f.tx_count, + asserted: f.asserted, + }), + _ => None, + } + } +} +``` +Replace `Indexes::insert` body with: +```rust + self.eavt.insert(EavtKey::from_fact(fact), fact_ref); + self.aevt.insert(AevtKey::from_fact(fact), fact_ref); + self.avet.insert(AvetKey::from_fact(fact), fact_ref); + if let Some(k) = VaetKey::from_fact(fact) { + self.vaet.insert(k, fact_ref); + } +``` +Replace the lookups (delete `lookup_eavt_entity_attr` — it has no callers — and `max_uuid`): +```rust + /// Query EAVT index for a specific entity (returns all facts for that entity). + pub fn lookup_eavt_entity(&self, entity: EntityId) -> Vec { + self.eavt + .range(EavtKey::entity_start(entity)..) + .take_while(|(k, _)| k.entity == entity) + .map(|(_, v)| *v) + .collect() + } + + /// Query AEVT index for a specific attribute (returns all facts with that attribute). + pub fn lookup_aevt_attr(&self, attribute: &str) -> Vec { + self.aevt + .range(AevtKey::attribute_start(attribute)..) + .take_while(|(k, _)| k.attribute == attribute) + .map(|(_, v)| *v) + .collect() + } + + /// Query AVET index for attribute + value. + pub fn lookup_avet_attr_value(&self, attribute: &str, value: &Value) -> Vec { + let value_bytes = encode_value(value); + let start = AvetKey { + attribute: attribute.to_string(), + value_bytes: value_bytes.clone(), + valid_from: i64::MIN, + valid_to: i64::MIN, + entity: EntityId::nil(), + tx_count: 0, + asserted: false, + }; + self.avet + .range(start..) + .take_while(|(k, _)| k.attribute == attribute && k.value_bytes == value_bytes) + .map(|(_, v)| *v) + .collect() + } + + /// Query VAET index for ref target (reverse references). + pub fn lookup_vaet_ref(&self, target: EntityId) -> Vec { + let start = VaetKey { + ref_target: target, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + source_entity: EntityId::nil(), + tx_count: 0, + asserted: false, + }; + self.vaet + .range(start..) + .take_while(|(k, _)| k.ref_target == target) + .map(|(_, v)| *v) + .collect() + } +``` +Update the existing tests in this module that build key literals (`test_eavt_key_ordering_by_entity`, `test_avet_key_orders_by_value_bytes`) by adding `value_bytes: Vec::new(), asserted: true,` / `asserted: true,`. + +- [ ] **Step 4: Use constructors everywhere else** + +- `src/storage/persistent_facts.rs` `build_sorted_index_entries`: replace each struct literal with `EavtKey::from_fact(f)`, `AevtKey::from_fact(f)`, `AvetKey::from_fact(f)`, and the VAET `filter_map` with `VaetKey::from_fact(f).map(|k| (k, fr))`. Remove `encode_value` from the import on line 15 if unused. +- `src/graph/storage.rs` `get_facts_by_entity`: `let start = EavtKey::entity_start(*entity_id);` and `let end = EavtKey::entity_start(next_entity);`. `get_facts_by_attribute`: `let start = AevtKey::attribute_start(attribute);` and `let end_opt = next_string_prefix(attribute).map(|a| AevtKey::attribute_start(&a));`. +- `src/storage/btree_v6.rs` tests: in `make_eavt` and every `EavtKey { … }` literal in the tests module, add `value_bytes: Vec::new(), asserted: true,`. +- Run `grep -rn "EavtKey {\|AevtKey {\|AvetKey {\|VaetKey {" src tests fuzz benches` → only `index.rs` (constructors, lookups, tests) and `btree_v6.rs` tests remain. + +- [ ] **Step 5: Bump to v8 and force the rebuild for v7 in `load`** + +`src/storage/mod.rs`: `pub const FORMAT_VERSION: u32 = 8;` and update the header doc comment "84 bytes in v7" → "84 bytes (v7 and v8 share the layout)". Rename/update tests: `test_format_version_is_7` → `test_format_version_is_8` asserting 8; `test_validate_accepts_version_7` keeps asserting v7 validates (v7 is still readable) and add `h.version = 8` validates; `test_new_header_has_version_7` → `_8`. + +`src/storage/persistent_facts.rs` `load`: replace the `needs_rebuild` computation with: +```rust + // v7 files carry index keys without value bytes / asserted flags; they + // cannot be decoded as v8 keys, so rebuild every index from the fact + // pages (#371, #287). The header is written last, so a crash mid-rebuild + // leaves a v7 header and the next open rebuilds again. + let needs_rebuild = if header.version < FORMAT_VERSION { + true + } else if num_fact_pages == 0 || header.eavt_root_page == 0 { + num_fact_pages > 0 // rebuild if facts exist but no index root + } else { + let backend = self + .backend + .lock() + .map_err(|_| err_coded!(ErrorCode::Stg016))?; + let total_data_pages = header.page_count.saturating_sub(1); + compute_page_checksum(&*backend, 1, total_data_pages)? != header.index_checksum + }; +``` +(This also drops the fact-pages-only checksum fallback: only v7 files could carry it, and they now always rebuild.) Add `use crate::storage::FORMAT_VERSION;` if not already imported. + +Add to `persistent_facts.rs` tests: +```rust + #[test] + fn v7_header_forces_rebuild_and_upgrades_to_v8() { + use crate::storage::FileHeader; + let e = Uuid::from_u128(7); + let mut backend = { + let mut s = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + s.storage() + .transact(vec![(e, ":n".to_string(), Value::Integer(1))], None) + .unwrap(); + s.mark_dirty(); + s.save().unwrap(); + s.into_backend().unwrap() + }; + // Downgrade the header to v7 (keys on disk are now v8-shaped, which is + // fine: the rebuild never reads them). + let mut h = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); + h.version = 7; + h.header_checksum = 0; + h.header_checksum = compute_header_checksum(&h); + let mut page = h.to_bytes(); + page.resize(PAGE_SIZE, 0); + backend.write_page(0, &page).unwrap(); + + let s = PersistentFactStorage::new(backend, 256).unwrap(); + assert_eq!(s.storage().get_facts_by_entity(&e).unwrap().len(), 1); + let b = s.into_backend().unwrap(); + let h2 = FileHeader::from_bytes(&b.read_page(0).unwrap()).unwrap(); + assert_eq!(h2.version, 8, "v7 file must be upgraded to v8 on open"); + } +``` +Check `compute_header_checksum`'s contract (line ~1119) — if it already zeroes the checksum field itself, drop the `h.header_checksum = 0;` line. + +Update remaining assertions of header version 7 in `persistent_facts.rs` tests (`test_save_writes_v4_header` and the `save() must write v7 header` assert near line 1932) to `FORMAT_VERSION`/8. + +- [ ] **Step 6: v7 compat fixture now migrates** + +- `tests/cross_platform_compat_test.rs` `fixture_readable_by_native`: after the existing asserts, add: +```rust + drop(db); + let raw = std::fs::read(&path).expect("read migrated fixture"); + let version = u32::from_le_bytes(raw[4..8].try_into().unwrap()); + assert_eq!(version, 8, "v7 fixture must be upgraded to v8 on open"); +``` + Update its doc comment: the fixture is a frozen v7 file written by v2.0.0; opening it exercises v7→v8 migration. (If `db` is used after, move the drop below the last use; if the file is only rewritten on checkpoint/close, the `drop` makes the check valid.) +- `examples/generate_compat_fixture.rs` doc: replace the "Do not regenerate it unless the v7 file format itself has changed" paragraph with: "`compat.graph` is the frozen v7 fixture written by Minigraf v2.0.0; the cross-platform tests use it to check v7→v8 migration. Do not regenerate it — running this example now writes a v8 file." Change line 1 to "Generates a `.graph` file with two known facts (the committed `compat.graph` is the frozen v7 output of this example from v2.0.0)." +- `src/browser/mod.rs` `native_fixture_readable_by_browser_db`: add after the queries: +```rust + let exported = db.export_graph().expect("export after import"); + let bytes = exported.to_vec(); + assert_eq!( + u32::from_le_bytes(bytes[4..8].try_into().unwrap()), + 8, + "v7 fixture must be upgraded to v8 on import" + ); +``` + +- [ ] **Step 7: Run tests** + +Run: `cargo test 2>&1 | tail -30` +Expected: all pass, including the four new `index.rs` tests, `same_tx_multi_value_visible_through_entity_and_attribute_lookups_before_save`, `v7_header_forces_rebuild_and_upgrades_to_v8`, and `fixture_readable_by_native`. + +- [ ] **Step 8: Commit** + +```bash +git add -A src tests examples +git commit -m "feat!: file format v8 — value bytes and asserted flag in index keys (#371, #287) + +EavtKey/AevtKey gain value_bytes and asserted; AvetKey/VaetKey gain +asserted. Fields are appended so range-scan order is unchanged. All key +construction goes through per-key constructors. A v7 file is always +re-indexed from its fact pages on open and rewritten with a v8 header. + +" +``` + +--- + +### Task 4: Query-time dedup includes the value; end-to-end regression tests + +**Files:** +- Create: `tests/multi_value_test.rs` +- Modify: `src/query/datalog/executor.rs:370-450` (`selective_fact_fetch`) + +**Interfaces:** +- Consumes: `crate::storage::index::encode_value(&Value) -> Vec` (existing). + +- [ ] **Step 1: Write the end-to-end tests** + +`tests/multi_value_test.rs`: +```rust +//! Same-transaction multi-valued facts (#371, #287): every query path must +//! return every value, before checkpoint, after WAL replay, and after +//! checkpoint + reopen. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, QueryResult, Value}; +use std::collections::BTreeSet; + +mod common; +use common::{CrashTx, run_crashing_child}; + +fn rows(r: QueryResult) -> Vec> { + match r { + QueryResult::QueryResults { results, .. } => results, + _ => panic!("expected QueryResults"), + } +} + +fn kw(v: &Value) -> String { + match v { + Value::Keyword(k) => k.clone(), + _ => panic!("expected keyword value"), + } +} + +/// Values of `attr` on the entity `ent` through EAVT (entity bound), AEVT +/// (attribute bound, joined to a marker attribute) and a full scan. +fn three_paths(db: &Minigraf, ent: &str, attr: &str, marker: &str) -> [BTreeSet; 3] { + let eavt = rows(db.execute(&format!("(query [:find ?v :where [{ent} {attr} ?v]])")).unwrap()) + .iter() + .map(|r| kw(&r[0])) + .collect(); + let aevt = rows( + db.execute(&format!( + r#"(query [:find ?v :where [?e {attr} ?v] [?e :note "{marker}"]])"# + )) + .unwrap(), + ) + .iter() + .map(|r| kw(&r[0])) + .collect(); + let scan = rows( + db.execute(&format!( + r#"(query [:find ?a ?v :where [?e ?a ?v] [?e :note "{marker}"]])"# + )) + .unwrap(), + ) + .iter() + .filter(|r| matches!(&r[0], Value::Keyword(a) if a == attr)) + .map(|r| kw(&r[1])) + .collect(); + [eavt, aevt, scan] +} + +fn setup_statements(i: usize) -> Vec { + let mut facts = vec![ + format!("[:t/x{i} :kind :k/a]"), + format!("[:t/x{i} :kind :k/b]"), + format!(r#"[:t/x{i} :note "two{i}"]"#), + ]; + for f in 0..30 { + facts.push(format!("[:t/f{i}-{f} :kind :k/c]")); + facts.push(format!(r#"[:t/f{i}-{f} :note "f"]"#)); + } + vec![format!("(transact [{}])", facts.join(" "))] +} + +fn both() -> BTreeSet { + [":k/a", ":k/b"].iter().map(|s| s.to_string()).collect() +} + +#[test] +fn multi_value_visible_on_every_path_before_checkpoint() { + let db = Minigraf::in_memory().unwrap(); + for s in setup_statements(0) { + db.execute(&s).unwrap(); + } + for (name, got) in ["eavt", "aevt", "scan"].iter().zip(three_paths(&db, ":t/x0", ":kind", "two0")) { + assert_eq!(got, both(), "{name} path must return both values before checkpoint"); + } +} + +#[test] +fn multi_value_visible_on_every_path_after_checkpoint_and_reopen() { + // Several graph shapes: the issue saw EAVT and AEVT disagree depending on content. + for i in 0..8 { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + { + let db = Minigraf::open(&path).unwrap(); + for s in setup_statements(i) { + db.execute(&s).unwrap(); + } + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + let x = format!(":t/x{i}"); + let marker = format!("two{i}"); + for (name, got) in ["eavt", "aevt", "scan"].iter().zip(three_paths(&db, &x, ":kind", &marker)) { + assert_eq!(got, both(), "{name} path must return both values after reopen"); + } + } +} + +#[test] +fn multi_value_visible_on_every_path_after_wal_replay() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + let stmts = setup_statements(0); + let refs: Vec<&str> = stmts.iter().map(String::as_str).collect(); + run_crashing_child(&path, 1_000_000, &refs, CrashTx::Implicit); + let db = Minigraf::open(&path).unwrap(); + for (name, got) in ["eavt", "aevt", "scan"].iter().zip(three_paths(&db, ":t/x0", ":kind", "two0")) { + assert_eq!(got, both(), "{name} path must return both values after WAL replay"); + } +} + +#[test] +fn batched_retract_of_both_values_hides_both_on_every_path() { + for i in 0..8 { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + { + let db = Minigraf::open(&path).unwrap(); + for s in setup_statements(i) { + db.execute(&s).unwrap(); + } + db.checkpoint().unwrap(); + } + { + let db = Minigraf::open(&path).unwrap(); + db.execute(&format!("(retract [[:t/x{i} :kind :k/a] [:t/x{i} :kind :k/b]])")) + .unwrap(); + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + let x = format!(":t/x{i}"); + let marker = format!("two{i}"); + for (name, got) in ["eavt", "aevt", "scan"].iter().zip(three_paths(&db, &x, ":kind", &marker)) { + assert!(got.is_empty(), "{name} path must hide both retracted values"); + } + } +} +``` +Note: `tests/common/mod.rs` dispatches the crash child via a test named `common::crash_child_entrypoint`; check how `wal_test.rs` includes `common` and mirror it exactly (some binaries need an extra `#[test]` shim — copy whatever `wal_test.rs` does). + +- [ ] **Step 2: Run to confirm failure** + +Run: `cargo test --test multi_value_test 2>&1 | tail -30` +Expected: `…_after_checkpoint_and_reopen` and `batched_retract_…` FAIL (dedup drops a value / leaves a retracted value visible); `…_before_checkpoint` and `…_after_wal_replay` may already PASS after Task 3 — record which. + +- [ ] **Step 3: Fix the dedup key in `selective_fact_fetch`** + +In `src/query/datalog/executor.rs`, update the doc line `deduplicated by (entity, attribute, tx_count, asserted)` to `deduplicated by (entity, attribute, tx_count, asserted, value)`, then replace the `seen` declaration comment and type, and both key constructions: +```rust + // Dedup key: (entity, attribute, tx_count, asserted, encoded value). + // `asserted` keeps an assertion and a retraction from the same + // WriteTransaction apart; the encoded value keeps two values of one + // attribute written in the same transaction apart (#371). Uses + // `encode_value` bytes rather than `Value` to avoid Float hashing. + let mut seen: HashSet<(uuid::Uuid, String, u64, bool, Vec)> = HashSet::new(); +``` +```rust + let key = ( + fact.entity, + fact.attribute.clone(), + fact.tx_count, + fact.asserted, + crate::storage::index::encode_value(&fact.value), + ); +``` +(both loops). + +Add a unit test next to existing `selective_fact_fetch` tests (search `selective_fact_fetch` in the executor tests module; if none exist, the integration tests above are the coverage and no unit test is added). + +- [ ] **Step 4: Run tests** + +Run: `cargo test --test multi_value_test && cargo test 2>&1 | tail -15` +Expected: all pass. + +- [ ] **Step 5: Commit** + +```bash +git add tests/multi_value_test.rs src/query/datalog/executor.rs +git commit -m "fix: keep same-transaction multi-valued facts through query-time dedup (#371) + +selective_fact_fetch deduplicated on (entity, attribute, tx_count, +asserted), which collapsed two values written in one transaction and left +one half of a batched retract un-cancelled. The key now includes the +encoded value. + +" +``` + +--- + +### Task 5: v7 multi-value fixture migration and maximum-size values + +**Files:** +- Modify: `tests/multi_value_test.rs` + +**Interfaces:** +- Consumes: `tests/fixtures/v7_multivalue.graph` (Task 1), migration (Task 3), dedup fix (Task 4). + +- [ ] **Step 1: Add the tests** + +Append to `tests/multi_value_test.rs`: +```rust +/// `tests/fixtures/v7_multivalue.graph` was written by the v7 writer at +/// 84bf375 (v2.0.0 format) with this generator: +/// +/// ```ignore +/// +/// ``` +/// +/// Opening it must migrate to v8 and return both values on every path, and +/// the batched retract of `:t/y`'s two `:tag` values must hide both. +#[test] +fn v7_multivalue_fixture_migrates_and_reads_correctly() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("v7.graph"); + std::fs::write(&path, include_bytes!("fixtures/v7_multivalue.graph")).unwrap(); + + { + let db = Minigraf::open(&path).unwrap(); + for (name, got) in ["eavt", "aevt", "scan"].iter().zip(three_paths(&db, ":t/x", ":kind", "two")) { + assert_eq!(got, both(), "{name} path must return both values after migration"); + } + let tags = rows(db.execute("(query [:find ?v :where [:t/y :tag ?v]])").unwrap()); + assert!(tags.is_empty(), "batched retract in the v7 file must hide both values"); + } + + let raw = std::fs::read(&path).unwrap(); + assert_eq!(u32::from_le_bytes(raw[4..8].try_into().unwrap()), 8, "file must be v8 after open"); + + // Second open is a plain v8 open (no rebuild) and reads the same. + let db = Minigraf::open(&path).unwrap(); + for (name, got) in ["eavt", "aevt", "scan"].iter().zip(three_paths(&db, ":t/x", ":kind", "two")) { + assert_eq!(got, both(), "{name} path must return both values on second open"); + } +} + +/// Index entries now carry the value bytes; a near-maximum string value must +/// still checkpoint and read back through every index. +#[test] +fn near_max_size_values_checkpoint_and_read_back() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("big.graph"); + let big_a = "a".repeat(3_800); + let big_b = "b".repeat(3_800); + { + let db = Minigraf::open(&path).unwrap(); + db.execute(&format!( + r#"(transact [[:t/big :blob "{big_a}"] [:t/big :blob "{big_b}"] [:t/big :note "big"]])"# + )) + .unwrap(); + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + let by_entity = rows(db.execute("(query [:find ?v :where [:t/big :blob ?v]])").unwrap()); + assert_eq!(by_entity.len(), 2, "EAVT path must return both large values"); + let by_attr = rows(db.execute(r#"(query [:find ?v :where [?e :blob ?v] [?e :note "big"]])"#).unwrap()); + assert_eq!(by_attr.len(), 2, "AEVT path must return both large values"); + let by_value = rows(db.execute(&format!(r#"(query [:find ?e :where [?e :blob "{big_a}"]])"#)).unwrap()); + assert_eq!(by_value.len(), 1, "AVET path must find the large value"); +} +``` +Before settling on 3 800, check `MAX_FACT_BYTES` (`src/storage/packed_pages.rs:48`) and the transact path's size check: pick the largest string length that still transacts successfully today (try 3 800; if the transact fails with a size error, lower it in steps of 100 and note the chosen value in a comment). The point is a value whose fact is within ~300 bytes of `MAX_FACT_BYTES`. + +- [ ] **Step 2: Run** + +Run: `cargo test --test multi_value_test 2>&1 | tail -20` +Expected: both new tests pass. If `near_max_size_values_checkpoint_and_read_back` fails inside `build_btree`/`write_leaf_page` (entry larger than a page), STOP and report — the spec's oversized-entry risk has materialised and needs a design decision. + +- [ ] **Step 3: Commit** + +```bash +git add tests/multi_value_test.rs +git commit -m "test: v7 multi-value fixture migration and near-max-size values (#371, #287) + +" +``` + +--- + +### Task 6: Benchmarks and documentation sync + +**Files:** +- Modify: `CHANGELOG.md`, `ROADMAP.md`, `CLAUDE.md`, `README.md`, `docs/TEST_COVERAGE.md`, `docs/BENCHMARKS.md` (only if the numbers are recorded there) +- Modify (separate repo): `.wiki/Architecture.md` in the **main checkout** (`/home/aditya/Work/AMC/Minigraf/minigraf/.wiki`) — it is not inside the worktree + +- [ ] **Step 1: Benchmark comparison** + +```bash +cargo bench --bench minigraf_bench -- --save-baseline v8 2>&1 | tail -40 +``` +Then in a throwaway worktree of `main` (`git worktree add /tmp/claude-1000/…/scratchpad/main-bench main`), run `cargo bench --bench minigraf_bench -- --save-baseline v7` and compare with `critcmp` if installed, or record both criterion summaries. Also record file size for 10 000 facts on both (write a tiny scratch example that transacts 10 000 facts, checkpoints, prints `std::fs::metadata(path).len()`; do not commit it). Remove the throwaway worktree afterwards. Put the numbers in the PR description. + +- [ ] **Step 2: CHANGELOG.md** — under an `## [Unreleased]` section (create it at the top if missing, following the file's existing heading style): +```markdown +### 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. +- **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 retired. `STG-005` and `STG-006` message text changed. + +### Fixed +- Two values of the same attribute written in one transaction are both returned by every query path. Previously only one came back, and entity-bound and attribute-bound queries could return different ones (#371, #287). +- A retract that removes several values of one attribute in one call now hides all of them (#371). +``` +- [ ] **Step 3: ROADMAP.md** — in "v3.0.0 — File Format Policy": replace the first paragraph's future tense with a statement that #287/#371 landed: format v8, v7 migration, v1–v6 dropped; remove "The v1–v6 → v7 auto-migration code … can be removed when cutting this release; a v7→v8 migration replaces it." In Scope, mark the `#287` line as done (follow the file's existing done-marker convention; if none, change to "- ✅ `EavtKey`/`AevtKey` value-bytes fix, format v8, v7→v8 migration, v1–v6 dropped (#287, #371)"). +- [ ] **Step 4: CLAUDE.md** — Module Structure: `mod.rs` "`FileHeader` v8 (84 bytes)"; remove the `btree.rs` line; `persistent_facts.rs` "v8 save/load, auto-migration v7→v8"; "### File Format (v8)" and replace "Auto-migrates v1/v2/…/v6 → v7 on open/checkpoint." with "Auto-migrates v7 → v8 on open (index rebuild). v1–v6 are rejected (STG-028)."; update the test count line with the exact numbers from `cargo test 2>&1 | grep -E "^test result"` summed (passed, ignored). +- [ ] **Step 5: README.md** — `grep -n "v7\|format version\|migrat" README.md`; update any file-format section to v8 and the supported-versions statement. +- [ ] **Step 6: docs/TEST_COVERAGE.md** — add `tests/multi_value_test.rs` (6 tests) and update per-file counts for the files changed in Tasks 2–5 and the total, matching `CLAUDE.md`. +- [ ] **Step 7: Cross-check** — `grep -rn "v7\b\|1-7\|v1–v6\|FORMAT_VERSION" CLAUDE.md ROADMAP.md README.md CHANGELOG.md docs/TEST_COVERAGE.md` and confirm no doc contradicts another. +- [ ] **Step 8: Commit docs** + +```bash +git add CHANGELOG.md ROADMAP.md CLAUDE.md README.md docs/TEST_COVERAGE.md +git commit -m "docs: file format v8, v1–v6 dropped, multi-value fix (#371, #287) + +" +``` +- [ ] **Step 9: Wiki** — in `/home/aditya/Work/AMC/Minigraf/minigraf/.wiki`: update `Architecture.md` (key layouts table with the new trailing fields, format v8, migration policy). Do **not** commit/push the wiki until the PR is approved for merge; note it in the PR description as a pending follow-up. + +--- + +### Task 7: Verify, push, PR + +- [ ] **Step 1: Full verification** + +```bash +cargo fmt --all -- --check +cargo clippy --all-targets --all-features -- -D warnings +cargo test 2>&1 | grep -E "^test result|FAILED|panicked" +cargo doc --no-deps 2>&1 | grep -i warning +``` +Expected: fmt clean, clippy clean, every `test result: ok`, no doc warnings. Also `cd fuzz && cargo check` if the fuzz crate builds locally (it references storage types via the public API only — confirm it still compiles). + +- [ ] **Step 2: Push and open the PR** + +```bash +git push -u origin fix/371-index-value-collision +gh pr create --title "fix!: file format v8 — keep same-transaction multi-valued facts (#371, #287)" --body-file /pr-body.md +``` +PR body: summary of root causes (pending `BTreeMap` overwrite, query-time dedup without value, unstable sort order), what changed (key fields, v8 + v7 rebuild, v1–v6 dropped, STG-028, retired STG-003/004), test list, benchmark and file-size numbers from Task 6, "Wiki `Architecture.md` update pending merge", `Closes #371`, `Closes #287`, and end with: +``` +🤖 Generated with [Claude Code](https://claude.com/claude-code) + +https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ +``` + +- [ ] **Step 3: Own CI until green** — watch `gh pr checks --watch`; fix every failure (clippy on CI's newer stable, wasm/browser build, CodeQL). Do not merge without explicit user confirmation. Keep the worktree until the PR is merged. From 4bd6997db128504d907004cfa5f4fe80cef1caf1 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 11:50:54 +0530 Subject: [PATCH 05/21] test: add v7 fixture with same-transaction multi-valued facts (#371, #287) Generated by the v7 writer at 84bf375 (v2.0.0 format). Generator source is recorded in tests/multi_value_test.rs. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- tests/fixtures/v7_multivalue.graph | Bin 0 -> 49152 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 tests/fixtures/v7_multivalue.graph diff --git a/tests/fixtures/v7_multivalue.graph b/tests/fixtures/v7_multivalue.graph new file mode 100644 index 0000000000000000000000000000000000000000..fb0d07c7c228dc262093333ca1be6476867f3def GIT binary patch literal 49152 zcmeI5dvMg%702&QHt)y&5Ri9BAR(|MB&^v00YjiOwiSbsM<5ai2?$smUeeOeKnoER zaL9lKv_2w=;#6%_1_VJW0y3Z|sk}f8L#hVWGFUTVt&a<-t#Lv1Fsx;;ro&nv8&q3jL+W8zOJPli^-N4iZHWo0 zg|L>wng;8c=%CsZ9a0Nn9SUn2tf!(vYEx8DEr4|>tSPXb@&(lfUq~&0wFK4_SU-;p zsSS}qRSjzitnDN7)MpWS>WzpTwHPFi|Fr|o`%5yL@BPQn;hXA@UHGcQk-ffxnUxcx zd<7G8s?HvLcj=P6NOk!ed}wtIyz=|uRc9KiM;zI{;+e-MecM7`tA*>H>3M_ttbGytpB>?$l1D~GuC&V-oI`BD`V|#=nfBUj`UcxVCsspy-#)g@N#_B zs(`%>-Ql5)E=%m|n|0Txk0$?Xa85@2Gxj!ghle&(x1YOMRWx$@>)U!h*|%`lQ}#A= zhle%~6n|5^Z$jy7n|*z^6s+tq-QI@o@X+R~K^t04-!p87054oxolW7g?>dmFmLLz{xY!QR24!^XXm z@sqsHGgLc!8@j_oo2idnnDgYp5qCWH$c)9qp01x`Z$o!@Xfx^QwL9u}4QsYO`1ib+ zNx$&$|1`S8Lz{LB7p-o&X5_s~(x;3*aP+fc`>UZlJhZ9aR-2Xg^N}lG$WK3cym?Z( zy$#*rq0PL0FHUiK-(B+Pxo1}2_1?fi_BM2fhc<&RrLx1l>cw0VAR#@#m^AF_XW-L&I1h3|Wq0(6ImHggN> zHlICER`+~$bGy>@3#3i^r8u zeq!l_DW49i-ezw@cX()XG^S;b{awZ!u00erYEi}Jz4kVAhle%~oj>ur((M)g+SO|D z+S(J%>}}`{4{e_9GHr71hvf^l^jbA1wJ7dQdmFmLLz_z-GSBV4fB3N#Z*_RR|K7xY z_BM2fhc<5?%1^jw_s}uRUwOB%wC-oO+uP6`9@^Bj&8W_LZp=rIo$OeeKJSH)y$#*r zp-pU0Rr0}~hA&_Jd4BAlhittvY$9jQn(F%Yp6+RCRQ2C%s&w0wrUo{B*MHC-P%ne3 zK_fvuKt9l4lLP8i(1W0IP!JRgI+7Gn>p+V^V?p_#M9?RR0ksiS0~!x106Cx&2?6yc z=n>E)P$8%V=wy5V&IJN$CFnlTKu~MY>9~N}0eT!X4Rjl*J*Yl5pmu?3K{G+OgHk~k zVghOp=vmM&L4!eom~<5l`df52wGOm68lEdCACw6CBnqA@s0K71Q~;8PI3Ny)1J`!I z;Xme*^BtYz(EkXA&x9x$%aGx@PstdE9_R2i`!OV6v#&$n;qWz+8IrG=VY1Z0Ss{+J`O#6;cI3wBww?;LqB8jHE(7}zGh2@o<;FBdoUzlGuxr> z(D|D249VAwbLc4(Uo*gve9dkSeN)WW^f4q~Gt!|Sg7}(=49V9_aOmkLUo*&%e9fK? zJxk$hrZ6O5vx7qqPWYPb8IrHr&Y>Up`I;>llCRm^p+_Qo&DIRb*KFm`??U*Rg$&8p zyw#zH>wL{ThU9DB;?RRfzGgZ@@-;g<^pugW*@+?fnrRL_?&WKCWk|kerbAEM_?m4Q zlCRmuq36YX%`Obd*UWI}aVlRkl_B|>9Uc0)oUa+dkbF(;nN$w_Hj3|_&yalgP+C)R zU#alte|d-l;($0H4u}KdfH)uyhy&t)I3Ny)1LD9B#R2BKDgLA&w-bE+zjCdA_&WaZ z<1hZMjX%i$iUZ<+I3Ny)1LA-iKOL?C zxCA->I?x)>Y|s!;SI}k1`tJw52zoFoT~&elM0LBNf3Nc7!~t>O25_L^?i3^wPDAMZ zdGNd0au3Xa#;eoFT&LFt9-ry^WS-tgM(QxR@F&_LR! zVic10sn`ce`&8_XqyL~D)N76nOTOnzmink(ZUVlMf`z=>U;|4I4?2M#&tpp|EGW&+t zZl8*oNZO}j8zk*hF#}2aRP2bPd1V28Mana&kuj*FM6D1LA-o1F2|$|ar{eH=*718sqUCY-U5X z#)LcvoAFSsF(l8yWRe-*mJNMFx47k_8e^HLAA#Gd^q-5WhTFl|Q@O0Q>8sCMd^AD0x1z6(zWFQ)We zcshGAtM9_o@r#Ll7oJXF%X5--V}h7&H7XJRQZDNZS-gunUwEm`TIaO16>8lFexwF?hu{EErv zn>lN$hfnEvKNRjrmmbmL?VmW9p3laH^Z!@A|BuCA-~oU4>-MXZ#^QiDAP$HF;($0H z4u}KdfH)uyhy&t)IN;F%_W&z70Z8*$QZR8q91sV@0dYVa5C_BoaX=gp2gCt!Kpgnt GI`AJiwFlP# literal 0 HcmV?d00001 From c5298964ce1c1bb2f75af54329b78248bf347b42 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 12:07:13 +0530 Subject: [PATCH 06/21] =?UTF-8?q?feat!:=20drop=20support=20for=20file=20fo?= =?UTF-8?q?rmats=20v1=E2=80=93v6=20(#287)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Formats older than v7 now fail to open with STG-028, which tells the user to open the file once with v2.x. Removes the v1→v2, one-per-page and v5→v6 migrations and the legacy v5 B+tree module. STG-003/STG-004 are retired. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- docs/ERROR_REFERENCE.md | 50 +-- src/error.rs | 31 +- src/storage/btree.rs | 547 ------------------------- src/storage/mod.rs | 187 ++------- src/storage/persistent_facts.rs | 657 +----------------------------- tests/btree_v6_test.rs | 56 +-- tests/error_codes_storage_test.rs | 17 + tests/migration_matrix_test.rs | 45 +- tests/wal_test.rs | 54 +-- 9 files changed, 157 insertions(+), 1487 deletions(-) delete mode 100644 src/storage/btree.rs diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index d4b1fe9df..98378d009 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -111,9 +111,7 @@ with no `CodedError` anywhere in its chain. | QRY-009 | Rules lock poisoned | Query Execution | | STG-001 | Invalid header: too short | Storage | | STG-002 | Invalid magic number: not a .graph file | Storage | -| STG-003 | Invalid v4/v5/v6 header too short | Storage | -| STG-004 | Invalid v6 header too short | Storage | -| STG-005 | Invalid v7 header too short | Storage | +| STG-005 | Invalid header too short | Storage | | STG-006 | Unsupported format version | Storage | | STG-007 | page_count must be greater than 0 | Storage | | STG-008 | eavt_root_page must be less than page_count | Storage | @@ -136,6 +134,7 @@ with no `CodedError` anywhere in its chain. | STG-025 | Database already open in this process | Storage | | STG-026 | Database locked by another process | Storage | | STG-027 | Filesystem does not support file locking | Storage | +| STG-028 | Format version no longer supported | Storage | | WAL-001 | Invalid WAL magic number | WAL | | WAL-002 | Unsupported WAL version | WAL | | WAL-003 | Fact serialised size exceeds maximum | WAL | @@ -208,6 +207,8 @@ with no `CodedError` anywhere in its chain. | INT-054 | Unstratifiable negative recursion cycle | Internal | | INT-055 | Rule predicate disappeared during rollback | Internal | +Retired codes: STG-003 and STG-004 (pre-v7 header sizes) were retired in v3.0.0, when formats v1–v6 stopped being readable. Retired codes are never reused. + --- ## PRS — Parser Errors @@ -1696,42 +1697,18 @@ See the [file format section in README](../README.md#file-format) for version hi **Scenario**: `Minigraf::open("config.json")` — a wrong file path was passed. -### STG-003 Invalid v4/v5/v6 header too short - -**Error text**: `Invalid v4/v5/v6 header: expected at least 72 bytes, got {}` - -**Cause**: A file identified as format version 4, 5, or 6 is too short to hold a valid header of that version. The file is truncated at the header. - -**Resolution**: -- Restore from backup. If the file is newly created, delete it. See the [file format section in README](../README.md#file-format). - -**Scenario**: A v5-format `.graph` file was corrupted by a partial write and is missing the latter part of its header. - -### STG-004 Invalid v6 header too short - -**Error text**: `Invalid v6 header: expected 80 bytes, got {}` - -**Cause**: A file identified as format version 6 is shorter than the required 80-byte v6 header. The file is truncated. - -**Resolution**: -- Restore from backup. If the file is newly created, delete it. See the [file format section in README](../README.md#file-format). - -**Scenario**: A v6-format `.graph` file was written by an older pre-release version and its header is incomplete. +### STG-005 Invalid header too short -### STG-005 Invalid v7 header too short +**Error text**: `Invalid header: expected 84 bytes, got {}` -**Error text**: `Invalid v7 header: expected 84 bytes, got {}` - -**Cause**: A file identified as format version 7 (current format) is shorter than the required 84-byte header. The file is truncated. +**Cause**: The file declares a supported format version (7 or later) but is shorter than the 84-byte header. The file is truncated. **Resolution**: - Restore from backup. If the file is newly created, delete it. See the [file format section in README](../README.md#file-format). -**Scenario**: A v7-format `.graph` file was partially written by a crash during header initialisation. - ### STG-006 Unsupported format version -**Error text**: `Unsupported format version: {} (supported: 1-{})` +**Error text**: `Unsupported format version: {} (supported: 7-{})` **Cause**: The file was written by a newer version of Minigraf than is currently installed. The format version number in the header is outside the range this library can read. @@ -1984,6 +1961,17 @@ See the [file format section in README](../README.md#file-format) for version hi **NFSv3 `nolock` is not covered by this error — it is a silent, undetectable gap (#334).** An export explicitly mounted with `-o nolock` behaves differently from plain "no `lockd`": the Linux NFS client serves `flock`/OFD locks out of its own local, in-kernel lock table instead of going over NLM to the server. `try_lock` sees an ordinary local success, `classify` takes the same branch it would on a filesystem where locking genuinely works, and this error is never raised — `allow_unlocked` is never consulted because the code never learns the mount can't really lock. Two separate client hosts writing the same `nolock` export each get a false `Ok(())` from their own kernel with zero cross-host coordination, and can silently corrupt the file. There is no way to detect this from inside `try_lock`'s result, so `nolock` NFSv3 exports are an unsupported deployment for multi-writer use, the same way running mixed Minigraf versions against one file is unsupported (see the kernel-locking CHANGELOG entry) — avoid `nolock` exports rather than relying on this check to catch them. +### STG-028 Format version no longer supported + +**Error text**: `Format version {} is no longer supported (oldest supported: {}). Open the file once with Minigraf v2.x to upgrade it to format v7, then open it with this version.` + +**Cause**: The file was last written by Minigraf v1.x or earlier in a format older than v7. Minigraf v3.0.0 and later read only format v7 (written by v2.x) and v8. + +**Resolution**: +- Open the file once with Minigraf v2.x, which upgrades it to format v7, then open it with this version. The file is not modified by the failed open. + +**Scenario**: A `.graph` file created with Minigraf v1.x and never opened with v2.x. + --- ## WAL — Write-Ahead Log Errors diff --git a/src/error.rs b/src/error.rs index 6c781ace8..6f7a3006a 100644 --- a/src/error.rs +++ b/src/error.rs @@ -138,8 +138,6 @@ pub(crate) enum ErrorCode { Int000, Stg001, Stg002, - Stg003, - Stg004, Stg005, Stg006, Stg007, @@ -163,6 +161,7 @@ pub(crate) enum ErrorCode { Stg025, Stg026, Stg027, + Stg028, Wal001, Wal002, Wal003, @@ -786,28 +785,16 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "Invalid magic number: not a .graph file", ErrorCategory::Storage, ), - ( - ErrorCode::Stg003, - "STG-003", - "Invalid v4/v5/v6 header: expected at least 72 bytes, got {}", - ErrorCategory::Storage, - ), - ( - ErrorCode::Stg004, - "STG-004", - "Invalid v6 header: expected 80 bytes, got {}", - ErrorCategory::Storage, - ), ( ErrorCode::Stg005, "STG-005", - "Invalid v7 header: expected 84 bytes, got {}", + "Invalid header: expected 84 bytes, got {}", ErrorCategory::Storage, ), ( ErrorCode::Stg006, "STG-006", - "Unsupported format version: {} (supported: 1-{})", + "Unsupported format version: {} (supported: 7-{})", ErrorCategory::Storage, ), ( @@ -936,6 +923,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "Failed to lock database at {}: {}. This filesystem does not support file locking (common on NFSv3 without lockd, and on some FUSE mounts). Set `allow_unlocked` in `OpenOptions` to open anyway — that accepts the risk that concurrent writers corrupt the file.", ErrorCategory::Storage, ), + ( + ErrorCode::Stg028, + "STG-028", + "Format version {} is no longer supported (oldest supported: {}). Open the file once with Minigraf v2.x to upgrade it to format v7, then open it with this version.", + ErrorCategory::Storage, + ), ( ErrorCode::Wal001, "WAL-001", @@ -1719,8 +1712,6 @@ mod tests { | ErrorCode::Qry009 | ErrorCode::Stg001 | ErrorCode::Stg002 - | ErrorCode::Stg003 - | ErrorCode::Stg004 | ErrorCode::Stg005 | ErrorCode::Stg006 | ErrorCode::Stg007 @@ -1744,6 +1735,7 @@ mod tests { | ErrorCode::Stg025 | ErrorCode::Stg026 | ErrorCode::Stg027 + | ErrorCode::Stg028 | ErrorCode::Wal001 | ErrorCode::Wal002 | ErrorCode::Wal003 @@ -1909,8 +1901,6 @@ mod tests { ErrorCode::Qry009, ErrorCode::Stg001, ErrorCode::Stg002, - ErrorCode::Stg003, - ErrorCode::Stg004, ErrorCode::Stg005, ErrorCode::Stg006, ErrorCode::Stg007, @@ -1934,6 +1924,7 @@ mod tests { ErrorCode::Stg025, ErrorCode::Stg026, ErrorCode::Stg027, + ErrorCode::Stg028, ErrorCode::Wal001, ErrorCode::Wal002, ErrorCode::Wal003, diff --git a/src/storage/btree.rs b/src/storage/btree.rs deleted file mode 100644 index 9e4db54e1..000000000 --- a/src/storage/btree.rs +++ /dev/null @@ -1,547 +0,0 @@ -//! Legacy v5 B+tree serialisation — kept for v5→v7 file format migration only. -//! The write_* functions are no longer called in production; they exist -//! only to support tests that verify round-trip serialisation. -// Suppress dead-code warnings: this entire module is legacy v5 code; the write_* -// functions are only invoked by the unit tests in this file. -#![allow(dead_code)] -//! B+tree page serialisation for covering index persistence. -//! -//! `write_*_index` writes a `BTreeMap` to B+tree leaf pages starting -//! at `start_page_id` on the backend. Returns the root page ID. -//! `read_*_index` is the inverse — reads all entries back into a BTreeMap. -//! -//! # Page layout -//! -//! Because `StorageBackend::write_page` / `read_page` require exactly -//! `PAGE_SIZE` (4096) bytes, this module uses a simple paged-blob strategy: -//! -//! * Each index is serialised to a single postcard byte-string. -//! * That byte-string is split into chunks of `DATA_BYTES_PER_PAGE` bytes. -//! * Each chunk is stored in one backend page with the following header: -//! -//! ```text -//! Offset Size Field -//! 0 1 page_type (0x11 = index data page) -//! 1 4 total_byte_len (u32 LE, only meaningful in the first page) -//! 5 4 chunk_byte_len (u32 LE, number of valid bytes in this page) -//! 9 1 is_last_page (0x00 = more pages follow, 0x01 = last page) -//! 10 4082 data bytes (padded with zeros if chunk_byte_len < 4082) -//! ``` -//! -//! `total_byte_len` in page 0 tells the reader how many bytes to expect in -//! total so it can pre-allocate and know when it's done. -//! -//! Phase 6.1 uses these only for save/load. In-memory BTreeMaps handle queries. - -use crate::error::{ErrorCode, bail_coded, err_coded}; -use anyhow::Result; -use std::collections::BTreeMap; - -use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; -use crate::storage::{PAGE_SIZE, StorageBackend}; - -// ─── Constants ─────────────────────────────────────────────────────────────── - -/// Maximum entries per leaf page (reserved for Phase 6.2 true B+tree layout). -#[allow(dead_code)] -pub const LEAF_CAPACITY: usize = 50; -/// Maximum children per internal page (reserved for Phase 6.2 true B+tree layout). -#[allow(dead_code)] -pub const INTERNAL_CAPACITY: usize = 50; - -/// Page type byte: index data page. -pub const PAGE_TYPE_INDEX: u8 = 0x11; - -/// Header bytes per page: type(1) + total_len(4) + chunk_len(4) + is_last(1) = 10. -const PAGE_HEADER_SIZE: usize = 10; - -/// Number of data bytes available per page. -const DATA_BYTES_PER_PAGE: usize = PAGE_SIZE - PAGE_HEADER_SIZE; - -// ─── Low-level page I/O ─────────────────────────────────────────────────────── - -fn write_blob(blob: &[u8], backend: &mut dyn StorageBackend, start_page_id: u64) -> Result { - if blob.len() > u32::MAX as usize { - bail_coded!( - ErrorCode::Int048, - format!( - "index blob too large to serialize: {} bytes (max {})", - blob.len(), - u32::MAX - ) - ); - } - // Safe: guarded by the > u32::MAX check above. - let total_len = u32::try_from(blob.len()).map_err(|_| { - err_coded!( - ErrorCode::Int048, - format!("blob.len() overflows u32 (len={})", blob.len()) - ) - })?; - let num_pages = if blob.is_empty() { - 1usize // always write at least one page - } else { - blob.len().div_ceil(DATA_BYTES_PER_PAGE) - }; - - for i in 0..num_pages { - let offset = i.checked_mul(DATA_BYTES_PER_PAGE).ok_or_else(|| { - err_coded!( - ErrorCode::Int048, - format!("btree write_blob: page offset overflow at i={i}") - ) - })?; - let chunk = if offset < blob.len() { - let end = blob - .len() - .min(offset.checked_add(DATA_BYTES_PER_PAGE).ok_or_else(|| { - err_coded!( - ErrorCode::Int048, - "btree write_blob: end offset overflow".to_string() - ) - })?); - blob.get(offset..end).ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("btree write_blob: slice {offset}..{end} out of bounds") - ) - })? - } else { - &[] - }; - let chunk_len = u32::try_from(chunk.len()).map_err(|_| { - err_coded!( - ErrorCode::Int048, - format!("chunk.len() overflows u32 (len={})", chunk.len()) - ) - })?; - // num_pages >= 1 is guaranteed: write_blob always writes at least one page. - let is_last: u8 = if i == num_pages - 1 { 0x01 } else { 0x00 }; - - let mut page = vec![0u8; PAGE_SIZE]; - *page.get_mut(0).ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "btree: page index 0 out of bounds".to_string() - ) - })? = PAGE_TYPE_INDEX; - page.get_mut(1..5) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "btree: page slice 1..5 out of bounds".to_string() - ) - })? - .copy_from_slice(&total_len.to_le_bytes()); - page.get_mut(5..9) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "btree: page slice 5..9 out of bounds".to_string() - ) - })? - .copy_from_slice(&chunk_len.to_le_bytes()); - *page.get_mut(9).ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "btree: page index 9 out of bounds".to_string() - ) - })? = is_last; - if !chunk.is_empty() { - let end = PAGE_HEADER_SIZE.checked_add(chunk.len()).ok_or_else(|| { - err_coded!( - ErrorCode::Int048, - "btree write_blob: data end overflow".to_string() - ) - })?; - page.get_mut(PAGE_HEADER_SIZE..end) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("btree: page slice {PAGE_HEADER_SIZE}..{end} out of bounds") - ) - })? - .copy_from_slice(chunk); - } - - let page_offset = u64::try_from(i).map_err(|_| { - err_coded!( - ErrorCode::Int048, - format!("btree write_blob: page index {i} overflows u64") - ) - })?; - backend.write_page( - start_page_id.checked_add(page_offset).ok_or_else(|| { - err_coded!( - ErrorCode::Int048, - "btree write_blob: page_id overflow".to_string() - ) - })?, - &page, - )?; - } - - // Return the page ID immediately after the last page written. - let num_pages_u64 = u64::try_from(num_pages).map_err(|_| { - err_coded!( - ErrorCode::Int048, - format!("btree write_blob: num_pages {num_pages} overflows u64") - ) - })?; - start_page_id.checked_add(num_pages_u64).ok_or_else(|| { - err_coded!( - ErrorCode::Int048, - "btree write_blob: final page_id overflow".to_string() - ) - }) -} - -fn read_blob(backend: &dyn StorageBackend, start_page_id: u64) -> Result> { - // Read the first page to get total_len. - let first_page = backend.read_page(start_page_id)?; - let first_byte = *first_page.first().ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "btree read_blob: first_page index 0 out of bounds".to_string() - ) - })?; - if first_byte != PAGE_TYPE_INDEX { - bail_coded!( - ErrorCode::Int049, - format!( - "Expected index page type 0x{:02x}, got 0x{:02x}", - PAGE_TYPE_INDEX, first_byte - ) - ); - } - - let total_len = u32::from_le_bytes( - first_page - .get(1..5) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "btree read_blob: first_page slice 1..5 out of bounds".to_string() - ) - })? - .try_into() - .map_err(|_| { - err_coded!( - ErrorCode::Int049, - "btree read_blob: slice 1..5 not exactly 4 bytes".to_string() - ) - })?, - ) as usize; - let mut blob = Vec::with_capacity(total_len); - - let mut page_id = start_page_id; - loop { - let page = backend.read_page(page_id)?; - let page_byte = *page.first().ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("btree read_blob: page index 0 out of bounds (page {page_id})") - ) - })?; - if page_byte != PAGE_TYPE_INDEX { - bail_coded!(ErrorCode::Stg012, page_id); - } - let chunk_len = u32::from_le_bytes( - page.get(5..9) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("btree read_blob: page slice 5..9 out of bounds (page {page_id})") - ) - })? - .try_into() - .map_err(|_| { - err_coded!( - ErrorCode::Int049, - "btree read_blob: slice 5..9 not exactly 4 bytes".to_string() - ) - })?, - ) as usize; - let is_last = *page.get(9).ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("btree read_blob: page index 9 out of bounds (page {page_id})") - ) - })? == 0x01; - - if chunk_len > 0 { - let end = PAGE_HEADER_SIZE.checked_add(chunk_len).ok_or_else(|| { - err_coded!( - ErrorCode::Int048, - format!("btree read_blob: data end overflow (chunk_len={chunk_len})") - ) - })?; - blob.extend_from_slice(page.get(PAGE_HEADER_SIZE..end).ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("btree read_blob: page slice {PAGE_HEADER_SIZE}..{end} out of bounds") - ) - })?); - } - - if is_last { - break; - } - page_id = page_id.checked_add(1).ok_or_else(|| { - err_coded!( - ErrorCode::Int048, - "btree read_blob: page_id overflow".to_string() - ) - })?; - } - - Ok(blob) -} - -// ─── Generic index write/read ───────────────────────────────────────────────── - -fn write_index_generic( - map: &BTreeMap, - backend: &mut dyn StorageBackend, - start_page_id: u64, -) -> Result -where - K: serde::Serialize + for<'de> serde::Deserialize<'de> + Ord + Clone, -{ - let entries: Vec<(&K, &FactRef)> = map.iter().collect(); - let blob = postcard::to_allocvec(&entries)?; - write_blob(&blob, backend, start_page_id) -} - -fn read_index_generic( - root_page_id: u64, - backend: &dyn StorageBackend, -) -> Result> -where - K: serde::Serialize + for<'de> serde::Deserialize<'de> + Ord + Clone, -{ - let blob = read_blob(backend, root_page_id)?; - let entries: Vec<(K, FactRef)> = postcard::from_bytes(&blob)?; - Ok(entries.into_iter().collect()) -} - -// ─── Public API ─────────────────────────────────────────────────────────────── - -/// Write the EAVT index to pages starting at `start_page_id`. -/// -/// Returns the next free page ID (i.e., `start_page_id + pages_written`). -pub fn write_eavt_index( - map: &BTreeMap, - backend: &mut dyn StorageBackend, - start_page_id: u64, -) -> Result { - write_index_generic(map, backend, start_page_id) -} - -/// Read the EAVT index from pages starting at `root_page_id`. -pub fn read_eavt_index( - root_page_id: u64, - backend: &dyn StorageBackend, -) -> Result> { - read_index_generic(root_page_id, backend) -} - -/// Write the AEVT index. Returns next free page ID. -pub fn write_aevt_index( - map: &BTreeMap, - backend: &mut dyn StorageBackend, - start_page_id: u64, -) -> Result { - write_index_generic(map, backend, start_page_id) -} - -/// Read the AEVT index. -pub fn read_aevt_index( - root_page_id: u64, - backend: &dyn StorageBackend, -) -> Result> { - read_index_generic(root_page_id, backend) -} - -/// Write the AVET index. Returns next free page ID. -pub fn write_avet_index( - map: &BTreeMap, - backend: &mut dyn StorageBackend, - start_page_id: u64, -) -> Result { - write_index_generic(map, backend, start_page_id) -} - -/// Read the AVET index. -pub fn read_avet_index( - root_page_id: u64, - backend: &dyn StorageBackend, -) -> Result> { - read_index_generic(root_page_id, backend) -} - -/// Write the VAET index. Returns next free page ID. -pub fn write_vaet_index( - map: &BTreeMap, - backend: &mut dyn StorageBackend, - start_page_id: u64, -) -> Result { - write_index_generic(map, backend, start_page_id) -} - -/// Read the VAET index. -pub fn read_vaet_index( - root_page_id: u64, - backend: &dyn StorageBackend, -) -> Result> { - read_index_generic(root_page_id, backend) -} - -/// Write all four indexes to pages starting at `start_page_id`. -/// -/// Returns `(eavt_root, aevt_root, avet_root, vaet_root)` — the start page ID -/// of each index blob. Each `*_root` value is the first page of that index's -/// blob; subsequent pages follow contiguously. -pub fn write_all_indexes( - eavt: &std::collections::BTreeMap, - aevt: &std::collections::BTreeMap, - avet: &std::collections::BTreeMap, - vaet: &std::collections::BTreeMap, - backend: &mut dyn StorageBackend, - start_page_id: u64, -) -> Result<(u64, u64, u64, u64)> { - let eavt_root = start_page_id; - let after_eavt = write_eavt_index(eavt, backend, eavt_root)?; - - let aevt_root = after_eavt; - let after_aevt = write_aevt_index(aevt, backend, aevt_root)?; - - let avet_root = after_aevt; - let after_avet = write_avet_index(avet, backend, avet_root)?; - - let vaet_root = after_avet; - write_vaet_index(vaet, backend, vaet_root)?; - - Ok((eavt_root, aevt_root, avet_root, vaet_root)) -} - -// ─── Tests ──────────────────────────────────────────────────────────────────── - -#[cfg(test)] -mod tests { - use super::*; - use crate::storage::backend::memory::MemoryBackend; - use crate::storage::index::{EavtKey, FactRef}; - use std::collections::BTreeMap; - use uuid::Uuid; - - fn eavt_entry(entity_lo: u128, attr: &str, tx: u64) -> (EavtKey, FactRef) { - ( - EavtKey { - entity: Uuid::from_u128(entity_lo), - attribute: attr.to_string(), - valid_from: 0, - valid_to: i64::MAX, - tx_count: tx, - }, - FactRef { - page_id: tx, - slot_index: 0, - }, - ) - } - - #[test] - fn test_empty_eavt_roundtrip() { - let mut backend = MemoryBackend::new(); - let map: BTreeMap = BTreeMap::new(); - let next = write_eavt_index(&map, &mut backend, 1).unwrap(); - // Empty serialization should still write exactly one page. - assert_eq!(next, 2, "empty index should consume exactly 1 page"); - let recovered = read_eavt_index(1, &backend).unwrap(); - assert_eq!(recovered.len(), 0); - } - - #[test] - fn test_small_eavt_roundtrip() { - let mut backend = MemoryBackend::new(); - let mut map = BTreeMap::new(); - for i in 0u128..10 { - let (k, v) = eavt_entry(i, ":name", i as u64 + 1); - map.insert(k, v); - } - let next = write_eavt_index(&map, &mut backend, 1).unwrap(); - assert!(next >= 2, "should write at least one page"); - let recovered = read_eavt_index(1, &backend).unwrap(); - assert_eq!(recovered.len(), 10); - for (k, v) in &map { - assert_eq!(recovered.get(k), Some(v), "missing key {:?}", k); - } - } - - #[test] - fn test_large_eavt_roundtrip_multi_leaf() { - // Force multi-page: insert more entries than LEAF_CAPACITY (50). - // With 150 entries × ~50 bytes each ≈ 7500 bytes > DATA_BYTES_PER_PAGE (4086), - // so this will span at least 2 pages. - let mut backend = MemoryBackend::new(); - let mut map = BTreeMap::new(); - for i in 0u128..150 { - let (k, v) = eavt_entry(i, ":attr", i as u64 + 1); - map.insert(k, v); - } - let next = write_eavt_index(&map, &mut backend, 1).unwrap(); - assert!(next > 2, "150 entries must span multiple pages"); - let recovered = read_eavt_index(1, &backend).unwrap(); - assert_eq!(recovered.len(), 150); - for (k, v) in &map { - assert_eq!(recovered.get(k), Some(v)); - } - } - - #[test] - fn test_eavt_preserves_sort_order() { - let mut backend = MemoryBackend::new(); - let mut map = BTreeMap::new(); - for i in 0u128..100 { - let (k, v) = eavt_entry(i, ":x", i as u64 + 1); - map.insert(k, v); - } - let root = write_eavt_index(&map, &mut backend, 1).unwrap(); - let recovered = read_eavt_index(1, &backend).unwrap(); - let orig_keys: Vec<_> = map.keys().collect(); - let rec_keys: Vec<_> = recovered.keys().collect(); - assert_eq!(orig_keys, rec_keys, "Sort order must be preserved"); - // Ensure the return value is sane. - assert!(root >= 2); - } - - // ══ #359: STG-012 regression test ═════════════════════════════════════ - - /// A non-first page of a multi-page index blob whose type byte has been - /// corrupted (page found is not `PAGE_TYPE_INDEX`) must surface as the - /// coded STG-012, not a generic error. - #[test] - fn read_blob_corrupted_non_first_page_returns_stg_012() { - let mut backend = MemoryBackend::new(); - let mut map = BTreeMap::new(); - // Enough entries to span at least 2 pages (see - // test_large_eavt_roundtrip_multi_leaf above). - for i in 0u128..150 { - let (k, v) = eavt_entry(i, ":attr", i as u64 + 1); - map.insert(k, v); - } - let next = write_eavt_index(&map, &mut backend, 1).unwrap(); - assert!(next > 2, "150 entries must span multiple pages"); - - // Corrupt page 2's type byte (the second page of the blob starting - // at page 1) so it no longer reads as PAGE_TYPE_INDEX. - let mut corrupt_page = backend.read_page(2).unwrap(); - corrupt_page[0] = 0x00; - backend.write_page(2, &corrupt_page).unwrap(); - - let err = read_eavt_index(1, &backend).expect_err("corrupted page must fail to read"); - let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-012"); - } -} diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 314550426..3657aedf9 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -6,7 +6,6 @@ /// /// Inspired by SQLite's VFS (Virtual File System) architecture. pub mod backend; -pub mod btree; pub mod btree_v6; pub mod cache; pub mod index; @@ -47,8 +46,10 @@ pub const MAGIC_NUMBER: [u8; 4] = *b"MGRF"; /// Current file format version pub const FORMAT_VERSION: u32 = 7; -/// fact_page_format: legacy one-per-page (v4 and earlier, or unset byte = 0x00). -pub const FACT_PAGE_FORMAT_ONE_PER_PAGE: u8 = 0x01; +/// Oldest file format version this library reads. Older files must first be +/// opened with Minigraf v2.x, which upgrades them to v7 (see STG-028). +pub const MIN_FORMAT_VERSION: u32 = 7; + /// fact_page_format: packed pages (v5+). pub const FACT_PAGE_FORMAT_PACKED: u8 = 0x02; @@ -128,10 +129,8 @@ pub struct FileHeader { pub fact_page_format: u8, pub(crate) _padding: [u8; 3], /// Number of pages (starting at page 1) holding committed fact data. - /// New in v6; zero-initialised when reading v5 or older headers. pub fact_page_count: u64, /// CRC32 checksum of the first 80 bytes of the header (excluding this field). - /// New in v7; zero-initialised when reading v6 or older headers. pub header_checksum: u32, } @@ -178,14 +177,8 @@ impl FileHeader { /// Deserialize the header from bytes. /// - /// Accepts v3 (64-byte), v4/v5 (72-byte), and v6 (80-byte) headers. - /// v3 headers are returned with zero-filled index fields; the - /// v3→v4 migration in persistent_facts.rs upgrades them on next save. - /// v4 headers have fact_page_format = 0x00 (legacy/unset). - /// v5 headers are returned with fact_page_count = 0. + /// Accepts only v7+ (84-byte) headers; older versions fail with STG-028. pub fn from_bytes(bytes: &[u8]) -> Result { - // Both v3 (64 bytes) and v4/v5/v6 (72+ bytes) must pass at least 64-byte - // validation before the version field is read. if bytes.len() < 64 { bail_coded!(ErrorCode::Stg001, bytes.len()); } @@ -202,53 +195,17 @@ impl FileHeader { } let version = read_u32_le(bytes, 4)?; + if version < MIN_FORMAT_VERSION { + bail_coded!(ErrorCode::Stg028, version, MIN_FORMAT_VERSION); + } + if bytes.len() < 84 { + bail_coded!(ErrorCode::Stg005, bytes.len()); + } let page_count = read_u64_le(bytes, 8)?; let node_count = read_u64_le(bytes, 16)?; let last_checkpointed_tx_count = read_u64_le(bytes, 24)?; - - // v3 and earlier: no index fields — return with zero-filled index fields. - // The v3→v4 migration in persistent_facts.rs will upgrade on next save. - if version <= 3 { - return Ok(FileHeader { - magic, - version, - page_count, - node_count, - last_checkpointed_tx_count, - eavt_root_page: 0, - aevt_root_page: 0, - avet_root_page: 0, - vaet_root_page: 0, - index_checksum: 0, - fact_page_format: 0, - _padding: [0; 3], - fact_page_count: 0, - header_checksum: 0, - }); - } - - // v4, v5, v6: need at least 72 bytes - if bytes.len() < 72 { - bail_coded!(ErrorCode::Stg003, bytes.len()); - } - - let fact_page_count = if version >= 6 { - if bytes.len() < 80 { - bail_coded!(ErrorCode::Stg004, bytes.len()); - } - read_u64_le(bytes, 72)? - } else { - 0 - }; - - let header_checksum = if version >= 7 { - if bytes.len() < 84 { - bail_coded!(ErrorCode::Stg005, bytes.len()); - } - read_u32_le(bytes, 80)? - } else { - 0 - }; + let fact_page_count = read_u64_le(bytes, 72)?; + let header_checksum = read_u32_le(bytes, 80)?; Ok(FileHeader { magic, @@ -285,7 +242,10 @@ impl FileHeader { if self.magic != MAGIC_NUMBER { bail_coded!(ErrorCode::Int039); } - if self.version < 1 || self.version > FORMAT_VERSION { + if self.version < MIN_FORMAT_VERSION { + bail_coded!(ErrorCode::Stg028, self.version, MIN_FORMAT_VERSION); + } + if self.version > FORMAT_VERSION { bail_coded!(ErrorCode::Stg006, self.version, FORMAT_VERSION); } // Validate logical relationships @@ -370,20 +330,6 @@ pub trait CommittedIndexReader: Send + Sync { mod tests { use super::*; - #[test] - fn test_file_header_from_bytes_v3_accepted() { - // v3 files have a 64-byte header. from_bytes must accept them and - // return zeroed index fields. - let mut bytes = vec![0u8; 64]; - bytes[0..4].copy_from_slice(b"MGRF"); - bytes[4..8].copy_from_slice(&3u32.to_le_bytes()); // version = 3 - bytes[8..16].copy_from_slice(&1u64.to_le_bytes()); // page_count = 1 - let header = FileHeader::from_bytes(&bytes).unwrap(); - assert_eq!(header.version, 3); - assert_eq!(header.eavt_root_page, 0); - assert_eq!(header.index_checksum, 0); - } - #[test] fn test_file_header_validation() { let header = FileHeader::new(); @@ -505,17 +451,6 @@ mod tests { assert_eq!(&b[80..84], &0xC1C2_C3C4_u32.to_le_bytes()); } - #[test] - fn test_file_header_v6_reads_header_checksum_zero() { - let mut bytes = vec![0u8; 80]; - bytes[0..4].copy_from_slice(b"MGRF"); - bytes[4..8].copy_from_slice(&6u32.to_le_bytes()); - bytes[8..16].copy_from_slice(&2u64.to_le_bytes()); - let h = FileHeader::from_bytes(&bytes).unwrap(); - assert_eq!(h.version, 6); - assert_eq!(h.header_checksum, 0); - } - #[test] fn test_file_header_v7_truncated_rejected() { let mut bytes = vec![0u8; 80]; @@ -524,15 +459,6 @@ mod tests { assert!(FileHeader::from_bytes(&bytes).is_err()); } - #[test] - fn test_validate_accepts_versions_1_to_7() { - let mut h = FileHeader::new(); - for v in 1u32..=7 { - h.version = v; - assert!(h.validate().is_ok(), "version {} should be accepted", v); - } - } - #[test] fn test_file_header_v7_header_checksum_roundtrip() { let mut h = FileHeader::new(); @@ -543,48 +469,11 @@ mod tests { assert_eq!(parsed.header_checksum, 42); } - #[test] - fn test_file_header_from_bytes_truncated_v4_rejected() { - // A header that claims version=4 but has fewer than 72 bytes must be rejected. - let mut bytes = vec![0u8; 68]; // only 68 bytes, not 72 - bytes[0..4].copy_from_slice(b"MGRF"); - bytes[4..8].copy_from_slice(&4u32.to_le_bytes()); // version = 4 - let result = FileHeader::from_bytes(&bytes); - assert!(result.is_err(), "truncated v4 header must be rejected"); - } - - #[test] - fn test_file_header_v5_fact_page_format_roundtrip() { - let mut h = FileHeader::new(); - h.fact_page_format = FACT_PAGE_FORMAT_PACKED; - let bytes = h.to_bytes(); - let parsed = FileHeader::from_bytes(&bytes).unwrap(); - assert_eq!(parsed.fact_page_format, FACT_PAGE_FORMAT_PACKED); - } - - #[test] - fn test_v4_header_reads_fact_page_format_zero() { - // v4 header has _padding = 0, so fact_page_format must come back as 0 - let mut bytes = vec![0u8; 72]; - bytes[0..4].copy_from_slice(b"MGRF"); - bytes[4..8].copy_from_slice(&4u32.to_le_bytes()); // version = 4 - bytes[8..16].copy_from_slice(&2u64.to_le_bytes()); // page_count = 2 - let h = FileHeader::from_bytes(&bytes).unwrap(); - assert_eq!(h.fact_page_format, 0); - } - - #[test] - fn test_validate_accepts_version_5() { - let mut h = FileHeader::new(); - h.version = 5; - assert!(h.validate().is_ok()); - } - // ══ #359: STG-0xx regression tests ═══════════════════════════════════ // - // STG-001/003/004/005 guard byte lengths (<64/<72/<80/<84) that the - // production `FileBackend` path never actually produces -- it always - // hands `FileHeader::from_bytes` a full `PAGE_SIZE` (4096-byte) buffer, + // STG-001/005 guard byte lengths (<64/<84) that the production + // `FileBackend` path never actually produces -- it always hands + // `FileHeader::from_bytes` a full `PAGE_SIZE` (4096-byte) buffer, // whatever the real file's length beyond the minimum one page. These // codes are only reachable by calling `FileHeader::from_bytes` directly // with a short slice, which `storage` being crate-private makes @@ -600,32 +489,32 @@ mod tests { } #[test] - fn from_bytes_v4_too_short_returns_stg_003() { - let mut bytes = vec![0u8; 70]; // >= 64, < 72 + fn from_bytes_v7_too_short_returns_stg_005() { + let mut bytes = vec![0u8; 82]; // >= 80, < 84 bytes[0..4].copy_from_slice(b"MGRF"); - bytes[4..8].copy_from_slice(&4u32.to_le_bytes()); // version = 4 - let err = FileHeader::from_bytes(&bytes).expect_err("70 bytes is too short for v4"); + bytes[4..8].copy_from_slice(&7u32.to_le_bytes()); // version = 7 + let err = FileHeader::from_bytes(&bytes).expect_err("82 bytes is too short for v7"); let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-003"); + assert_eq!(coded.code(), "STG-005"); } #[test] - fn from_bytes_v6_too_short_returns_stg_004() { - let mut bytes = vec![0u8; 75]; // >= 72, < 80 - bytes[0..4].copy_from_slice(b"MGRF"); - bytes[4..8].copy_from_slice(&6u32.to_le_bytes()); // version = 6 - let err = FileHeader::from_bytes(&bytes).expect_err("75 bytes is too short for v6"); - let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-004"); + fn from_bytes_pre_v7_returns_stg_028() { + for version in 1u32..=6 { + let mut bytes = FileHeader::new().to_bytes(); + bytes[4..8].copy_from_slice(&version.to_le_bytes()); + let err = FileHeader::from_bytes(&bytes).expect_err("pre-v7 header must be rejected"); + let coded: crate::error::MinigrafError = err.into(); + assert_eq!(coded.code(), "STG-028"); + } } #[test] - fn from_bytes_v7_too_short_returns_stg_005() { - let mut bytes = vec![0u8; 82]; // >= 80, < 84 - bytes[0..4].copy_from_slice(b"MGRF"); - bytes[4..8].copy_from_slice(&7u32.to_le_bytes()); // version = 7 - let err = FileHeader::from_bytes(&bytes).expect_err("82 bytes is too short for v7"); + fn validate_pre_v7_returns_stg_028() { + let mut h = FileHeader::new(); + h.version = 6; + let err = h.validate().expect_err("v6 must be rejected"); let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-005"); + assert_eq!(coded.code(), "STG-028"); } } diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 2a057513f..dd0cf27fe 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -6,7 +6,6 @@ use crate::graph::FactStorage; /// low-level page-based storage backends. use crate::graph::types::Fact; use crate::storage::FACT_PAGE_FORMAT_PACKED; -use crate::storage::btree::{read_aevt_index, read_avet_index, read_eavt_index, read_vaet_index}; use crate::storage::btree_v6::{ MutexStorageBackend, OnDiskIndexReader, btree_entries, build_btree, merge_sorted_vecs, stream_all_entries, @@ -94,18 +93,6 @@ impl crate::storage::CommittedFactReader } } -/// V1 fact format (Phase 3, before bi-temporal fields were added). -/// -/// Used only during migration from v1 → v2 file format. -#[derive(Debug, serde::Deserialize)] -struct FactV1 { - entity: crate::graph::types::EntityId, - attribute: crate::graph::types::Attribute, - value: crate::graph::types::Value, - tx_id: crate::graph::types::TxId, - asserted: bool, -} - /// Persistent fact storage with serialization support. /// /// Architecture: @@ -177,7 +164,8 @@ impl PersistentFactStorage { // The load condition combines two checks: // - `!is_new`: FileBackend reports false when the file existed on disk // (even with only a header page, page_count == 1). This ensures - // migrate_v5_to_v6 runs for a v5 file that has no fact pages. + // `load()` runs (and its version check rejects pre-v7 files) even + // for a file that has no fact pages. // - `page_count > 1`: catches MemoryBackend, which always reports // is_new == true; page count > 1 means facts were previously saved. let (is_new_backend, page_count) = { @@ -216,19 +204,8 @@ impl PersistentFactStorage { (h, header_page) }; - // Migrate v1 → v2 if needed - if header.version < 2 { - return self.migrate_v1_to_v2(); - } - - // Migrate v5 → v6 (paged-blob indexes → on-disk B+tree) - if header.version == 5 { - return self.migrate_v5_to_v6(&header); - } - // For v7+ files, validate header checksum using raw bytes from disk - // For older versions (v6 and earlier), header_checksum is 0 so validation is skipped - if header.version >= 7 && header.header_checksum != 0 { + if header.header_checksum != 0 { let computed = compute_header_checksum_from_bytes(&raw_header_bytes); if header.header_checksum != computed { bail_coded!(ErrorCode::Int053); @@ -241,21 +218,8 @@ impl PersistentFactStorage { // Clear existing storage self.storage.clear()?; - let fact_page_format = header.fact_page_format; - - if fact_page_format == 0 - || fact_page_format == crate::storage::FACT_PAGE_FORMAT_ONE_PER_PAGE - { - // Legacy one-per-page format (v4 or earlier): load all facts, then migrate to v5. - self.load_one_per_page_legacy(&header)?; - self.storage.restore_tx_counter()?; - self.dirty = true; - self.save()?; - return Ok(()); - } - // v6 packed format - let num_fact_pages = if header.version >= 6 && header.fact_page_count > 0 { + let num_fact_pages = if header.fact_page_count > 0 { header.fact_page_count } else { let first_index_page = [ @@ -412,7 +376,7 @@ impl PersistentFactStorage { } else { // No rebuild needed - validate header checksum for v7+ files // Re-read header from disk to get any updates from rebuild path - if header.version >= 7 && header.header_checksum != 0 { + if header.header_checksum != 0 { let backend = self .backend .lock() @@ -445,376 +409,6 @@ impl PersistentFactStorage { Ok(()) } - /// Load facts from legacy one-per-page format (v4 and earlier). - fn load_one_per_page_legacy(&mut self, header: &FileHeader) -> Result { - let page_count = header.page_count; - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let mut loaded: usize = 0; - let mut skipped: usize = 0; - for page_id in 1..page_count { - let page = backend.read_page(page_id)?; - // Try to deserialize a fact from this page (legacy format: raw postcard bytes) - match postcard::from_bytes::(&page) { - Ok(fact) => { - self.storage.load_fact(fact)?; - loaded = loaded.saturating_add(1); - } - Err(e) => { - skipped = skipped.saturating_add(1); - eprintln!( - "Warning: failed to deserialize fact at page {}: {}. Skipping.", - page_id, e - ); - } - } - } - if skipped > 0 { - eprintln!( - "Warning: {} facts failed to deserialize during legacy load (version {})", - skipped, header.version - ); - } - Ok(loaded) - } - - /// Migrate a v1 file (Phase 3 format, no bi-temporal fields) to v2. - /// - /// V1 facts only have (entity, attribute, value, tx_id, asserted). - /// V2 facts add tx_count, valid_from, valid_to. - /// - /// Migration strategy: - /// - Sort v1 facts by tx_id ascending - /// - Group facts with the same tx_id into the same tx_count (monotonic counter) - /// - Set valid_from = tx_id as i64 (wall-clock approximation) - /// - Set valid_to = VALID_TIME_FOREVER (open-ended) - /// - Write the migrated data back in v2 format - fn migrate_v1_to_v2(&mut self) -> Result<()> { - use crate::graph::types::VALID_TIME_FOREVER; - - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let header_page = backend.read_page(0)?; - let header = FileHeader::from_bytes(&header_page)?; - let page_count = header.page_count; - - // Read all v1 facts (track deserialization failures) - let mut v1_facts: Vec = Vec::new(); - let mut skipped: usize = 0; - for page_id in 1..page_count { - let page = backend.read_page(page_id)?; - match postcard::from_bytes::(&page) { - Ok(fact) => v1_facts.push(fact), - Err(e) => { - skipped = skipped.saturating_add(1); - eprintln!( - "Warning: failed to deserialize v1 fact at page {}: {}. Skipping.", - page_id, e - ); - } - } - } - if skipped > 0 { - eprintln!( - "Warning: {} v1 facts failed to deserialize during migration", - skipped - ); - } - drop(backend); - - // Sort by tx_id ascending so we can group them - v1_facts.sort_by_key(|f| f.tx_id); - - // Assign tx_count, grouping facts with the same tx_id into the same tx_count - let mut tx_count: u64 = 0; - let mut prev_tx_id: Option = None; - let mut migrated: Vec = Vec::new(); - - for v1 in v1_facts { - if prev_tx_id != Some(v1.tx_id) { - tx_count = tx_count.saturating_add(1); - prev_tx_id = Some(v1.tx_id); - } - let valid_from = v1.tx_id.cast_signed(); - let mut fact = Fact::with_valid_time( - v1.entity, - v1.attribute, - v1.value, - v1.tx_id, - tx_count, - valid_from, - VALID_TIME_FOREVER, - ); - // Preserve the asserted flag (with_valid_time sets asserted=true by default) - fact.asserted = v1.asserted; - migrated.push(fact); - } - - self.storage.clear()?; - for fact in migrated { - self.storage.load_fact(fact)?; - } - self.storage.restore_tx_counter()?; - - // Persist in v2 format immediately - self.dirty = true; - self.save()?; - Ok(()) - } - - /// Migrate a v5 file (paged-blob indexes) to v6 (on-disk B+tree indexes). - fn migrate_v5_to_v6(&mut self, header: &FileHeader) -> Result<()> { - let num_fact_pages = { - let first_index_page = [ - header.eavt_root_page, - header.aevt_root_page, - header.avet_root_page, - header.vaet_root_page, - ] - .iter() - .filter(|&&p| p > 0) - .copied() - .min() - .unwrap_or(header.page_count); - first_index_page.saturating_sub(1) - }; - - // Validate the calculated range contains valid pages. - // If the file was in an inconsistent state (partial checkpoint), - // the calculated range might be incorrect. Do a quick validation - // by checking that the first fact page can be read (doesn't need to - // be a packed page - the index checksum will catch any real corruption). - let validated_num_fact_pages = if num_fact_pages > 0 { - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - // Just verify we can read the page - actual validation happens via checksum - if backend.read_page(1).is_ok() { - num_fact_pages - } else { - eprintln!( - "Warning: cannot read first fact page (page 1). Header claims {}. Using 0.", - num_fact_pages - ); - 0 - } - } else { - num_fact_pages - }; - - self.committed_fact_pages - .store(validated_num_fact_pages, Ordering::SeqCst); - - // Verify index integrity via checksum before trusting the old indexes. - // Try full checksum (facts + indexes) first, then fact-only for old files. - let use_old_indexes = validated_num_fact_pages > 0 && header.index_checksum > 0 && { - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let total_data_pages = header.page_count.saturating_sub(1); - let full = compute_page_checksum(&*backend, 1, total_data_pages)?; - if full == header.index_checksum { - true - } else { - let fact_only = compute_page_checksum(&*backend, 1, validated_num_fact_pages)?; - fact_only == header.index_checksum - } - }; - - let (eavt, aevt, avet, vaet) = if use_old_indexes { - // Read and trust the old v5 indexes - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let e = if header.eavt_root_page > 0 { - read_eavt_index(header.eavt_root_page, &*backend)? - } else { - std::collections::BTreeMap::new() - }; - let a = if header.aevt_root_page > 0 { - read_aevt_index(header.aevt_root_page, &*backend)? - } else { - std::collections::BTreeMap::new() - }; - let av = if header.avet_root_page > 0 { - read_avet_index(header.avet_root_page, &*backend)? - } else { - std::collections::BTreeMap::new() - }; - let v = if header.vaet_root_page > 0 { - read_vaet_index(header.vaet_root_page, &*backend)? - } else { - std::collections::BTreeMap::new() - }; - (e, a, av, v) - } else { - // Checksum mismatch or missing - rebuild indexes from facts - let all_facts = { - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - crate::storage::packed_pages::read_all_from_pages( - &*backend, - 1, - validated_num_fact_pages, - )? - }; - // Build indexes from fact data - let mut eavt_map = std::collections::BTreeMap::new(); - let mut aevt_map = std::collections::BTreeMap::new(); - let mut avet_map = std::collections::BTreeMap::new(); - let mut vaet_map = std::collections::BTreeMap::new(); - for (i, fact) in all_facts.iter().enumerate() { - let slot_index = u16::try_from(i).map_err(|_| err_coded!(ErrorCode::Stg020, i))?; - let fr = FactRef { - page_id: 1, - slot_index, - }; - eavt_map.insert( - EavtKey { - entity: fact.entity, - attribute: fact.attribute.clone(), - valid_from: fact.valid_from, - valid_to: fact.valid_to, - tx_count: fact.tx_count, - }, - fr, - ); - aevt_map.insert( - AevtKey { - attribute: fact.attribute.clone(), - entity: fact.entity, - valid_from: fact.valid_from, - valid_to: fact.valid_to, - tx_count: fact.tx_count, - }, - fr, - ); - avet_map.insert( - AvetKey { - attribute: fact.attribute.clone(), - value_bytes: encode_value(&fact.value), - valid_from: fact.valid_from, - valid_to: fact.valid_to, - entity: fact.entity, - tx_count: fact.tx_count, - }, - fr, - ); - if let crate::graph::types::Value::Ref(target) = &fact.value { - vaet_map.insert( - VaetKey { - ref_target: *target, - attribute: fact.attribute.clone(), - valid_from: fact.valid_from, - valid_to: fact.valid_to, - source_entity: fact.entity, - tx_count: fact.tx_count, - }, - fr, - ); - } - } - (eavt_map, aevt_map, avet_map, vaet_map) - }; - - let mut backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - // Use the actual end of fact pages as the start for new index pages, NOT - // header.page_count — that field comes from the (possibly untrusted) file - // on disk and may be a huge fuzz-crafted value that causes build_btree to - // write leaf pages at a ~TB offset, then compute_page_checksum to loop - // over billions of pages. - let next_free = 1u64 - .checked_add(validated_num_fact_pages) - .ok_or_else(|| err_coded!(ErrorCode::Stg018))?; - - let (eavt_root, next_free2) = build_btree( - btree_entries(eavt.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - next_free, - )?; - let (aevt_root, next_free3) = build_btree( - btree_entries(aevt.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - next_free2, - )?; - let (avet_root, next_free4) = build_btree( - btree_entries(avet.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - next_free3, - )?; - let (vaet_root, final_next_free) = build_btree( - btree_entries(vaet.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - next_free4, - )?; - - let mut new_header = FileHeader::new(); // version=7 - new_header.page_count = final_next_free; - new_header.node_count = header.node_count; - new_header.last_checkpointed_tx_count = header.last_checkpointed_tx_count; - new_header.eavt_root_page = eavt_root; - new_header.aevt_root_page = aevt_root; - new_header.avet_root_page = avet_root; - new_header.vaet_root_page = vaet_root; - // Checksum over all data pages (facts + indexes) - let total_data_pages = final_next_free.saturating_sub(1); - let computed_checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; - new_header.index_checksum = computed_checksum; - new_header.fact_page_format = header.fact_page_format; - new_header.fact_page_count = validated_num_fact_pages; - new_header.header_checksum = compute_header_checksum(&new_header); - - let mut header_page = new_header.to_bytes(); - header_page.resize(PAGE_SIZE, 0); - backend.write_page(0, &header_page)?; - backend.sync()?; - drop(backend); - - self.last_checkpointed_tx_count = header.last_checkpointed_tx_count; - - let loader: Arc = - Arc::new(CommittedFactLoaderImpl { - backend: self.backend.clone(), - backend_adapter: MutexStorageBackend(self.backend.clone()), - page_cache: self.page_cache.clone(), - committed_fact_pages: self.committed_fact_pages.clone(), - first_fact_page: 1, - }); - self.storage.set_committed_reader(loader); - - let index_reader: Arc = - Arc::new(OnDiskIndexReader::new( - self.backend.clone(), - self.page_cache.clone(), - eavt_root, - aevt_root, - avet_root, - vaet_root, - )); - self.storage.set_committed_index_reader(index_reader); - - self.storage - .restore_tx_counter_from(header.last_checkpointed_tx_count); - self.dirty = false; - Ok(()) - } - /// Consume this storage and return the underlying backend. /// /// Useful in tests to inspect or reuse the backend after saving. @@ -1351,60 +945,6 @@ mod tests { // This test verifies the pattern, actual persistence is tested above } - // ----------------------------------------------------------------------- - // Migration helpers - // ----------------------------------------------------------------------- - - /// Build a MemoryBackend that contains a v1-format file with two FactV1 facts. - fn make_v1_backend() -> MemoryBackend { - use crate::storage::{MAGIC_NUMBER, PAGE_SIZE}; - - let alice = Uuid::new_v4(); - - #[derive(serde::Serialize)] - struct FactV1Ser { - entity: Uuid, - attribute: String, - value: Value, - tx_id: u64, - asserted: bool, - } - - let fact1 = FactV1Ser { - entity: alice, - attribute: ":person/name".to_string(), - value: Value::String("Alice".to_string()), - tx_id: 1000, - asserted: true, - }; - let fact2 = FactV1Ser { - entity: alice, - attribute: ":person/age".to_string(), - value: Value::Integer(30), - tx_id: 1000, - asserted: true, - }; - - let mut backend = MemoryBackend::new(); - - // Write v1 header (version=1, page_count=3) - let mut header_bytes = vec![0u8; PAGE_SIZE]; - header_bytes[0..4].copy_from_slice(&MAGIC_NUMBER); - header_bytes[4..8].copy_from_slice(&1u32.to_le_bytes()); // version = 1 - header_bytes[8..16].copy_from_slice(&3u64.to_le_bytes()); // page_count = 3 - backend.write_page(0, &header_bytes).unwrap(); - - // Write facts (one per page) - for (i, fact) in [&fact1, &fact2].iter().enumerate() { - let data = postcard::to_allocvec(*fact).unwrap(); - let mut page = vec![0u8; PAGE_SIZE]; - page[..data.len()].copy_from_slice(&data); - backend.write_page((i + 1) as u64, &page).unwrap(); - } - - backend - } - #[test] fn test_load_preserves_original_tx_id() { let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); @@ -1437,30 +977,6 @@ mod tests { ); } - #[test] - fn test_migrate_v1_to_v2_assigns_defaults() { - use crate::graph::types::VALID_TIME_FOREVER; - - let backend = make_v1_backend(); - let pfs = PersistentFactStorage::new(backend, 256).unwrap(); - let facts = pfs.storage().get_all_facts().unwrap(); - - assert_eq!(facts.len(), 2); - // Both facts share tx_id=1000 → same tx_count - assert_eq!( - facts[0].tx_count, facts[1].tx_count, - "facts from the same tx_id batch must get the same tx_count" - ); - assert_eq!( - facts[0].valid_to, VALID_TIME_FOREVER, - "migrated fact must have open-ended valid_to" - ); - assert_eq!( - facts[0].valid_from, 1000_i64, - "migrated fact valid_from must equal original tx_id" - ); - } - #[test] fn test_save_writes_v4_header() { use crate::storage::FORMAT_VERSION; @@ -1698,34 +1214,6 @@ mod tests { assert_eq!(c1, c2, "Checksum must be order-independent"); } - #[test] - fn test_migrate_v1_tx_counter_set_correctly() { - let backend = make_v1_backend(); - let pfs = PersistentFactStorage::new(backend, 256).unwrap(); - - let alice = Uuid::new_v4(); - pfs.storage() - .transact( - vec![(alice, ":new/fact".to_string(), Value::Boolean(true))], - None, - ) - .unwrap(); - - let new_fact = pfs - .storage() - .get_all_facts() - .unwrap() - .into_iter() - .find(|f| f.attribute == ":new/fact") - .unwrap(); - - // After migrating 1 unique tx_id (tx_count=1), next tx should get tx_count=2 - assert_eq!( - new_fact.tx_count, 2, - "first new transaction after migration must get tx_count=2" - ); - } - #[test] fn test_save_writes_packed_pages() { use crate::storage::backend::FileBackend; @@ -1804,70 +1292,6 @@ mod tests { } } - #[test] - fn test_v4_database_migrates_to_v5_on_open() { - use crate::storage::backend::FileBackend; - use crate::storage::{FACT_PAGE_FORMAT_PACKED, PAGE_SIZE}; - use tempfile::NamedTempFile; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let alice = Uuid::new_v4(); - - // Write a "v4-style" file: version=4, fact_page_format byte = 0 (legacy padding) - { - use crate::storage::FileHeader; - let fact = crate::graph::types::Fact::with_valid_time( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - 1u64, - 1u64, - 0i64, - i64::MAX, - ); - let mut backend = FileBackend::open(&path).unwrap(); - - // Write fact at page 1 (one-per-page format) - let data = postcard::to_allocvec(&fact).unwrap(); - let mut page = vec![0u8; PAGE_SIZE]; - page[..data.len()].copy_from_slice(&data); - backend.write_page(1, &page).unwrap(); - - // Write v4 header (fact_page_format byte will be 0) - let mut header = FileHeader::new(); - header.page_count = 2; - header.node_count = 1; - let mut hbytes = header.to_bytes(); - // Force version to 4 - hbytes[4..8].copy_from_slice(&4u32.to_le_bytes()); - // Force fact_page_format byte (offset 68) to 0 - hbytes[68] = 0; - hbytes.resize(PAGE_SIZE, 0); - backend.write_page(0, &hbytes).unwrap(); - backend.sync().unwrap(); - } - - // Open — should auto-migrate to v7 - { - let pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - assert_eq!( - pfs.storage().fact_count(), - 1, - "migrated fact must be loaded" - ); - } - - // Verify file is now v7 - { - let backend = FileBackend::open(&path).unwrap(); - let header_bytes = backend.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_bytes).unwrap(); - assert_eq!(header.version, 7, "file must be upgraded to v7"); - assert_eq!(header.fact_page_format, FACT_PAGE_FORMAT_PACKED); - } - } - #[test] fn test_v5_load_fast_path_indexes_loaded() { use crate::storage::backend::FileBackend; @@ -2013,53 +1437,6 @@ mod tests { ); } - #[test] - fn test_v6_migration_from_v5_unit() { - let mut backend = MemoryBackend::new(); - let mut page = vec![0u8; PAGE_SIZE]; - page[0..4].copy_from_slice(b"MGRF"); - page[4..8].copy_from_slice(&5u32.to_le_bytes()); // version = 5 - page[8..16].copy_from_slice(&2u64.to_le_bytes()); // page_count = 2 (header + 1 empty page) - page[68] = 0x02; // fact_page_format = PACKED - backend.write_page(0, &page).unwrap(); - // Write an empty fact page so page_count > 1 triggers load() - backend.write_page(1, &vec![0u8; PAGE_SIZE]).unwrap(); - - let s = PersistentFactStorage::new(backend, 256).unwrap(); - let b = s.into_backend().unwrap(); - let header_page = b.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_page).unwrap(); - assert_eq!(header.version, 7, "migration must upgrade header to v7"); - assert_eq!(header.to_bytes().len(), 84, "v7 header must be 84 bytes"); - // page_count=2 means 1 fact page (page 1), even if empty - assert_eq!( - header.fact_page_count, 1, - "fact_page_count must reflect page layout" - ); - } - - #[test] - fn test_v6_migration_crash_safe_unit() { - let mut backend = MemoryBackend::new(); - let mut page = vec![0u8; PAGE_SIZE]; - page[0..4].copy_from_slice(b"MGRF"); - page[4..8].copy_from_slice(&5u32.to_le_bytes()); - page[8..16].copy_from_slice(&1u64.to_le_bytes()); // page_count = 1 - page[68] = 0x02; - backend.write_page(0, &page).unwrap(); - backend.write_page(1, &vec![0xFF_u8; PAGE_SIZE]).unwrap(); - backend.write_page(2, &vec![0xFF_u8; PAGE_SIZE]).unwrap(); - - let s = PersistentFactStorage::new(backend, 256).unwrap(); - let b = s.into_backend().unwrap(); - let header_bytes = b.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_bytes).unwrap(); - assert_eq!( - header.version, 7, - "migration must complete despite prior partial run" - ); - } - /// Regression test for fuzz-discovered timeout (artifact: /// `timeout-23b2b7e0aa43d92c12c49f123a48d6f4ace6ce33`). /// @@ -2069,8 +1446,7 @@ mod tests { /// compute_page_checksum looped over 3.6 billion zero-filled sparse pages /// (each read_exact returns zeros, no error), hanging the process. /// - /// After the fix, next_free = 1 + validated_num_fact_pages (= 1 here), - /// so migration completes in constant time and produces a sane v7 header. + /// Since v3.0.0 a v5 header is rejected before any page is touched. #[test] fn test_v5_migration_large_page_count_does_not_hang() { use crate::storage::backend::FileBackend; @@ -2088,19 +1464,16 @@ mod tests { page[68] = 0x20; // fact_page_format std::fs::write(&path, &page).unwrap(); - // Must complete without hanging; next_free must be computed from actual - // fact pages (= 1 + 0 = 1), not from the crafted header.page_count. - let s = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256) - .expect("migration must complete"); - let b = s.into_backend().unwrap(); - let header_bytes = b.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_bytes).unwrap(); - assert_eq!(header.version, 7, "migration must upgrade to v7"); - // Resulting page_count must be small (0 fact pages + 4 index pages + header), - // NOT the crafted 3.6-billion-page value. + // `FileBackend::open` itself reads and validates the header, so the + // pre-v7 rejection surfaces there rather than in + // `PersistentFactStorage::new`. + let err = match FileBackend::open(&path) { + Ok(_) => panic!("v5 header must be rejected"), + Err(e) => e, + }; assert!( - header.page_count < 100, - "page_count must be sane after migration" + err.to_string().contains("no longer supported"), + "must fail with STG-028" ); } diff --git a/tests/btree_v6_test.rs b/tests/btree_v6_test.rs index b2a813132..d3cd77050 100644 --- a/tests/btree_v6_test.rs +++ b/tests/btree_v6_test.rs @@ -110,49 +110,29 @@ fn test_v6_pending_plus_committed_merge() { } #[test] -fn test_v6_migration_from_v5_eager() { - // Write a minimal v5 header directly to the .graph file (raw bytes), - // then open with v6 code — migrate_v5_to_v6 must run and produce a v6 file. - // We cannot use OpenOptions to produce a v5 file (v6 code always writes v6), - // so we write the raw 72-byte v5 header at offset 0. +fn test_v5_file_is_rejected() { + // v3.0.0 dropped support for formats v1–v6. Write a minimal v5 header + // directly to the .graph file (raw bytes) and verify that opening it + // fails with STG-028 and leaves the file unmodified. let (_tmp, path) = tmp_path(); - // Create an empty v5 .graph file with only a header (no facts, no index pages) - { - let mut f = std::fs::OpenOptions::new() - .create(true) - .write(true) - .truncate(true) - .open(&path) - .unwrap(); - let mut page = vec![0u8; 4096]; // PAGE_SIZE - page[0..4].copy_from_slice(b"MGRF"); - page[4..8].copy_from_slice(&5u32.to_le_bytes()); // version = 5 - page[8..16].copy_from_slice(&1u64.to_le_bytes()); // page_count = 1 - page[68] = 0x02; // fact_page_format = PACKED - use std::io::Write; - f.write_all(&page).unwrap(); - } + let mut page = vec![0u8; 4096]; // PAGE_SIZE + page[0..4].copy_from_slice(b"MGRF"); + page[4..8].copy_from_slice(&5u32.to_le_bytes()); // version = 5 + page[8..16].copy_from_slice(&1u64.to_le_bytes()); // page_count = 1 + page[68] = 0x02; // fact_page_format = PACKED + std::fs::write(&path, &page).unwrap(); - // Open with v6 code — migration must run - let db = OpenOptions::new().path(&path).open().unwrap(); + let err = match OpenOptions::new().path(&path).open() { + Ok(_) => panic!("v5 file must not open"), + Err(e) => e, + }; + assert_eq!(err.code(), "STG-028", "v5 file must fail with STG-028"); - // Query on empty DB must return empty result (not an error) - let _result = db - .execute("(query [:find ?e :where [?e :any :any]])") - .unwrap(); - drop(db); - - // Re-open and verify header was upgraded to v6 - let mut f = std::fs::File::open(&path).unwrap(); - let mut header_bytes = vec![0u8; 4096]; - use std::io::Read; - f.read_exact(&mut header_bytes).unwrap(); - let version = u32::from_le_bytes(header_bytes[4..8].try_into().unwrap()); assert_eq!( - version, 7, - "header must be upgraded from v5 to v7; got version={}", - version + std::fs::read(&path).unwrap(), + page, + "rejected file must be left unmodified" ); } diff --git a/tests/error_codes_storage_test.rs b/tests/error_codes_storage_test.rs index 9920ac06b..edebe0ea5 100644 --- a/tests/error_codes_storage_test.rs +++ b/tests/error_codes_storage_test.rs @@ -69,6 +69,23 @@ fn open_unsupported_version_returns_stg_006() { assert_eq!(err.category(), ErrorCategory::Storage); } +#[test] +fn open_pre_v7_version_returns_stg_028() { + let dir = scratch_dir("pre_v7"); + let path = dir.join("db.graph"); + write_file( + &path, + &header_page(|b| { + b[4..8].copy_from_slice(&6u32.to_le_bytes()); // version = 6 + }), + ); + let err = match Minigraf::open(&path) { + Ok(_) => panic!("opening a v6 file should fail"), + Err(e) => e, + }; + assert_eq!(err.code(), "STG-028"); +} + #[test] fn open_zero_page_count_returns_stg_007() { let dir = scratch_dir("zero_pages"); diff --git a/tests/migration_matrix_test.rs b/tests/migration_matrix_test.rs index 787b5b295..a6c2482ac 100644 --- a/tests/migration_matrix_test.rs +++ b/tests/migration_matrix_test.rs @@ -34,24 +34,34 @@ fn v7_round_trip_is_idempotent() { assert_eq!(n, 1, "v7 round-trip: Alice must survive close/reopen"); } +/// Formats v1–v6 are no longer readable (v3.0.0 file-format policy). Opening +/// one must fail with STG-028 and must not modify the file. #[test] -fn v3_empty_migrates_without_error() { - use std::io::Write; - let dir = tempfile::tempdir().unwrap(); - let path = dir.path().join("v3.graph"); - // Build a minimally valid v3 header: magic + version=3 + page_count=1 - // All other fields zero (roots=0 means empty index, fact_count=0). - let mut page = vec![0u8; PAGE_SIZE]; - page[0..4].copy_from_slice(&MAGIC_NUMBER); - page[4..8].copy_from_slice(&3u32.to_le_bytes()); // version - page[8..16].copy_from_slice(&1u64.to_le_bytes()); // page_count = 1 - let mut f = std::fs::File::create(&path).unwrap(); - f.write_all(&page).unwrap(); - drop(f); - assert!( - Minigraf::open(&path).is_ok(), - "v3 empty file should open without error" - ); +fn pre_v7_versions_are_rejected_with_stg_028() { + for version in 1u32..=6 { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("old.graph"); + let mut page = vec![0u8; PAGE_SIZE]; + page[0..4].copy_from_slice(&MAGIC_NUMBER); + page[4..8].copy_from_slice(&version.to_le_bytes()); + page[8..16].copy_from_slice(&1u64.to_le_bytes()); // page_count = 1 + std::fs::write(&path, &page).unwrap(); + + let err = match Minigraf::open(&path) { + Ok(_) => panic!("pre-v7 file must not open"), + Err(e) => e, + }; + assert_eq!(err.code(), "STG-028", "pre-v7 file must fail with STG-028"); + assert!( + err.to_string().contains("v2.x"), + "STG-028 message must tell the user how to upgrade" + ); + assert_eq!( + std::fs::read(&path).unwrap(), + page, + "rejected file must be left unmodified" + ); + } } #[test] @@ -85,6 +95,7 @@ fn unsupported_version_fails_loudly() { f.write_all(&page).unwrap(); let result = Minigraf::open(&path); assert!(result.is_err(), "unsupported version must produce an error"); + assert_eq!(result.err().unwrap().code(), "STG-006"); } #[test] diff --git a/tests/wal_test.rs b/tests/wal_test.rs index 02cdc4a20..58d8bd303 100644 --- a/tests/wal_test.rs +++ b/tests/wal_test.rs @@ -9,7 +9,7 @@ //! - Auto-checkpoint threshold //! - Explicit transaction commit and rollback //! - Concurrent reads while writer holds the write lock -//! - V2 → V3 file format upgrade on first checkpoint +//! - Pre-v7 file formats (e.g. V2) are rejected, not silently upgraded #![cfg(not(target_arch = "wasm32"))] use minigraf::QueryResult; @@ -720,13 +720,13 @@ fn write_state_clean_after_drop() { assert_eq!(n, 1, "only committed fact visible after dropped tx"); } -// ── 12. V2 file upgrades to V3 on checkpoint ───────────────────────────────── +// ── 12. V2 file is rejected ────────────────────────────────────────────────── -/// Create a v2-format `.graph` file manually (version field = 2, no -/// `last_checkpointed_tx_count`), open it with `Minigraf`, write a fact, -/// checkpoint, then read the raw header and verify it is now v3. +/// v3.0.0 dropped support for formats v1–v6. Create a v2-format `.graph` +/// file manually (version field = 2) and verify that opening it fails with +/// STG-028 rather than silently upgrading it. #[test] -fn test_v2_file_opens_and_upgrades_to_v3_on_checkpoint() { +fn test_v2_file_is_rejected() { use std::io::Write; let dir = tempfile::tempdir().unwrap(); @@ -734,14 +734,6 @@ fn test_v2_file_opens_and_upgrades_to_v3_on_checkpoint() { // ── Build a minimal v2 `.graph` file ────────────────────────────────── // - // V2 and V3 have identical binary layouts. - // The only difference is the version field (bytes 4-7): 2 vs 3. - // In V2, bytes 24-31 were the unused `edge_count` field (always 0). - // Phase 5 repurposed that slot as `last_checkpointed_tx_count` without - // changing the wire layout. Opening a V2 file with Phase 5 code works - // transparently because `last_checkpointed_tx_count` reads as 0 from - // the old `edge_count` slot. - // // The file contains exactly 1 page (the header page, 4096 bytes). { let mut page = vec![0u8; PAGE_SIZE]; @@ -751,39 +743,15 @@ fn test_v2_file_opens_and_upgrades_to_v3_on_checkpoint() { page[4..8].copy_from_slice(&2u32.to_le_bytes()); // page_count = 1 page[8..16].copy_from_slice(&1u64.to_le_bytes()); - // node_count = 0 (bytes 16..24 already zero) - // last_checkpointed_tx_count = 0 (bytes 24..32 already zero) - // reserved = 0 (bytes 32..64 already zero) let mut file = std::fs::File::create(&db_path).unwrap(); file.write_all(&page).unwrap(); file.sync_all().unwrap(); } - // ── Open, write a fact, and checkpoint ──────────────────────────────── - { - let db = Minigraf::open(&db_path).unwrap(); - db.execute(r#"(transact [[:alice :name "Alice"]])"#) - .unwrap(); - db.checkpoint().unwrap(); - // Drop runs another checkpoint, but that's idempotent. - } - - // ── Read the raw header and assert version = 7 ─────────────────────── - // Reads raw bytes: magic at 0..4, version at 4..8 (u32 LE), - // last_checkpointed_tx_count at 24..32 (u64 LE). - let raw = std::fs::read(&db_path).unwrap(); - assert!( - raw.len() >= PAGE_SIZE, - "file must be at least one page after checkpoint" - ); - let magic = &raw[0..4]; - let version = u32::from_le_bytes(raw[4..8].try_into().unwrap()); - let last_checkpointed_tx_count = u64::from_le_bytes(raw[24..32].try_into().unwrap()); - assert_eq!(version, 7, "file must be upgraded to v7 on checkpoint"); - assert_eq!(magic, b"MGRF", "magic number must be preserved"); - assert!( - last_checkpointed_tx_count > 0, - "last_checkpointed_tx_count must be set after checkpoint on v2→v6 upgrade" - ); + let err = match Minigraf::open(&db_path) { + Ok(_) => panic!("v2 file must not open"), + Err(e) => e, + }; + assert_eq!(err.code(), "STG-028", "v2 file must fail with STG-028"); } From c74f89d630e44b763e1da1c0f3f08f35c9688f34 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 12:21:43 +0530 Subject: [PATCH 07/21] =?UTF-8?q?feat!:=20file=20format=20v8=20=E2=80=94?= =?UTF-8?q?=20value=20bytes=20and=20asserted=20flag=20in=20index=20keys=20?= =?UTF-8?q?(#371,=20#287)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit EavtKey/AevtKey gain value_bytes and asserted; AvetKey/VaetKey gain asserted. Fields are appended so range-scan order is unchanged. All key construction goes through per-key constructors. A v7 file is always re-indexed from its fact pages on open and rewritten with a v8 header. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- examples/generate_compat_fixture.rs | 10 +- src/browser/mod.rs | 8 + src/graph/storage.rs | 33 +-- src/storage/btree_v6.rs | 24 ++ src/storage/index.rs | 397 ++++++++++++++++++---------- src/storage/mod.rs | 21 +- src/storage/persistent_facts.rs | 154 ++++++----- tests/cross_platform_compat_test.rs | 11 +- 8 files changed, 398 insertions(+), 260 deletions(-) diff --git a/examples/generate_compat_fixture.rs b/examples/generate_compat_fixture.rs index b8b0b098c..7e781e462 100644 --- a/examples/generate_compat_fixture.rs +++ b/examples/generate_compat_fixture.rs @@ -1,12 +1,12 @@ -//! Generates `tests/fixtures/compat.graph` — a minimal v7 `.graph` file containing -//! two known facts used by the cross-platform compatibility tests. +//! Generates a `.graph` file with two known facts (the committed `compat.graph` is +//! the frozen v7 output of this example from v2.0.0). //! //! Run once when the file format changes or the fixture needs regenerating: //! cargo run --example generate_compat_fixture //! -//! The fixture is committed to the repository. Do not regenerate it unless the -//! v7 file format itself has changed — regenerating changes the binary and -//! every cross-platform test that embeds it via `include_bytes!`. +//! `compat.graph` is the frozen v7 fixture written by Minigraf v2.0.0; the +//! cross-platform tests use it to check v7→v8 migration. Do not regenerate it +//! — running this example now writes a v8 file. // wasm-pack compiles examples for the browser target; provide a no-op entry // point so the example compiles cleanly. The actual generator only makes sense diff --git a/src/browser/mod.rs b/src/browser/mod.rs index 75daf39f0..e8a065f42 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -483,6 +483,14 @@ mod tests { "expected 1 age result from native fixture" ); assert_eq!(results2[0][0], serde_json::Value::Number(30.into())); + + let exported = db.export_graph().expect("export after import"); + let bytes = exported.to_vec(); + assert_eq!( + u32::from_le_bytes(bytes[4..8].try_into().unwrap()), + 8, + "v7 fixture must be upgraded to v8 on import" + ); } /// #275: `BrowserBufferBackend` is already an in-memory page store, so the diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 74c9405d7..693551597 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -621,21 +621,9 @@ impl FactStorage { use crate::storage::index::EavtKey; let d = self.data.read().unwrap_or_else(|e| e.into_inner()); - let start = EavtKey { - entity: *entity_id, - attribute: String::new(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - }; + let start = EavtKey::entity_start(*entity_id); let next_entity = uuid::Uuid::from_u128(entity_id.as_u128().wrapping_add(1)); - let end = EavtKey { - entity: next_entity, - attribute: String::new(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - }; + let end = EavtKey::entity_start(next_entity); // Fallback: no indexes built yet if d.pending_indexes.eavt.is_empty() && d.committed_index_reader.is_none() { @@ -699,20 +687,9 @@ impl FactStorage { .collect()); } - let start = AevtKey { - attribute: attribute.clone(), - entity: uuid::Uuid::nil(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - }; - let end_opt: Option = next_string_prefix(attribute).map(|next_attr| AevtKey { - attribute: next_attr, - entity: uuid::Uuid::nil(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - }); + let start = AevtKey::attribute_start(attribute); + let end_opt: Option = + next_string_prefix(attribute).map(|next_attr| AevtKey::attribute_start(&next_attr)); let mut facts = Vec::new(); diff --git a/src/storage/btree_v6.rs b/src/storage/btree_v6.rs index 5c5a9b9e1..e9a6020b3 100644 --- a/src/storage/btree_v6.rs +++ b/src/storage/btree_v6.rs @@ -818,6 +818,8 @@ mod tests { valid_from: 0, valid_to: i64::MAX, tx_count: tx, + value_bytes: Vec::new(), + asserted: true, }, FactRef { page_id: tx + 1, @@ -1087,6 +1089,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let next_entity = Uuid::from_u128(43); let end = EavtKey { @@ -1095,6 +1099,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let refs = range_scan(root, &start, Some(&end), &backend, &cache).unwrap(); @@ -1125,6 +1131,8 @@ mod tests { valid_from: 0, valid_to: 0, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let refs = range_scan::(root, &start, None, &backend, &cache).unwrap(); assert_eq!(refs.len(), 0); @@ -1146,6 +1154,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let refs = range_scan::(root, &start, None, &backend, &cache).unwrap(); assert_eq!(refs.len(), 5, "entities 5..9 = 5 entries"); @@ -1167,6 +1177,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let end = EavtKey { entity: Uuid::from_u128(200), @@ -1174,6 +1186,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let refs = range_scan(root, &start, Some(&end), &backend, &cache).unwrap(); // NOTE: The end key has attribute="" which sorts BEFORE ":a". So entity 200's @@ -1243,6 +1257,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let err = range_scan::(root, &start, None, &backend, &cache) .expect_err("following a next_leaf pointer into a non-leaf page must fail"); @@ -1272,6 +1288,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let end = EavtKey { entity: Uuid::from_u128(10), @@ -1279,6 +1297,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let refs = reader.range_scan_eavt(&start, Some(&end)).unwrap(); // Same exclusion logic: entity 10's entry {10, ":x", ...} > end {10, "", ...} @@ -1320,6 +1340,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let end = EavtKey { entity: Uuid::from_u128(20), @@ -1327,6 +1349,8 @@ mod tests { valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, + value_bytes: Vec::new(), + asserted: true, }; let barrier = Arc::new(Barrier::new(8)); diff --git a/src/storage/index.rs b/src/storage/index.rs index 8eb59ea89..9099c4660 100644 --- a/src/storage/index.rs +++ b/src/storage/index.rs @@ -7,19 +7,6 @@ use crate::graph::types::{Attribute, EntityId, Fact, Value}; use serde::{Deserialize, Serialize}; -use uuid::Uuid; - -/// Generate the maximum UUID value (all bits set to 1). -/// Used as an upper bound for range queries on UUID fields. -fn max_uuid() -> Uuid { - // This is safe because MAX_UUID is a valid hardcoded UUID string literal. - // It will never fail at runtime. - const MAX_UUID_BYTES: [u8; 16] = [ - 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, - 0xFF, - ]; - Uuid::from_bytes(MAX_UUID_BYTES) -} // ─── FactRef ──────────────────────────────────────────────────────────────── @@ -97,7 +84,11 @@ pub fn encode_value(v: &Value) -> Vec { // ─── Index Key Types ───────────────────────────────────────────────────────── -/// EAVT: sort by (Entity, Attribute, ValidFrom, ValidTo, TxCount) +/// EAVT: sort by (Entity, Attribute, ValidFrom, ValidTo, TxCount, ValueBytes, Asserted) +/// +/// `value_bytes` and `asserted` come last so entity/attribute range scans keep +/// their order; they keep facts that differ only in value or assert/retract +/// from colliding (#371, #287). #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] pub struct EavtKey { pub entity: EntityId, @@ -105,9 +96,15 @@ pub struct EavtKey { pub valid_from: i64, pub valid_to: i64, pub tx_count: u64, + pub value_bytes: Vec, + pub asserted: bool, } -/// AEVT: sort by (Attribute, Entity, ValidFrom, ValidTo, TxCount) +/// AEVT: sort by (Attribute, Entity, ValidFrom, ValidTo, TxCount, ValueBytes, Asserted) +/// +/// `value_bytes` and `asserted` come last so entity/attribute range scans keep +/// their order; they keep facts that differ only in value or assert/retract +/// from colliding (#371, #287). #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] pub struct AevtKey { pub attribute: Attribute, @@ -115,9 +112,11 @@ pub struct AevtKey { pub valid_from: i64, pub valid_to: i64, pub tx_count: u64, + pub value_bytes: Vec, + pub asserted: bool, } -/// AVET: sort by (Attribute, ValueBytes, ValidFrom, ValidTo, Entity, TxCount) +/// AVET: sort by (Attribute, ValueBytes, ValidFrom, ValidTo, Entity, TxCount, Asserted) /// /// `value_bytes` is the canonical encoding from `encode_value`. #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] @@ -128,9 +127,10 @@ pub struct AvetKey { pub valid_to: i64, pub entity: EntityId, pub tx_count: u64, + pub asserted: bool, } -/// VAET: sort by (RefTarget, Attribute, ValidFrom, ValidTo, SourceEntity, TxCount) +/// VAET: sort by (RefTarget, Attribute, ValidFrom, ValidTo, SourceEntity, TxCount, Asserted) /// /// Only facts with `Value::Ref` are indexed here. #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] @@ -141,6 +141,93 @@ pub struct VaetKey { pub valid_to: i64, pub source_entity: EntityId, pub tx_count: u64, + pub asserted: bool, +} + +impl EavtKey { + pub fn from_fact(f: &Fact) -> Self { + EavtKey { + entity: f.entity, + attribute: f.attribute.clone(), + valid_from: f.valid_from, + valid_to: f.valid_to, + tx_count: f.tx_count, + value_bytes: encode_value(&f.value), + asserted: f.asserted, + } + } + + /// Smallest possible key for `entity`: every EAVT key of that entity sorts at or after it. + pub fn entity_start(entity: EntityId) -> Self { + EavtKey { + entity, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + value_bytes: Vec::new(), + asserted: false, + } + } +} + +impl AevtKey { + pub fn from_fact(f: &Fact) -> Self { + AevtKey { + attribute: f.attribute.clone(), + entity: f.entity, + valid_from: f.valid_from, + valid_to: f.valid_to, + tx_count: f.tx_count, + value_bytes: encode_value(&f.value), + asserted: f.asserted, + } + } + + /// Smallest possible key for `attribute`. + pub fn attribute_start(attribute: &str) -> Self { + AevtKey { + attribute: attribute.to_string(), + entity: EntityId::nil(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + value_bytes: Vec::new(), + asserted: false, + } + } +} + +impl AvetKey { + pub fn from_fact(f: &Fact) -> Self { + AvetKey { + attribute: f.attribute.clone(), + value_bytes: encode_value(&f.value), + valid_from: f.valid_from, + valid_to: f.valid_to, + entity: f.entity, + tx_count: f.tx_count, + asserted: f.asserted, + } + } +} + +impl VaetKey { + /// `None` unless the fact's value is a `Value::Ref` (only refs are VAET-indexed). + pub fn from_fact(f: &Fact) -> Option { + match &f.value { + Value::Ref(target) => Some(VaetKey { + ref_target: *target, + attribute: f.attribute.clone(), + valid_from: f.valid_from, + valid_to: f.valid_to, + source_entity: f.entity, + tx_count: f.tx_count, + asserted: f.asserted, + }), + _ => None, + } + } } // ─── Indexes ───────────────────────────────────────────────────────────────── @@ -167,159 +254,67 @@ impl Indexes { /// `FactRef { page_id: 0, slot_index: 0 }` as a placeholder; real /// page IDs are assigned by `save()` and updated via `reindex_from_facts`. pub fn insert(&mut self, fact: &Fact, fact_ref: FactRef) { - self.eavt.insert( - EavtKey { - entity: fact.entity, - attribute: fact.attribute.clone(), - valid_from: fact.valid_from, - valid_to: fact.valid_to, - tx_count: fact.tx_count, - }, - fact_ref, - ); - - self.aevt.insert( - AevtKey { - attribute: fact.attribute.clone(), - entity: fact.entity, - valid_from: fact.valid_from, - valid_to: fact.valid_to, - tx_count: fact.tx_count, - }, - fact_ref, - ); - - self.avet.insert( - AvetKey { - attribute: fact.attribute.clone(), - value_bytes: encode_value(&fact.value), - valid_from: fact.valid_from, - valid_to: fact.valid_to, - entity: fact.entity, - tx_count: fact.tx_count, - }, - fact_ref, - ); - - if let Value::Ref(target) = &fact.value { - self.vaet.insert( - VaetKey { - ref_target: *target, - attribute: fact.attribute.clone(), - valid_from: fact.valid_from, - valid_to: fact.valid_to, - source_entity: fact.entity, - tx_count: fact.tx_count, - }, - fact_ref, - ); + self.eavt.insert(EavtKey::from_fact(fact), fact_ref); + self.aevt.insert(AevtKey::from_fact(fact), fact_ref); + self.avet.insert(AvetKey::from_fact(fact), fact_ref); + if let Some(k) = VaetKey::from_fact(fact) { + self.vaet.insert(k, fact_ref); } } /// Query EAVT index for a specific entity (returns all facts for that entity). pub fn lookup_eavt_entity(&self, entity: EntityId) -> Vec { - let start = EavtKey { - entity, - attribute: String::new(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - }; - // Use exclusive range with a very high attribute string - let end = EavtKey { - entity, - attribute: String::from("zzzzzzzzzzzzzzzzzz"), - valid_from: i64::MAX, - valid_to: i64::MAX, - tx_count: u64::MAX, - }; - self.eavt.range(start..end).map(|(_, v)| *v).collect() - } - - /// Query EAVT index for entity + attribute. - #[allow(dead_code)] - pub fn lookup_eavt_entity_attr(&self, entity: EntityId, attribute: &str) -> Vec { - let start = EavtKey { - entity, - attribute: attribute.to_string(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - }; - let end = EavtKey { - entity, - attribute: attribute.to_string(), - valid_from: i64::MAX, - valid_to: i64::MAX, - tx_count: u64::MAX, - }; - self.eavt.range(start..=end).map(|(_, v)| *v).collect() + self.eavt + .range(EavtKey::entity_start(entity)..) + .take_while(|(k, _)| k.entity == entity) + .map(|(_, v)| *v) + .collect() } /// Query AEVT index for a specific attribute (returns all facts with that attribute). pub fn lookup_aevt_attr(&self, attribute: &str) -> Vec { - let max_uuid = max_uuid(); - let start = AevtKey { - attribute: attribute.to_string(), - entity: EntityId::default(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - }; - let end = AevtKey { - attribute: attribute.to_string(), - entity: max_uuid, - valid_from: i64::MAX, - valid_to: i64::MAX, - tx_count: u64::MAX, - }; - self.aevt.range(start..=end).map(|(_, v)| *v).collect() + self.aevt + .range(AevtKey::attribute_start(attribute)..) + .take_while(|(k, _)| k.attribute == attribute) + .map(|(_, v)| *v) + .collect() } /// Query AVET index for attribute + value. pub fn lookup_avet_attr_value(&self, attribute: &str, value: &Value) -> Vec { - let max_uuid = max_uuid(); let value_bytes = encode_value(value); let start = AvetKey { attribute: attribute.to_string(), value_bytes: value_bytes.clone(), valid_from: i64::MIN, valid_to: i64::MIN, - entity: EntityId::default(), + entity: EntityId::nil(), tx_count: 0, + asserted: false, }; - let end = AvetKey { - attribute: attribute.to_string(), - value_bytes, - valid_from: i64::MAX, - valid_to: i64::MAX, - entity: max_uuid, - tx_count: u64::MAX, - }; - self.avet.range(start..=end).map(|(_, v)| *v).collect() + self.avet + .range(start..) + .take_while(|(k, _)| k.attribute == attribute && k.value_bytes == value_bytes) + .map(|(_, v)| *v) + .collect() } /// Query VAET index for ref target (reverse references). pub fn lookup_vaet_ref(&self, target: EntityId) -> Vec { - let max_uuid = max_uuid(); let start = VaetKey { ref_target: target, attribute: String::new(), valid_from: i64::MIN, valid_to: i64::MIN, - source_entity: EntityId::default(), + source_entity: EntityId::nil(), tx_count: 0, + asserted: false, }; - let end = VaetKey { - ref_target: target, - // Use max char to include all attributes - attribute: char::MAX.to_string(), - valid_from: i64::MAX, - valid_to: i64::MAX, - source_entity: max_uuid, - tx_count: u64::MAX, - }; - self.vaet.range(start..=end).map(|(_, v)| *v).collect() + self.vaet + .range(start..) + .take_while(|(k, _)| k.ref_target == target) + .map(|(_, v)| *v) + .collect() } } @@ -329,6 +324,126 @@ mod tests { use crate::graph::types::{Fact, VALID_TIME_FOREVER, Value}; use uuid::Uuid; + fn fact_at(entity: Uuid, attr: &str, value: Value, asserted: bool) -> Fact { + let mut f = Fact::with_valid_time( + entity, + attr.to_string(), + value, + 100, + 7, + 100, + VALID_TIME_FOREVER, + ); + f.asserted = asserted; + f + } + + /// #371: two values of one attribute in one transaction must both be indexed. + #[test] + fn same_tx_multi_value_keeps_both_entries_in_all_indexes() { + let e = Uuid::from_u128(1); + let t1 = Uuid::from_u128(10); + let t2 = Uuid::from_u128(11); + let mut idx = Indexes::new(); + idx.insert( + &fact_at(e, ":kind", Value::Ref(t1), true), + FactRef { + page_id: 0, + slot_index: 0, + }, + ); + idx.insert( + &fact_at(e, ":kind", Value::Ref(t2), true), + FactRef { + page_id: 0, + slot_index: 1, + }, + ); + assert_eq!( + idx.lookup_eavt_entity(e).len(), + 2, + "EAVT must keep both values" + ); + assert_eq!( + idx.lookup_aevt_attr(":kind").len(), + 2, + "AEVT must keep both values" + ); + assert_eq!(idx.eavt.len(), 2); + assert_eq!(idx.aevt.len(), 2); + assert_eq!(idx.avet.len(), 2); + assert_eq!(idx.vaet.len(), 2); + } + + /// An assertion and a retraction of the same value at the same tx_count + /// must not collide in any index. + #[test] + fn same_tx_assert_and_retract_keep_both_entries_in_all_indexes() { + let e = Uuid::from_u128(1); + let t = Uuid::from_u128(10); + let mut idx = Indexes::new(); + idx.insert( + &fact_at(e, ":kind", Value::Ref(t), true), + FactRef { + page_id: 0, + slot_index: 0, + }, + ); + idx.insert( + &fact_at(e, ":kind", Value::Ref(t), false), + FactRef { + page_id: 0, + slot_index: 1, + }, + ); + assert_eq!(idx.eavt.len(), 2, "EAVT must keep assert and retract"); + assert_eq!(idx.aevt.len(), 2, "AEVT must keep assert and retract"); + assert_eq!(idx.avet.len(), 2, "AVET must keep assert and retract"); + assert_eq!(idx.vaet.len(), 2, "VAET must keep assert and retract"); + } + + #[test] + fn lookups_do_not_leak_neighbouring_entities_or_attributes() { + let (a, b) = (Uuid::from_u128(1), Uuid::from_u128(2)); + let mut idx = Indexes::new(); + idx.insert( + &fact_at(a, ":x", Value::Integer(1), true), + FactRef { + page_id: 0, + slot_index: 0, + }, + ); + idx.insert( + &fact_at(b, ":x", Value::Integer(1), true), + FactRef { + page_id: 0, + slot_index: 1, + }, + ); + idx.insert( + &fact_at(a, ":xy", Value::Integer(1), true), + FactRef { + page_id: 0, + slot_index: 2, + }, + ); + assert_eq!(idx.lookup_eavt_entity(a).len(), 2); + assert_eq!(idx.lookup_aevt_attr(":x").len(), 2); + assert_eq!( + idx.lookup_avet_attr_value(":x", &Value::Integer(1)).len(), + 2 + ); + } + + #[test] + fn entity_and_attribute_start_keys_sort_before_every_matching_key() { + let e = Uuid::from_u128(5); + let f = fact_at(e, ":a", Value::Null, false); + assert!(EavtKey::entity_start(e) <= EavtKey::from_fact(&f)); + assert!(AevtKey::attribute_start(":a") <= AevtKey::from_fact(&f)); + assert!(EavtKey::entity_start(Uuid::from_u128(6)) > EavtKey::from_fact(&f)); + } + #[test] fn test_fact_ref_fields() { let r = FactRef { @@ -382,6 +497,8 @@ mod tests { valid_from: 0, valid_to: i64::MAX, tx_count: 1, + value_bytes: Vec::new(), + asserted: true, }; let k2 = EavtKey { entity: e2, @@ -389,6 +506,8 @@ mod tests { valid_from: 0, valid_to: i64::MAX, tx_count: 1, + value_bytes: Vec::new(), + asserted: true, }; assert!(k1 < k2); } @@ -403,6 +522,7 @@ mod tests { valid_to: i64::MAX, entity: e, tx_count: 1, + asserted: true, }; let k2 = AvetKey { attribute: ":score".to_string(), @@ -411,6 +531,7 @@ mod tests { valid_to: i64::MAX, entity: e, tx_count: 2, + asserted: true, }; assert!(k1 < k2); } diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 3657aedf9..34f324f65 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -44,7 +44,7 @@ pub const PAGE_SIZE: usize = 4096; pub const MAGIC_NUMBER: [u8; 4] = *b"MGRF"; /// Current file format version -pub const FORMAT_VERSION: u32 = 7; +pub const FORMAT_VERSION: u32 = 8; /// Oldest file format version this library reads. Older files must first be /// opened with Minigraf v2.x, which upgrades them to v7 (see STG-028). @@ -96,7 +96,7 @@ pub trait StorageBackend: Send + Sync { fn is_new(&self) -> bool; } -/// File header for .graph files — 84 bytes in v7. +/// File header for .graph files — 84 bytes (v7 and v8 share the layout). /// /// Layout (all fields little-endian): /// 0..4 magic ("MGRF") @@ -341,8 +341,8 @@ mod tests { } #[test] - fn test_format_version_is_7() { - assert_eq!(FORMAT_VERSION, 7); + fn test_format_version_is_8() { + assert_eq!(FORMAT_VERSION, 8); } #[test] @@ -352,6 +352,13 @@ mod tests { assert!(h.validate().is_ok()); } + #[test] + fn test_validate_accepts_version_8() { + let mut h = FileHeader::new(); + h.version = 8; + assert!(h.validate().is_ok()); + } + #[test] fn test_validate_page_count_must_be_positive() { let mut h = FileHeader::new(); @@ -394,10 +401,10 @@ mod tests { } #[test] - fn test_new_header_has_version_7() { + fn test_new_header_has_version_8() { let header = FileHeader::new(); assert_eq!(header.version, FORMAT_VERSION); - assert_eq!(header.version, 7); + assert_eq!(header.version, 8); } #[test] @@ -436,7 +443,7 @@ mod tests { assert_eq!(b.len(), 84, "v7 header must be exactly 84 bytes"); assert_eq!(&b[0..4], b"MGRF"); - assert_eq!(&b[4..8], &7u32.to_le_bytes()); + assert_eq!(&b[4..8], &FORMAT_VERSION.to_le_bytes()); assert_eq!(&b[8..16], &0x0102_0304_0506_0708_u64.to_le_bytes()); assert_eq!(&b[16..24], &0x1112_1314_1516_1718_u64.to_le_bytes()); assert_eq!(&b[24..32], &0x2122_2324_2526_2728_u64.to_le_bytes()); diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index dd0cf27fe..e2607ee54 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -11,9 +11,9 @@ use crate::storage::btree_v6::{ stream_all_entries, }; use crate::storage::cache::PageCache; -use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey, encode_value}; +use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; use crate::storage::packed_pages::pack_facts; -use crate::storage::{FileHeader, PAGE_SIZE, StorageBackend}; +use crate::storage::{FORMAT_VERSION, FileHeader, PAGE_SIZE, StorageBackend}; use anyhow::Result; use crc32fast::Hasher; use std::sync::atomic::{AtomicU64, Ordering}; @@ -238,32 +238,21 @@ impl PersistentFactStorage { self.committed_fact_pages .store(num_fact_pages, Ordering::SeqCst); - // Compute page-based checksum to verify data integrity. - // New files (post-fix): checksum covers ALL pages (facts + indexes). - // Old files (pre-fix): checksum covers only fact pages. - // Try full checksum first; fall back to fact-only for backwards compat. - let needs_rebuild = if num_fact_pages == 0 || header.eavt_root_page == 0 { + // v7 files carry index keys without value bytes / asserted flags; they + // cannot be decoded as v8 keys, so rebuild every index from the fact + // pages (#371, #287). The header is written last, so a crash mid-rebuild + // leaves a v7 header and the next open rebuilds again. + let needs_rebuild = if header.version < FORMAT_VERSION { + true + } else if num_fact_pages == 0 || header.eavt_root_page == 0 { num_fact_pages > 0 // rebuild if facts exist but no index root } else { let backend = self .backend .lock() .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let stored = header.index_checksum; - // Total data pages: pages 1 through page_count-1 (everything except header) let total_data_pages = header.page_count.saturating_sub(1); - let full_checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; - if full_checksum == stored { - false // new-style checksum matches: facts + indexes verified - } else { - // Fall back: old files stored checksum over fact pages only - let fact_checksum = compute_page_checksum(&*backend, 1, num_fact_pages)?; - if fact_checksum == stored { - false // old-style checksum matches: facts verified, indexes unprotected - } else { - true // neither matches: corruption detected, rebuild - } - } + compute_page_checksum(&*backend, 1, total_data_pages)? != header.index_checksum }; // Register CommittedFactReader on FactStorage (before WAL replay) @@ -559,7 +548,7 @@ impl PersistentFactStorage { let checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; // ── Step E: write header (last write = crash-safe boundary) ───────────── - let mut header = FileHeader::new(); // version=7 + let mut header = FileHeader::new(); // version=FORMAT_VERSION header.page_count = next4; let pending_len = u64::try_from(pending_facts.len()).map_err(|_| err_coded!(ErrorCode::Stg024))?; @@ -776,78 +765,28 @@ fn build_sorted_index_entries( let mut eavt: Vec<(EavtKey, FactRef)> = facts .iter() .zip(refs.iter()) - .map(|(f, &fr)| { - ( - EavtKey { - entity: f.entity, - attribute: f.attribute.clone(), - valid_from: f.valid_from, - valid_to: f.valid_to, - tx_count: f.tx_count, - }, - fr, - ) - }) + .map(|(f, &fr)| (EavtKey::from_fact(f), fr)) .collect(); eavt.sort_unstable_by(|(a, _), (b, _)| a.cmp(b)); let mut aevt: Vec<(AevtKey, FactRef)> = facts .iter() .zip(refs.iter()) - .map(|(f, &fr)| { - ( - AevtKey { - attribute: f.attribute.clone(), - entity: f.entity, - valid_from: f.valid_from, - valid_to: f.valid_to, - tx_count: f.tx_count, - }, - fr, - ) - }) + .map(|(f, &fr)| (AevtKey::from_fact(f), fr)) .collect(); aevt.sort_unstable_by(|(a, _), (b, _)| a.cmp(b)); let mut avet: Vec<(AvetKey, FactRef)> = facts .iter() .zip(refs.iter()) - .map(|(f, &fr)| { - ( - AvetKey { - attribute: f.attribute.clone(), - value_bytes: encode_value(&f.value), - valid_from: f.valid_from, - valid_to: f.valid_to, - entity: f.entity, - tx_count: f.tx_count, - }, - fr, - ) - }) + .map(|(f, &fr)| (AvetKey::from_fact(f), fr)) .collect(); avet.sort_unstable_by(|(a, _), (b, _)| a.cmp(b)); let mut vaet: Vec<(VaetKey, FactRef)> = facts .iter() .zip(refs.iter()) - .filter_map(|(f, &fr)| { - if let crate::graph::types::Value::Ref(target) = &f.value { - Some(( - VaetKey { - ref_target: *target, - attribute: f.attribute.clone(), - valid_from: f.valid_from, - valid_to: f.valid_to, - source_entity: f.entity, - tx_count: f.tx_count, - }, - fr, - )) - } else { - None - } - }) + .filter_map(|(f, &fr)| VaetKey::from_fact(f).map(|k| (k, fr))) .collect(); vaet.sort_unstable_by(|(a, _), (b, _)| a.cmp(b)); @@ -880,6 +819,29 @@ mod tests { assert_eq!(storage.storage().fact_count(), 0); } + #[test] + fn same_tx_multi_value_visible_through_entity_and_attribute_lookups_before_save() { + let pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + let e = Uuid::from_u128(42); + pfs.storage() + .transact( + vec![ + (e, ":kind".to_string(), Value::Keyword(":k/a".to_string())), + (e, ":kind".to_string(), Value::Keyword(":k/b".to_string())), + ], + None, + ) + .unwrap(); + assert_eq!(pfs.storage().get_facts_by_entity(&e).unwrap().len(), 2); + assert_eq!( + pfs.storage() + .get_facts_by_attribute(&":kind".to_string()) + .unwrap() + .len(), + 2 + ); + } + #[test] fn test_persistent_fact_storage_save_load() { // Create separate scopes to test persistence @@ -1237,12 +1199,12 @@ mod tests { pfs.save().unwrap(); } - // Verify: header says v6, fact_page_format = PACKED + // Verify: header says current version, fact_page_format = PACKED { let backend = FileBackend::open(&path).unwrap(); let header_bytes = backend.read_page(0).unwrap(); let header = crate::storage::FileHeader::from_bytes(&header_bytes).unwrap(); - assert_eq!(header.version, 7); + assert_eq!(header.version, FORMAT_VERSION); assert_eq!( header.fact_page_format, crate::storage::FACT_PAGE_FORMAT_PACKED @@ -1353,8 +1315,11 @@ mod tests { let backend = storage.into_backend().unwrap(); let header_page = backend.read_page(0).unwrap(); let header = crate::storage::FileHeader::from_bytes(&header_page).unwrap(); - assert_eq!(header.version, 7, "save() must write v7 header"); - assert_eq!(header.to_bytes().len(), 84, "v7 header must be 84 bytes"); + assert_eq!( + header.version, FORMAT_VERSION, + "save() must write current-version header" + ); + assert_eq!(header.to_bytes().len(), 84, "header must be 84 bytes"); assert!(header.fact_page_count > 0, "fact_page_count must be set"); assert!( header.eavt_root_page > 0, @@ -1362,6 +1327,35 @@ mod tests { ); } + #[test] + fn v7_header_forces_rebuild_and_upgrades_to_v8() { + use crate::storage::FileHeader; + let e = Uuid::from_u128(7); + let mut backend = { + let mut s = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + s.storage() + .transact(vec![(e, ":n".to_string(), Value::Integer(1))], None) + .unwrap(); + s.mark_dirty(); + s.save().unwrap(); + s.into_backend().unwrap() + }; + // Downgrade the header to v7 (keys on disk are now v8-shaped, which is + // fine: the rebuild never reads them). + let mut h = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); + h.version = 7; + h.header_checksum = compute_header_checksum(&h); + let mut page = h.to_bytes(); + page.resize(PAGE_SIZE, 0); + backend.write_page(0, &page).unwrap(); + + let s = PersistentFactStorage::new(backend, 256).unwrap(); + assert_eq!(s.storage().get_facts_by_entity(&e).unwrap().len(), 1); + let b = s.into_backend().unwrap(); + let h2 = FileHeader::from_bytes(&b.read_page(0).unwrap()).unwrap(); + assert_eq!(h2.version, 8, "v7 file must be upgraded to v8 on open"); + } + #[test] fn test_load_v6_wires_committed_index_reader() { let alice = Uuid::new_v4(); diff --git a/tests/cross_platform_compat_test.rs b/tests/cross_platform_compat_test.rs index 0d1c3a8d0..fc7674a58 100644 --- a/tests/cross_platform_compat_test.rs +++ b/tests/cross_platform_compat_test.rs @@ -82,8 +82,10 @@ fn native_raw_page_bytes_round_trip() { /// Load the committed fixture (produced by `cargo run --example generate_compat_fixture`) /// via `Minigraf::open` and assert that the known facts are present. /// -/// This fixture is also loaded by the browser WASM tests via `include_bytes!` + -/// `BrowserDb::import_graph`, completing the cross-boundary coverage. +/// The fixture is a frozen v7 file written by Minigraf v2.0.0; opening it +/// here exercises v7→v8 migration (#371, #287). It is also loaded by the +/// browser WASM tests via `include_bytes!` + `BrowserDb::import_graph`, +/// completing the cross-boundary coverage. #[test] fn fixture_readable_by_native() { let fixture: &[u8] = include_bytes!("fixtures/compat.graph"); @@ -115,5 +117,10 @@ fn fixture_readable_by_native() { _ => panic!("expected QueryResults for age query"), } + drop(db); + let raw = std::fs::read(&path).expect("read migrated fixture"); + let version = u32::from_le_bytes(raw[4..8].try_into().unwrap()); + assert_eq!(version, 8, "v7 fixture must be upgraded to v8 on open"); + cleanup(&path); } From e425eb58e25fbc182f9c3f0875c6169e04f7ab28 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 12:28:26 +0530 Subject: [PATCH 08/21] fix: v7->v8 rebuild must not rewind tx_counter or skip the index sync barrier (#371, #287) Round-1 review findings on c74f89d: - Empty transactions (`(transact [])`, `(retract [])`) allocate a tx_count without producing facts, so restoring the tx_counter from `max(fact.tx_count)` alone could rewind it below what the v7 file's header already recorded. Floor it at the old header's `last_checkpointed_tx_count` so migration never lets a new transaction reuse a tx_count that `:as-of N` already served facts for. - The rebuild path wrote the header before syncing the freshly built index pages. Add the same `backend.sync()` barrier `save()` uses, after the B+tree builds and before the header write, so the header (the crash-safe commit point) is never durable ahead of the data it points to. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- src/storage/persistent_facts.rs | 73 ++++++++++++++++++++++++++++++++- 1 file changed, 71 insertions(+), 2 deletions(-) diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index e2607ee54..8afcbe53a 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -287,8 +287,15 @@ impl PersistentFactStorage { let (eavt_entries, aevt_entries, avet_entries, vaet_entries) = build_sorted_index_entries(&all_facts, &real_refs); - // Fix up tx_counter from actual facts - let max_tx = all_facts.iter().map(|f| f.tx_count).max().unwrap_or(0); + // Fix up tx_counter from actual facts. Empty transactions + // (`(transact [])`, `(retract [])`) still allocate a tx_count + // without producing any facts, so the highest fact tx_count can + // undercount the counter the file was actually at; floor it at + // the old header's last_checkpointed_tx_count so migration never + // rewinds the counter and lets new transactions reuse tx_counts + // that `:as-of N` already served facts for (#371, #287). + let max_fact_tx = all_facts.iter().map(|f| f.tx_count).max().unwrap_or(0); + let max_tx = max_fact_tx.max(header.last_checkpointed_tx_count); self.storage.restore_tx_counter_from(max_tx); // Build v6 B+tree indexes directly @@ -324,6 +331,12 @@ impl PersistentFactStorage { next3, )?; + // Sync index pages to disk before writing the header. + // The header update is the atomic commit point: once it's durable, + // recovery uses the new root pages. All data those roots reference + // must already be on stable storage. + backend.sync()?; + // Write header with full-coverage checksum (facts + indexes) let total_data_pages = next4.saturating_sub(1); let full_checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; @@ -1356,6 +1369,62 @@ mod tests { assert_eq!(h2.version, 8, "v7 file must be upgraded to v8 on open"); } + /// #371/#287 review finding: empty transactions (`(transact [])`, + /// `(retract [])`) still allocate a tx_count without producing any facts + /// (see `FactStorage::transact` — `fetch_add` happens unconditionally). + /// The v7->v8 rebuild path must not compute the restored tx_counter as + /// `max(fact.tx_count)` alone, or trailing empty transactions before the + /// last checkpoint would be forgotten, rewinding the counter and letting + /// new transactions reuse tx_counts that `:as-of N` already served facts + /// for. + #[test] + fn v7_migration_does_not_rewind_tx_counter_past_empty_transactions() { + use crate::storage::FileHeader; + let e = Uuid::from_u128(70); + let mut backend = { + let mut s = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + s.storage() + .transact(vec![(e, ":n".to_string(), Value::Integer(1))], None) + .unwrap(); + // Empty transactions still allocate tx_count without producing facts. + s.storage().transact(vec![], None).unwrap(); + s.storage().transact(vec![], None).unwrap(); + s.mark_dirty(); + s.save().unwrap(); + s.into_backend().unwrap() + }; + let pre_migration_last_checkpointed = { + let h = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); + h.last_checkpointed_tx_count + }; + assert_eq!( + pre_migration_last_checkpointed, 3, + "one fact-bearing transact plus two empty transacts" + ); + + // Downgrade the header to v7 (keys on disk are now v8-shaped, which is + // fine: the rebuild never reads them). + let mut h = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); + h.version = 7; + h.header_checksum = compute_header_checksum(&h); + let mut page = h.to_bytes(); + page.resize(PAGE_SIZE, 0); + backend.write_page(0, &page).unwrap(); + + let s = PersistentFactStorage::new(backend, 256).unwrap(); + assert!( + s.storage().current_tx_count() >= pre_migration_last_checkpointed, + "tx_counter must not rewind below the pre-migration last_checkpointed_tx_count" + ); + + let b = s.into_backend().unwrap(); + let h2 = FileHeader::from_bytes(&b.read_page(0).unwrap()).unwrap(); + assert!( + h2.last_checkpointed_tx_count >= pre_migration_last_checkpointed, + "v8 header's last_checkpointed_tx_count must not decrease across migration" + ); + } + #[test] fn test_load_v6_wires_committed_index_reader() { let alice = Uuid::new_v4(); From 8a4a89087a7b19ca07a61564a347509ce313ffa9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 12:32:05 +0530 Subject: [PATCH 09/21] fix: keep same-transaction multi-valued facts through query-time dedup (#371) selective_fact_fetch deduplicated on (entity, attribute, tx_count, asserted), which collapsed two values written in one transaction and left one half of a batched retract un-cancelled. The key now includes the encoded value. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- src/query/datalog/executor.rs | 15 +-- tests/multi_value_test.rs | 175 ++++++++++++++++++++++++++++++++++ 2 files changed, 184 insertions(+), 6 deletions(-) create mode 100644 tests/multi_value_test.rs diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index dfaa16aac..5ea8f7ec9 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -373,7 +373,7 @@ impl DatalogExecutor { /// selective, but multi-pattern joins still need attribute candidates for patterns that do not /// bind an entity. If any pattern has neither a bound entity nor a bound attribute, or if the /// distinct lookup count exceeds `threshold`, returns `None` to use a full scan. Otherwise - /// returns `Some(facts)`, deduplicated by `(entity, attribute, tx_count, asserted)`. + /// returns `Some(facts)`, deduplicated by `(entity, attribute, tx_count, asserted, value)`. fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option> { use std::collections::HashSet; @@ -404,11 +404,12 @@ impl DatalogExecutor { return None; } - // Dedup key: (entity uuid, attribute string, tx_count, asserted) — avoids Value debug - // formatting. Including `asserted` ensures that a retraction and an assertion committed in - // the same WriteTransaction (same tx_count) are both retained, since they differ only by - // the `asserted` flag. - let mut seen: HashSet<(uuid::Uuid, String, u64, bool)> = HashSet::new(); + // Dedup key: (entity, attribute, tx_count, asserted, encoded value). + // `asserted` keeps an assertion and a retraction from the same + // WriteTransaction apart; the encoded value keeps two values of one + // attribute written in the same transaction apart (#371). Uses + // `encode_value` bytes rather than `Value` to avoid Float hashing. + let mut seen: HashSet<(uuid::Uuid, String, u64, bool, Vec)> = HashSet::new(); let mut all_facts: Vec = Vec::new(); for uid in &entity_ids { @@ -420,6 +421,7 @@ impl DatalogExecutor { fact.attribute.clone(), fact.tx_count, fact.asserted, + crate::storage::index::encode_value(&fact.value), ); if seen.insert(key) { all_facts.push(fact); @@ -439,6 +441,7 @@ impl DatalogExecutor { fact.attribute.clone(), fact.tx_count, fact.asserted, + crate::storage::index::encode_value(&fact.value), ); if seen.insert(key) { all_facts.push(fact); diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs new file mode 100644 index 000000000..541008c7c --- /dev/null +++ b/tests/multi_value_test.rs @@ -0,0 +1,175 @@ +//! Same-transaction multi-valued facts (#371, #287): every query path must +//! return every value, before checkpoint, after WAL replay, and after +//! checkpoint + reopen. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, QueryResult, Value}; +use std::collections::BTreeSet; + +mod common; +use common::{CrashTx, run_crashing_child}; + +fn rows(r: QueryResult) -> Vec> { + match r { + QueryResult::QueryResults { results, .. } => results, + _ => panic!("expected QueryResults"), + } +} + +fn kw(v: &Value) -> String { + match v { + Value::Keyword(k) => k.clone(), + _ => panic!("expected keyword value"), + } +} + +/// Values of `attr` on the entity `ent` through EAVT (entity bound), AEVT +/// (attribute bound, joined to a marker attribute) and a full scan. +fn three_paths(db: &Minigraf, ent: &str, attr: &str, marker: &str) -> [BTreeSet; 3] { + let eavt = rows( + db.execute(&format!("(query [:find ?v :where [{ent} {attr} ?v]])")) + .unwrap(), + ) + .iter() + .map(|r| kw(&r[0])) + .collect(); + let aevt = rows( + db.execute(&format!( + r#"(query [:find ?v :where [?e {attr} ?v] [?e :note "{marker}"]])"# + )) + .unwrap(), + ) + .iter() + .map(|r| kw(&r[0])) + .collect(); + let scan = rows( + db.execute(&format!( + r#"(query [:find ?a ?v :where [?e ?a ?v] [?e :note "{marker}"]])"# + )) + .unwrap(), + ) + .iter() + .filter(|r| matches!(&r[0], Value::Keyword(a) if a == attr)) + .map(|r| kw(&r[1])) + .collect(); + [eavt, aevt, scan] +} + +fn setup_statements(i: usize) -> Vec { + let mut facts = vec![ + format!("[:t/x{i} :kind :k/a]"), + format!("[:t/x{i} :kind :k/b]"), + format!(r#"[:t/x{i} :note "two{i}"]"#), + ]; + for f in 0..30 { + facts.push(format!("[:t/f{i}-{f} :kind :k/c]")); + facts.push(format!(r#"[:t/f{i}-{f} :note "f"]"#)); + } + vec![format!("(transact [{}])", facts.join(" "))] +} + +fn both() -> BTreeSet { + [":k/a", ":k/b"].iter().map(|s| s.to_string()).collect() +} + +#[test] +fn multi_value_visible_on_every_path_before_checkpoint() { + let db = Minigraf::in_memory().unwrap(); + for s in setup_statements(0) { + db.execute(&s).unwrap(); + } + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, ":t/x0", ":kind", "two0")) + { + assert_eq!( + got, + both(), + "{name} path must return both values before checkpoint" + ); + } +} + +#[test] +fn multi_value_visible_on_every_path_after_checkpoint_and_reopen() { + // Several graph shapes: the issue saw EAVT and AEVT disagree depending on content. + for i in 0..8 { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + { + let db = Minigraf::open(&path).unwrap(); + for s in setup_statements(i) { + db.execute(&s).unwrap(); + } + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + let x = format!(":t/x{i}"); + let marker = format!("two{i}"); + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, &x, ":kind", &marker)) + { + assert_eq!( + got, + both(), + "{name} path must return both values after reopen" + ); + } + } +} + +#[test] +fn multi_value_visible_on_every_path_after_wal_replay() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + let stmts = setup_statements(0); + let refs: Vec<&str> = stmts.iter().map(String::as_str).collect(); + run_crashing_child(&path, 1_000_000, &refs, CrashTx::Implicit); + let db = Minigraf::open(&path).unwrap(); + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, ":t/x0", ":kind", "two0")) + { + assert_eq!( + got, + both(), + "{name} path must return both values after WAL replay" + ); + } +} + +#[test] +fn batched_retract_of_both_values_hides_both_on_every_path() { + for i in 0..8 { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + { + let db = Minigraf::open(&path).unwrap(); + for s in setup_statements(i) { + db.execute(&s).unwrap(); + } + db.checkpoint().unwrap(); + } + { + let db = Minigraf::open(&path).unwrap(); + db.execute(&format!( + "(retract [[:t/x{i} :kind :k/a] [:t/x{i} :kind :k/b]])" + )) + .unwrap(); + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + let x = format!(":t/x{i}"); + let marker = format!("two{i}"); + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, &x, ":kind", &marker)) + { + assert!( + got.is_empty(), + "{name} path must hide both retracted values" + ); + } + } +} From 7f77e4ffa301d284daa5487a8df791bf950712a5 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 24 Sep 2026 12:43:26 +0530 Subject: [PATCH 10/21] test: add retract-collision regression tests that fail on the pre-fix dedup key (#371) batched_retract_of_both_values_hides_both_on_every_path passes even against the pre-fix (entity, attribute, tx_count, asserted) dedup key: retracting exactly the asserted value set is symmetric under that key, since the smallest-encoded-byte value always wins the collision on both the assert side and the retract side and correctly cancels itself, regardless of statement order or whether the retracts are batched or split across separate transactions (verified empirically, not just argued). Add two tests where the retracted value set includes a value that was never asserted (:k/A, which sorts before :k/a): under the old key this non-asserted value wins the retract-batch collision and silently drops the real retraction records for :k/a and :k/b, leaving :k/a visible. Confirmed RED against a reverted copy of executor.rs and GREEN against the fix from the prior commit. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PuKbXn6NaHBMDVkScdBNQZ --- tests/multi_value_test.rs | 79 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs index 541008c7c..b132ed3d0 100644 --- a/tests/multi_value_test.rs +++ b/tests/multi_value_test.rs @@ -173,3 +173,82 @@ fn batched_retract_of_both_values_hides_both_on_every_path() { } } } + +/// Retracting exactly the values that were asserted together (same +/// order or not, one transaction or split across several) is not, on its +/// own, a sufficient regression guard for the pre-fix dedup key: the old +/// `(entity, attribute, tx_count, asserted)` key — no value — collapses +/// every fact sharing that tuple down to whichever one sorts first by +/// encoded value bytes. When the retracted set is *exactly* the asserted +/// set, that same smallest-byte member wins the collision on both the +/// assert side and the retract side, so it always cancels itself out +/// correctly and the net result is empty either way — this was verified +/// empirically (reordering the retract list, and splitting the two +/// retracts across separate transactions, both still pass against the +/// pre-fix key). What actually exercises the retract-side collision is a +/// batched retract whose value set is *not* identical to what was +/// asserted: here, `:k/A` (uppercase — encodes to fewer bytes than +/// `:k/a`) is retracted alongside the two real values but was never +/// itself asserted. Under the pre-fix key, `:k/A` wins the three-way +/// collision in the retract batch, and the real retraction records for +/// `:k/a` and `:k/b` are silently dropped — leaving `:k/a` visible. +#[test] +fn batched_retract_with_non_asserted_colliding_value_hides_real_values_on_every_path() { + for i in 0..8 { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + { + let db = Minigraf::open(&path).unwrap(); + for s in setup_statements(i) { + db.execute(&s).unwrap(); + } + db.checkpoint().unwrap(); + } + { + let db = Minigraf::open(&path).unwrap(); + db.execute(&format!( + "(retract [[:t/x{i} :kind :k/A] [:t/x{i} :kind :k/a] [:t/x{i} :kind :k/b]])" + )) + .unwrap(); + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + let x = format!(":t/x{i}"); + let marker = format!("two{i}"); + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, &x, ":kind", &marker)) + { + assert!( + got.is_empty(), + "{name} path must hide real values even when the retract batch also \ + contains a never-asserted colliding value" + ); + } + } +} + +/// Same construction as +/// `batched_retract_with_non_asserted_colliding_value_hides_real_values_on_every_path`, +/// checked on the same handle immediately after the retract — no +/// intervening checkpoint or reopen — to cover the pending in-memory +/// index path as well as the on-disk one. +#[test] +fn batched_retract_with_non_asserted_colliding_value_hides_real_values_before_checkpoint() { + let db = Minigraf::in_memory().unwrap(); + for s in setup_statements(0) { + db.execute(&s).unwrap(); + } + db.execute("(retract [[:t/x0 :kind :k/A] [:t/x0 :kind :k/a] [:t/x0 :kind :k/b]])") + .unwrap(); + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, ":t/x0", ":kind", "two0")) + { + assert!( + got.is_empty(), + "{name} path must hide real values even when the retract batch also \ + contains a never-asserted colliding value, before checkpoint" + ); + } +} From 8931e84dbfc4e7264d3c7c94338571463a3995fc Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 00:18:47 +0530 Subject: [PATCH 11/21] test: v7 multi-value fixture migration and near-max-size values (#371, #287) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- tests/multi_value_test.rs | 123 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 123 insertions(+) diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs index b132ed3d0..e83f3146d 100644 --- a/tests/multi_value_test.rs +++ b/tests/multi_value_test.rs @@ -252,3 +252,126 @@ fn batched_retract_with_non_asserted_colliding_value_hides_real_values_before_ch ); } } + +/// `tests/fixtures/v7_multivalue.graph` was written by the v7 writer at +/// 84bf375 (v2.0.0 format) with this generator: +/// +/// ```ignore +/// fn main() -> anyhow::Result<()> { +/// use std::path::PathBuf; +/// let dir = PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("tests/fixtures"); +/// let tmp = dir.join("v7_multivalue.graph.tmp"); +/// let _ = std::fs::remove_file(&tmp); +/// let _ = std::fs::remove_file(dir.join("v7_multivalue.graph.tmp.wal")); +/// +/// let db = minigraf::Minigraf::open(&tmp)?; +/// let mut facts = vec![ +/// "[:t/x :kind :k/a]".to_string(), +/// "[:t/x :kind :k/b]".to_string(), +/// r#"[:t/x :note "two"]"#.to_string(), +/// ]; +/// for i in 0..30 { +/// facts.push(format!("[:t/f-{i} :kind :k/c]")); +/// facts.push(format!(r#"[:t/f-{i} :note "f"]"#)); +/// } +/// db.execute(&format!("(transact [{}])", facts.join(" ")))?; +/// db.execute("(transact [[:t/y :tag :g/a] [:t/y :tag :g/b]])")?; +/// db.execute("(retract [[:t/y :tag :g/a] [:t/y :tag :g/b]])")?; +/// db.checkpoint()?; +/// drop(db); +/// let _ = std::fs::remove_file(dir.join("v7_multivalue.graph.tmp.wal")); +/// std::fs::rename(&tmp, dir.join("v7_multivalue.graph"))?; +/// Ok(()) +/// } +/// ``` +/// +/// Opening it must migrate to v8 and return both values on every path, and +/// the batched retract of `:t/y`'s two `:tag` values must hide both. +#[test] +fn v7_multivalue_fixture_migrates_and_reads_correctly() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("v7.graph"); + std::fs::write(&path, include_bytes!("fixtures/v7_multivalue.graph")).unwrap(); + + { + let db = Minigraf::open(&path).unwrap(); + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, ":t/x", ":kind", "two")) + { + assert_eq!( + got, + both(), + "{name} path must return both values after migration" + ); + } + let tags = rows( + db.execute("(query [:find ?v :where [:t/y :tag ?v]])") + .unwrap(), + ); + assert!( + tags.is_empty(), + "batched retract in the v7 file must hide both values" + ); + } + + let raw = std::fs::read(&path).unwrap(); + assert_eq!( + u32::from_le_bytes(raw[4..8].try_into().unwrap()), + 8, + "file must be v8 after open" + ); + + // Second open is a plain v8 open (no rebuild) and reads the same. + let db = Minigraf::open(&path).unwrap(); + for (name, got) in ["eavt", "aevt", "scan"] + .iter() + .zip(three_paths(&db, ":t/x", ":kind", "two")) + { + assert_eq!( + got, + both(), + "{name} path must return both values on second open" + ); + } +} + +/// Index entries now carry the value bytes; a near-maximum string value must +/// still checkpoint and read back through every index. +#[test] +fn near_max_size_values_checkpoint_and_read_back() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("big.graph"); + let big_a = "a".repeat(3_800); + let big_b = "b".repeat(3_800); + { + let db = Minigraf::open(&path).unwrap(); + db.execute(&format!( + r#"(transact [[:t/big :blob "{big_a}"] [:t/big :blob "{big_b}"] [:t/big :note "big"]])"# + )) + .unwrap(); + db.checkpoint().unwrap(); + } + let db = Minigraf::open(&path).unwrap(); + let by_entity = rows( + db.execute("(query [:find ?v :where [:t/big :blob ?v]])") + .unwrap(), + ); + assert_eq!( + by_entity.len(), + 2, + "EAVT path must return both large values" + ); + let by_attr = rows( + db.execute(r#"(query [:find ?v :where [?e :blob ?v] [?e :note "big"]])"#) + .unwrap(), + ); + assert_eq!(by_attr.len(), 2, "AEVT path must return both large values"); + let by_value = rows( + db.execute(&format!( + r#"(query [:find ?e :where [?e :blob "{big_a}"]])"# + )) + .unwrap(), + ); + assert_eq!(by_value.len(), 1, "AVET path must find the large value"); +} From 9d960071d20f50db1e5ef9ef63868cfc4ac30097 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 00:32:50 +0530 Subject: [PATCH 12/21] =?UTF-8?q?docs:=20file=20format=20v8,=20v1=E2=80=93?= =?UTF-8?q?v6=20dropped,=20multi-value=20fix=20(#371,=20#287)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CHANGELOG.md | 12 ++++++++++++ CLAUDE.md | 11 +++++------ README.md | 2 +- ROADMAP.md | 4 ++-- docs/TEST_COVERAGE.md | 15 ++++++++++----- 5 files changed, 30 insertions(+), 14 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 7484edbc6..3506458c6 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -5,6 +5,18 @@ All notable changes to this project will be documented in this file. The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). +## [Unreleased] + +### 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. +- **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 retired. `STG-005` and `STG-006` message text changed. + +### Fixed + +- Two values of the same attribute written in one transaction are both returned by every query path. Previously only one came back, and entity-bound and attribute-bound queries could return different ones (#371, #287). +- A retract that removes several values of one attribute in one call now hides all of them (#371). + ## v2.0.0 — 2026-08-26 This was originally slated as v1.3.0, matching the GitHub milestone name under diff --git a/CLAUDE.md b/CLAUDE.md index 2b83e26fa..66b000e00 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -104,15 +104,14 @@ cargo run < demos/demo_negation.txt - `storage.rs`: `FactStorage` — in-memory store, `transact_batch`, `retract`, `get_facts_as_of`, `get_facts_valid_at`, `net_asserted_facts` 2. **`src/storage/`** — Persistence layer - - `mod.rs`: `StorageBackend` trait, `FileHeader` v7 (84 bytes), `CommittedFactReader` / `CommittedIndexReader` traits + - `mod.rs`: `StorageBackend` trait, `FileHeader` v8 (84 bytes), `CommittedFactReader` / `CommittedIndexReader` traits - `backend/file.rs`: Single `.graph` file backend (4KB pages, cross-platform) - `backend/memory.rs`: In-memory backend for testing - `index.rs`: EAVT / AEVT / AVET / VAET key types, `FactRef`, `encode_value` - `btree_v6.rs`: On-disk B+tree (`build_btree`, `OnDiskIndexReader`, `MutexStorageBackend`) - - `btree.rs`: Legacy v5 B+tree (migration only) - `cache.rs`: LRU page cache (`PageCache`, default 256 pages) - `packed_pages.rs`: Packed fact pages (~25 facts/4KB page), `MAX_FACT_BYTES` - - `persistent_facts.rs`: `PersistentFactStorage` — v7 save/load, auto-migration v1–v6→v7 + - `persistent_facts.rs`: `PersistentFactStorage` — v8 save/load, auto-migration v7→v8 3. **`src/query/datalog/`** — Datalog engine - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join` @@ -153,7 +152,7 @@ enum Value { String(String), Integer(i64), Float(f64), Boolean(bool), **Important**: `tx_count` (sequential 1, 2, 3…) is what `:as-of N` compares against. The REPL displays `tx_id` (Unix ms). A single `(transact [...])` command increments `tx_count` once regardless of how many facts it contains (`transact_batch`). -### File Format (v7) +### File Format (v8) ``` Page 0: Header (84 bytes) — magic "MGRF", version, page/fact counts, @@ -163,11 +162,11 @@ After: On-disk B+tree index pages (one node per 4KB page) Sidecar: .wal — CRC32-protected WAL entries; replayed on open; deleted on checkpoint ``` -Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. +Auto-migrates v7 → v8 on open (index rebuild). v1–v6 are rejected (STG-028). ## Test Coverage -**1153 tests passing** (1145 passing, 8 ignored; unit + integration + doc). +**1155 tests passing** (1147 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. diff --git a/README.md b/README.md index 82414ce6d..e6217173d 100644 --- a/README.md +++ b/README.md @@ -92,7 +92,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1153 tests +cargo test # run 1155 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index 187668918..969c4c6b1 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -10,13 +10,13 @@ Completed releases and their implementation details live in the [CHANGELOG](CHAN ## v3.0.0 — File Format Policy -**v3.0.0 supports file format v8 only.** Fixing #287's `EavtKey`/`AevtKey` missing-value-bytes data-loss bug bumps the format from v7 to v8. Support for v1–v6 is dropped at the same time. The v1–v6 → v7 auto-migration code in `persistent_facts.rs` can be removed when cutting this release; a v7→v8 migration replaces it. Any database opened at least once under a v1.x release will already be on v7; there are no known users on older formats. +**#287/#371 have landed in-tree (unreleased): file format v8, replacing v7.** Fixing #287's `EavtKey`/`AevtKey` missing-value-bytes data-loss bug bumped the format from v7 to v8; index keys now include the encoded value and the assert/retract flag. Support for v1–v6 is dropped at the same time — opening one fails with `STG-028`. A v7 file is auto-migrated (re-indexed) to v8 the first time it is opened. v3.0.0 itself has not been released yet; this work will ship as part of it. Any database opened at least once under a v1.x release will already be on v7; there are no known users on older formats. This was the GitHub milestone named “2.0” before v2.0.0 used that version number for the kernel-locking and structured-error-code breaking changes; it was consequently renumbered to v3.0.0. Scope: -- `EavtKey`/`AevtKey` missing-value-bytes fix and file-format v7→v8 migration (#287) +- ✅ `EavtKey`/`AevtKey` value-bytes fix, format v8, v7→v8 migration, v1–v6 dropped (#287, #371) - `lag`/`lead` window functions (#182) - Sliding row frames — `:rows N preceding` (#183; builds on #182) - `PreparedQuery` over UniFFI (#181) diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 2ccaaadce..9b8d0ae81 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -1,17 +1,22 @@ # Minigraf Test Coverage -## v2.0.0 Coverage Summary +## Coverage Summary -**Verified**: 2026-08-26 with `cargo test --quiet` +**Verified**: 2026-09-25 with `cargo test --quiet` -**Result**: 1,145 passing tests and 8 ignored tests (1,153 total) +**Result**: 1,147 passing tests and 8 ignored tests (1,155 total) -The v2.0.0 suite covers the public database API, the Datalog engine, storage and recovery paths, and the release’s locking and structured-error-code changes. +This supersedes the v2.0.0-era count (1,145 passing, 8 ignored) with 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, and v2.0.0's locking +and structured-error-code changes. ### Covered Areas - **Core database behavior**: in-memory and file-backed operation, transactions, checkpoints, retractions, bi-temporal queries, recursive rules, prepared statements, aggregation, expressions, disjunction, window functions, UDFs, and magic-sets evaluation. -- **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration, WAL replay, checksums, corruption handling, and fault injection. +- **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 8 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). +- **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, and SIGKILL recovery. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: cross-platform format compatibility, property-based tests, long-haul smoke coverage, XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. From 89b73259ec455181c05539fe060b250052edfeee Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 08:56:32 +0530 Subject: [PATCH 13/21] fix: add valid_from/valid_to to selective_fact_fetch dedup key (#371, #287) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit `selective_fact_fetch`'s dedup key (entity, attribute, tx_count, asserted, value_bytes) had no valid-time component, so two facts differing only in their per-fact valid-time window — same tx_count (one transact call), same value bytes, same asserted flag — collapsed into a single arbitrary survivor in both the entity-bound and attribute-bound loops. A `:valid-at` query landing inside the dropped window's range returned zero rows instead of one, and `:any-valid-time` returned one stint instead of two. Add fact.valid_from/valid_to to the key in both loops and update the doc comment. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/query/datalog/executor.rs | 22 ++++++--- tests/multi_value_test.rs | 85 +++++++++++++++++++++++++++++++++++ 2 files changed, 101 insertions(+), 6 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 5ea8f7ec9..462cdaade 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -404,12 +404,18 @@ impl DatalogExecutor { return None; } - // Dedup key: (entity, attribute, tx_count, asserted, encoded value). - // `asserted` keeps an assertion and a retraction from the same - // WriteTransaction apart; the encoded value keeps two values of one - // attribute written in the same transaction apart (#371). Uses - // `encode_value` bytes rather than `Value` to avoid Float hashing. - let mut seen: HashSet<(uuid::Uuid, String, u64, bool, Vec)> = HashSet::new(); + // Dedup key: (entity, attribute, tx_count, asserted, encoded value, + // valid_from, valid_to). `asserted` keeps an assertion and a + // retraction from the same WriteTransaction apart; the encoded value + // keeps two values of one attribute written in the same transaction + // apart (#371). Uses `encode_value` bytes rather than `Value` to + // avoid Float hashing. `valid_from`/`valid_to` keep two distinct + // valid-time stints of the same (entity, attribute, value, tx_count, + // asserted) tuple apart — without them, two per-fact valid-time + // windows on the same value in one transaction collapse into a + // single arbitrary survivor and the other window's row is silently + // dropped from `:valid-at` and `:any-valid-time` results (#371). + let mut seen: HashSet<(uuid::Uuid, String, u64, bool, Vec, i64, i64)> = HashSet::new(); let mut all_facts: Vec = Vec::new(); for uid in &entity_ids { @@ -422,6 +428,8 @@ impl DatalogExecutor { fact.tx_count, fact.asserted, crate::storage::index::encode_value(&fact.value), + fact.valid_from, + fact.valid_to, ); if seen.insert(key) { all_facts.push(fact); @@ -442,6 +450,8 @@ impl DatalogExecutor { fact.tx_count, fact.asserted, crate::storage::index::encode_value(&fact.value), + fact.valid_from, + fact.valid_to, ); if seen.insert(key) { all_facts.push(fact); diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs index e83f3146d..6d5b6392f 100644 --- a/tests/multi_value_test.rs +++ b/tests/multi_value_test.rs @@ -336,6 +336,91 @@ fn v7_multivalue_fixture_migrates_and_reads_correctly() { } } +/// Two valid-time stints for the *same* (entity, attribute, value) written in +/// one transaction must both be individually visible: a `:valid-at` query +/// inside the second window's range must return that stint (not the first, +/// not neither), and `:any-valid-time` must return both, on every selective +/// query path. The pre-fix `selective_fact_fetch` dedup key +/// `(entity, attribute, tx_count, asserted, value_bytes)` has no valid-time +/// component, so these two facts — same tx_count (one transact call), same +/// value bytes (`true`), same asserted flag — collapse into a single +/// arbitrary survivor in the entity-bound and attribute+join loops. A full +/// scan does not go through `selective_fact_fetch` (its patterns are not +/// selective — unbound attribute/value), so it is unaffected and serves as +/// the control. +#[test] +fn multi_value_time_stints_visible_at_correct_valid_time_on_every_path() { + let db = Minigraf::in_memory().unwrap(); + // The `:note` marker's valid-time window must cover both stints' windows — + // otherwise the query's `:valid-at "2022-06-01"` filter (applied to every + // candidate fact, including the join marker) would drop `:note` itself, + // since its default valid_from is the real transaction wall-clock time. + db.execute( + r#"(transact [[:vt/alice :employed true {:valid-from "2020-01-01" :valid-to "2021-01-01"}] [:vt/alice :employed true {:valid-from "2022-01-01" :valid-to "2023-01-01"}] [:vt/alice :note "vt" {:valid-from "2000-01-01"}]])"#, + ) + .unwrap(); + + // Inside the second window only: exactly one row on every path. + let eavt = rows( + db.execute(r#"(query [:find ?v :valid-at "2022-06-01" :where [:vt/alice :employed ?v]])"#) + .unwrap(), + ); + assert_eq!( + eavt.len(), + 1, + "entity-bound path must return the stint valid in the second window" + ); + + let aevt = rows( + db.execute( + r#"(query [:find ?v :valid-at "2022-06-01" :where [?e :employed ?v] [?e :note "vt"]])"#, + ) + .unwrap(), + ); + assert_eq!( + aevt.len(), + 1, + "attribute+join path must return the stint valid in the second window" + ); + + let scan = rows( + db.execute( + r#"(query [:find ?a ?v :valid-at "2022-06-01" :where [?e ?a ?v] [?e :note "vt"]])"#, + ) + .unwrap(), + ) + .into_iter() + .filter(|r| matches!(&r[0], Value::Keyword(a) if a == ":employed")) + .count(); + assert_eq!( + scan, 1, + "full scan path must return the stint valid in the second window" + ); + + // Under :any-valid-time, both stints must be visible on the selective paths. + let eavt_any = rows( + db.execute(r#"(query [:find ?v :any-valid-time :where [:vt/alice :employed ?v]])"#) + .unwrap(), + ); + assert_eq!( + eavt_any.len(), + 2, + "entity-bound path must return both stints under :any-valid-time" + ); + + let aevt_any = rows( + db.execute( + r#"(query [:find ?v :any-valid-time :where [?e :employed ?v] [?e :note "vt"]])"#, + ) + .unwrap(), + ); + assert_eq!( + aevt_any.len(), + 2, + "attribute+join path must return both stints under :any-valid-time" + ); +} + /// Index entries now carry the value bytes; a near-maximum string value must /// still checkpoint and read back through every index. #[test] From ca646dc6da0fae10710159f093dc32ac7ec12671 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 08:58:03 +0530 Subject: [PATCH 14/21] fix: fuzz btree_page/fact_page targets against real v8 headers (#371, #287) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Both targets hardcoded header version 7 with an all-zero page_count, so `Minigraf::open()` always either failed STG-007 immediately (page_count 0) or took the version<8 forced-rebuild path, which rebuilds indexes from fact pages and never reads the fuzzed page at all. - fact_page.rs: version 8, page_count 2, fact_page_count 1, eavt_root_page left at 0 so `load()` still rebuilds from fact pages — opening alone now decodes the fuzzed page as a packed fact page (postcard `Fact`). - btree_page.rs: version 8, page_count 3, eavt_root_page pointing at the fuzzed page so `load()` wires it up as the EAVT B+tree root instead of rebuilding. `open()` only wires the reader lazily and never reads the root page itself, so the target now also runs a minimal entity-bound query to force an EAVT range scan, which decodes the fuzzed page as a v8 B+tree leaf/internal node (with value bytes + asserted flag). fuzz/Cargo.lock and fuzz/target/ remain untracked/uncommitted. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- fuzz/fuzz_targets/btree_page.rs | 24 ++++++++++++++++++++++-- fuzz/fuzz_targets/fact_page.rs | 14 +++++++++++++- 2 files changed, 35 insertions(+), 3 deletions(-) diff --git a/fuzz/fuzz_targets/btree_page.rs b/fuzz/fuzz_targets/btree_page.rs index c93a26b03..5e9fe3027 100644 --- a/fuzz/fuzz_targets/btree_page.rs +++ b/fuzz/fuzz_targets/btree_page.rs @@ -9,11 +9,31 @@ fuzz_target!(|data: &[u8]| { let path = dir.path().join("fuzz.graph"); let mut content = vec![0u8; 4096 * 3]; content[0..4].copy_from_slice(b"MGRF"); - content[4..8].copy_from_slice(&7u32.to_le_bytes()); + // v8 header (v1-v6 are rejected; v7 would always force a full rebuild + // from fact pages and never touch the root page below, which is a + // different code path than the one this target means to fuzz). + content[4..8].copy_from_slice(&8u32.to_le_bytes()); + // page_count = 3 (header page 0, unused page 1, fuzzed root page 2). + content[8..16].copy_from_slice(&3u64.to_le_bytes()); + // eavt_root_page = 2: points `load()`'s index wiring, and the query + // below, at the fuzzed page as the EAVT B+tree root. fact_page_count is + // left at 0, so `load()` takes the "no facts, trust the root" branch + // and does not force a rebuild that would ignore this page. + content[32..40].copy_from_slice(&2u64.to_le_bytes()); + // header_checksum (bytes 80-83) and index_checksum (bytes 64-67) are left + // zero: zero is the "unset" sentinel that skips checksum verification. let copy_len = data.len().min(4096); content[4096 * 2..4096 * 2 + copy_len].copy_from_slice(&data[..copy_len]); if std::fs::write(&path, &content).is_err() { return; } - let _ = minigraf::db::Minigraf::open(&path); + let Ok(db) = minigraf::db::Minigraf::open(&path) else { + return; + }; + // `open()` alone only wires up `OnDiskIndexReader` against the root page — + // it never reads it. Run an entity-bound query so the EAVT range scan + // actually decodes the fuzzed page as a v8 B+tree leaf/internal node. + let _ = db.execute( + r#"(query [:find ?a ?v :where [#uuid "00000000-0000-0000-0000-000000000000" ?a ?v]])"#, + ); }); diff --git a/fuzz/fuzz_targets/fact_page.rs b/fuzz/fuzz_targets/fact_page.rs index c63d38219..ee38ecfc0 100644 --- a/fuzz/fuzz_targets/fact_page.rs +++ b/fuzz/fuzz_targets/fact_page.rs @@ -9,7 +9,19 @@ fuzz_target!(|data: &[u8]| { let path = dir.path().join("fuzz.graph"); let mut content = vec![0u8; 4096 * 2]; content[0..4].copy_from_slice(b"MGRF"); - content[4..8].copy_from_slice(&7u32.to_le_bytes()); + // v8 header (v1-v6 are rejected; v7 would always force a full rebuild + // regardless of these fields, which is a different code path than the + // one this target means to fuzz). + content[4..8].copy_from_slice(&8u32.to_le_bytes()); + // page_count = 2 (header page 0 + one fact page at page 1). + content[8..16].copy_from_slice(&2u64.to_le_bytes()); + // fact_page_count = 1, eavt_root_page left at 0: with no index root, + // `load()` always rebuilds from the fact pages, so opening alone decodes + // page 1 as a packed fact page (postcard `Fact` deserialization) without + // needing a follow-up query. + content[72..80].copy_from_slice(&1u64.to_le_bytes()); + // header_checksum (bytes 80-83) and index_checksum (bytes 64-67) are left + // zero: zero is the "unset" sentinel that skips checksum verification. let copy_len = data.len().min(4096); content[4096..4096 + copy_len].copy_from_slice(&data[..copy_len]); if std::fs::write(&path, &content).is_err() { From edf34328a81fb42b1cdf699003c9ee57fb446a2e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 08:58:46 +0530 Subject: [PATCH 15/21] fix: stop generate_compat_fixture from overwriting the frozen v7 fixture (#371, #287) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The example's doc header said "do not regenerate" the v7 compat.graph fixture, but the code still wrote straight to tests/fixtures/compat.graph and renamed over it — running the example silently replaced the frozen v7 file with a v8 one, invalidating the v7->v8 migration coverage. Write to target/generate_compat_fixture/compat_generated.graph instead, and fix the doc header to describe the new behavior. Also assert in fixture_readable_by_native (cross_platform_compat_test.rs) that the embedded fixture bytes are version 7 before opening, so a future regeneration-in-place is caught by the test instead of silently changing what's being covered. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- examples/generate_compat_fixture.rs | 18 +++++++++++------- tests/cross_platform_compat_test.rs | 11 +++++++++++ 2 files changed, 22 insertions(+), 7 deletions(-) diff --git a/examples/generate_compat_fixture.rs b/examples/generate_compat_fixture.rs index 7e781e462..bf1760e75 100644 --- a/examples/generate_compat_fixture.rs +++ b/examples/generate_compat_fixture.rs @@ -1,12 +1,14 @@ -//! Generates a `.graph` file with two known facts (the committed `compat.graph` is -//! the frozen v7 output of this example from v2.0.0). +//! Generates a `.graph` file with two known facts, for inspecting what the +//! current storage layer writes. //! -//! Run once when the file format changes or the fixture needs regenerating: //! cargo run --example generate_compat_fixture //! -//! `compat.graph` is the frozen v7 fixture written by Minigraf v2.0.0; the -//! cross-platform tests use it to check v7→v8 migration. Do not regenerate it -//! — running this example now writes a v8 file. +//! `tests/fixtures/compat.graph` is the frozen v7 fixture written by Minigraf +//! v2.0.0; the cross-platform tests use it to check v7→v8 migration on open. +//! This example must never overwrite it — running it now would write a v8 +//! file, silently invalidating that migration coverage. It writes to +//! `target/generate_compat_fixture/compat_generated.graph` instead, which is +//! not read by any test. // wasm-pack compiles examples for the browser target; provide a no-op entry // point so the example compiles cleanly. The actual generator only makes sense @@ -19,7 +21,9 @@ fn main() -> anyhow::Result<()> { use std::path::PathBuf; let manifest_dir = env!("CARGO_MANIFEST_DIR"); - let fixture_path = PathBuf::from(manifest_dir).join("tests/fixtures/compat.graph"); + let out_dir = PathBuf::from(manifest_dir).join("target/generate_compat_fixture"); + std::fs::create_dir_all(&out_dir)?; + let fixture_path = out_dir.join("compat_generated.graph"); let tmp_path = fixture_path.with_extension("graph.tmp"); // Remove any leftover from a previous run. diff --git a/tests/cross_platform_compat_test.rs b/tests/cross_platform_compat_test.rs index fc7674a58..fbc61c6a0 100644 --- a/tests/cross_platform_compat_test.rs +++ b/tests/cross_platform_compat_test.rs @@ -90,6 +90,17 @@ fn native_raw_page_bytes_round_trip() { fn fixture_readable_by_native() { let fixture: &[u8] = include_bytes!("fixtures/compat.graph"); + // The whole point of this fixture is exercising v7->v8 migration on open; + // catch a silent regeneration (e.g. someone running + // `cargo run --example generate_compat_fixture` against the old output + // path and overwriting the frozen fixture) before it opens successfully + // for the wrong reason. + let embedded_version = u32::from_le_bytes(fixture[4..8].try_into().unwrap()); + assert_eq!( + embedded_version, 7, + "compat.graph fixture must remain the frozen v7 file" + ); + // Write to a temp path so Minigraf::open can use it. let path = tmp("fixture"); cleanup(&path); From 1be1d1532a17699bf7947b6ebf0b08d73c5520f7 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 08:59:06 +0530 Subject: [PATCH 16/21] test: assert rejected future-version file is left unmodified (#371, #287) unsupported_version_fails_loudly checked that opening a v99 file errors with STG-006, but not that Minigraf::open() left the file alone on that error path (spec Testing 5). Compare the file bytes before and after the rejected open. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- tests/migration_matrix_test.rs | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/tests/migration_matrix_test.rs b/tests/migration_matrix_test.rs index a6c2482ac..3c3c66819 100644 --- a/tests/migration_matrix_test.rs +++ b/tests/migration_matrix_test.rs @@ -93,9 +93,16 @@ fn unsupported_version_fails_loudly() { page[4..8].copy_from_slice(&99u32.to_le_bytes()); let mut f = std::fs::File::create(&path).unwrap(); f.write_all(&page).unwrap(); + drop(f); + let before = std::fs::read(&path).unwrap(); let result = Minigraf::open(&path); assert!(result.is_err(), "unsupported version must produce an error"); assert_eq!(result.err().unwrap().code(), "STG-006"); + let after = std::fs::read(&path).unwrap(); + assert_eq!( + before, after, + "a rejected future-version file must be left unmodified" + ); } #[test] From 5b8d83bcc12dc2733e6ec2ceda84785ad866dda9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 09:00:32 +0530 Subject: [PATCH 17/21] test: add exact-boundary max-value-size case to multi_value_test (#371, #287) near_max_size_values_checkpoint_and_read_back leaves ~230 bytes of headroom below the real per-fact maximum (MAX_FACT_BYTES minus the fixed postcard overhead of the rest of the Fact struct, which isn't a public constant so tests can't compute it directly). Add a case that locates the exact edge at runtime via a binary search over transact attempts, then checkpoints/reads back two values of that exact length through EAVT, AEVT and AVET, and confirms one byte past the boundary is rejected. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- tests/multi_value_test.rs | 89 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 89 insertions(+) diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs index 6d5b6392f..eb41859b8 100644 --- a/tests/multi_value_test.rs +++ b/tests/multi_value_test.rs @@ -460,3 +460,92 @@ fn near_max_size_values_checkpoint_and_read_back() { ); assert_eq!(by_value.len(), 1, "AVET path must find the large value"); } + +/// `near_max_size_values_checkpoint_and_read_back` above leaves roughly 230 +/// bytes of headroom below the real per-fact maximum (`MAX_FACT_BYTES` minus +/// the fixed postcard overhead of the rest of the `Fact` struct, which isn't +/// a public constant). This test locates the exact edge at runtime — the +/// largest value length that still transacts — by searching downward from a +/// length guaranteed to fail, and checkpoints/reads back exactly there. +#[test] +fn max_size_value_at_exact_boundary_checkpoint_and_read_back() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("boundary.graph"); + let db = Minigraf::open(&path).unwrap(); + + // Binary search the largest ASCII string length that still transacts as + // a single fact value, using a throwaway probe entity (and a fill + // character distinct from the real assertions below) so the search + // doesn't interfere with them — the AVET lookup below is by exact value, + // and the search's last successful probe value would otherwise collide + // with `big_a`. Same attribute name (`:blob`) as the real facts below: + // the attribute string is part of the encoded fact size, so a + // differently-sized attribute name would find a different boundary. + // `hi` starts comfortably above MAX_FACT_BYTES (4080), so it is + // guaranteed to fail. + let mut lo = 0usize; + let mut hi = 4096usize; + while lo + 1 < hi { + let mid = lo + (hi - lo) / 2; + let s = "z".repeat(mid); + let stmt = format!(r#"(transact [[:t/probe :blob "{s}"]])"#); + match db.execute(&stmt) { + Ok(_) => lo = mid, + Err(_) => hi = mid, + } + } + let max_len = lo; + assert!( + max_len > 3_800, + "boundary search must find a length past the near-max test's headroom" + ); + + let big_a = "a".repeat(max_len); + let big_b = "b".repeat(max_len); + db.execute(&format!( + r#"(transact [[:t/boundary :blob "{big_a}"] [:t/boundary :blob "{big_b}"] [:t/boundary :note "boundary"]])"# + )) + .unwrap(); + db.checkpoint().unwrap(); + drop(db); + + let db = Minigraf::open(&path).unwrap(); + let by_entity = rows( + db.execute("(query [:find ?v :where [:t/boundary :blob ?v]])") + .unwrap(), + ); + assert_eq!( + by_entity.len(), + 2, + "EAVT path must return both exact-boundary values" + ); + let by_attr = rows( + db.execute(r#"(query [:find ?v :where [?e :blob ?v] [?e :note "boundary"]])"#) + .unwrap(), + ); + assert_eq!( + by_attr.len(), + 2, + "AEVT path must return both exact-boundary values" + ); + let by_value = rows( + db.execute(&format!( + r#"(query [:find ?e :where [?e :blob "{big_a}"]])"# + )) + .unwrap(), + ); + assert_eq!( + by_value.len(), + 1, + "AVET path must find the exact-boundary value" + ); + + // One byte past the boundary must fail cleanly, confirming max_len is + // really the edge and not just some length that happens to work. + let over = "a".repeat(max_len + 1); + let over_result = db.execute(&format!(r#"(transact [[:t/over :blob "{over}"]])"#)); + assert!( + over_result.is_err(), + "one byte past the boundary must be rejected" + ); +} From b950aa045fbd84c649fbbdf179e8050101dccd86 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 09:00:58 +0530 Subject: [PATCH 18/21] docs: fix stale fact_page_format doc comment (#371, #287) The field doc still listed 0x00/0x01 as if they were live decode options. Only 0x02 (packed, FACT_PAGE_FORMAT_PACKED) is ever written or read; v1-v6 files (the only ones that could carry 0x00/0x01) are rejected outright by STG-028, not migrated. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/storage/mod.rs | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 34f324f65..14a28b8de 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -125,7 +125,9 @@ pub struct FileHeader { pub avet_root_page: u64, pub vaet_root_page: u64, pub index_checksum: u32, - /// fact_page_format (v5+): 0x00 = unset/legacy, 0x01 = one-per-page, 0x02 = packed. + /// fact_page_format: only 0x02 (packed, `FACT_PAGE_FORMAT_PACKED`) is + /// written or read; v1-v6 files (which could carry 0x00 unset/legacy or + /// 0x01 one-per-page) are rejected outright (STG-028), not migrated. pub fact_page_format: u8, pub(crate) _padding: [u8; 3], /// Number of pages (starting at page 1) holding committed fact data. From 3bc3e45f56c79ef626290116665328df3953a3f4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 09:02:15 +0530 Subject: [PATCH 19/21] fix: extract FactDedupKey type alias to satisfy clippy::type_complexity (#371, #287) The 7-tuple dedup key added for the valid_from/valid_to fix trips clippy::type_complexity under the CI gate (cargo clippy --all-features -- -D warnings). Factor it into a local type alias. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/query/datalog/executor.rs | 26 ++++++++++++++------------ 1 file changed, 14 insertions(+), 12 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 462cdaade..6aa3d8b1a 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -377,6 +377,19 @@ impl DatalogExecutor { fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option> { use std::collections::HashSet; + // Dedup key: (entity, attribute, tx_count, asserted, encoded value, + // valid_from, valid_to). `asserted` keeps an assertion and a + // retraction from the same WriteTransaction apart; the encoded value + // keeps two values of one attribute written in the same transaction + // apart (#371). Uses `encode_value` bytes rather than `Value` to + // avoid Float hashing. `valid_from`/`valid_to` keep two distinct + // valid-time stints of the same (entity, attribute, value, tx_count, + // asserted) tuple apart — without them, two per-fact valid-time + // windows on the same value in one transaction collapse into a + // single arbitrary survivor and the other window's row is silently + // dropped from `:valid-at` and `:any-valid-time` results (#371). + type FactDedupKey = (uuid::Uuid, String, u64, bool, Vec, i64, i64); + let mut entity_ids: HashSet = HashSet::new(); let mut attributes: HashSet = HashSet::new(); @@ -404,18 +417,7 @@ impl DatalogExecutor { return None; } - // Dedup key: (entity, attribute, tx_count, asserted, encoded value, - // valid_from, valid_to). `asserted` keeps an assertion and a - // retraction from the same WriteTransaction apart; the encoded value - // keeps two values of one attribute written in the same transaction - // apart (#371). Uses `encode_value` bytes rather than `Value` to - // avoid Float hashing. `valid_from`/`valid_to` keep two distinct - // valid-time stints of the same (entity, attribute, value, tx_count, - // asserted) tuple apart — without them, two per-fact valid-time - // windows on the same value in one transaction collapse into a - // single arbitrary survivor and the other window's row is silently - // dropped from `:valid-at` and `:any-valid-time` results (#371). - let mut seen: HashSet<(uuid::Uuid, String, u64, bool, Vec, i64, i64)> = HashSet::new(); + let mut seen: HashSet = HashSet::new(); let mut all_facts: Vec = Vec::new(); for uid in &entity_ids { From bd87b95289bb396a1765954983fc508f6458ebc4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 09:53:47 +0530 Subject: [PATCH 20/21] docs: update test counts after final-review fixes (#371, #287) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 ++-- 3 files changed, 4 insertions(+), 4 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index 66b000e00..d54e87d9e 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -166,7 +166,7 @@ Auto-migrates v7 → v8 on open (index rebuild). v1–v6 are rejected (STG-028). ## Test Coverage -**1155 tests passing** (1147 passing, 8 ignored; unit + integration + doc). +**1157 tests passing** (1149 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. diff --git a/README.md b/README.md index e6217173d..721a0fa11 100644 --- a/README.md +++ b/README.md @@ -92,7 +92,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1155 tests +cargo test # run 1157 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 9b8d0ae81..eecbbd86d 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-09-25 with `cargo test --quiet` -**Result**: 1,147 passing tests and 8 ignored tests (1,155 total) +**Result**: 1,149 passing tests and 8 ignored tests (1,157 total) This supersedes the v2.0.0-era count (1,145 passing, 8 ignored) with the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 @@ -15,7 +15,7 @@ and structured-error-code changes. ### Covered Areas - **Core database behavior**: in-memory and file-backed operation, transactions, checkpoints, retractions, bi-temporal queries, recursive rules, prepared statements, aggregation, expressions, disjunction, window functions, UDFs, and magic-sets evaluation. -- **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 8 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). +- **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, and SIGKILL recovery. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). From 76cb3769dba83ffd70c46c65954e4c93ec2e4fe4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 10:15:02 +0530 Subject: [PATCH 21/21] fix: keep STG-003/STG-004 registered as deprecated instead of removing them (#287) Error codes are a stable public contract and are never removed or reused. STG-003 and STG-004 can no longer be emitted (pre-v7 headers are rejected with STG-028 before any size check), so they stay in ErrorCode, REGISTRY and ERROR_REFERENCE.md, marked deprecated in v3.0.0. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CHANGELOG.md | 2 +- docs/ERROR_REFERENCE.md | 30 ++++++++++++++++++- .../2026-09-24-index-key-value-collision.md | 2 +- src/error.rs | 23 ++++++++++++++ 4 files changed, 54 insertions(+), 3 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 3506458c6..557cbc003 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,7 +10,7 @@ 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. -- **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 retired. `STG-005` and `STG-006` message text changed. +- **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. ### Fixed diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 98378d009..e14e29915 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -111,6 +111,8 @@ with no `CodedError` anywhere in its chain. | QRY-009 | Rules lock poisoned | Query Execution | | STG-001 | Invalid header: too short | Storage | | STG-002 | Invalid magic number: not a .graph file | Storage | +| STG-003 | Invalid v4/v5/v6 header too short (deprecated) | Storage | +| STG-004 | Invalid v6 header too short (deprecated) | Storage | | STG-005 | Invalid header too short | Storage | | STG-006 | Unsupported format version | Storage | | STG-007 | page_count must be greater than 0 | Storage | @@ -207,7 +209,7 @@ with no `CodedError` anywhere in its chain. | INT-054 | Unstratifiable negative recursion cycle | Internal | | INT-055 | Rule predicate disappeared during rollback | Internal | -Retired codes: STG-003 and STG-004 (pre-v7 header sizes) were retired in v3.0.0, when formats v1–v6 stopped being readable. Retired codes are never reused. +Deprecated codes: STG-003 and STG-004 (pre-v7 header sizes) are deprecated as of v3.0.0 and are no longer emitted, because formats v1–v6 are rejected with STG-028 before any header-size check. They stay registered and documented, and error codes are never removed or reused. --- @@ -1697,6 +1699,32 @@ See the [file format section in README](../README.md#file-format) for version hi **Scenario**: `Minigraf::open("config.json")` — a wrong file path was passed. +### STG-003 Invalid v4/v5/v6 header too short + +> **Deprecated in v3.0.0.** No longer emitted: files in formats v1–v6 are rejected with [STG-028](#stg-028-format-version-no-longer-supported) before any header-size check. Kept for reference; this code will not be reused. + +**Error text**: `Invalid v4/v5/v6 header: expected at least 72 bytes, got {}` + +**Cause**: A file identified as format version 4, 5, or 6 is too short to hold a valid header of that version. The file is truncated at the header. + +**Resolution**: +- Restore from backup. If the file is newly created, delete it. See the [file format section in README](../README.md#file-format). + +**Scenario**: A v5-format `.graph` file was corrupted by a partial write and is missing the latter part of its header. + +### STG-004 Invalid v6 header too short + +> **Deprecated in v3.0.0.** No longer emitted: files in formats v1–v6 are rejected with [STG-028](#stg-028-format-version-no-longer-supported) before any header-size check. Kept for reference; this code will not be reused. + +**Error text**: `Invalid v6 header: expected 80 bytes, got {}` + +**Cause**: A file identified as format version 6 is shorter than the required 80-byte v6 header. The file is truncated. + +**Resolution**: +- Restore from backup. If the file is newly created, delete it. See the [file format section in README](../README.md#file-format). + +**Scenario**: A v6-format `.graph` file was written by an older pre-release version and its header is incomplete. + ### STG-005 Invalid header too short **Error text**: `Invalid header: expected 84 bytes, got {}` diff --git a/docs/superpowers/plans/2026-09-24-index-key-value-collision.md b/docs/superpowers/plans/2026-09-24-index-key-value-collision.md index ad0a8ad1c..273dddda8 100644 --- a/docs/superpowers/plans/2026-09-24-index-key-value-collision.md +++ b/docs/superpowers/plans/2026-09-24-index-key-value-collision.md @@ -22,7 +22,7 @@ ``` - Commits and the PR reference `#371` and `#287`; only the PR body uses closing keywords (`Closes #371`, `Closes #287`). - No version bump, no tag, no `release.yml` edits (cargo-dist owns it). -- New error code: `STG-028`. Retired codes: `STG-003`, `STG-004` (never reused). +- New error code: `STG-028`. `STG-003`, `STG-004` become deprecated (kept registered and documented, never reused). **Amended after review:** the plan originally deleted them as "retired"; error codes are never removed. - `FORMAT_VERSION = 8`, new `MIN_FORMAT_VERSION = 7`. - The pre-push hook runs fmt + clippy + test; CI's clippy may be newer than local — run `cargo clippy --all-targets --all-features -- -D warnings` before pushing. diff --git a/src/error.rs b/src/error.rs index 6f7a3006a..bf4fed8ab 100644 --- a/src/error.rs +++ b/src/error.rs @@ -138,6 +138,13 @@ pub(crate) enum ErrorCode { Int000, Stg001, Stg002, + // STG-003/STG-004 are deprecated since v3.0.0: they reported truncated + // v4–v6 headers, and formats older than v7 are now rejected with STG-028 + // before any size check. Kept so the codes are never reused. + #[allow(dead_code)] + Stg003, + #[allow(dead_code)] + Stg004, Stg005, Stg006, Stg007, @@ -785,6 +792,18 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "Invalid magic number: not a .graph file", ErrorCategory::Storage, ), + ( + ErrorCode::Stg003, + "STG-003", + "Invalid v4/v5/v6 header: expected at least 72 bytes, got {}", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg004, + "STG-004", + "Invalid v6 header: expected 80 bytes, got {}", + ErrorCategory::Storage, + ), ( ErrorCode::Stg005, "STG-005", @@ -1712,6 +1731,8 @@ mod tests { | ErrorCode::Qry009 | ErrorCode::Stg001 | ErrorCode::Stg002 + | ErrorCode::Stg003 + | ErrorCode::Stg004 | ErrorCode::Stg005 | ErrorCode::Stg006 | ErrorCode::Stg007 @@ -1901,6 +1922,8 @@ mod tests { ErrorCode::Qry009, ErrorCode::Stg001, ErrorCode::Stg002, + ErrorCode::Stg003, + ErrorCode::Stg004, ErrorCode::Stg005, ErrorCode::Stg006, ErrorCode::Stg007,