From 2ddc96d65acccd4da2794b8664f25e2558a73f8e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Mon, 19 Oct 2026 22:00:26 +0530 Subject: [PATCH] fix(rules): stratify a rule above a not/or rule it calls (#628) Backport of #631. StratifiedEvaluator runs a stratum's positive-only rules to a fixpoint, then each rule with not / not-join / or / or-join once. stratify() gave a positive dependency the callee's stratum, so a rule calling a mixed rule ran before the callee's rows existed and returned too few rows, often none. A positive edge to a predicate with a mixed rule now needs dep_stratum + 1, unless the callee reaches the caller: recursion through a mixed rule stays in one stratum (#633) and is not rejected. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz --- CHANGELOG.md | 1 + CLAUDE.md | 4 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +- src/query/datalog/evaluator.rs | 11 +-- src/query/datalog/stratification.rs | 116 ++++++++++++++++++++++++++-- tests/not_join_test.rs | 87 +++++++++++++++++++++ 7 files changed, 203 insertions(+), 22 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 8eb9e4c3b0..d3f1ce6a23 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -12,6 +12,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **A `:db/valid-at` pattern in a `not-join` body binds the query's valid time on every path** (#615). When the body also held an expression, sat in an `or` branch, or ran in a query that invokes a rule, the body bound `nil`, so `(not-join [?e] [?e :db/valid-at ?t] [(> ?t 0)])` never matched and excluded nothing; without the expression the same body excluded every entity. It now binds the query's `:valid-at` value (or the current time) as the other paths do. Present since v0.13.1. - **A `:db/valid-at` pattern in a rule definition binds the query's valid time** (#617). The rule evaluators never received it, so in a rule body the pattern bound `nil` and the query failed with `INT-022`; in a rule's `not` / `not-join` body it bound `nil`, so the negation never matched on it; and in a rule's `or` branch it bound the current time instead of the query's `:valid-at`. Rule bodies, their negation bodies and `or` branches now bind the query's `:valid-at` value, the current time without one, and `nil` under `:any-valid-time`, as patterns outside rules do. - **An expression reading a variable only an `or` binds keeps its rows** (#625). The planner places expressions among the patterns and `not`s, and `or` / `or-join` run after them, so an expression such as `[(> ?x 1)]` in `[?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]` ran before `?x` was bound and dropped every row, in queries and in rule bodies. Such an expression now runs after the `or`s, before the `not`s that wait for them, as those `not`s already did. +- **A rule calling a rule with `not`, `not-join`, `or` or `or-join` gets all its rows** (#628). Stratification put a rule in the same stratum as the rules it calls, and within a stratum the rules without those clauses run first, so `(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])` ran before any `cur` row existed when `cur` had a `not-join`, and returned nothing; a caller that had a `not` or `or` of its own ran before or after its callee depending on the query. A rule now sits in a stratum above any rule with such a clause it calls, unless the two call each other. - **An `or` / `or-join` branch whose expression reads an outer variable matches** (#620). A branch such as `[(> ?v 1)]` in `[?e :n ?v] (or [(> ?v 1)] [(< ?v 0)])` was evaluated on its own from an empty binding and joined back afterwards, so its expression saw `?v` unbound and the branch matched nothing: the `or` silently dropped rows it should keep, in queries and in rule bodies. A branch whose expression reads a variable the branch does not bind itself is now seeded with each incoming row (an `or-join` branch with the row's join variables). ## v2.0.7 — 2026-10-16 diff --git a/CLAUDE.md b/CLAUDE.md index 1fa2881644..7efb3c9cc5 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -121,7 +121,7 @@ cargo run < demos/demo_negation.txt - `executor.rs`: Query executor — temporal filter (tx-time → net-assert → valid-time), not/not-join post-filter - `matcher.rs`: Pattern matching with variable unification; `edn_to_value`, `edn_to_entity_id` - `evaluator.rs`: `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator`, `evaluate_not_join` - - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection + - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628) - `rules.rs`: `RuleRegistry` — thread-safe rule management - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper - `optimizer.rs`: Selectivity-based join reordering; disabled under `wasm` feature @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1293 tests** (1284 passing, 9 ignored; unit + integration + doc). +**1300 tests** (1291 passing, 9 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 c1e4a6a563..54092457d4 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 1293 tests +cargo test # run 1300 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 91a54696ae..1414574eb3 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-16 with `cargo test` -**Result**: 1,284 passing tests and 9 ignored tests (1,293 total), including the golden-file corpus (#391) +**Result**: 1,291 passing tests and 9 ignored tests (1,300 total), including the golden-file corpus (#391) For v2.0.5, `tests/edge_cases_test.rs` checks that a file of 1 to 4,095 bytes is `STG-045`, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes a write and reads it back after reopen when it is a prefix of the initial header or all zeros (#506). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). @@ -18,7 +18,7 @@ For v2.0.5, torn-WAL-tail tests (#513) check that opening a WAL writer cuts off `tests/magic_sets_test.rs` checks rule queries with a literal argument where some call site cannot carry the magic-sets demand (#608): a rule-body call with an argument nothing binds yet, the same rule called with free arguments, a call from a rule called with free arguments, calls inside `or` and `not`, a fully literal call, and a call bound only by a variable; `magic_sets.rs` unit tests check the adornment each shape solves to. -`tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product (#610), before or after them, through the seeded path (a branch with `not`) and in a rule body, keeps the earlier clauses' variables and fact metadata (a pseudo-attribute), and gives no rows when no branch matches. It also checks that `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds match, nested and in rule bodies (#620); a unit test covers `branch_outer_reads`. Expressions reading a variable only an `or` binds, including a chain and a `not` after them, keep their rows in queries, with rules and in rule bodies (#625); optimizer unit tests cover deferring them ahead of the deferred `not`s. +`tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product (#610), before or after them, through the seeded path (a branch with `not`) and in a rule body, keeps the earlier clauses' variables and fact metadata (a pseudo-attribute), and gives no rows when no branch matches. It also checks that `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds match, nested and in rule bodies (#620); a unit test covers `branch_outer_reads`. Expressions reading a variable only an `or` binds, including a chain and a `not` after them, keep their rows in queries, with rules and in rule bodies (#625); optimizer unit tests cover deferring them ahead of the deferred `not`s. Tests in `tests/not_join_test.rs` check that a rule calling a rule with `not-join`, `not` or `or` returns that rule's rows, with a free and a literal argument and through a forwarding rule, and that a rule with its own `not-join` calling one gets the same rows whether or not the query asks for the callee first; stratification unit tests check that such a caller, a rule forwarding to it and a caller of a recursive one sit above the callee, and that recursion through a rule with a `not` still stratifies (#628). Not counted above: the `BrowserDb` tests run only on wasm32 with `wasm-bindgen-test` in a browser. Two of them check that the IndexedDB flush returns every page a write dirtied, and that a dirty page that cannot be read is an error rather than left out. diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 110c21b612..2e0013efec 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -725,16 +725,7 @@ impl StratifiedEvaluator { for pred in &stratum_preds { for rule in registry.get_rules(pred) { - let has_not = rule.body.iter().any(|c| { - matches!( - c, - WhereClause::Not(_) - | WhereClause::NotJoin { .. } - | WhereClause::Or(_) - | WhereClause::OrJoin { .. } - ) - }); - if has_not { + if crate::query::datalog::stratification::has_mixed_clause(&rule.body) { mixed_rules.push((pred.clone(), rule)); } else { positive_rules.push((pred.clone(), rule)); diff --git a/src/query/datalog/stratification.rs b/src/query/datalog/stratification.rs index b21204b35c..e192cc93c2 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::{BTreeMap, HashMap}; +use std::collections::{BTreeMap, BTreeSet, HashMap}; use crate::query::datalog::rules::RuleRegistry; use crate::query::datalog::types::WhereClause; @@ -38,6 +38,21 @@ fn collect_clause_deps(clause: &WhereClause, entry: &mut Vec<(String, bool)>) { } } +/// Whether a rule body holds a `not`, `not-join`, `or` or `or-join`. +/// `StratifiedEvaluator` runs such a rule once per stratum, after the +/// positive-only rules, so a rule that calls one must sit above it (#628). +pub(crate) fn has_mixed_clause(body: &[WhereClause]) -> bool { + body.iter().any(|c| { + matches!( + c, + WhereClause::Not(_) + | WhereClause::NotJoin { .. } + | WhereClause::Or(_) + | WhereClause::OrJoin { .. } + ) + }) +} + // ── Structs ─────────────────────────────────────────────────────────────────── pub struct DependencyGraph { @@ -46,14 +61,20 @@ pub struct DependencyGraph { /// A `BTreeMap` so `stratify()` walks heads in a fixed order and always /// reports the same pair for a given negative cycle (#410). edges: BTreeMap>, + /// Predicates with at least one rule for which `has_mixed_clause` holds. + mixed: BTreeSet, } impl DependencyGraph { pub fn from_rules(registry: &RuleRegistry) -> Self { let mut edges: BTreeMap> = BTreeMap::new(); + let mut mixed = BTreeSet::new(); for (head_pred, rules) in registry.all_rules() { for rule in rules { + if has_mixed_clause(&rule.body) { + mixed.insert(head_pred.to_string()); + } let entry = edges.entry(head_pred.to_string()).or_default(); for clause in &rule.body { collect_clause_deps(clause, entry); @@ -61,7 +82,24 @@ impl DependencyGraph { } } - DependencyGraph { edges } + DependencyGraph { edges, mixed } + } + + /// Whether `to` is reachable from `from` through one or more edges. + fn reaches(&self, from: &str, to: &str) -> bool { + let mut seen: BTreeSet<&str> = BTreeSet::new(); + let mut stack = vec![from]; + while let Some(p) = stack.pop() { + for (dep, _) in self.edges.get(p).into_iter().flatten() { + if dep == to { + return true; + } + if seen.insert(dep.as_str()) { + stack.push(dep.as_str()); + } + } + } + false } pub fn stratify(&self) -> Result> { @@ -79,6 +117,18 @@ impl DependencyGraph { let mut strata: HashMap = all_predicates.into_iter().map(|p| (p, 0)).collect(); + // A positive edge to a mixed predicate also needs a higher stratum, + // so the callee's not/or rules finish before the caller runs (#628). + // Not on a cycle: recursion through a mixed rule stays in one stratum. + let mut raised: BTreeSet<(&str, &str)> = BTreeSet::new(); + for (head, deps) in &self.edges { + for (dep, is_negative) in deps { + if !*is_negative && self.mixed.contains(dep) && !self.reaches(dep, head) { + raised.insert((head.as_str(), dep.as_str())); + } + } + } + // Bellman-Ford-style constraint propagation let mut changed = true; while changed { @@ -86,11 +136,12 @@ impl DependencyGraph { for (head, deps) in &self.edges { for (dep, is_negative) in deps { let dep_stratum = *strata.get(dep).unwrap_or(&0); - let required = if *is_negative { - dep_stratum.saturating_add(1) - } else { - dep_stratum - }; + let required = + if *is_negative || raised.contains(&(head.as_str(), dep.as_str())) { + dep_stratum.saturating_add(1) + } else { + dep_stratum + }; let head_stratum = strata.entry(head.clone()).or_insert(0); if required > *head_stratum { *head_stratum = required; @@ -210,6 +261,57 @@ mod tests { assert!(s_eligible > s_rejected); } + #[test] + fn test_positive_edge_to_mixed_predicate_raises_caller() { + // #628: p →⁺ q, q has a `not`; q must finish before p runs. + let registry = + make_registry_with_rules(vec![positive_rule("p", "q"), negative_rule("q", "r")]); + let strata = DependencyGraph::from_rules(®istry).stratify().unwrap(); + assert!(strata["p"] > strata["q"], "p above its mixed callee"); + // A chain through a forwarding rule keeps the order. + let registry = make_registry_with_rules(vec![ + positive_rule("p", "f"), + positive_rule("f", "q"), + negative_rule("q", "r"), + ]); + let strata = DependencyGraph::from_rules(®istry).stratify().unwrap(); + assert!(strata["f"] > strata["q"], "forwarding rule above q"); + assert!(strata["p"] >= strata["f"], "p not below f"); + } + + #[test] + fn test_recursion_through_mixed_predicate_stratifies() { + // q →⁺ q with a `not` in q's body: a cycle stays in one stratum and is + // not rejected as unstratifiable. + let (_, base) = base_rule("q"); + let (_, neg) = negative_rule("q", "r"); + let (_, rec) = positive_rule("q", "q"); + let mut mixed_rec = neg; + mixed_rec.body.extend(rec.body); + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked("q".to_string(), base); + registry.register_rule_unchecked("q".to_string(), mixed_rec); + let strata = DependencyGraph::from_rules(®istry).stratify().unwrap(); + assert!(strata["q"] > strata["r"], "q above its negated r"); + } + + #[test] + fn test_caller_of_recursive_mixed_predicate_raised() { + // p →⁺ q, where q has a `not` and calls itself: q's cycle does not + // reach p, so p still sits above q. + let (_, neg) = negative_rule("q", "r"); + let (_, rec) = positive_rule("q", "q"); + let mut mixed_rec = neg; + mixed_rec.body.extend(rec.body); + let mut registry = make_registry_with_rules(vec![positive_rule("p", "q")]); + registry.register_rule_unchecked("q".to_string(), mixed_rec); + let strata = DependencyGraph::from_rules(®istry).stratify().unwrap(); + assert!( + strata["p"] > strata["q"], + "p above its recursive mixed callee" + ); + } + #[test] fn test_negative_cycle_returns_error() { // p →⁻ q, q →⁻ p diff --git a/tests/not_join_test.rs b/tests/not_join_test.rs index 62c0810d97..b173e0e4a7 100644 --- a/tests/not_join_test.rs +++ b/tests/not_join_test.rs @@ -554,3 +554,90 @@ fn test_not_join_expression_only_body() { .unwrap(); assert_eq!(result_count(&result), 1, "only :a has ?v <= 1"); } + +// ── #628: a rule calling a rule with `not` / `not-join` / `or` ─────────────── + +fn issue_628_db() -> Minigraf { + let db = in_memory_db(); + db.execute( + "(transact [[:m1 :msg/actor :a1] + [:r1 :run/actor :a1] [:r1 :run/to :s1] + [:r2 :run/actor :a1] [:r2 :run/to :s2] [:r2 :run/done true]])", + ) + .unwrap(); + db +} + +#[test] +fn test_rule_calling_not_join_rule() { + let db = issue_628_db(); + db.execute( + "(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not-join [?r] [?r :run/done true])])", + ) + .unwrap(); + db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])") + .unwrap(); + db.execute("(rule [(st3 ?a ?s) (cur ?a ?s)])").unwrap(); + + let r = db + .execute("(query [:find ?m ?s :where [?m :msg/actor ?a] (cur ?a ?s)])") + .unwrap(); + assert_eq!(result_count(&r), 1, "query calling the not-join rule"); + let r = db + .execute("(query [:find ?m ?s :where (st ?m ?s)])") + .unwrap(); + assert_eq!(result_count(&r), 1, "rule calling the not-join rule"); + let r = db.execute("(query [:find ?s :where (st :m1 ?s)])").unwrap(); + assert_eq!(result_count(&r), 1, "literal argument"); + let r = db + .execute("(query [:find ?a ?s :where (st3 ?a ?s)])") + .unwrap(); + assert_eq!(result_count(&r), 1, "forwarding rule"); +} + +#[test] +fn test_rule_calling_not_rule() { + let db = issue_628_db(); + db.execute("(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not [?r :run/done true])])") + .unwrap(); + db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])") + .unwrap(); + let r = db + .execute("(query [:find ?m ?s :where (st ?m ?s)])") + .unwrap(); + assert_eq!(result_count(&r), 1, "rule calling the not rule"); +} + +#[test] +fn test_mixed_rule_calling_mixed_rule() { + let db = issue_628_db(); + db.execute( + "(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not-join [?r] [?r :run/done true])])", + ) + .unwrap(); + db.execute( + "(rule [(stm ?m ?s) [?m :msg/actor ?a] (cur ?a ?s) (not-join [?m] [?m :nope true])])", + ) + .unwrap(); + let r = db + .execute("(query [:find ?m ?s :where (stm ?m ?s)])") + .unwrap(); + assert_eq!(result_count(&r), 1, "caller alone"); + let r = db + .execute("(query [:find ?m ?s :where (cur ?a ?x) (stm ?m ?s)])") + .unwrap(); + assert_eq!(result_count(&r), 1, "callee asked first"); +} + +#[test] +fn test_rule_calling_or_rule() { + let db = issue_628_db(); + db.execute("(rule [(dest ?a ?s) [?r :run/actor ?a] (or [?r :run/to ?s] [?r :run/from ?s])])") + .unwrap(); + db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (dest ?a ?s)])") + .unwrap(); + let r = db + .execute("(query [:find ?m ?s :where (st ?m ?s)])") + .unwrap(); + assert_eq!(result_count(&r), 2, "rule calling the or rule"); +}