From 410c0ddb69f811ff7464b5c90454223b775dfd41 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 10:32:34 +0530 Subject: [PATCH] revert: move file format v8 (#377) from main to the v3 branch MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Main must stay releasable as v2.x so v2.1–v2.3 (and #370's unreleased fix) can ship without a forced one-way format migration. The v8 work (#371, #287) is preserved unchanged on the long-lived `v3` branch (at b8a9762), which will merge main regularly and becomes main when v3.0.0 is cut. This reverts commit b8a9762fe7607bb79ae084f5f0c2d4bffb26008a. 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/ERROR_REFERENCE.md | 34 +- docs/TEST_COVERAGE.md | 15 +- .../2026-09-24-index-key-value-collision.md | 1120 ----------------- ...-09-21-index-key-value-collision-design.md | 171 --- examples/generate_compat_fixture.rs | 18 +- fuzz/fuzz_targets/btree_page.rs | 24 +- fuzz/fuzz_targets/fact_page.rs | 14 +- src/browser/mod.rs | 8 - src/error.rs | 18 +- src/graph/storage.rs | 33 +- src/query/datalog/executor.rs | 27 +- src/storage/btree.rs | 547 ++++++++ src/storage/btree_v6.rs | 24 - src/storage/index.rs | 397 ++---- src/storage/mod.rs | 212 +++- src/storage/persistent_facts.rs | 884 ++++++++++--- tests/btree_v6_test.rs | 56 +- tests/cross_platform_compat_test.rs | 22 +- tests/error_codes_storage_test.rs | 17 - tests/fixtures/v7_multivalue.graph | Bin 49152 -> 0 bytes tests/migration_matrix_test.rs | 52 +- tests/multi_value_test.rs | 551 -------- tests/wal_test.rs | 54 +- 27 files changed, 1735 insertions(+), 2592 deletions(-) delete mode 100644 docs/superpowers/plans/2026-09-24-index-key-value-collision.md delete mode 100644 docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md create mode 100644 src/storage/btree.rs delete mode 100644 tests/fixtures/v7_multivalue.graph delete mode 100644 tests/multi_value_test.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 557cbc003..7484edbc6 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -5,18 +5,6 @@ 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 deprecated (no longer emitted, still registered, never reused). `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 d54e87d9e..2b83e26fa 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -104,14 +104,15 @@ 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` v8 (84 bytes), `CommittedFactReader` / `CommittedIndexReader` traits + - `mod.rs`: `StorageBackend` trait, `FileHeader` v7 (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` — v8 save/load, auto-migration v7→v8 + - `persistent_facts.rs`: `PersistentFactStorage` — v7 save/load, auto-migration v1–v6→v7 3. **`src/query/datalog/`** — Datalog engine - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join` @@ -152,7 +153,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 (v8) +### File Format (v7) ``` Page 0: Header (84 bytes) — magic "MGRF", version, page/fact counts, @@ -162,11 +163,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 v7 → v8 on open (index rebuild). v1–v6 are rejected (STG-028). +Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1157 tests passing** (1149 passing, 8 ignored; unit + integration + doc). +**1153 tests passing** (1145 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 721a0fa11..82414ce6d 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 1157 tests +cargo test # run 1153 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index 969c4c6b1..187668918 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 -**#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. +**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. 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` value-bytes fix, format v8, v7→v8 migration, v1–v6 dropped (#287, #371) +- `EavtKey`/`AevtKey` missing-value-bytes fix and file-format v7→v8 migration (#287) - `lag`/`lead` window functions (#182) - Sliding row frames — `:rows N preceding` (#183; builds on #182) - `PreparedQuery` over UniFFI (#181) diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index e14e29915..d4b1fe9df 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -111,9 +111,9 @@ 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-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-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,7 +136,6 @@ 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 | @@ -209,8 +208,6 @@ with no `CodedError` anywhere in its chain. | INT-054 | Unstratifiable negative recursion cycle | Internal | | INT-055 | Rule predicate disappeared during rollback | Internal | -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. - --- ## PRS — Parser Errors @@ -1701,8 +1698,6 @@ See the [file format section in README](../README.md#file-format) for version hi ### 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. @@ -1714,8 +1709,6 @@ See the [file format section in README](../README.md#file-format) for version hi ### 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. @@ -1725,18 +1718,20 @@ See the [file format section in README](../README.md#file-format) for version hi **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**: The file declares a supported format version (7 or later) but is shorter than the 84-byte header. The file is truncated. +**Cause**: A file identified as format version 7 (current format) is shorter than the required 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: 7-{})` +**Error text**: `Unsupported format version: {} (supported: 1-{})` **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. @@ -1989,17 +1984,6 @@ 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/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index eecbbd86d..2ccaaadce 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -1,22 +1,17 @@ # Minigraf Test Coverage -## Coverage Summary +## v2.0.0 Coverage Summary -**Verified**: 2026-09-25 with `cargo test --quiet` +**Verified**: 2026-08-26 with `cargo test --quiet` -**Result**: 1,149 passing tests and 8 ignored tests (1,157 total) +**Result**: 1,145 passing tests and 8 ignored tests (1,153 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 -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. +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. ### 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`, 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. +- **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration, 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. 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 deleted file mode 100644 index 273dddda8..000000000 --- a/docs/superpowers/plans/2026-09-24-index-key-value-collision.md +++ /dev/null @@ -1,1120 +0,0 @@ -# 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`. `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. - -## 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. 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 deleted file mode 100644 index cde3736a7..000000000 --- a/docs/superpowers/specs/2026-09-21-index-key-value-collision-design.md +++ /dev/null @@ -1,171 +0,0 @@ -# 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. 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: - -- 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. `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. - -### 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. -- 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, 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 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 - 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. - -### 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 - -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 - (`[: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` 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. 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. -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. - -## 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 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. diff --git a/examples/generate_compat_fixture.rs b/examples/generate_compat_fixture.rs index bf1760e75..b8b0b098c 100644 --- a/examples/generate_compat_fixture.rs +++ b/examples/generate_compat_fixture.rs @@ -1,14 +1,12 @@ -//! Generates a `.graph` file with two known facts, for inspecting what the -//! current storage layer writes. +//! Generates `tests/fixtures/compat.graph` — a minimal v7 `.graph` file containing +//! two known facts used by the cross-platform compatibility tests. //! +//! Run once when the file format changes or the fixture needs regenerating: //! cargo run --example generate_compat_fixture //! -//! `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. +//! 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!`. // 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 @@ -21,9 +19,7 @@ fn main() -> anyhow::Result<()> { use std::path::PathBuf; let manifest_dir = env!("CARGO_MANIFEST_DIR"); - 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 fixture_path = PathBuf::from(manifest_dir).join("tests/fixtures/compat.graph"); let tmp_path = fixture_path.with_extension("graph.tmp"); // Remove any leftover from a previous run. diff --git a/fuzz/fuzz_targets/btree_page.rs b/fuzz/fuzz_targets/btree_page.rs index 5e9fe3027..c93a26b03 100644 --- a/fuzz/fuzz_targets/btree_page.rs +++ b/fuzz/fuzz_targets/btree_page.rs @@ -9,31 +9,11 @@ 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"); - // 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. + content[4..8].copy_from_slice(&7u32.to_le_bytes()); 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 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]])"#, - ); + let _ = minigraf::db::Minigraf::open(&path); }); diff --git a/fuzz/fuzz_targets/fact_page.rs b/fuzz/fuzz_targets/fact_page.rs index ee38ecfc0..c63d38219 100644 --- a/fuzz/fuzz_targets/fact_page.rs +++ b/fuzz/fuzz_targets/fact_page.rs @@ -9,19 +9,7 @@ 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"); - // 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. + content[4..8].copy_from_slice(&7u32.to_le_bytes()); 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() { diff --git a/src/browser/mod.rs b/src/browser/mod.rs index e8a065f42..75daf39f0 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -483,14 +483,6 @@ 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/error.rs b/src/error.rs index bf4fed8ab..6c781ace8 100644 --- a/src/error.rs +++ b/src/error.rs @@ -138,12 +138,7 @@ 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, @@ -168,7 +163,6 @@ pub(crate) enum ErrorCode { Stg025, Stg026, Stg027, - Stg028, Wal001, Wal002, Wal003, @@ -807,13 +801,13 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ ( ErrorCode::Stg005, "STG-005", - "Invalid header: expected 84 bytes, got {}", + "Invalid v7 header: expected 84 bytes, got {}", ErrorCategory::Storage, ), ( ErrorCode::Stg006, "STG-006", - "Unsupported format version: {} (supported: 7-{})", + "Unsupported format version: {} (supported: 1-{})", ErrorCategory::Storage, ), ( @@ -942,12 +936,6 @@ 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", @@ -1756,7 +1744,6 @@ mod tests { | ErrorCode::Stg025 | ErrorCode::Stg026 | ErrorCode::Stg027 - | ErrorCode::Stg028 | ErrorCode::Wal001 | ErrorCode::Wal002 | ErrorCode::Wal003 @@ -1947,7 +1934,6 @@ mod tests { ErrorCode::Stg025, ErrorCode::Stg026, ErrorCode::Stg027, - ErrorCode::Stg028, ErrorCode::Wal001, ErrorCode::Wal002, ErrorCode::Wal003, diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 693551597..74c9405d7 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -621,9 +621,21 @@ impl FactStorage { use crate::storage::index::EavtKey; let d = self.data.read().unwrap_or_else(|e| e.into_inner()); - let start = EavtKey::entity_start(*entity_id); + let start = EavtKey { + entity: *entity_id, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; let next_entity = uuid::Uuid::from_u128(entity_id.as_u128().wrapping_add(1)); - let end = EavtKey::entity_start(next_entity); + let end = EavtKey { + entity: next_entity, + attribute: String::new(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; // Fallback: no indexes built yet if d.pending_indexes.eavt.is_empty() && d.committed_index_reader.is_none() { @@ -687,9 +699,20 @@ impl FactStorage { .collect()); } - let start = AevtKey::attribute_start(attribute); - let end_opt: Option = - next_string_prefix(attribute).map(|next_attr| AevtKey::attribute_start(&next_attr)); + 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 mut facts = Vec::new(); diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 6aa3d8b1a..dfaa16aac 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -373,23 +373,10 @@ 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, value)`. + /// returns `Some(facts)`, deduplicated by `(entity, attribute, tx_count, asserted)`. 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(); @@ -417,7 +404,11 @@ impl DatalogExecutor { return None; } - let mut seen: HashSet = HashSet::new(); + // 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(); let mut all_facts: Vec = Vec::new(); for uid in &entity_ids { @@ -429,9 +420,6 @@ impl DatalogExecutor { fact.attribute.clone(), 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); @@ -451,9 +439,6 @@ impl DatalogExecutor { fact.attribute.clone(), 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/src/storage/btree.rs b/src/storage/btree.rs new file mode 100644 index 000000000..9e4db54e1 --- /dev/null +++ b/src/storage/btree.rs @@ -0,0 +1,547 @@ +//! 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/btree_v6.rs b/src/storage/btree_v6.rs index e9a6020b3..5c5a9b9e1 100644 --- a/src/storage/btree_v6.rs +++ b/src/storage/btree_v6.rs @@ -818,8 +818,6 @@ mod tests { valid_from: 0, valid_to: i64::MAX, tx_count: tx, - value_bytes: Vec::new(), - asserted: true, }, FactRef { page_id: tx + 1, @@ -1089,8 +1087,6 @@ 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 { @@ -1099,8 +1095,6 @@ 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(); @@ -1131,8 +1125,6 @@ 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); @@ -1154,8 +1146,6 @@ 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"); @@ -1177,8 +1167,6 @@ 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), @@ -1186,8 +1174,6 @@ 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 @@ -1257,8 +1243,6 @@ 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"); @@ -1288,8 +1272,6 @@ 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), @@ -1297,8 +1279,6 @@ 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, "", ...} @@ -1340,8 +1320,6 @@ 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), @@ -1349,8 +1327,6 @@ 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 9099c4660..8eb59ea89 100644 --- a/src/storage/index.rs +++ b/src/storage/index.rs @@ -7,6 +7,19 @@ 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 ──────────────────────────────────────────────────────────────── @@ -84,11 +97,7 @@ pub fn encode_value(v: &Value) -> Vec { // ─── Index Key Types ───────────────────────────────────────────────────────── -/// 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). +/// EAVT: sort by (Entity, Attribute, ValidFrom, ValidTo, TxCount) #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] pub struct EavtKey { pub entity: EntityId, @@ -96,15 +105,9 @@ 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, 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). +/// AEVT: sort by (Attribute, Entity, ValidFrom, ValidTo, TxCount) #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] pub struct AevtKey { pub attribute: Attribute, @@ -112,11 +115,9 @@ 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, Asserted) +/// AVET: sort by (Attribute, ValueBytes, ValidFrom, ValidTo, Entity, TxCount) /// /// `value_bytes` is the canonical encoding from `encode_value`. #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] @@ -127,10 +128,9 @@ 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, Asserted) +/// VAET: sort by (RefTarget, Attribute, ValidFrom, ValidTo, SourceEntity, TxCount) /// /// Only facts with `Value::Ref` are indexed here. #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)] @@ -141,93 +141,6 @@ 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 ───────────────────────────────────────────────────────────────── @@ -254,67 +167,159 @@ 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::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); + 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, + ); } } /// 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() + 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() } /// 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() + 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() } /// 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::nil(), + entity: EntityId::default(), tx_count: 0, - asserted: false, }; - self.avet - .range(start..) - .take_while(|(k, _)| k.attribute == attribute && k.value_bytes == value_bytes) - .map(|(_, v)| *v) - .collect() + 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() } /// 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::nil(), + source_entity: EntityId::default(), tx_count: 0, - asserted: false, }; - self.vaet - .range(start..) - .take_while(|(k, _)| k.ref_target == target) - .map(|(_, v)| *v) - .collect() + 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() } } @@ -324,126 +329,6 @@ 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 { @@ -497,8 +382,6 @@ mod tests { valid_from: 0, valid_to: i64::MAX, tx_count: 1, - value_bytes: Vec::new(), - asserted: true, }; let k2 = EavtKey { entity: e2, @@ -506,8 +389,6 @@ mod tests { valid_from: 0, valid_to: i64::MAX, tx_count: 1, - value_bytes: Vec::new(), - asserted: true, }; assert!(k1 < k2); } @@ -522,7 +403,6 @@ mod tests { valid_to: i64::MAX, entity: e, tx_count: 1, - asserted: true, }; let k2 = AvetKey { attribute: ":score".to_string(), @@ -531,7 +411,6 @@ 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 14a28b8de..314550426 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -6,6 +6,7 @@ /// /// 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; @@ -44,12 +45,10 @@ pub const PAGE_SIZE: usize = 4096; pub const MAGIC_NUMBER: [u8; 4] = *b"MGRF"; /// Current file format version -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). -pub const MIN_FORMAT_VERSION: u32 = 7; +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; /// fact_page_format: packed pages (v5+). pub const FACT_PAGE_FORMAT_PACKED: u8 = 0x02; @@ -96,7 +95,7 @@ pub trait StorageBackend: Send + Sync { fn is_new(&self) -> bool; } -/// File header for .graph files — 84 bytes (v7 and v8 share the layout). +/// File header for .graph files — 84 bytes in v7. /// /// Layout (all fields little-endian): /// 0..4 magic ("MGRF") @@ -125,14 +124,14 @@ pub struct FileHeader { pub avet_root_page: u64, pub vaet_root_page: u64, pub index_checksum: u32, - /// 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. + /// fact_page_format (v5+): 0x00 = unset/legacy, 0x01 = one-per-page, 0x02 = packed. 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, } @@ -179,8 +178,14 @@ impl FileHeader { /// Deserialize the header from bytes. /// - /// Accepts only v7+ (84-byte) headers; older versions fail with STG-028. + /// 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. 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()); } @@ -197,17 +202,53 @@ 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)?; - let fact_page_count = read_u64_le(bytes, 72)?; - let header_checksum = read_u32_le(bytes, 80)?; + + // 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 + }; Ok(FileHeader { magic, @@ -244,10 +285,7 @@ impl FileHeader { if self.magic != MAGIC_NUMBER { bail_coded!(ErrorCode::Int039); } - if self.version < MIN_FORMAT_VERSION { - bail_coded!(ErrorCode::Stg028, self.version, MIN_FORMAT_VERSION); - } - if self.version > FORMAT_VERSION { + if self.version < 1 || self.version > FORMAT_VERSION { bail_coded!(ErrorCode::Stg006, self.version, FORMAT_VERSION); } // Validate logical relationships @@ -332,6 +370,20 @@ 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(); @@ -343,8 +395,8 @@ mod tests { } #[test] - fn test_format_version_is_8() { - assert_eq!(FORMAT_VERSION, 8); + fn test_format_version_is_7() { + assert_eq!(FORMAT_VERSION, 7); } #[test] @@ -354,13 +406,6 @@ 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(); @@ -403,10 +448,10 @@ mod tests { } #[test] - fn test_new_header_has_version_8() { + fn test_new_header_has_version_7() { let header = FileHeader::new(); assert_eq!(header.version, FORMAT_VERSION); - assert_eq!(header.version, 8); + assert_eq!(header.version, 7); } #[test] @@ -445,7 +490,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], &FORMAT_VERSION.to_le_bytes()); + assert_eq!(&b[4..8], &7u32.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()); @@ -460,6 +505,17 @@ 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]; @@ -468,6 +524,15 @@ 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(); @@ -478,11 +543,48 @@ 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/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, + // 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, // 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 @@ -498,32 +600,32 @@ mod tests { } #[test] - fn from_bytes_v7_too_short_returns_stg_005() { - let mut bytes = vec![0u8; 82]; // >= 80, < 84 + fn from_bytes_v4_too_short_returns_stg_003() { + let mut bytes = vec![0u8; 70]; // >= 64, < 72 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"); + 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"); let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-005"); + assert_eq!(coded.code(), "STG-003"); } #[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"); - let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-028"); - } + 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"); } #[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"); + 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"); let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-028"); + assert_eq!(coded.code(), "STG-005"); } } diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 8afcbe53a..2a057513f 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -6,14 +6,15 @@ 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, }; use crate::storage::cache::PageCache; -use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; +use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey, encode_value}; use crate::storage::packed_pages::pack_facts; -use crate::storage::{FORMAT_VERSION, FileHeader, PAGE_SIZE, StorageBackend}; +use crate::storage::{FileHeader, PAGE_SIZE, StorageBackend}; use anyhow::Result; use crc32fast::Hasher; use std::sync::atomic::{AtomicU64, Ordering}; @@ -93,6 +94,18 @@ 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: @@ -164,8 +177,7 @@ 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 - // `load()` runs (and its version check rejects pre-v7 files) even - // for a file that has no fact pages. + // migrate_v5_to_v6 runs for a v5 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) = { @@ -204,8 +216,19 @@ 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 - if header.header_checksum != 0 { + // For older versions (v6 and earlier), header_checksum is 0 so validation is skipped + if header.version >= 7 && header.header_checksum != 0 { let computed = compute_header_checksum_from_bytes(&raw_header_bytes); if header.header_checksum != computed { bail_coded!(ErrorCode::Int053); @@ -218,8 +241,21 @@ 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.fact_page_count > 0 { + let num_fact_pages = if header.version >= 6 && header.fact_page_count > 0 { header.fact_page_count } else { let first_index_page = [ @@ -238,21 +274,32 @@ impl PersistentFactStorage { self.committed_fact_pages .store(num_fact_pages, Ordering::SeqCst); - // 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 { + // 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 { 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); - compute_page_checksum(&*backend, 1, total_data_pages)? != header.index_checksum + 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 + } + } }; // Register CommittedFactReader on FactStorage (before WAL replay) @@ -287,15 +334,8 @@ 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. 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); + // Fix up tx_counter from actual facts + let max_tx = all_facts.iter().map(|f| f.tx_count).max().unwrap_or(0); self.storage.restore_tx_counter_from(max_tx); // Build v6 B+tree indexes directly @@ -331,12 +371,6 @@ 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)?; @@ -378,7 +412,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.header_checksum != 0 { + if header.version >= 7 && header.header_checksum != 0 { let backend = self .backend .lock() @@ -411,6 +445,376 @@ 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. @@ -561,7 +965,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=FORMAT_VERSION + let mut header = FileHeader::new(); // version=7 header.page_count = next4; let pending_len = u64::try_from(pending_facts.len()).map_err(|_| err_coded!(ErrorCode::Stg024))?; @@ -778,28 +1182,78 @@ fn build_sorted_index_entries( let mut eavt: Vec<(EavtKey, FactRef)> = facts .iter() .zip(refs.iter()) - .map(|(f, &fr)| (EavtKey::from_fact(f), fr)) + .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, + ) + }) .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::from_fact(f), fr)) + .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, + ) + }) .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::from_fact(f), fr)) + .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, + ) + }) .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)| VaetKey::from_fact(f).map(|k| (k, fr))) + .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 + } + }) .collect(); vaet.sort_unstable_by(|(a, _), (b, _)| a.cmp(b)); @@ -832,29 +1286,6 @@ 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 @@ -920,6 +1351,60 @@ 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(); @@ -952,6 +1437,30 @@ 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; @@ -1189,6 +1698,34 @@ 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; @@ -1212,12 +1749,12 @@ mod tests { pfs.save().unwrap(); } - // Verify: header says current version, fact_page_format = PACKED + // Verify: header says v6, 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, FORMAT_VERSION); + assert_eq!(header.version, 7); assert_eq!( header.fact_page_format, crate::storage::FACT_PAGE_FORMAT_PACKED @@ -1267,6 +1804,70 @@ 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; @@ -1328,11 +1929,8 @@ 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, FORMAT_VERSION, - "save() must write current-version header" - ); - assert_eq!(header.to_bytes().len(), 84, "header must be 84 bytes"); + assert_eq!(header.version, 7, "save() must write v7 header"); + assert_eq!(header.to_bytes().len(), 84, "v7 header must be 84 bytes"); assert!(header.fact_page_count > 0, "fact_page_count must be set"); assert!( header.eavt_root_page > 0, @@ -1340,91 +1938,6 @@ 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"); - } - - /// #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(); @@ -1500,6 +2013,53 @@ 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`). /// @@ -1509,7 +2069,8 @@ mod tests { /// compute_page_checksum looped over 3.6 billion zero-filled sparse pages /// (each read_exact returns zeros, no error), hanging the process. /// - /// Since v3.0.0 a v5 header is rejected before any page is touched. + /// After the fix, next_free = 1 + validated_num_fact_pages (= 1 here), + /// so migration completes in constant time and produces a sane v7 header. #[test] fn test_v5_migration_large_page_count_does_not_hang() { use crate::storage::backend::FileBackend; @@ -1527,16 +2088,19 @@ mod tests { page[68] = 0x20; // fact_page_format std::fs::write(&path, &page).unwrap(); - // `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, - }; + // 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. assert!( - err.to_string().contains("no longer supported"), - "must fail with STG-028" + header.page_count < 100, + "page_count must be sane after migration" ); } diff --git a/tests/btree_v6_test.rs b/tests/btree_v6_test.rs index d3cd77050..b2a813132 100644 --- a/tests/btree_v6_test.rs +++ b/tests/btree_v6_test.rs @@ -110,29 +110,49 @@ fn test_v6_pending_plus_committed_merge() { } #[test] -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. +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. let (_tmp, path) = tmp_path(); - 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(); + // 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 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"); + // Open with v6 code — migration must run + let db = OpenOptions::new().path(&path).open().unwrap(); + // 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!( - std::fs::read(&path).unwrap(), - page, - "rejected file must be left unmodified" + version, 7, + "header must be upgraded from v5 to v7; got version={}", + version ); } diff --git a/tests/cross_platform_compat_test.rs b/tests/cross_platform_compat_test.rs index fbc61c6a0..0d1c3a8d0 100644 --- a/tests/cross_platform_compat_test.rs +++ b/tests/cross_platform_compat_test.rs @@ -82,25 +82,12 @@ 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. /// -/// 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. +/// This fixture 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"); - // 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); @@ -128,10 +115,5 @@ 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); } diff --git a/tests/error_codes_storage_test.rs b/tests/error_codes_storage_test.rs index edebe0ea5..9920ac06b 100644 --- a/tests/error_codes_storage_test.rs +++ b/tests/error_codes_storage_test.rs @@ -69,23 +69,6 @@ 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/fixtures/v7_multivalue.graph b/tests/fixtures/v7_multivalue.graph deleted file mode 100644 index fb0d07c7c228dc262093333ca1be6476867f3def..0000000000000000000000000000000000000000 GIT binary patch literal 0 HcmV?d00001 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# diff --git a/tests/migration_matrix_test.rs b/tests/migration_matrix_test.rs index 3c3c66819..787b5b295 100644 --- a/tests/migration_matrix_test.rs +++ b/tests/migration_matrix_test.rs @@ -34,34 +34,24 @@ 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 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" - ); - } +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" + ); } #[test] @@ -93,16 +83,8 @@ 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] diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs deleted file mode 100644 index eb41859b8..000000000 --- a/tests/multi_value_test.rs +++ /dev/null @@ -1,551 +0,0 @@ -//! 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" - ); - } - } -} - -/// 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" - ); - } -} - -/// `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" - ); - } -} - -/// 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] -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"); -} - -/// `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" - ); -} diff --git a/tests/wal_test.rs b/tests/wal_test.rs index 58d8bd303..02cdc4a20 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 -//! - Pre-v7 file formats (e.g. V2) are rejected, not silently upgraded +//! - V2 → V3 file format upgrade on first checkpoint #![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 is rejected ────────────────────────────────────────────────── +// ── 12. V2 file upgrades to V3 on checkpoint ───────────────────────────────── -/// 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. +/// 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. #[test] -fn test_v2_file_is_rejected() { +fn test_v2_file_opens_and_upgrades_to_v3_on_checkpoint() { use std::io::Write; let dir = tempfile::tempdir().unwrap(); @@ -734,6 +734,14 @@ fn test_v2_file_is_rejected() { // ── 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]; @@ -743,15 +751,39 @@ fn test_v2_file_is_rejected() { 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(); } - 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"); + // ── 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" + ); }