From a5edf03a83e0940216cea4d1cb297f62f492bd71 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 13 Oct 2026 19:19:09 +0530 Subject: [PATCH 1/4] docs(plan): #543 snapshots and page quarantine plan Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- ...2026-10-11-543-snapshots-and-quarantine.md | 150 ++++++++++++++++++ 1 file changed, 150 insertions(+) create mode 100644 docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md diff --git a/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md b/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md new file mode 100644 index 0000000000..4127d21988 --- /dev/null +++ b/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md @@ -0,0 +1,150 @@ +# Snapshots and page quarantine (#543) — Plan + +Spec: `docs/superpowers/specs/2026-10-11-streaming-engine-design.md` §4 (#473, part 1 of 9). +Branch `feat/543-snapshots` → `v3`, one PR. No closing keyword for #473, #554 or #555. + +## Already done + +- `WriteTransaction::commit`, `execute` and WAL replay append a transaction with one + `load_facts` call (#554, PR #556). Spec §4.1's first rule holds; only the checkpoint + publish is left. +- Every lookup of one query reads under one `FactData` lock (#555, PR #557). +- `tests/snapshot_atomicity_test.rs` is on `v3`; `checkpoint_never_shows_a_fact_twice` + is the one test still `#[ignore]`d for #543. + +## Design decisions not fixed by the spec + +1. **Where pins live.** A new `src/storage/pins.rs` holds `Pins` (behind + `Arc>`): `pinned: BTreeMap` (generation → open snapshots) and + `quarantine: BTreeMap>` (generation `g` → ids its checkpoint freed). + `FactStorage` owns the `Arc` (it replaces `log_pins`) because snapshots are + taken there; `PersistentFactStorage` reaches it through `storage()`. Works for + in-memory databases too (they never pin: no committed reader). +2. **Pin under the `FactData` lock.** A snapshot reads `committed`, `generation` and + the pending length and takes its pin while holding `FactData`'s read lock. A + checkpoint publishes (new reader, new generation, new `PendingStore`, quarantine + entry) under `FactData`'s write lock. So a pin is always on the active generation + at the moment it is taken, and a quarantine entry is never discarded before a pin + that needs it exists. Lock order: `FactData` → `Pins`; `Pins` alone for + `in_force()` and pin release. No cycle. +3. **In-force set is read once per checkpoint.** `save()` / `rebuild_indexes()` call + `pins.in_force()` before allocating. Pins taken during the checkpoint are on the + active generation, which no existing entry needs and which the entry this + checkpoint creates already covers (its ids are listed free, not handed out, in this + generation). Pins released meanwhile only shrink the set, so the stale copy is a + safe superset. +4. **Entry discard.** On publish of generation `g`: if no generation below `g` is + pinned, the entry is dropped at once. On pin release: drop entries with + `g ≤ lowest pinned` (all, when nothing is pinned). +5. **`Snapshot` type.** `src/graph/storage.rs` gains + `#[derive(Clone)] pub(crate) struct Snapshot { committed, pin: Option>, pending: Arc, pending_len, now }`. + It carries the read methods (`live_facts_of_scans`, `all_facts`, `facts_as_of`, + `pending_range`). `FactStorage`'s read methods become `self.snapshot()?.…`, so + every existing caller and test keeps working and each call is whole. +6. **Executor.** `DatalogExecutor` gets `snapshot: Option`. + `Minigraf::read_executor` and `PreparedQuery::query` take one snapshot and pass it; + `filter_facts_for_query`, `live_source_facts` and `read_now` read from it (the + overlay floor still applies). Writes keep using `FactStorage`. The executor is + unchanged otherwise. +7. **Cursor.** `Cursor` gets a private `_snapshot: Option` (`from_result` + unchanged for `BrowserDb`'s path, a new `from_result_with(result, snapshot)` for the + rest). The answer is still computed at open, so holding the pin buys nothing until + #544; it is held now so the structure and the file-growth behaviour land and are + tested with this sub-issue. Decided 2026-10-13: keep it (not dropped until #544). + +## Steps + +### 1. `PendingStore` and the one-lock publish +- Move `facts`, `pending_keys`, `pending_indexes` into `struct PendingStore` with its + own `RwLock`; `FactData { committed, generation: u64, pending: Arc }`. +- Appends (`transact_batch`, `retract`, `load_fact(s)`) hold `FactData`'s read lock + and the pending write lock, so no append can land in a store after it is swapped + out. +- Replace `post_checkpoint_clear` + `set_committed_reader` on the checkpoint path with + `FactStorage::publish(reader, generation, quarantine_ids)`: one `FactData` write + lock sets `committed`, `generation`, a fresh `PendingStore`, and records the entry. +- `PersistentFactStorage::activate` splits: build the reader; open/migration call + `set_committed(reader, generation)`; `save` and `rebuild_indexes` call `publish`. +- Un-ignore `checkpoint_never_shows_a_fact_twice`; run it in a loop (it is a race + test) before and after to see it fail, then pass. + +### 2. `Pins` and `GenerationPin` +- `pins.rs` per decision 1, 4. `GenerationPin` is RAII (release on drop). +- Unit tests: entry in force while a lower generation is pinned; dropped when the pin + goes; dropped at once with no pin; two pins on different generations release in + either order. + +### 3. `PageAllocator` skips ids in force +- `PageAllocator::with_quarantine(HashSet)`; `alloc` moves a popped id in the set + to `skipped` and continues; `finish_free_list` lists `skipped` with the other unused + ids. `new` filters its list the same way. +- Unit tests in `page.rs`: skipped ids are never handed out, appear in the new list, + and the list's count matches. + +### 4. Checkpoint and rebuild record quarantine +- `save()`: allocator with `pins.in_force()`; publish with `freed`. +- `rebuild_indexes()`: drop ids in force from `pool`; entry = old referenced pages + (`keep`) minus `reached`; publish. +- Remove `refuse_while_logs_open` and the `log_pins() == 0` conditions in `execute` + and `WriteTransaction::commit` (`db.rs:764`, `db.rs:1598`). +- `PFS` tests (`MemoryBackend`): pin generation `g`, run checkpoints that free and + would reuse its pages (assert by page id), read the pinned reader after each and + compare with its facts at open; drop the pin, next checkpoint reuses the ids; + `verify()` clean throughout; same with `rebuild_indexes` (file grows by the index + size, then reuse). `assert_space_accounted` holds with quarantined ids. + +### 5. Snapshots for queries and cursors +- `Snapshot` (decision 5), `FactStorage::snapshot()`, executor (decision 6), cursor + (decision 7), `PreparedQuery::query`. +- Test: a cursor open across writes and page-freeing checkpoints returns its answer; + the pin holds pages (no reuse) until the cursor is dropped. + +### 6. Fact log +- `FactLog` holds a `Snapshot` instead of `LogPin` + `FactStorage` + `pending_end`; + pending reads go to `snapshot.pending_range`. `Minigraf::fact_log` no longer takes + `write_lock`. Remove `LogPin`, `pin_log`, `log_pins`, `log_snapshot`. +- `tests/fact_log_test.rs`: `checkpoint_and_rebuild_are_api_013_while_a_log_is_open` + becomes "checkpoint and rebuild proceed while a log is open, and the log still + returns its snapshot". Add: log opened during a concurrent writer + checkpointer + sees whole transactions only; in-memory log opens while transacting. +- Update rustdoc on `fact_log`, the `fact_log.rs` module doc and `FactLog` doc. + +### 7. `API-013` deprecated +- `error.rs`: `#[allow(dead_code)]` with a comment, as for STG-003/004; keep the + registry entries. `docs/ERROR_REFERENCE.md`: "(deprecated)" in the table, the + deprecation note under the heading and in the deprecated-codes paragraph. +- `docs/DURABILITY.md` lines 125 and 188: logs no longer defer checkpoints; a + long-lived log or cursor grows the file by the pages checkpoints replace meanwhile. + +### 8. `BrowserDb` +- `take_released` returns `listed` minus ids in force and keeps the rest in a + `withheld` list, returned at a later commit once out of force. Pure helper + `split_released(listed, withheld, in_force)` with native unit tests; one + `#[wasm_bindgen_test]`: a browser cursor/log held across two commits still reads. + +### 9. Crash with an open snapshot +- `persistent_facts` crash test: open a pin, run checkpoints, crash at every write + point (existing `crash_at_every_point_in_save` helper), reopen: every fact present, + `verify()` clean, quarantined ids reused by the next checkpoint (no pins after + reopen). + +### 10. Docs and checks +- `CHANGELOG.md` (Unreleased, v3.0.0): fact logs no longer defer checkpoints, API-013 + deprecated, readers and checkpoints never see a half-published checkpoint (#554/#555 + v3 side), file growth with long-lived readers. +- `CLAUDE.md` (fact_log line, `pins.rs` in the module list, test count), + `ROADMAP.md` line 84, `docs/TEST_COVERAGE.md`, `README.md` if it mentions API-013. +- Docs site PR (`../minigraf-docs`): `content/database-tools.md:46` and + `content/architecture.md:443` wrapped in `@until v3.0.0` / `@since v3.0.0`. +- #421 entries for #554/#555: note the v3 side now fully fixed (issues stay open). +- `cargo fmt`, `cargo clippy` (and the wasm targets), `cargo test`; run + `snapshot_atomicity_test` repeatedly; #394 envelope at 100K/1M on an idle machine + (point queries must not regress: snapshot adds an `Arc` clone and a pin lock per + query). +- Codex review (`codex exec -s read-only`, background, `-o`), then PR to `v3`. + +## Bindings + +No public API change and no new error code (API-013 stays registered), so no binding +cascade. Binding docs that mention API-013 for `fact_log` (#465/#462 work) get a +follow-up note once those land. From e65d65cc39390222c143e59c2843057e65ece289 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 13 Oct 2026 20:00:42 +0530 Subject: [PATCH 2/4] feat(storage): swap the pending store on checkpoint, publish under one lock (#543) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Pending facts, their duplicate-check keys and indexes move into a PendingStore behind its own lock. FactData holds the committed reader, its generation and the active pending store. A checkpoint calls FactStorage::publish, which sets all three under one write lock instead of set_committed_reader followed by post_checkpoint_clear, so no read sees a checkpointed fact twice (#473 spec §4.1). The old store is replaced, not cleared. Appends hold FactData's read lock while writing the store. Un-ignores checkpoint_never_shows_a_fact_twice. The race did not reproduce in 34 runs before the change; the test stays as a regression guard. Part of #473 (streaming engine 1/9). Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- src/graph/storage.rs | 325 ++++++++++++++++++------------- src/storage/persistent_facts.rs | 27 +-- tests/snapshot_atomicity_test.rs | 1 - 3 files changed, 207 insertions(+), 146 deletions(-) diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 2f78411df8..2418c1d014 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -9,7 +9,7 @@ use std::collections::HashSet; use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering}; use std::sync::{Arc, RwLock}; -/// Compact key for O(1) duplicate detection in `FactData::pending_keys`. +/// Compact key for O(1) duplicate detection in `PendingStore::keys`. /// /// Mirrors the equality predicate used by `load_fact`: /// (entity, attribute, encoded_value, valid_from, valid_to, tx_count, asserted). @@ -33,21 +33,68 @@ fn pending_key(f: &Fact) -> PendingKey { // Datalog Fact Storage (Phase 3+) // ============================================================================ -/// Private container that co-locates the fact list and all four indexes under -/// a single `RwLock`. This ensures facts and indexes are always updated together -/// without needing a second lock. -struct FactData { +/// The facts written since the last checkpoint, with their duplicate-check set +/// and indexes, always updated together under one lock. +/// +/// Append-only while it is the active store: a checkpoint publishes a new +/// empty one ([`FactStorage::publish`]) instead of clearing it, so a reader +/// holding this one keeps its positions. +struct PendingStore { facts: Vec, /// O(1) duplicate-detection set for `load_fact`. /// /// Maintained in sync with `facts` by every method that appends to `facts`. /// Replaces the O(n) linear scan that made `load_fact` O(n²) for large /// fact sets (e.g. 1M-fact benchmark setup). - pending_keys: HashSet, - pending_indexes: Indexes, + keys: HashSet, + indexes: Indexes, +} + +impl PendingStore { + fn new() -> Arc> { + Arc::new(RwLock::new(PendingStore { + facts: Vec::new(), + keys: HashSet::new(), + indexes: Indexes::new(), + })) + } + + /// Append `fact` unless it is already here; returns whether it was added. + fn push(&mut self, fact: Fact) -> bool { + if !self.keys.insert(pending_key(&fact)) { + return false; + } + self.indexes.insert(&fact, self.facts.len()); + self.facts.push(fact); + true + } + + /// Append `facts` without the duplicate check (fresh writes: each has a + /// new tx_count, so none can repeat a stored one). + fn extend(&mut self, facts: Vec) { + let base = self.facts.len(); + for (i, fact) in facts.iter().enumerate() { + self.keys.insert(pending_key(fact)); + self.indexes.insert(fact, base + i); + } + self.facts.extend(facts); + } +} + +/// The state a read sees: the committed generation and the pending store +/// that follows it. A checkpoint replaces all three under this lock's write +/// side (#473 spec §4.1), so no read sees the new committed facts together +/// with the pending facts they came from. +/// +/// Lock order: `FactData`, then its `pending`. Appends hold `FactData`'s read +/// side while they write `pending`, so none lands in a store being replaced. +struct FactData { /// Reads committed (checkpointed) facts through the on-disk covering indexes. /// None for in-memory databases. Set after every open, migration and checkpoint. committed: Option>, + /// Generation of `committed`; 0 while there is none. + generation: u64, + pending: Arc>, } /// In-memory storage for Datalog facts with transaction support @@ -114,10 +161,9 @@ impl FactStorage { pub(crate) fn new() -> Self { FactStorage { data: Arc::new(RwLock::new(FactData { - facts: Vec::new(), - pending_keys: HashSet::new(), - pending_indexes: Indexes::new(), committed: None, + generation: 0, + pending: PendingStore::new(), })), tx_counter: Arc::new(AtomicU64::new(0)), log_pins: Arc::new(AtomicUsize::new(0)), @@ -165,16 +211,7 @@ impl FactStorage { fact.tx_count = tx_count; } - let mut d = self - .data - .write() - .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let base = d.facts.len(); - for (i, fact) in facts.iter().enumerate() { - d.pending_keys.insert(pending_key(fact)); - d.pending_indexes.insert(fact, base + i); - } - d.facts.extend(facts); + self.write_pending(|p| p.extend(facts))?; Ok(tx_id) } @@ -223,16 +260,7 @@ impl FactStorage { fact.tx_count = tx_count; } - let mut d = self - .data - .write() - .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let base = d.facts.len(); - for (i, fact) in facts.iter().enumerate() { - d.pending_keys.insert(pending_key(fact)); - d.pending_indexes.insert(fact, base + i); - } - d.facts.extend(facts); + self.write_pending(|p| p.extend(facts))?; Ok((tx_id, tx_count)) } @@ -267,16 +295,7 @@ impl FactStorage { }) .collect(); - let mut d = self - .data - .write() - .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let base = d.facts.len(); - for (i, fact) in retractions.iter().enumerate() { - d.pending_keys.insert(pending_key(fact)); - d.pending_indexes.insert(fact, base + i); - } - d.facts.extend(retractions); + self.write_pending(|p| p.extend(retractions))?; Ok((tx_id, tx_count)) } @@ -290,23 +309,7 @@ impl FactStorage { /// Checks for duplicate facts before loading (based on entity, attribute, value, /// valid_from, valid_to, tx_count, and asserted). pub(crate) fn load_fact(&self, fact: Fact) -> Result { - let mut d = self - .data - .write() - .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - - // O(1) duplicate check via the pending_keys HashSet. - // Previously this was an O(n) linear scan over d.facts, causing O(n²) - // total complexity when loading n facts (e.g. 1M-fact benchmarks). - let key = pending_key(&fact); - if !d.pending_keys.insert(key) { - return Ok(false); // Already exists, not loaded - } - - let pos = d.facts.len(); - d.pending_indexes.insert(&fact, pos); - d.facts.push(fact); - Ok(true) + self.write_pending(|p| p.push(fact)) } /// Insert facts with their tx_id and tx_count preserved, all under one @@ -315,21 +318,26 @@ impl FactStorage { /// Commits and WAL replay use this for a whole transaction. Duplicates are /// skipped as in [`Self::load_fact`]. Returns how many facts were loaded. pub(crate) fn load_facts(&self, facts: impl IntoIterator) -> Result { - let mut d = self + self.write_pending(|p| { + facts.into_iter().fold( + 0usize, + |n, fact| if p.push(fact) { n.saturating_add(1) } else { n }, + ) + }) + } + + /// Run `f` on the active pending store under its write lock, with + /// `FactData`'s read lock held so no checkpoint replaces the store meanwhile. + fn write_pending(&self, f: impl FnOnce(&mut PendingStore) -> R) -> Result { + let d = self .data - .write() + .read() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let mut loaded = 0usize; - for fact in facts { - if !d.pending_keys.insert(pending_key(&fact)) { - continue; - } - let pos = d.facts.len(); - d.pending_indexes.insert(&fact, pos); - d.facts.push(fact); - loaded = loaded.saturating_add(1); - } - Ok(loaded) + let mut p = d + .pending + .write() + .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; + Ok(f(&mut p)) } /// Raise tx_counter to max(tx_count) across all loaded facts. @@ -343,7 +351,11 @@ impl FactStorage { .data .read() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let max = d.facts.iter().map(|f| f.tx_count).max().unwrap_or(0); + let p = d + .pending + .read() + .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; + let max = p.facts.iter().map(|f| f.tx_count).max().unwrap_or(0); self.tx_counter.fetch_max(max, Ordering::SeqCst); Ok(()) } @@ -381,7 +393,11 @@ impl FactStorage { all.extend(reader.all_facts()?); } // Then pending facts (post-checkpoint, in memory) - all.extend(d.facts.iter().cloned()); + let p = d + .pending + .read() + .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; + all.extend(p.facts.iter().cloned()); Ok(all) } @@ -406,7 +422,8 @@ impl FactStorage { /// Return the pending (uncommitted) facts held in memory. pub(crate) fn get_pending_facts(&self) -> Vec { let d = self.data.read().unwrap_or_else(|e| e.into_inner()); - d.facts.clone() + let p = d.pending.read().unwrap_or_else(|e| e.into_inner()); + p.facts.clone() } /// The committed reader and the number of pending facts, read together. @@ -420,7 +437,11 @@ impl FactStorage { .data .read() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - Ok((d.committed.clone(), d.facts.len())) + let p = d + .pending + .read() + .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; + Ok((d.committed.clone(), p.facts.len())) } /// Clones of the pending facts at positions `from..to` (clamped). @@ -429,8 +450,12 @@ impl FactStorage { .data .read() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let to = to.min(d.facts.len()); - Ok(d.facts.get(from.min(to)..to).unwrap_or(&[]).to_vec()) + let p = d + .pending + .read() + .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; + let to = to.min(p.facts.len()); + Ok(p.facts.get(from.min(to)..to).unwrap_or(&[]).to_vec()) } /// Register an open fact log; checkpoints are refused until it is dropped. @@ -444,31 +469,54 @@ impl FactStorage { self.log_pins.load(Ordering::SeqCst) } - /// Clear pending facts and pending indexes after a successful checkpoint. - pub(crate) fn post_checkpoint_clear(&self) { - let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); - d.facts.clear(); - d.pending_keys.clear(); - d.pending_indexes = Indexes::new(); - } - /// Set the tx_counter to `max` (used on load to restore from persisted state). pub(crate) fn restore_tx_counter_from(&self, max: u64) { self.tx_counter.store(max, Ordering::SeqCst); } - /// Set the committed reader. Called by `PersistentFactStorage` after each - /// open, migration and checkpoint. - pub(crate) fn set_committed_reader(&self, reader: Arc) { + /// Set the committed reader of generation `generation`, keeping the + /// pending store. Called by `PersistentFactStorage` after open and + /// migration, where the pending facts are not in `reader`. + pub(crate) fn set_committed( + &self, + reader: Arc, + generation: u64, + ) { + let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); + d.committed = Some(reader); + d.generation = generation; + } + + /// Publish a checkpoint: `reader` (generation `generation`) now holds every + /// pending fact, and an empty pending store replaces the old one, all under + /// one write lock, so no read sees a checkpointed fact twice (#473 spec + /// §4.1). The old store is left intact for readers that hold it. + pub(crate) fn publish( + &self, + reader: Arc, + generation: u64, + ) { let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); d.committed = Some(reader); + d.generation = generation; + d.pending = PendingStore::new(); + } + + /// Generation of the committed reader; 0 while there is none. + #[cfg(test)] + pub(crate) fn generation(&self) -> u64 { + self.data + .read() + .unwrap_or_else(|e| e.into_inner()) + .generation } /// Returns (eavt_len, aevt_len) for the pending indexes (tests). #[cfg(test)] pub(crate) fn pending_index_counts(&self) -> (usize, usize) { let d = self.data.read().unwrap_or_else(|e| e.into_inner()); - (d.pending_indexes.eavt.len(), d.pending_indexes.aevt.len()) + let p = d.pending.read().unwrap_or_else(|e| e.into_inner()); + (p.indexes.eavt.len(), p.indexes.aevt.len()) } } @@ -666,9 +714,9 @@ pub(crate) fn check_valid_windows(facts: &[Fact], tx_id: TxId) -> Result<()> { Ok(()) } -/// The pending fact at `pos`, as indexed by `FactData::pending_indexes`. -fn pending_fact(d: &FactData, pos: usize) -> Result { - d.facts +/// The pending fact at `pos`, as indexed by `PendingStore::indexes`. +fn pending_fact(p: &PendingStore, pos: usize) -> Result { + p.facts .get(pos) .cloned() .ok_or_else(|| err_coded!(ErrorCode::Int045, pos)) @@ -701,18 +749,20 @@ impl FactStorage { as_of: Option, ) -> Result> { let d = self.data.read().unwrap_or_else(|e| e.into_inner()); + let p = d.pending.read().unwrap_or_else(|e| e.into_inner()); let mut facts = Vec::new(); for &scan in scans { - live_facts_of_scan(&d, scan, as_of, &mut facts)?; + live_facts_of_scan(&d, &p, scan, as_of, &mut facts)?; } Ok(facts) } } /// The pending facts of `scan` up to `as_of`, then its committed live facts, -/// appended to `facts`. The caller holds `d`'s lock for the whole read. +/// appended to `facts`. The caller holds `d`'s and `p`'s locks for the whole read. fn live_facts_of_scan( d: &FactData, + p: &PendingStore, scan: crate::storage::Scan<'_>, as_of: Option, facts: &mut Vec, @@ -720,7 +770,7 @@ fn live_facts_of_scan( use crate::storage::Scan; use crate::storage::index::{AevtKey, EavtKey}; let mut push = |pos: usize| -> Result<()> { - let f = pending_fact(d, pos)?; + let f = pending_fact(p, pos)?; if as_of.is_none_or(|n| f.tx_count <= n) { facts.push(f); } @@ -728,16 +778,12 @@ fn live_facts_of_scan( }; match scan { Scan::All => { - for pos in 0..d.facts.len() { + for pos in 0..p.facts.len() { push(pos)?; } } Scan::Entity(entity) => { - for (key, &pos) in d - .pending_indexes - .eavt - .range(EavtKey::entity_start(*entity)..) - { + for (key, &pos) in p.indexes.eavt.range(EavtKey::entity_start(*entity)..) { if key.entity != *entity { break; } @@ -746,7 +792,7 @@ fn live_facts_of_scan( } Scan::EntityAttribute(entity, attribute) => { let start = EavtKey::entity_attribute_start(*entity, attribute); - for (key, &pos) in d.pending_indexes.eavt.range(start..) { + for (key, &pos) in p.indexes.eavt.range(start..) { if key.entity != *entity || key.attribute != attribute { break; } @@ -754,11 +800,7 @@ fn live_facts_of_scan( } } Scan::Attribute(attribute) => { - for (key, &pos) in d - .pending_indexes - .aevt - .range(AevtKey::attribute_start(attribute)..) - { + for (key, &pos) in p.indexes.aevt.range(AevtKey::attribute_start(attribute)..) { if key.attribute != attribute { break; } @@ -779,16 +821,13 @@ impl FactStorage { pub(crate) fn get_facts_by_entity(&self, entity_id: &EntityId) -> Result> { use crate::storage::index::EavtKey; let d = self.data.read().unwrap_or_else(|e| e.into_inner()); + let p = d.pending.read().unwrap_or_else(|e| e.into_inner()); let mut facts = Vec::new(); - for (key, &pos) in d - .pending_indexes - .eavt - .range(EavtKey::entity_start(*entity_id)..) - { + for (key, &pos) in p.indexes.eavt.range(EavtKey::entity_start(*entity_id)..) { if key.entity != *entity_id { break; } - facts.push(pending_fact(&d, pos)?); + facts.push(pending_fact(&p, pos)?); } if let Some(reader) = &d.committed { facts.extend(reader.facts_for_entity(entity_id)?); @@ -810,13 +849,14 @@ impl FactStorage { ) -> Result> { use crate::storage::index::EavtKey; let d = self.data.read().unwrap_or_else(|e| e.into_inner()); + let p = d.pending.read().unwrap_or_else(|e| e.into_inner()); let start = EavtKey::entity_attribute_start(*entity_id, attribute); let mut facts = Vec::new(); - for (key, &pos) in d.pending_indexes.eavt.range(start..) { + for (key, &pos) in p.indexes.eavt.range(start..) { if key.entity != *entity_id || key.attribute != *attribute { break; } - facts.push(pending_fact(&d, pos)?); + facts.push(pending_fact(&p, pos)?); } if let Some(reader) = &d.committed { facts.extend(reader.facts_for_entity_attribute(entity_id, attribute)?); @@ -830,16 +870,13 @@ impl FactStorage { pub(crate) fn get_facts_by_attribute(&self, attribute: &Attribute) -> Result> { use crate::storage::index::AevtKey; let d = self.data.read().unwrap_or_else(|e| e.into_inner()); + let p = d.pending.read().unwrap_or_else(|e| e.into_inner()); let mut facts = Vec::new(); - for (key, &pos) in d - .pending_indexes - .aevt - .range(AevtKey::attribute_start(attribute)..) - { + for (key, &pos) in p.indexes.aevt.range(AevtKey::attribute_start(attribute)..) { if key.attribute != *attribute { break; } - facts.push(pending_fact(&d, pos)?); + facts.push(pending_fact(&p, pos)?); } if let Some(reader) = &d.committed { facts.extend(reader.facts_for_attribute(attribute)?); @@ -899,7 +936,7 @@ impl FactStorage { .and_then(|r| r.all_facts().ok()) .map(|v| v.len()) .unwrap_or(0); - committed_count + d.facts.len() + committed_count + d.pending.read().unwrap().facts.len() } /// Get the count of currently asserted facts. Test use only. @@ -1604,7 +1641,7 @@ mod tests { ), ]; let storage = FactStorage::new(); - storage.set_committed_reader(std::sync::Arc::new(MockReader(committed))); + storage.set_committed(std::sync::Arc::new(MockReader(committed)), 1); storage .transact(vec![(e, ":a".to_string(), Value::Integer(4))], None) .unwrap(); @@ -1632,7 +1669,7 @@ mod tests { } #[test] - fn test_post_checkpoint_clear_clears_indexes() { + fn publish_replaces_pending_store_and_reader_together() { use uuid::Uuid; let storage = FactStorage::new(); let e = Uuid::new_v4(); @@ -1642,23 +1679,45 @@ mod tests { None, ) .unwrap(); - assert_eq!( storage.pending_index_counts().0, 1, "one pending EAVT entry" ); - storage.post_checkpoint_clear(); - assert_eq!( - storage.pending_index_counts().0, - 0, - "pending indexes cleared" - ); + let checkpointed = storage.get_pending_facts(); + + storage.publish(std::sync::Arc::new(MockReader(checkpointed)), 2); + assert_eq!(storage.generation(), 2); assert_eq!( - storage.get_pending_facts().len(), - 0, - "pending facts cleared" + storage.pending_index_counts(), + (0, 0), + "new pending indexes" ); + assert!(storage.get_pending_facts().is_empty(), "new pending store"); + assert_eq!(storage.get_all_facts().unwrap().len(), 1, "fact read once"); + + // Appends after the publish land in the new store. + storage + .transact(vec![(e, ":age".to_string(), Value::Integer(30))], None) + .unwrap(); + assert_eq!(storage.get_pending_facts().len(), 1); + assert_eq!(storage.get_all_facts().unwrap().len(), 2); + } + + #[test] + fn set_committed_keeps_pending_store() { + use uuid::Uuid; + let storage = FactStorage::new(); + assert_eq!(storage.generation(), 0, "no committed reader yet"); + storage + .transact( + vec![(Uuid::new_v4(), ":a".to_string(), Value::Integer(1))], + None, + ) + .unwrap(); + storage.set_committed(std::sync::Arc::new(MockReader(Vec::new())), 1); + assert_eq!(storage.generation(), 1); + assert_eq!(storage.get_pending_facts().len(), 1, "pending kept"); } #[test] diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index d6f157c5ca..ad245a4d7b 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -94,7 +94,8 @@ impl PersistentFactStorage { } Opened::LegacyV7(h) => pfs.migrate_v7(&h)?, }; - pfs.activate(meta); + let reader = pfs.activate(meta); + pfs.storage.set_committed(reader, meta.generation); pfs.storage .restore_tx_counter_from(meta.last_checkpointed_tx_count); Ok(pfs) @@ -124,7 +125,8 @@ impl PersistentFactStorage { } Opened::LegacyV7(h) => pfs.load_v7_in_memory(&h)?, }; - pfs.activate(meta); + let reader = pfs.activate(meta); + pfs.storage.set_committed(reader, meta.generation); pfs.storage .restore_tx_counter_from(meta.last_checkpointed_tx_count); Ok(pfs) @@ -274,16 +276,17 @@ impl PersistentFactStorage { Ok(meta) } - /// Make `meta` the active state: cache bound and committed reader. - fn activate(&mut self, meta: MetaPage) { + /// Make `meta` the active state (cache bound) and return its committed + /// reader. The caller hands the reader to `FactStorage`: `set_committed` + /// after open and migration, `publish` after a checkpoint. + fn activate(&mut self, meta: MetaPage) -> Arc { self.meta = meta; self.page_cache.set_generation_bound(meta.generation); - let reader: Arc = Arc::new(OnDiskReader::new( + Arc::new(OnDiskReader::new( self.backend.clone(), self.page_cache.clone(), &meta, - )); - self.storage.set_committed_reader(reader); + )) } /// Migrate a format v7 file to v8 (spec §9). @@ -482,15 +485,15 @@ impl PersistentFactStorage { self.dirty = false; self.failed = false; - self.activate(new_meta); + let reader = self.activate(new_meta); #[cfg(all(target_arch = "wasm32", feature = "browser"))] { self.released = listed; } #[cfg(not(all(target_arch = "wasm32", feature = "browser")))] drop(listed); - // Clear pending — all data now on disk - self.storage.post_checkpoint_clear(); + // All pending facts are now in `reader`. + self.storage.publish(reader, new_meta.generation); Ok(()) } @@ -682,8 +685,8 @@ impl PersistentFactStorage { self.dirty = false; self.failed = false; - self.activate(new_meta); - self.storage.post_checkpoint_clear(); + let reader = self.activate(new_meta); + self.storage.publish(reader, new_meta.generation); Ok(()) } diff --git a/tests/snapshot_atomicity_test.rs b/tests/snapshot_atomicity_test.rs index 22cb2ada55..bbc17e9d1e 100644 --- a/tests/snapshot_atomicity_test.rs +++ b/tests/snapshot_atomicity_test.rs @@ -126,7 +126,6 @@ fn execute_transact_is_seen_whole_on_file() { /// facts twice. Every fact here has its own entity, so a repeated row is a /// fact read twice. #[test] -#[ignore = "reproducer: fails on v3 today; fixed by #473 sub-issue #543"] fn checkpoint_never_shows_a_fact_twice() { let dir = tempfile::tempdir().unwrap(); let opts = OpenOptions::default().wal_checkpoint_threshold(usize::MAX); From 7c836873a49ff415565d04404954094d6a9b40e3 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 13 Oct 2026 20:03:43 +0530 Subject: [PATCH 3/4] docs: test counts after the one-lock publish; #543 plan split into three PRs Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 5 ++--- .../plans/2026-10-11-543-snapshots-and-quarantine.md | 12 +++++++++++- 4 files changed, 15 insertions(+), 6 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index cfa13bba8d..4d5070f972 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -201,7 +201,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1444 tests** (1433 passing, 11 ignored; unit + integration + doc). +**1445 tests** (1435 passing, 10 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 e85f6ad5da..118d91fad1 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1444 tests +cargo test # run 1445 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 5a7c185902..85e6fe172e 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-13 with `cargo test --quiet` -**Result**: 1,433 passing tests and 11 ignored tests (1,444 total) +**Result**: 1,435 passing tests and 10 ignored tests (1,445 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). @@ -19,13 +19,12 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value ### Ignored Tests -The eleven ignored tests are intentionally excluded from a normal local run: +The ten ignored tests are intentionally excluded from a normal local run: - Six rustdoc examples that reference internal types and cannot compile as standalone examples. - One high-contention concurrency stress test intended for scheduled runs. - One long-haul smoke test intended for scheduled runs. - One soak test at 10M facts (`soak`), run weekly by `.github/workflows/soak.yml` (#392); `soak_short` runs the same driver at 20K facts in the normal suite. -- One snapshot test in `tests/snapshot_atomicity_test.rs` checking that a checkpoint never shows a fact twice; it has not failed, and guards the checkpoint change planned in #543. - One size test at 1.15M facts (`size_per_fact_in_433_shape_1m`), run by the nightly smoke workflow. ### Reproducing diff --git a/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md b/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md index 4127d21988..45d24aff27 100644 --- a/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md +++ b/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md @@ -1,7 +1,17 @@ # Snapshots and page quarantine (#543) — Plan Spec: `docs/superpowers/specs/2026-10-11-streaming-engine-design.md` §4 (#473, part 1 of 9). -Branch `feat/543-snapshots` → `v3`, one PR. No closing keyword for #473, #554 or #555. +Three PRs to `v3` (split agreed 2026-10-13; the first draft had one), each leaving +`v3` with no unused code. No closing keyword for #473, #543, #554 or #555. + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1: `PendingStore` and the one-lock publish | `feat/543-snapshots` | +| 2 | 2, 3, 4, 6, 7: pins, allocator quarantine, checkpoint/rebuild entries, fact log on the pin, `API-013` deprecated | `feat/543-pins` | +| 3 | 5, 8, 9, 10: query and cursor snapshots, `BrowserDb`, crash test, docs | `feat/543-snapshots-read` | + +Each PR updates the test counts and `CHANGELOG.md` for what it ships; step 10 holds +the rest of the docs. ## Already done From 9fe46bb49b4920961ebb6b0c00ddecf6f4305eb4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 13 Oct 2026 20:09:42 +0530 Subject: [PATCH 4/4] fix(storage): publish keeps facts appended after the checkpoint read (#543) A checkpoint reads the pending facts, writes them, then publishes. publish now takes how many it wrote and carries any later facts into the new pending store. The database's write lock keeps that range empty today, but FactStorage is cloneable and does not enforce it (Codex review). Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 2 +- src/graph/storage.rs | 50 +++++++++++++++++++++++++++++---- src/storage/persistent_facts.rs | 6 ++-- 5 files changed, 51 insertions(+), 11 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index 4d5070f972..ab39b68b01 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -201,7 +201,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1445 tests** (1435 passing, 10 ignored; unit + integration + doc). +**1446 tests** (1436 passing, 10 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 118d91fad1..aff16e0ae2 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1445 tests +cargo test # run 1446 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 85e6fe172e..166744d800 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-13 with `cargo test --quiet` -**Result**: 1,435 passing tests and 10 ignored tests (1,445 total) +**Result**: 1,436 passing tests and 10 ignored tests (1,446 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 2418c1d014..250ec5f589 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -487,19 +487,33 @@ impl FactStorage { d.generation = generation; } - /// Publish a checkpoint: `reader` (generation `generation`) now holds every - /// pending fact, and an empty pending store replaces the old one, all under - /// one write lock, so no read sees a checkpointed fact twice (#473 spec - /// §4.1). The old store is left intact for readers that hold it. + /// Publish a checkpoint: `reader` (generation `generation`) now holds the + /// first `checkpointed` pending facts, and a new pending store replaces the + /// old one, all under one write lock, so no read sees a checkpointed fact + /// twice (#473 spec §4.1). The old store is left intact for readers that + /// hold it. + /// + /// Facts appended after the checkpoint read the pending store (positions + /// `checkpointed..`) move to the new store, so none is lost. The database's + /// write lock keeps that range empty today; this does not depend on it. pub(crate) fn publish( &self, reader: Arc, generation: u64, + checkpointed: usize, ) { let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); + let pending = PendingStore::new(); + { + let old = d.pending.read().unwrap_or_else(|e| e.into_inner()); + let mut new = pending.write().unwrap_or_else(|e| e.into_inner()); + for fact in old.facts.get(checkpointed..).unwrap_or(&[]) { + new.push(fact.clone()); + } + } d.committed = Some(reader); d.generation = generation; - d.pending = PendingStore::new(); + d.pending = pending; } /// Generation of the committed reader; 0 while there is none. @@ -1686,7 +1700,8 @@ mod tests { ); let checkpointed = storage.get_pending_facts(); - storage.publish(std::sync::Arc::new(MockReader(checkpointed)), 2); + let n = checkpointed.len(); + storage.publish(std::sync::Arc::new(MockReader(checkpointed)), 2, n); assert_eq!(storage.generation(), 2); assert_eq!( storage.pending_index_counts(), @@ -1704,6 +1719,29 @@ mod tests { assert_eq!(storage.get_all_facts().unwrap().len(), 2); } + #[test] + fn publish_keeps_facts_appended_after_the_checkpoint_read() { + use uuid::Uuid; + let storage = FactStorage::new(); + let e = Uuid::new_v4(); + storage + .transact(vec![(e, ":a".to_string(), Value::Integer(1))], None) + .unwrap(); + let checkpointed = storage.get_pending_facts(); + // A write lands after the checkpoint read the pending facts. + storage + .transact(vec![(e, ":a".to_string(), Value::Integer(2))], None) + .unwrap(); + + let n = checkpointed.len(); + storage.publish(std::sync::Arc::new(MockReader(checkpointed)), 2, n); + let pending = storage.get_pending_facts(); + assert_eq!(pending.len(), 1, "late fact carried over"); + assert_eq!(pending[0].value, Value::Integer(2)); + assert_eq!(storage.pending_index_counts(), (1, 1), "and indexed"); + assert_eq!(storage.get_all_facts().unwrap().len(), 2, "each fact once"); + } + #[test] fn set_committed_keeps_pending_store() { use uuid::Uuid; diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index ad245a4d7b..2e137d8e80 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -493,7 +493,8 @@ impl PersistentFactStorage { #[cfg(not(all(target_arch = "wasm32", feature = "browser")))] drop(listed); // All pending facts are now in `reader`. - self.storage.publish(reader, new_meta.generation); + self.storage + .publish(reader, new_meta.generation, pending_facts.len()); Ok(()) } @@ -686,7 +687,8 @@ impl PersistentFactStorage { self.dirty = false; self.failed = false; let reader = self.activate(new_meta); - self.storage.publish(reader, new_meta.generation); + self.storage + .publish(reader, new_meta.generation, pending_facts.len()); Ok(()) }