diff --git a/CHANGELOG.md b/CHANGELOG.md index b397fde44..57a2672ca 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -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 diff --git a/CLAUDE.md b/CLAUDE.md index 83802ebe3..7d2566ae7 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 -**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. diff --git a/README.md b/README.md index 638d6ccad..a6a2f5be4 100644 --- a/README.md +++ b/README.md @@ -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 ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 3692b181e..82f016f80 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -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 diff --git a/src/query/datalog/stratification.rs b/src/query/datalog/stratification.rs index b7f407695..b21204b35 100644 --- a/src/query/datalog/stratification.rs +++ b/src/query/datalog/stratification.rs @@ -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>, + /// + /// A `BTreeMap` so `stratify()` walks heads in a fixed order and always + /// reports the same pair for a given negative cycle (#410). + edges: BTreeMap>, } impl DependencyGraph { pub fn from_rules(registry: &RuleRegistry) -> Self { - let mut edges: HashMap> = HashMap::new(); + let mut edges: BTreeMap> = 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(®istry) + .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