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"); +}