adityamukho · Oct 6, 2026 · Oct 6, 2026
@@ -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)).

@@ -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.

@@ -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
 ```
 

@@ -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
 

@@ -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,14 +556,32 @@ pub(crate) fn net_asserted_facts(facts: Vec<Fact>) -> Vec<Fact> {
         .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<Vec<FactRef>> {
+    (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`,
 /// `get_facts_by_attribute`).
 fn resolve_fact_ref(d: &FactData, fr: FactRef) -> Result<Fact> {
     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<PendingKey> = 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<u32> = 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");
+        }
+    }
 }
@@ -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));
+        }
+    }
 }
@@ -157,7 +157,7 @@ pub fn pack_facts(facts: &[Fact], start_page_id: u64) -> Result<(Vec<Vec<u8>>, 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<Vec<u8>>, V
 }
 
 /// Read a single fact from a packed page at the given slot index.
-pub fn read_slot(page: &[u8], slot: u16) -> Result<Fact> {
+pub fn read_slot(page: &[u8], slot: u32) -> Result<Fact> {
     if page.len() < PAGE_SIZE {
         bail_coded!(
             ErrorCode::Int024,
@@ -194,15 +194,16 @@ pub fn read_slot(page: &[u8], slot: u16) -> Result<Fact> {
         .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)")
         );
     }
     // 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),
             });
         }
     }