From 6739a94b98db3ed0d12771b8e14b918a188db8af Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 07:50:42 +0530 Subject: [PATCH 1/2] fix(storage): index pending facts past 65,535 correctly (#445) Each pending fact was indexed with FactRef { page_id: 0, slot_index }, where slot_index is its position in the pending list. The position was a saturating u16, so every fact from position 65,535 on shared one slot and entity lookups and attribute scans silently lost or duplicated facts. This affected in-memory databases and file databases before a checkpoint. slot_index is now a u32, and pending positions are checked rather than saturated. postcard writes u16 and u32 as the same varint, so v7 index pages are byte-for-byte unchanged; a test pins this. Refs #445 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 6 ++ CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +- src/graph/storage.rs | 160 ++++++++++++++++++++++++-------- src/storage/index.rs | 44 ++++++++- src/storage/packed_pages.rs | 13 +-- src/storage/persistent_facts.rs | 4 +- tests/edge_cases_test.rs | 65 +++++++++++++ 9 files changed, 248 insertions(+), 52 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 32c7f56cb..208e39804 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -5,6 +5,12 @@ All notable changes to this project will be documented in this file. The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). +## Unreleased + +### Fixed + +- **Queries returned wrong results with more than 65,535 uncheckpointed facts (#445).** Each fact not yet checkpointed was indexed by its position in memory, stored as a 16-bit number that stopped counting at 65,535. Every later fact was indexed as that same position, so entity-bound queries (`[:e :attr ?v]`) and attribute scans (`[?e :attr ?v]`) silently lost or duplicated facts. This affected in-memory databases with more than 65,535 facts and file databases with more than 65,535 facts written since the last checkpoint. The stored data was always intact, and a checkpoint made file databases correct again. Positions are now 32-bit and checked. Affected releases: v0.7.0 through v2.0.2. The file format is unchanged. + ## v2.0.2 — 2026-09-27 Final planned release on the v2.x line. File format is unchanged (v7). No breaking API changes; one new user-facing error code (API-010). v2.x gets data-integrity and security fixes for 12 months after v3.0.0 ships ([support policy](PHILOSOPHY.md#support-policy)). diff --git a/CLAUDE.md b/CLAUDE.md index ad4acfdfa..2aedaa28d 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1212 tests passing** (1204 passing, 8 ignored; unit + integration + doc). +**1217 tests** (1209 passing, 8 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index 39a84889a..318191365 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1212 tests +cargo test # run 1217 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 70906c7e8..3298a56fe 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-09-27 with `cargo test` -**Result**: 1,204 passing tests and 8 ignored tests (1,212 total) +**Result**: 1,209 passing tests and 8 ignored tests (1,217 total, including the #445 tests added after v2.0.2) -The v2.0.2 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `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 cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). 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). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). +The v2.0.2 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `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 cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). 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). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). After v2.0.2, storage unit tests and two `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, before and after a checkpoint, and that the widened `FactRef` encodes to the same bytes as before (#445). ### Covered Areas diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 82d54d71b..771151e50 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -156,15 +156,10 @@ impl FactStorage { .data .write() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - for (slot, fact) in (u16::try_from(d.facts.len()).unwrap_or(u16::MAX)..).zip(facts.iter()) { + let refs = pending_refs(d.facts.len(), facts.len())?; + for (fact_ref, fact) in refs.into_iter().zip(facts.iter()) { d.pending_keys.insert(pending_key(fact)); - d.pending_indexes.insert( - fact, - FactRef { - page_id: 0, - slot_index: slot, - }, - ); + d.pending_indexes.insert(fact, fact_ref); } d.facts.extend(facts); @@ -215,15 +210,10 @@ impl FactStorage { .data .write() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - for (slot, fact) in (u16::try_from(d.facts.len()).unwrap_or(u16::MAX)..).zip(facts.iter()) { + let refs = pending_refs(d.facts.len(), facts.len())?; + for (fact_ref, fact) in refs.into_iter().zip(facts.iter()) { d.pending_keys.insert(pending_key(fact)); - d.pending_indexes.insert( - fact, - FactRef { - page_id: 0, - slot_index: slot, - }, - ); + d.pending_indexes.insert(fact, fact_ref); } d.facts.extend(facts); @@ -264,17 +254,10 @@ impl FactStorage { .data .write() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - for (slot, fact) in - (u16::try_from(d.facts.len()).unwrap_or(u16::MAX)..).zip(retractions.iter()) - { + let refs = pending_refs(d.facts.len(), retractions.len())?; + for (fact_ref, fact) in refs.into_iter().zip(retractions.iter()) { d.pending_keys.insert(pending_key(fact)); - d.pending_indexes.insert( - fact, - FactRef { - page_id: 0, - slot_index: slot, - }, - ); + d.pending_indexes.insert(fact, fact_ref); } d.facts.extend(retractions); @@ -299,18 +282,14 @@ impl FactStorage { // 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) { + if d.pending_keys.contains(&key) { return Ok(false); // Already exists, not loaded } - - let slot = u16::try_from(d.facts.len()).unwrap_or(u16::MAX); - d.pending_indexes.insert( - &fact, - FactRef { - page_id: 0, - slot_index: slot, - }, - ); + let fact_ref = pending_refs(d.facts.len(), 1)? + .pop() + .ok_or_else(|| err_coded!(ErrorCode::Int045, d.facts.len()))?; + d.pending_keys.insert(key); + d.pending_indexes.insert(&fact, fact_ref); d.facts.push(fact); Ok(true) } @@ -577,6 +556,24 @@ pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { .collect() } +/// `FactRef`s for `count` pending facts appended at position `base`. +/// +/// A pending fact's `slot_index` is its position in `FactData::facts`. Each one is +/// distinct: a position that does not fit `u32` is an error, never a shared slot +/// (#445: a saturating `u16` sent every fact past 65,535 to the same slot). +fn pending_refs(base: usize, count: usize) -> Result> { + (0..count) + .map(|i| { + let pos = base.saturating_add(i); + let slot_index = u32::try_from(pos).map_err(|_| err_coded!(ErrorCode::Int045, pos))?; + Ok(FactRef { + page_id: 0, + slot_index, + }) + }) + .collect() +} + /// Resolve a [FactRef] to a [Fact] using the committed reader (for on-disk facts) /// or the pending facts vector (for in-memory facts with page_id=0). /// Used by the production index-driven lookup methods (`get_facts_by_entity`, @@ -584,7 +581,7 @@ pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { fn resolve_fact_ref(d: &FactData, fr: FactRef) -> Result { if fr.page_id == 0 { d.facts - .get(fr.slot_index as usize) + .get(usize::try_from(fr.slot_index).unwrap_or(usize::MAX)) .cloned() .ok_or_else(|| err_coded!(ErrorCode::Int045, fr.slot_index)) } else { @@ -2222,7 +2219,7 @@ mod tests { f, FactRef { page_id: 1, - slot_index: u16::try_from(slot).unwrap(), + slot_index: u32::try_from(slot).unwrap(), }, ); } @@ -2419,4 +2416,91 @@ mod tests { ); } } + + /// #445: more than 65,535 pending facts must each resolve to their own fact + /// through the EAVT (entity) and AEVT (attribute) paths, for every write path. + #[test] + fn pending_facts_past_u16_resolve_to_themselves() { + const N: u32 = 70_000; + let entity = |i: u32| uuid::Uuid::from_u128(u128::from(i) + 1); + + let storage = FactStorage::new(); + storage + .transact_batch( + (0..N) + .map(|i| { + ( + entity(i), + ":n".to_string(), + Value::Integer(i64::from(i)), + None, + ) + }) + .collect(), + None, + ) + .unwrap(); + // One fact each through transact, retract and load_fact, all past slot 65,535. + storage + .transact( + vec![(entity(N), ":n".to_string(), Value::Integer(-1))], + None, + ) + .unwrap(); + storage + .retract(vec![(entity(N), ":n".to_string(), Value::Integer(-1))]) + .unwrap(); + let mut loaded = Fact::new(entity(N + 1), ":n".to_string(), Value::Integer(-2), 1); + loaded.tx_count = 99; + assert!(storage.load_fact(loaded).unwrap()); + + for i in [0, 65_534, 65_535, 65_536, N - 1] { + let facts = storage.get_facts_by_entity(&entity(i)).unwrap(); + assert_eq!(facts.len(), 1, "one fact per entity"); + assert_eq!( + facts[0].value, + Value::Integer(i64::from(i)), + "entity's own value" + ); + let facts = storage + .get_facts_by_entity_attribute_indexed(&entity(i), &":n".to_string()) + .unwrap(); + assert_eq!(facts.len(), 1, "one fact per (entity, attribute)"); + assert_eq!( + facts[0].value, + Value::Integer(i64::from(i)), + "entity's own value" + ); + } + let retract_pair = storage.get_facts_by_entity(&entity(N)).unwrap(); + assert_eq!(retract_pair.len(), 2, "assert and retract"); + assert_eq!( + retract_pair.iter().filter(|f| !f.asserted).count(), + 1, + "one retraction" + ); + let loaded = storage.get_facts_by_entity(&entity(N + 1)).unwrap(); + assert_eq!(loaded.len(), 1, "loaded fact"); + assert_eq!(loaded[0].value, Value::Integer(-2), "loaded fact's value"); + + let by_attr = storage.get_facts_by_attribute(&":n".to_string()).unwrap(); + assert_eq!(by_attr.len(), N as usize + 3, "every fact once"); + let distinct: HashSet = by_attr.iter().map(pending_key).collect(); + assert_eq!(distinct.len(), N as usize + 3, "no fact returned twice"); + } + + #[test] + fn pending_refs_are_distinct_and_checked() { + let refs = pending_refs(65_534, 3).unwrap(); + let slots: Vec = refs.iter().map(|r| r.slot_index).collect(); + assert_eq!(slots, vec![65_534, 65_535, 65_536]); + assert!( + refs.iter().all(|r| r.page_id == 0), + "pending refs use page 0" + ); + if let Ok(base) = usize::try_from(u64::from(u32::MAX)) { + assert!(pending_refs(base, 1).is_ok(), "u32::MAX is the last slot"); + assert!(pending_refs(base, 2).is_err(), "past u32::MAX is an error"); + } + } } diff --git a/src/storage/index.rs b/src/storage/index.rs index 8eb59ea89..26047cd0c 100644 --- a/src/storage/index.rs +++ b/src/storage/index.rs @@ -25,12 +25,16 @@ fn max_uuid() -> Uuid { /// Disk location of a fact. /// -/// `slot_index` is always `0` in Phase 6.1 (one fact per page). -/// In Phase 6.2 it identifies the record within a packed page. +/// For a committed fact (`page_id > 0`), `slot_index` is the record within a +/// packed page. For a pending fact (`page_id == 0`), it is the fact's position in +/// `FactStorage`'s pending list, which can exceed `u16::MAX` (#445). +/// +/// `slot_index` was a `u16` before #445. postcard writes `u16` and `u32` as the +/// same varint, so index pages on disk are byte-for-byte unchanged. #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)] pub struct FactRef { pub page_id: u64, - pub slot_index: u16, + pub slot_index: u32, } // ─── Canonical Value Encoding ─────────────────────────────────────────────── @@ -513,4 +517,38 @@ mod tests { // Just verify it doesn't panic and produces a fixed-length result assert_eq!(nan1.len(), 9); } + + /// #445 widened `slot_index` from `u16` to `u32`. postcard must still write + /// and read exactly the bytes a `u16` slot produced, so v7 index pages are + /// unchanged on disk. + #[test] + fn fact_ref_encoding_matches_the_u16_layout() { + #[derive(Serialize, Deserialize)] + struct FactRefU16 { + page_id: u64, + slot_index: u16, + } + for (page_id, slot) in [ + (0u64, 0u16), + (1, 1), + (7, 127), + (300, 128), + (u64::MAX, u16::MAX), + ] { + let old = postcard::to_allocvec(&FactRefU16 { + page_id, + slot_index: slot, + }) + .unwrap(); + let new = postcard::to_allocvec(&FactRef { + page_id, + slot_index: u32::from(slot), + }) + .unwrap(); + assert_eq!(old, new, "same bytes as the u16 layout"); + let read: FactRef = postcard::from_bytes(&old).unwrap(); + assert_eq!(read.page_id, page_id); + assert_eq!(read.slot_index, u32::from(slot)); + } + } } diff --git a/src/storage/packed_pages.rs b/src/storage/packed_pages.rs index 4bb874aa3..caa81d2e2 100644 --- a/src/storage/packed_pages.rs +++ b/src/storage/packed_pages.rs @@ -157,7 +157,7 @@ pub fn pack_facts(facts: &[Fact], start_page_id: u64) -> Result<(Vec>, V ); fact_refs.push(FactRef { page_id, - slot_index: current_record_count, + slot_index: u32::from(current_record_count), }); current_record_count = current_record_count.saturating_add(1); } @@ -170,7 +170,7 @@ pub fn pack_facts(facts: &[Fact], start_page_id: u64) -> Result<(Vec>, V } /// Read a single fact from a packed page at the given slot index. -pub fn read_slot(page: &[u8], slot: u16) -> Result { +pub fn read_slot(page: &[u8], slot: u32) -> Result { if page.len() < PAGE_SIZE { bail_coded!( ErrorCode::Int024, @@ -194,7 +194,7 @@ pub fn read_slot(page: &[u8], slot: u16) -> Result { .get(3) .ok_or_else(|| err_coded!(ErrorCode::Int024, "too short for record_count byte 3"))?; let record_count = u16::from_le_bytes([b2, b3]); - if slot >= record_count { + if slot >= u32::from(record_count) { bail_coded!( ErrorCode::Int024, format!("Slot {slot} out of bounds (page has {record_count} records)") @@ -202,7 +202,8 @@ pub fn read_slot(page: &[u8], slot: u16) -> Result { } // dir_base = PACKED_HEADER_SIZE + slot * 4; slot < record_count <= u16::MAX, // so slot as usize * 4 <= (65534 * 4) which fits in usize. - let slot_usize = usize::from(slot); + let slot_usize = usize::try_from(slot) + .map_err(|_| err_coded!(ErrorCode::Int024, format!("slot {slot} overflows usize")))?; let dir_base = PACKED_HEADER_SIZE.saturating_add(slot_usize.saturating_mul(4)); let db0 = *page .get(dir_base) @@ -283,10 +284,10 @@ pub fn read_all_with_refs( let b3 = page.get(3).copied().unwrap_or(0); let record_count = u16::from_le_bytes([b2, b3]); for slot in 0..record_count { - facts.push(read_slot(&page, slot)?); + facts.push(read_slot(&page, u32::from(slot))?); refs.push(FactRef { page_id, - slot_index: slot, + slot_index: u32::from(slot), }); } } diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index fec31be77..eccbf0ae8 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -696,7 +696,9 @@ impl PersistentFactStorage { let mut avet_map = std::collections::BTreeMap::new(); let mut vaet_map = std::collections::BTreeMap::new(); for (i, fact) in all_facts.iter().enumerate() { - let slot_index = u16::try_from(i).map_err(|_| err_coded!(ErrorCode::Stg020, i))?; + let slot_index = u16::try_from(i) + .map(u32::from) + .map_err(|_| err_coded!(ErrorCode::Stg020, i))?; let fr = FactRef { page_id: 1, slot_index, diff --git a/tests/edge_cases_test.rs b/tests/edge_cases_test.rs index 1c4ee58f5..c97bfa264 100644 --- a/tests/edge_cases_test.rs +++ b/tests/edge_cases_test.rs @@ -4,6 +4,7 @@ //! - Oversized fact rejected at insertion (file-backed, both execute() and commit() paths) //! - Oversized fact accepted in-memory (no page size constraint) //! - Stale WAL after checkpoint is replayed idempotently (no duplicate facts) +//! - More than 65,535 uncheckpointed facts query correctly (#445) #![cfg(not(target_arch = "wasm32"))] use minigraf::{Minigraf, OpenOptions, QueryResult}; @@ -138,3 +139,67 @@ fn test_stale_wal_after_checkpoint_is_idempotent() { }; assert_eq!(bob_rows.len(), 1, "bob:age must survive the checkpoint"); } + +// ── More than 65,535 uncheckpointed facts (#445) ───────────────────────────── + +const PAST_U16: u32 = 70_000; + +fn transact_past_u16(db: &Minigraf) { + let mut batch = String::from("(transact ["); + for i in 0..PAST_U16 { + batch.push_str(&format!("[:e{i} :n {i}] ")); + } + batch.push_str("])"); + db.execute(&batch).unwrap(); +} + +fn ints(r: QueryResult) -> Vec { + let QueryResult::QueryResults { results, .. } = r else { + panic!("expected query results"); + }; + results + .iter() + .flatten() + .map(|v| match v { + minigraf::Value::Integer(n) => *n, + _ => panic!("expected an integer"), + }) + .collect() +} + +fn assert_all_facts_visible(db: &Minigraf, when: &str) { + for i in [0u32, 65_535, 65_536, PAST_U16 - 1] { + let got = ints( + db.execute(&format!("(query [:find ?v :where [:e{i} :n ?v]])")) + .unwrap(), + ); + assert_eq!(got, vec![i64::from(i)], "entity lookup {when}"); + } + let got = ints( + db.execute("(query [:find (count ?e) (max ?v) :where [?e :n ?v]])") + .unwrap(), + ); + assert_eq!( + got, + vec![i64::from(PAST_U16), i64::from(PAST_U16) - 1], + "attribute scan {when}" + ); +} + +#[test] +fn test_more_than_u16_pending_facts_in_memory() { + let db = Minigraf::in_memory().unwrap(); + transact_past_u16(&db); + assert_all_facts_visible(&db, "in memory"); +} + +#[test] +fn test_more_than_u16_pending_facts_file_backed() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("test.graph"); + let db = Minigraf::open(&path).unwrap(); + transact_past_u16(&db); + assert_all_facts_visible(&db, "before checkpoint"); + db.checkpoint().unwrap(); + assert_all_facts_visible(&db, "after checkpoint"); +} From 170d6fae82a404f2a80da999ff2b4fd0e11d3318 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 08:30:35 +0530 Subject: [PATCH 2/2] fix(storage): never rewind the tx counter on WAL replay (#447) Open sets the transaction counter from the file's checkpointed count, then WAL replay skips entries at or below it and calls restore_tx_counter, which stored the highest tx_count among the facts it had loaded. When every WAL entry was already checkpointed, nothing was loaded and the counter was reset to 0, so later transactions reused tx_counts already in the file and :as-of history was wrong, permanently after the next checkpoint. restore_tx_counter now only raises the counter (fetch_max). Refs #447 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +-- src/graph/storage.rs | 27 +++++++++++++++++--- tests/wal_test.rs | 57 +++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 86 insertions(+), 7 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 208e39804..c39aadd29 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,6 +10,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed - **Queries returned wrong results with more than 65,535 uncheckpointed facts (#445).** Each fact not yet checkpointed was indexed by its position in memory, stored as a 16-bit number that stopped counting at 65,535. Every later fact was indexed as that same position, so entity-bound queries (`[:e :attr ?v]`) and attribute scans (`[?e :attr ?v]`) silently lost or duplicated facts. This affected in-memory databases with more than 65,535 facts and file databases with more than 65,535 facts written since the last checkpoint. The stored data was always intact, and a checkpoint made file databases correct again. Positions are now 32-bit and checked. Affected releases: v0.7.0 through v2.0.2. The file format is unchanged. +- **Reopening next to an already-checkpointed WAL rewound the transaction counter (#447).** The WAL normally disappears after a checkpoint. It survives one only if the process crashes between the checkpoint's commit and the WAL delete, if the delete fails (WAL-006), or with `wal_checkpoint_threshold(usize::MAX)`. When such a WAL held only entries already in the file, replay skipped them all and then reset the transaction counter from the facts it had loaded, which were none, so it reset to 0. The next transactions reused `tx_count` values already in the file, `:as-of` answers mixed old and new transactions, and the next checkpoint made that history permanent. The counter now never moves backwards on replay. Affected releases: v0.5.0 through v2.0.2. ## v2.0.2 — 2026-09-27 diff --git a/CLAUDE.md b/CLAUDE.md index 2aedaa28d..0d31311ec 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1217 tests** (1209 passing, 8 ignored; unit + integration + doc). +**1219 tests** (1211 passing, 8 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index 318191365..082451215 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1217 tests +cargo test # run 1219 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 3298a56fe..540d5ba8e 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-09-27 with `cargo test` -**Result**: 1,209 passing tests and 8 ignored tests (1,217 total, including the #445 tests added after v2.0.2) +**Result**: 1,211 passing tests and 8 ignored tests (1,219 total, including the #445 and #447 tests added after v2.0.2) -The v2.0.2 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `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 cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). 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). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). After v2.0.2, storage unit tests and two `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, before and after a checkpoint, and that the widened `FactRef` encodes to the same bytes as before (#445). +The v2.0.2 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `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 cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). 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). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). After v2.0.2, storage unit tests and two `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, before and after a checkpoint, and that the widened `FactRef` encodes to the same bytes as before (#445). A WAL test reopens a database next to a WAL whose entries are all checkpointed, writes again, and checks that `:as-of` history is unchanged before and after another reopen; a unit test checks that restoring the transaction counter never lowers it (#447). ### Covered Areas diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 771151e50..1edaa6354 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -294,17 +294,19 @@ impl FactStorage { Ok(true) } - /// Set tx_counter to max(tx_count) across all loaded facts. + /// Raise tx_counter to max(tx_count) across all loaded facts. /// /// Must be called after all `load_fact()` calls complete so that the next - /// `transact()` call picks up from the right sequence number. + /// `transact()` call picks up from the right sequence number. The counter + /// never moves backwards: it may already hold the file's checkpointed count, + /// and when WAL replay loads no facts that count must survive (#447). pub(crate) fn restore_tx_counter(&self) -> Result<()> { let d = self .data .read() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; let max = d.facts.iter().map(|f| f.tx_count).max().unwrap_or(0); - self.tx_counter.store(max, Ordering::SeqCst); + self.tx_counter.fetch_max(max, Ordering::SeqCst); Ok(()) } @@ -2503,4 +2505,23 @@ mod tests { assert!(pending_refs(base, 2).is_err(), "past u32::MAX is an error"); } } + + /// #447: restoring the counter after loading facts never lowers it. + #[test] + fn restore_tx_counter_never_moves_backwards() { + let storage = FactStorage::new(); + storage.restore_tx_counter_from(5); + storage.restore_tx_counter().unwrap(); + assert_eq!(storage.current_tx_count(), 5, "no loaded facts: keep 5"); + let mut f = Fact::new( + uuid::Uuid::from_u128(1), + ":a".to_string(), + Value::Integer(1), + 1, + ); + f.tx_count = 9; + storage.load_fact(f).unwrap(); + storage.restore_tx_counter().unwrap(); + assert_eq!(storage.current_tx_count(), 9, "a higher loaded count wins"); + } } diff --git a/tests/wal_test.rs b/tests/wal_test.rs index 02cdc4a20..68e76fdf3 100644 --- a/tests/wal_test.rs +++ b/tests/wal_test.rs @@ -148,6 +148,63 @@ fn test_no_duplicate_facts_after_post_checkpoint_crash() { ); } +/// #447: reopening next to a WAL whose entries are all checkpointed must not +/// rewind the transaction counter. Before the fix, the next transactions +/// reused tx 1 and 2, so `:as-of` saw them as part of history they never were. +#[test] +fn test_reopen_with_checkpointed_wal_does_not_reuse_tx_counts() { + let dir = tempfile::tempdir().unwrap(); + let db_path = dir.path().join("rewind.graph"); + let wal_path = wal_path_for(&db_path); + { + // usize::MAX: no close-time checkpoint, so the restored WAL survives drop. + let db = OpenOptions::default() + .wal_checkpoint_threshold(usize::MAX) + .path(db_path.to_str().unwrap()) + .open() + .unwrap(); + db.execute("(transact [[:alice :age 30]])").unwrap(); // tx 1 + db.execute("(transact [[:alice :age 31]])").unwrap(); // tx 2 + let stale = std::fs::read(&wal_path).unwrap(); + db.checkpoint().unwrap(); + // Crash between the checkpoint's commit and the WAL delete. + std::fs::write(&wal_path, &stale).unwrap(); + } + let ages = |db: &Minigraf, q: &str| -> Vec { + let QueryResult::QueryResults { results, .. } = db.execute(q).unwrap() else { + panic!("expected query results"); + }; + let mut v: Vec = results + .iter() + .flatten() + .map(|v| match v { + minigraf::Value::Integer(n) => *n, + _ => panic!("expected an integer"), + }) + .collect(); + v.sort_unstable(); + v + }; + for reopen in 0..2 { + let db = Minigraf::open(&db_path).unwrap(); + if reopen == 0 { + db.execute("(retract [[:alice :age 30]])").unwrap(); // tx 3 + db.execute("(transact [[:alice :age 99]])").unwrap(); // tx 4 + } + let when = if reopen == 0 { + "before reopen" + } else { + "after reopen" + }; + let q = |n| format!("(query [:find ?a :as-of {n} :where [:alice :age ?a]])"); + assert_eq!(ages(&db, &q(1)), vec![30], "as-of 1 {when}"); + assert_eq!(ages(&db, &q(2)), vec![30, 31], "as-of 2 {when}"); + assert_eq!(ages(&db, &q(3)), vec![31], "as-of 3 {when}"); + let now = ages(&db, "(query [:find ?a :where [:alice :age ?a]])"); + assert_eq!(now, vec![31, 99], "current {when}"); + } +} + // ── 4. Partial WAL entry is discarded; earlier entries intact ───────────────── /// Write 1 fact, crash (no checkpoint), then append garbage bytes to the WAL