diff --git a/CHANGELOG.md b/CHANGELOG.md index dfe1b6f8c..b4b293f53 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -19,6 +19,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - Two values of the same attribute written in one transaction are both returned by every query path. Previously only one came back, and entity-bound and attribute-bound queries could return different ones (#371, #287). - A retract that removes several values of one attribute in one call now hides all of them (#371). +- Queries no longer lose or duplicate facts when more than 65,535 facts are waiting for a checkpoint (#445; also fixed in v2.x). - Reopening next to a WAL whose entries were all already checkpointed no longer rewinds the transaction counter, so later transactions no longer reuse `tx_count` values and `:as-of` history stays correct (#447; also fixed in v2.x). ### Internal diff --git a/CLAUDE.md b/CLAUDE.md index 35e8af25c..15d358a0d 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -190,7 +190,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1223 tests** (1215 passing, 8 ignored; unit + integration + doc). +**1226 tests** (1218 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 bc4df031d..0e0a299c0 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 1215 tests +cargo test # run 1226 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 3b43234a2..b37ae085c 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-05 with `cargo test --quiet` -**Result**: 1,215 passing tests and 8 ignored tests (1,223 total) +**Result**: 1,218 passing tests and 8 ignored tests (1,226 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). +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). 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). ### Covered Areas diff --git a/src/graph/storage.rs b/src/graph/storage.rs index b51ac7567..0dfa72f83 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -1837,4 +1837,76 @@ mod tests { storage.restore_tx_counter().unwrap(); assert_eq!(storage.current_tx_count(), 9, "a higher loaded count wins"); } + + /// #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"); + } } diff --git a/tests/edge_cases_test.rs b/tests/edge_cases_test.rs index e5fe0aaf8..272390c67 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"); +}