adityamukho · Oct 6, 2026 · Oct 6, 2026
@@ -17,6 +17,10 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit.
 - **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed.
 
+### Added
+
+- **`Minigraf::verify()` and `Minigraf::rebuild_indexes()`** (#373). Page checksums turn a torn or rotted page into an error, but they cannot see a page that is valid and says the wrong thing. `verify()` walks every committed page and returns an `IntegrityReport` with one structured error per finding: an index that holds different facts than EAVT or a different count than the meta page (new `STG-038`), keys out of order or a page reached twice (new `STG-039`), dictionary maps that disagree (new `STG-040`), ids with no dictionary entry (`STG-036`), and leaked, doubly used or wrongly free pages (`STG-035`). It keeps no per-fact state: indexes are compared by an order-independent digest. `rebuild_indexes()` rebuilds EAVT, AEVT, AVET and VAET from an intact index that agrees with another one (or the only intact one), derives the free list again, and commits like a checkpoint, including uncheckpointed writes; a crash at any point leaves the previous checkpoint. If no index can serve as the source, or the dictionary is damaged, it fails with new `STG-041` and writes nothing. Both are Rust API only for now; the bindings follow.
+
 ### 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).

@@ -115,6 +115,7 @@ cargo run < demos/demo_negation.txt
    - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building)
    - `value_pages.rs`: append-only value pages for strings over 64 bytes
    - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`)
+   - `verify.rs`: integrity walk for `Minigraf::verify` (tree order, index digests, DICT, page accounting) and the source choice for `rebuild_indexes` (#373)
    - `meta.rs` / `page.rs` / `freelist.rs`: meta pages A/B, the common page header and allocator, free-list chain
    - `cache.rs`: LRU page cache (`PageCache`, default 256 pages)
    - `dir_sync.rs`: `sync_parent_dir` — fsyncs the parent directory after creating the `.graph`/WAL or deleting the WAL (no-op off Unix)
@@ -137,7 +138,7 @@ cargo run < demos/demo_negation.txt
 
 5. **`src/repl.rs`** — Interactive REPL; TTY-aware (suppresses prompts/banner for piped input)
 
-6. **`src/db.rs`** — Public API: `Minigraf::open/execute/prepare/begin_write/checkpoint/save`, `WriteTransaction`, `OpenOptions::page_cache_size`
+6. **`src/db.rs`** — Public API: `Minigraf::open/execute/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size`
 
 7. **`src/wal.rs`** — Fact-level sidecar WAL, CRC32-protected entries, crash recovery
 
@@ -193,7 +194,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1238 tests** (1229 passing, 9 ignored; unit + integration + doc).
+**1248 tests** (1239 passing, 9 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.

@@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit
 
 ```bash
 cargo run          # interactive Datalog REPL
-cargo test         # run 1238 tests
+cargo test         # run 1248 tests
 cargo run < demos/demo_recursive.txt   # recursive rules demo
 ```
 

@@ -60,7 +60,7 @@ Scope — format and storage integrity:
   - covering byte-comparable keys with a dictionary and deduplicated long values, at about 142 bytes per fact (#433).
 
   The format is frozen for the golden-file corpus (#391).
-- Index `verify` and public `rebuild_indexes()` (#373)
+- Index `verify` and public `rebuild_indexes()` (#373; done on `v3`)
 - Net-assert on v8 keys before resolving facts, for O(live) point queries (#379)
 - `btree_page` fuzz target that reaches node decoding (#375)
 

@@ -146,6 +146,10 @@ with no `CodedError` anywhere in its chain.
 | STG-035 | Free-list inconsistency | Storage |
 | STG-036 | Dictionary entry missing | Storage |
 | STG-037 | Transaction with two timestamps | Storage |
+| STG-038 | Index disagrees with the committed facts | Storage |
+| STG-039 | Malformed tree | Storage |
+| STG-040 | Dictionary inconsistency | Storage |
+| STG-041 | Cannot rebuild indexes | Storage |
 | WAL-001 | Invalid WAL magic number | WAL |
 | WAL-002 | Unsupported WAL version | WAL |
 | WAL-003 | Value size exceeds maximum | WAL |
@@ -2083,10 +2087,11 @@ See the [file format section in README](../README.md#file-format) for version hi
 
 **Error text**: `Free list is inconsistent: {}`
 
-**Cause**: The chain of free-list pages loops, or holds a page id that is reserved or past the end of the file.
+**Cause**: The chain of free-list pages loops, or holds a page id that is reserved or past the end of the file. `Minigraf::verify()` also reports here a free-list count that disagrees with the meta page, a page listed twice, a free page that is still in use, a page used twice, and pages that are neither free nor in use (leaked).
 
 **Resolution**:
-- Restore from backup.
+- Run `Minigraf::rebuild_indexes()`: it derives a new free list from the pages the rebuilt file uses.
+- Restore from backup if the rebuild fails.
 
 **Scenario**: A corrupted free-list page whose `next` pointer points back at itself.
 
@@ -2118,6 +2123,60 @@ See the [file format section in README](../README.md#file-format) for version hi
 
 ---
 
+### STG-038 Index disagrees with the committed facts
+
+**Error text**: `Index {} disagrees with the committed facts: {}`
+
+**Cause**: `Minigraf::verify()` found an index whose pages are intact (every checksum passes) but whose contents are wrong: it holds a different number of entries or different facts than EAVT, EAVT's entry count differs from the meta page's fact count, an entry belongs to a transaction newer than the last checkpoint, or a key's long value does not match the stored value. Queries that use that index can return wrong or missing results.
+
+**Resolution**:
+- Run `Minigraf::rebuild_indexes()`, which rebuilds all four indexes from an index that agrees with another one.
+- Restore from backup if the rebuild fails with STG-041.
+
+**Scenario**: A bug or a lost write leaves AVET without some entries that EAVT and AEVT hold.
+
+---
+
+### STG-039 Malformed tree
+
+**Error text**: `Tree {} is malformed: {}`
+
+**Cause**: `Minigraf::verify()` found a B+tree whose pages pass their checksums but whose structure is wrong: keys out of order, a key outside its parent's separator range, a page reached twice (from the same tree or from two trees), a tree deeper than any real tree can be, a node or an index key that does not decode.
+
+**Resolution**:
+- If the tree is EAVT, AEVT, AVET or VAET, run `Minigraf::rebuild_indexes()`.
+- If the tree is DICT, restore from backup: the dictionary holds the only copy of entity UUIDs and attribute names.
+
+**Scenario**: A misdirected write leaves an older, valid leaf where a newer one belonged, so two leaves of the tree overlap.
+
+---
+
+### STG-040 Dictionary inconsistency
+
+**Error text**: `Dictionary is inconsistent: {}`
+
+**Cause**: `Minigraf::verify()` found DICT entries that disagree with each other or with the meta page: the UUID → entity-id and entity-id → UUID maps (or the ident maps) are not inverse, an id is not below the meta page's next id, an entry has the wrong shape or an unknown tag, or a long value does not match its hash.
+
+**Resolution**:
+- Restore from backup. The dictionary cannot be rebuilt from the indexes.
+
+**Scenario**: A DICT leaf is replaced by an older valid copy, so an entity id maps to a UUID that maps to another id.
+
+---
+
+### STG-041 Cannot rebuild indexes
+
+**Error text**: `Cannot rebuild indexes: {}`
+
+**Cause**: `Minigraf::rebuild_indexes()` found no index to rebuild from. A source must be an intact index (EAVT, AEVT or AVET) that agrees with another intact index, or the only intact one. This error also means the dictionary is damaged. The file is not modified.
+
+**Resolution**:
+- Restore from backup.
+
+**Scenario**: EAVT, AEVT and AVET are all intact but each holds a different set of facts.
+
+---
+
 ## WAL — Write-Ahead Log Errors
 
 WAL errors relate to the sidecar `.wal` file written alongside the `.graph` file.

@@ -0,0 +1,156 @@
+# Integrity check and index rebuild — Design
+
+**Issue:** #373 (split out of #370), tracker #383
+**Milestone:** v3.0.0, branch `v3`, file format v8 (no format change)
+**Builds on:** `2026-10-05-v8-storage-format-design.md` §4.2, §5.2, §7, §8, §11
+
+## 1. Problem
+
+#373 was written against v7: fact pages were the source of truth and four reference
+indexes pointed into them. An index that disagreed with the fact pages was silent.
+Entity-bound queries returned `[]` and the file checksum still passed (#370).
+
+v8 removes fact pages. Every index entry holds the whole fact (D4), and EAVT, AEVT and
+AVET each hold the complete fact set. Every page carries a CRC, its own id and its
+generation, and every read checks them (G3). A torn or rotted page is therefore an error
+on the read that hits it, never a wrong answer.
+
+Two gaps remain:
+
+1. **Logical damage is still silent.** A bug like #370's, or a lost write that leaves an
+   older valid page in place, gives pages that pass their CRC but say the wrong thing:
+   an index missing entries, two indexes that disagree, a leaked or doubly referenced
+   page, a key whose ids have no DICT entry. Only a full cross-check finds these.
+2. **There is no repair.** The spec promises `rebuild_indexes` from EAVT or AEVT
+   (§5.2, §7). A checkpoint cannot repair: it inserts copy-on-write into the existing
+   trees and fails on a damaged leaf.
+
+## 2. API
+
+```rust
+impl Minigraf {
+    /// Check the committed file. O(file).
+    pub fn verify(&self) -> Result<IntegrityReport, MinigrafError>;
+    /// Rebuild EAVT, AEVT, AVET and VAET from an intact index, then checkpoint.
+    pub fn rebuild_indexes(&self) -> Result<(), MinigrafError>;
+}
+
+#[non_exhaustive]
+pub struct IntegrityReport {
+    pub facts: u64,              // EAVT entries
+    pub pages: u64,              // pages checked
+    pub problems: Vec<MinigrafError>,
+}
+impl IntegrityReport { pub fn is_ok(&self) -> bool; }
+```
+
+- `verify` returns `Err` only when it cannot run (lock poisoned, I/O error reading the
+  meta). Damage goes into `problems`, one structured error per finding, so a caller can
+  match on codes. It keeps going after a finding where it can.
+- It checks the committed file only. Pending facts live in memory and in the WAL, whose
+  entries carry their own CRC.
+- In-memory databases have no committed pages: the report is empty and `is_ok()`.
+- Both take the write lock, so the active meta and its pages cannot change underneath
+  them. Readers keep running.
+- No Datalog or REPL syntax. Datalog stays the query language; SQLite's equivalent is a
+  pragma, not SQL. Bindings expose the two methods later (Python is Tier 1).
+- No on-open sampling. v8 open is O(1) by design (G4), and per-page checks already turn
+  physical damage into errors. Sampling a few entries cannot find a missing one.
+
+## 3. Checks (`verify`)
+
+All against the active meta `M`.
+
+| # | check | code |
+|---|---|---|
+| C1 | E
10BC8
very node of the five trees verifies (CRC, id, generation, type), decodes, and is reached once across all trees | STG-029/030/031/013, STG-039 |
+| C2 | Keys strictly increase across each tree (cursor walk) | STG-039 |
+| C3 | Every index key decodes; VAET values are refs | STG-039 |
+| C4 | EAVT count = `M.fact_count` | STG-038 |
+| C5 | AEVT and AVET hold the same facts as EAVT; VAET holds exactly EAVT's ref facts | STG-038 |
+| C6 | Every `tx_count` ≤ `M.last_checkpointed_tx_count` | STG-038 |
+| C7 | Every eid (entity or ref) has 0x02, every iid (attribute or keyword) 0x04, every `tx_count` 0x05, every long value ref a 0x06 entry | STG-036 |
+| C8 | 0x01 ↔ 0x02 and 0x03 ↔ 0x04 are inverse; ids below `next_eid` / `next_iid` | STG-040 |
+| C9 | Each long value reads, and its hash and prefix match the key | STG-038 |
+| C10 | Free list reads; ids distinct; count = `M.freelist_count`; free ∩ reachable = ∅; free ∪ reachable = `2..M.page_count` | STG-035 |
+
+**C5 without O(N) memory.** Each entry is mapped to its canonical EAVT key bytes and
+hashed. Per index the check keeps `(count, Σ h₁, ⊕ h₂)` with two independent 64-bit
+hashes. Equal digests mean equal multisets except with probability ≈ 2⁻⁶⁴ per pair. This
+is a corruption check, not an adversarial one. The digest also tells which index is the
+odd one out (§4).
+
+Memory: the reachable page set (8 B per page) and the DICT id sets (one entry per entity,
+ident and transaction). No per-fact state.
+
+## 4. Rebuild (`rebuild_indexes`)
+
+**Choosing the source.** Walk EAVT, AEVT and AVET (C1–C3 and the C5 digest). An index
+is *clean* if its walk finished without error.
+
+1. If two clean indexes have the same digest, the first of them (EAVT, AEVT, AVET order)
+   is the source.
+2. Otherwise, if exactly one is clean, it is the source: it is the only copy left.
+3. Otherwise fail with STG-041 and change nothing.
+
+DICT is not rebuilt: UUIDs and ident names exist only there. A damaged DICT is not
+repairable by this operation (STG-036 / STG-041); restore from backup.
+
+**Writing.** Like `save()` (§8.3), with bulk builds instead of copy-on-write inserts:
+
+1. Encode pending facts on top of `M`'s dictionary (new ids, new long values), as `save()`.
+2. Stream the source, re-encode each entry as a `KeyFact`, and produce keys for all four
+   indexes. Merge the pending index entries. Sort each list and `build_btree` it.
+3. `cow_insert` the new DICT entries into `M`'s DICT.
+4. New free list: `2..next_append` minus everything the new meta reaches (the four new
+   trees, DICT nodes, value pages through DICT 0x06). This re-derives the list from
+   scratch, so a leaked or wrong free list is repaired too. Chain pages are appended.
+5. Sync, write meta `g+1` to the inactive slot, sync. Delete the WAL as a checkpoint does.
+
+**Crash safety (§8.1 invariant).** Pages for steps 1–3 come from `M`'s free list only if
+it reads cleanly and is disjoint from every page that the DICT tree, the value pages and
+the source tree use; otherwise every page is appended. Either way nothing the old meta
+needs to reopen is overwritten before the commit. A crash reopens at `g` plus the WAL.
+
+**Cost.** O(N) time. Memory O(N) for the four key lists, as the v7 migration already
+does. An external sort is not worth the code for a repair operation. The file can grow by
+one copy of the indexes; those pages return to the free list at commit and are reused.
+
+## 5. Errors
+
+New codes, never recycled; `docs/ERROR_REFERENCE.md` updated:
+
+- **STG-038** `Index {} disagrees with the committed facts: {}`
+- **STG-039** `Tree {} is malformed: {}`
+- **STG-040** `Dictionary is inconsistent: {}`
+- **STG-041** `Cannot rebuild indexes: {}`
+
+STG-035 (free list) and STG-036 (dictionary entry missing) gain the verify scenarios.
+
+## 6. Testing
+
+- Clean files of mixed facts (strings, long strings, refs, keywords, retractions,
+  several checkpoints) verify with no problems; `facts` and `pages` are exact.
+- Each check fires on a targeted damage, built with page-level helpers: a leaf whose
+  entries are removed and resealed (C4/C5 for that index only), a dropped VAET entry,
+  swapped keys (C2), a node linked from two trees (C1), a leaked page and a free id that
+  is still referenced (C10), a deleted DICT entry (C7), a flipped bit (C1 / STG-029).
+- Rebuild: after each damage above that leaves a source, `rebuild_indexes` succeeds,
+  `verify` is clean, and queries return the model's facts. Pending facts and WAL entries
+  made before the rebuild survive it and the WAL is gone.
+- Source choice: EAVT damaged → AEVT; EAVT and AEVT disagree with AVET agreeing with one;
+  all three disagree → STG-041 with the file unchanged.
+- Crash at every write and sync of a rebuild (FaultInjectingBackend): reopen gives
+  either the old or the rebuilt state, never a loss.
+- Space accounting (`assert_space_accounted`) holds after every rebuild.
+
+## 7. Philosophy
+
+Aligned: reliability over features, single file, no format change, no dependency, no
+configuration. Two methods, like SQLite's `integrity_check` and `REINDEX`.
+
+## 8. Out of scope
+
+- Recovering at generation `g` after STG-033 (§4.1.1): an open option, separate issue.
+- Rebuilding DICT, vacuum, salvage of individual pages.
+- Browser (`BrowserDb`) and binding exposure: follow-ups.