adityamukho · Oct 8000 15, 2026 · Oct 15, 2026 · Oct 15, 2026 · Oct 15, 2026 · Oct 15, 2026
@@ -53,6 +53,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **A query on another thread sees each transaction whole** (#554). A commit wrote its WAL entry, then added the transaction's facts to the in-memory store one fact at a time, each under its own lock, so a query running on another thread could return part of the transaction. `execute("(transact ...)")`, `execute("(retract ...)")` and `WriteTransaction::commit` all did this. They now add the whole transaction under one lock, as does WAL replay. Stored data was never affected. Affected `WriteTransaction` since v0.5.0 and `execute` since v0.6.0.
 - **All patterns of one query read the same state of the database** (#555). A query whose patterns name entities or attributes read each of them with its own lookup, each under its own lock, so a transaction that committed between two lookups was seen by some patterns and not others, and the query could return rows that match no state of the database (an entity with one attribute but not another that was always written with it). The lookups now run under one lock. Stored data was never affected. Affected every release since v1.1.0.
 - **A query never sees a checkpoint half published** (#543). A checkpoint cleared the in-memory pending facts and installed the new committed index as two steps, so a query between them could miss the facts being checkpointed or, with the opposite order, see them twice. Both now change under one lock. Every read of one query, cursor or fact log is taken from one snapshot of the database, which holds the committed generation it read until it is dropped. This affected only v3.0.0 development builds; in released versions the checkpoint race is #558, fixed separately.
+- **A damaged index tree whose node points back up fails the query with `INT-049` instead of never finishing** (#597). A scan resumes each batch after the last key it read. When a corrupt internal node led back to a leaf already read, the scan read the same keys again on every batch and never ended, holding more memory each time; the nightly fuzz run found it as an out-of-memory. The B+tree cursor now requires keys to increase from one leaf to the next and never to fall below its start or the key it was last moved to, and refuses an empty leaf below an internal node; any of these fails with `INT-049`. `verify()` already reported such a tree.
 
 ### Internal
 
@@ -75,6 +76,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **Coverage gates that gate (#396).** The per-module gate in `coverage-gates.yml` had never checked anything: the instrumented test run failed (the lock tests could not find `pid_ns_helper`), the report it grepped was empty, and every module was skipped with a warning, so the job passed. It also read `cargo llvm-cov --text`, which has no per-file percentages, and named `btree_v6`, which v3 no longer has. The job now runs the whole suite with branch coverage on a pinned nightly, fails if any test fails, and checks each file's line and branch percentage against `coverage-thresholds.toml` with `scripts/coverage_gates.py`; a file missing from the report, or without branch data, fails. The thresholds file covers the WAL, `db.rs`, the fact log and log writer, every storage file, and the evaluator, executor and stratification, with floors at the measured values less one point. It also lists the paths left uncovered on purpose (invariant checks, browser-only and Windows-only paths). New tests cover the WAL's fact-size and fact-count limits (the old fact-size test changed bytes inside the fact and never reached the limit), a WAL opened in a missing directory, a failed cut of a torn WAL tail, short v7 pages and slots past the count, backup meta pages of another generation or length, a torn first meta with data in page 1, `save` with nothing pending, `into_backend` with pending facts, `rebuild_indexes` with nothing checkpointed, unsorted or repeated B+tree input, a stored key inserted with another value, a tree pointer to a page of another type, the read-only `MutexStorageBackend`, and two threads missing the same page in the page cache (before, only a lucky race reached that path). Branch coverage of `wal.rs` went from 83% to 95%, `packed_pages.rs` from 86% to 100%, `persistent_facts.rs` from 82% to 88%, and `btree.rs` from 85% to 85.5%. A follow-up brought the storage files the issue named to 90% branch coverage or more: `btree.rs` to 95.7%, `persistent_facts.rs` to 91.7% and `index.rs` to 100%, with floors raised to match. New tests cover a leaf packing retried around one large entry, an entry larger than a page, separators over the fill target, an insert into a tree whose root points to itself, auto-save on drop, a torn first meta with a blank page 1, and an unreadable page past the meta's page count. Splitting internal nodes is now one pass: the old retry loop could not run, because the balanced cut always leaves each node within the fill target. The workflow pins cargo-llvm-cov 0.9.1, since 0.8.x missed the library's unit tests under the pinned nightly and reported much lower numbers.
 - **Performance envelope at 100K–10M facts (#394).** `examples/perf_envelope.rs` builds and caches fixtures of 100K, 1M and 10M facts (six attributes per entity, a ref tree, two valid-time windows, an entity with 1,000 versions). It reports open and checkpoint times, RSS, and p50/p99 latency for twelve query shapes, each shape in its own process. It builds with a new `envelope` Cargo profile (`release` at opt-level 3, as an application compiles the library; `release` itself is opt-level "z"). `docs/BENCHMARKS.md` and the README publish the results: point lookups and single-entity time travel stay flat (12–14 µs at 10M facts). Scans, aggregations and joins grow linearly with the attributes they touch. Rule queries are supported to 100K facts only. A Python FFI round trip (`bench/envelope.py` in minigraf-python) adds about 70 µs per query. `.github/workflows/envelope.yml` runs 100K and 1M on demand, and a 10K smoke pass on PRs that change the harness. The nightly Criterion `query/*` groups gain 100K and 1M scales. Profiling at 1M facts found #528, #529, #530, #531 and #532.
 - `tests/snapshot_atomicity_test.rs` races a writer against a reader: a query must see each transaction whole, whether written with `execute` or a `WriteTransaction` (#554), and must read one state for all its patterns (#555), in memory and on file. It also runs the v2.x checkpoint race from #558, which never failed on v3: copy-on-write checkpoints do not overwrite pages a published reader uses.
+- **The `datalog_eval` fuzz guard counts partial bindings** (#597). The guard skipped inputs whose patterns join to more than 50,000 rows, counting only the rows after the last pattern. A `not-join` body still runs on the executor pattern by pattern in text order, so a 120-pattern body built hundreds of thousands of partial bindings before its last pattern matched nothing, and ran past the 60-second timeout. The guard now counts the bindings after every pattern. On the `v3` corpus (4,783 inputs) coverage drops by 7 of 9,719 edges. The input is added as a seed, as is the `btree_page` input of the cursor fix above.
 
 ### Documentation
 

@@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1503 tests** (1493 passing, 10 ignored; unit + integration + doc).
+**1507 tests** (1497 passing, 10 ignored; unit + integration + doc).
 See `docs/TEST_COVERAGE.md` for the full per-file breakdown.
 
 **Testing conventions** — see the Testing Conventions section below before writing any tests.

@@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit
 
 ```bash
 cargo run          # interactive Datalog REPL
-cargo test         # run 1503 tests
+cargo test         # run 1507 tests
 cargo run < demos/demo_recursive.txt   # recursive rules demo
 ```
 

@@ -0,0 +1 @@
+(query [: :where [?e ?FFFFFFF ?c] (not-join [?e ?_ct?6EEEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c]  [?_?e ?lEEneFFFunqnjFmaxqfn ?c]  [?e ?lynEEEEEEEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueFF-nnyneFFFFqfn ?k]  [?e ?lynEEEEdEqfn ?c]  [?e ?lynEEEEEEEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueFF-nnyneFFFFqfn ?k]  [?e ?lynEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueVFnnyneFFFFqfn ?k]  [?e ?lynEEEEEEEEEEEEEqfn ?a]  [?e ?ynsufun ??nc]  [?e ?lunufn ?a]  [?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c]  [?_?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c]  [?_?e ?lysnufn ?s]  [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c]  [?_?e ?lyznufn6666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnlnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc]  [?_?e ?lEEneFFFunqnjFqfn ?c]  [?e ??lynEEEEEEEEEEdEEq ?c000000001002302725]  [?e ?lunufn ?c]  [?e ?lynnueFFnnue166633333nufn ?c]  [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lu?lynnueFFnnueFEECEEEEEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lunufn ?c]  [?e ?lynnueFFnnue166666666nufn ?c]  [?e ?lynnueFFnnue6666666?66666666662666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc]  [?_?e ?lEEneFFFunqnjFqfn ?c]  [?e ??lynEEEEEEEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueFF-Eqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueVFnnyneFFFFqfn ?k]  [?e ?lynEEEEEEEEEEEEEqfn ?a]  [?e ?ynsufun ??nc]  [?e ?lunufn ?a]  [?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c]  [?_?e ?lyznufn ?c000000002004605448]  [?e ?lunufn ?c]  [?e ?lynnueFFnnue333333333nufn ?c]  [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lunufn ?c]  [?e ?lynnueFFnnue333333333nufn ?c]  [?e ?lynnueFFnnue6666666?66666666666666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnjnnnnnc]  [?_?e ?lEEneFFFunqnjFqfn ?c]  [?e ??lynEEEEEEEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueFF-nnyneFFFFqfn ?k]  [?e ?lynEEEEdEEqfn ?g]  [?E ?lynnufn ?c]  [?e ?lynnueVFn2nyneFFFfq ?kfn]  [?e ?lynEEEE6666?66666600000000011406509395579415211FEEEEEeEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnc]  [?_?e ?lEEneFFFunqnjFqfn ?c]  [?e ??lynEEEEEEEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueFF-nnyneFFFFqfn ?k]  [?e ?lynEEEEdEEyznufn ?c000000001002302724]  [?e ?lunufn ?c]  [?e ?lynnueFFnnue333333333nufn ?c]  [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lu?lynnueFFnnueFEECEEEEEEEEqfn ?c]  [?_?e ?lysnufn ?c]  [?e ?lunufn ?c]  [?e ?lynnueFFnnue333333333nufn ?c]  [?e ?lynnueFFnnue6666666?66666666666666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc]  [?_?e ?lEEneFFFunqnjFqfn ?c]  [?e ??ylnEEEEEEEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueFF-Eqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueVFnnyneFFFFqfn ?k]  [?e ?lynEEEEEEEEEEEEEqfn ?a]  [?e ?ynsufun ??nc]  [?e ?lunufn ?a]  [?e ?lynnue666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc]  [?_?e ?lEEneFFFunqnjFqfn ?c]  [?e ??lynEEEEEEEEEEdEEqfn ?g]  [?e ?lynnufn ?c]  [?e ?lynnueFF-nnyneFFFFqfn ?k]  [?e ?lynEEEEdEEqfn ?g]  [?E ?lynnufn ?c]  [?e ?lynnueVFn2nyneFFFfqfn ?k]  [?e ?lynEEEE6666?66666600000000011406509395579415211FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnc]  [?_?e ?lEEneFFFunqnjFqfn ?c]  [?e ??lynEEEEEEdEEqfn ?g]  [?E ?lfalseynnufn ?c]  [?e :__magic_qunqnjoqqqq??lynnueVFnnyneFFFfqfn ?ke])])
@@ -9,14 +9,17 @@ const FACTS: [[&str; 3]; 3] = [
     [":alice", ":age", "30"],
 ];
 
-/// Inputs whose patterns could join to more rows than this are skipped.
+/// Inputs whose patterns could build more bindings than this are skipped.
 const MAX_JOIN_ROWS: u64 = 50_000;
 
 fuzz_target!(|data: &[u8]| {
     if let Ok(s) = std::str::from_utf8(data) {
         // The executor holds every intermediate binding, so patterns that share no
         // variables build their whole cross product: 3^k rows over these 3 facts.
-        // That is a known limit, not a new bug (#575, fixed by #473/#549).
+        // Negation bodies still run there, pattern by pattern in text order, so a
+        // long body builds every partial binding even when its last pattern
+        // matches nothing (#597). That is a known limit, not a new bug (#575,
+        // fixed by #473/#549, and #546 for negation).
         if join_rows_bound(s) > MAX_JOIN_ROWS {
             return;
         }
@@ -30,7 +33,8 @@ fuzz_target!(|data: &[u8]| {
     }
 });
 
-/// An upper estimate of the rows a cross product of the input's patterns yields.
+/// An upper estimate of the bindings the input's patterns build, partial ones
+/// included.
 ///
 /// Every innermost vector of three or more tokens counts as a pattern. Patterns are
 /// grouped by the variables they share (`_` and `?_…` are wildcards and share
@@ -123,14 +127,15 @@ fn find(parent: &mut [usize], mut i: usize) -> usize {
     i
 }
 
-/// Counts the group's join over `FACTS` depth first, stopping past `MAX_JOIN_ROWS`.
+/// Counts the bindings the group's join over `FACTS` builds in text order, after
+/// each pattern and not only after the last one, depth first, stopping past
+/// `MAX_JOIN_ROWS`.
 fn count_join<'a>(
     group: &[[&'a str; 3]],
     bound: &mut Vec<(&'a str, &'static str)>,
     rows: &mut u64,
 ) {
     let Some((pattern, rest)) = group.split_first() else {
-        *rows += 1;
         return;
     };
     for fact in &FACTS {
@@ -154,6 +159,7 @@ fn count_join<'a>(
             }
         });
         if matches {
+            *rows += 1;
             count_join(rest, bound, rows);
         }
         bound.truncate(mark);
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		(query [: :where [?e ?FFFFFFF ?c] (not-join [?e ?_ct?6EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lEEneFFFunqnjFmaxqfn ?c] [?e ?lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEqfn ?c] [?e ?lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueVFnnyneFFFFqfn ?k] [?e ?lynEEEEEEEEEEEEEqfn ?a] [?e ?ynsufun ??nc] [?e ?lunufn ?a] [?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c] [?_?e ?lysnufn ?s] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lyznufn6666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnlnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEq ?c000000001002302725] [?e ?lunufn ?c] [?e ?lynnueFFnnue166633333nufn ?c] [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEECEEEEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lunufn ?c] [?e ?lynnueFFnnue166666666nufn ?c] [?e ?lynnueFFnnue6666666?66666666662666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-Eqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueVFnnyneFFFFqfn ?k] [?e ?lynEEEEEEEEEEEEEqfn ?a] [?e ?ynsufun ??nc] [?e ?lunufn ?a] [?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lyznufn ?c000000002004605448] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666?66666666666666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnjnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEqfn ?g] [?E ?lynnufn ?c] [?e ?lynnueVFn2nyneFFFfq ?kfn] [?e ?lynEEEE6666?66666600000000011406509395579415211FEEEEEeEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEyznufn ?c000000001002302724] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEECEEEEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666?66666666666666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??ylnEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-Eqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueVFnnyneFFFFqfn ?k] [?e ?lynEEEEEEEEEEEEEqfn ?a] [?e ?ynsufun ??nc] [?e ?lunufn ?a] [?e ?lynnue666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEqfn ?g] [?E ?lynnufn ?c] [?e ?lynnueVFn2nyneFFFfqfn ?k] [?e ?lynEEEE6666?66666600000000011406509395579415211FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEdEEqfn ?g] [?E ?lfalseynnufn ?c] [?e :__magic_qunqnjoqqqq??lynnueVFnnyneFFFfqfn ?ke])])