adityamukho · Sep 26, 2026 · Sep 26, 2026
@@ -21,6 +21,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **`or-join` failed with INT-031 when no rows reached it (#405).** A valid query such as `[?item :order-item/product ?p] (or-join [?item] ...)` returned `or-join variable ?item is not bound in the incoming scope` on an empty database, or whenever the clauses before the `or-join` matched nothing, but worked once matching data existed. A safety check read the bound variables from the incoming rows, so with no rows every join variable looked unbound. `or-join` now returns an empty result when no rows reach it, like `or` and `not-join` already did. This applies to queries and rule bodies.
 - **A query with `$slot` bind tokens run through `execute()` reported an internal error (#407).** Such a query failed with `[INT-025] internal: unsubstituted :valid-at bind slot reached the executor` when it had a `:valid-at` slot, and with slots in other positions it could run and quietly return nothing. `Minigraf::execute()`, `WriteTransaction::execute()` and the REPL now reject it before execution with the new user error **API-010**, which names the slots and points to `prepare()`. Prepared queries are unchanged.
 - **Bound-entity queries could drop rows when one `WriteTransaction` wrote the same attribute in several valid-time windows (#323).** Both facts share a `tx_count`, and the selective lookup path de-duplicated on `(entity, attribute, tx_count, asserted)`, so one window's value was silently lost, while the same query via a full scan returned both. That de-duplication has been removed, and bound-entity queries now always match a full scan.
+- **The INT-054 negative-cycle error named its two predicates in a random order (#410).** Registering `(rule [(p ?x) (not (q ?x))])` and then `(rule [(q ?x) (not (p ?x))])` reported `predicate 'q' is involved in a negative cycle through 'p'` on some runs and the reverse on others, because stratification walked the rule dependency graph in `HashMap` order. It now walks rules in sorted order, so the same rules always give the same message. Which rules are accepted or rejected is unchanged.
 
 ### CI
 

@@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint.
 
 ## Test Coverage
 
-**1210 tests passing** (1202 passing, 8 ignored; unit + integration + doc).
+**1211 tests passing** (1203 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.

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

@@ -4,9 +4,9 @@
 
 **Verified**: 2026-09-26 with `cargo test`
 
-**Result**: 1,202 passing tests and 8 ignored tests (1,210 total)
+**Result**: 1,203 passing tests and 8 ignored tests (1,211 total)
 
-The v2.0.1 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).
+The v2.0.1 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).
 
 ### Covered Areas
 

@@ -1,6 +1,6 @@
 use crate::error::{ErrorCode, err_coded};
 use anyhow::Result;
-use std::collections::HashMap;
+use std::collections::{BTreeMap, HashMap};
 
 use crate::query::datalog::rules::RuleRegistry;
 use crate::query::datalog::types::WhereClause;
@@ -42,12 +42,15 @@ fn collect_clause_deps(clause: &WhereClause, entry: &mut Vec<(String, bool)>) {
 
 pub struct DependencyGraph {
     /// head_predicate → Vec<(dependency_predicate, is_negative)>
-    edges: HashMap<String, Vec<(String, bool)>>,
+    ///
+    /// A `BTreeMap` so `stratify()` walks heads in a fixed order and always
+    /// reports the same pair for a given negative cycle (#410).
+    edges: BTreeMap<String, Vec<(String, bool)>>,
 }
 
 impl DependencyGraph {
     pub fn from_rules(registry: &RuleRegistry) -> Self {
-        let mut edges: HashMap<String, Vec<(String, bool)>> = HashMap::new();
+        let mut edges: BTreeMap<String, Vec<(String, bool)>> = BTreeMap::new();
 
         for (head_pred, rules) in registry.all_rules() {
             for rule in rules {
@@ -216,6 +219,25 @@ mod tests {
         assert!(graph.stratify().is_err());
     }
 
+    #[test]
+    fn test_negative_cycle_error_message_is_deterministic() {
+        // #410: the reported (head, dep) pair must not depend on HashMap
+        // iteration order. Each registry gets a fresh RandomState, so looping
+        // exercises many different orders within one process.
+        for _ in 0..64 {
+            let registry =
+                make_registry_with_rules(vec![negative_rule("p", "q"), negative_rule("q", "p")]);
+            let err = DependencyGraph::from_rules(&registry)
+                .stratify()
+                .expect_err("negative cycle must be rejected");
+            assert_eq!(
+                err.to_string(),
+                "unstratifiable: predicate 'q' is involved in a negative cycle through 'p'",
+                "negative-cycle error must name the same pair every time"
+            );
+        }
+    }
+
     #[test]
     fn test_self_negative_cycle_returns_error() {
         // p →⁻ p