diff --git a/CHANGELOG.md b/CHANGELOG.md index d3f1ce6a23..07ca128e88 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -13,6 +13,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **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. +- **Recursion through a rule with `not`, `not-join`, `or` or `or-join` returns all its rows** (#633). Within a stratum such a rule ran once, after the rules without those clauses had reached their fixpoint, so its rows never fed back into the recursion: `(rule [(reach ?x ?y) [?x :e ?z] (reach ?z ?y) (not [?y :blocked true])])` stopped after one step and returned 7 of 10 pairs on a four-edge chain, with no error. A stratum whose rules call such a rule in it now repeats until that rule derives nothing new, bounded by the rule limits (INT-020), and the rule no longer adds a row it already derived. `max_results` now counts every fact the rules derive in one evaluation, across strata and repeated passes, as documented; it used to count each stratum's rules without those clauses separately and not the rules with them at all. - **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 7efb3c9cc5..9e8025f767 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -120,7 +120,7 @@ cargo run < demos/demo_negation.txt - `parser.rs`: EDN/Datalog parser — `transact`, `retract`, `query`, `rule`, `:as-of`, `:valid-at`, `not`, `not-join` - `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` + - `evaluator.rs`: `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator` (repeats a stratum whose rules recurse through a `not`/`or` rule until it derives nothing new, #633), `evaluate_not_join` - `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 @@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1300 tests** (1291 passing, 9 ignored; unit + integration + doc). +**1307 tests** (1298 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 54092457d4..55d5a0b6ce 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 1300 tests +cargo test # run 1307 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 1414574eb3..8094bafcc6 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-16 with `cargo test` -**Result**: 1,291 passing tests and 9 ignored tests (1,300 total), including the golden-file corpus (#391) +**Result**: 1,298 passing tests and 9 ignored tests (1,307 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 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). +`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). Tests in `tests/not_join_test.rs` check that recursion through a rule with `not`, `not-join` or `or`, directly or through another rule, returns every row along a chain, and that the `not` still removes the rows it should; evaluator unit tests check that such recursion stops at its fixpoint, that `max_iterations` and `max_results` end one that does not with INT-020, and that `max_results` counts the facts every pass derives, not only the mixed rule's (#633). 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 2e0013efec..6c7f31bbff 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -703,6 +703,9 @@ impl StratifiedEvaluator { drop(registry); // release read lock before recursive calls let accumulated = self.storage.clone(); + // Facts the rules derive, for `max_results` across strata and repeated + // passes (each pass's `RecursiveEvaluator` sees earlier ones as base). + let mut derived_total = 0usize; for stratum in 0..=max_stratum { let registry = self @@ -734,330 +737,420 @@ impl StratifiedEvaluator { } drop(registry); - // Evaluate positive-only rules via RecursiveEvaluator - if !positive_rules.is_empty() { - let mut sub_registry = RuleRegistry::new(); - for (pred, rule) in &positive_rules { - sub_registry.register_rule_unchecked(pred.clone(), rule.clone()); + // Recursion through a mixed rule stays in this stratum (#633): some + // rule here calls a mixed predicate of the stratum. Then the mixed + // rules' output feeds the positive rules and themselves, so the + // stratum repeats until the mixed pass derives nothing new. Every + // negated predicate sits in a lower, complete stratum, so this is + // monotone. + let mixed_preds: HashSet<&str> = mixed_rules.iter().map(|(p, _)| p.as_str()).collect(); + let repeat = positive_rules + .iter() + .chain(&mixed_rules) + .flat_map(|(_, rule)| rule.body.iter().flat_map(|c| c.rule_invocations())) + .any(|dep| mixed_preds.contains(dep)); + + let mut pass = 0; + loop { + pass += 1; + if pass > self.max_iterations { + return Err(err_coded!( + ErrorCode::Int020, + format!( + "Max iterations ({}) exceeded. Possible infinite recursion or cycle in rules.", + self.max_iterations + ) + )); } - let sub_rules = Arc::new(RwLock::new(sub_registry)); - let sub_eval = RecursiveEvaluator::new( - accumulated.clone(), - sub_rules, - self.functions.clone(), - self.max_iterations, - self.max_derived_facts, - self.max_results, - ) - .with_valid_at(self.valid_at.clone()); - let derived = sub_eval.evaluate_recursive_rules(&stratum_preds)?; - // Snapshot existing fact keys so we only load truly new (derived) facts - let existing: HashSet<(uuid::Uuid, String, Vec)> = accumulated - .get_asserted_facts()? - .into_iter() - .map(|f| { - let encoded = encode_value(&f.value); - (f.entity, f.attribute, encoded) - }) - .collect(); - for fact in derived.get_asserted_facts()? { - let key = ( - fact.entity, - fact.attribute.clone(), - encode_value(&fact.value), - ); - if !existing.contains(&key) { - let _ = accumulated.load_fact(fact); + + // Evaluate positive-only rules via RecursiveEvaluator + if !positive_rules.is_empty() { + let mut sub_registry = RuleRegistry::new(); + for (pred, rule) in &positive_rules { + sub_registry.register_rule_unchecked(pred.clone(), rule.clone()); } + let sub_rules = Arc::new(RwLock::new(sub_registry)); + let sub_eval = RecursiveEvaluator::new( + accumulated.clone(), + sub_rules, + self.functions.clone(), + self.max_iterations, + self.max_derived_facts, + self.max_results, + ) + .with_valid_at(self.valid_at.clone()); + let derived = sub_eval.evaluate_recursive_rules(&stratum_preds)?; + // Snapshot existing fact keys so we only load truly new (derived) facts + let existing: HashSet<(uuid::Uuid, String, Vec)> = accumulated + .get_asserted_facts()? + .into_iter() + .map(|f| { + let encoded = encode_value(&f.value); + (f.entity, f.attribute, encoded) + }) + .collect(); + for fact in derived.get_asserted_facts()? { + let key = ( + fact.entity, + fact.attribute.clone(), + encode_value(&fact.value), + ); + if !existing.contains(&key) { + derived_total += 1; + if derived_total > self.max_results { + return Err(err_coded!( + ErrorCode::Int020, + format!("Max query results ({}) exceeded.", self.max_results) + )); + } + let _ = accumulated.load_fact(fact); + } + } + accumulated.restore_tx_counter()?; } - accumulated.restore_tx_counter()?; - } - // Evaluate mixed rules (with not-filter) - for (_pred, rule) in &mixed_rules { - // Collect Pattern and Expr clauses for the planner. - // RuleInvocations are converted to Pattern; Not/NotJoin/Or/OrJoin extracted separately. - let mut plan_clauses: Vec = Vec::new(); - for c in &rule.body { - match c { - WhereClause::Pattern(_) | WhereClause::Expr { .. } => { - plan_clauses.push(c.clone()); - } - WhereClause::RuleInvocation { predicate, args } => { - let pattern = match args.len() { - 1 => args.first().map(|a0| { - Pattern::new( - a0.clone(), - EdnValue::Keyword(format!(":{}", predicate)), - EdnValue::Symbol("?_rule_value".to_string()), - ) - }), - 2 => args.first().and_then(|a0| { - args.get(1).map(|a1| { + // Evaluate mixed rules (with not-filter). A head already in + // `accumulated` is skipped, so a repeated pass sees what is new. + let mut known: HashSet<(uuid::Uuid, String, Vec)> = HashSet::new(); + if !mixed_rules.is_empty() { + known = accumulated + .get_asserted_facts()? + .into_iter() + .map(|f| { + let encoded = encode_value(&f.value); + (f.entity, f.attribute, encoded) + }) + .collect(); + } + let mut new_in_pass = 0usize; + for (_pred, rule) in &mixed_rules { + // Collect Pattern and Expr clauses for the planner. + // RuleInvocations are converted to Pattern; Not/NotJoin/Or/OrJoin extracted separately. + let mut plan_clauses: Vec = Vec::new(); + for c in &rule.body { + match c { + WhereClause::Pattern(_) | WhereClause::Expr { .. } => { + plan_clauses.push(c.clone()); + } + WhereClause::RuleInvocation { predicate, args } => { + let pattern = match args.len() { + 1 => args.first().map(|a0| { Pattern::new( a0.clone(), EdnValue::Keyword(format!(":{}", predicate)), - a1.clone(), + EdnValue::Symbol("?_rule_value".to_string()), ) - }) - }), - _ => None, - }; - if let Some(p) = pattern { - plan_clauses.push(WhereClause::Pattern(p)); + }), + 2 => args.first().and_then(|a0| { + args.get(1).map(|a1| { + Pattern::new( + a0.clone(), + EdnValue::Keyword(format!(":{}", predicate)), + a1.clone(), + ) + }) + }), + _ => None, + }; + if let Some(p) = pattern { + plan_clauses.push(WhereClause::Pattern(p)); + } } + WhereClause::Not(_) + | WhereClause::NotJoin { .. } + | WhereClause::Or(_) + | WhereClause::OrJoin { .. } => {} } - WhereClause::Not(_) - | WhereClause::NotJoin { .. } - | WhereClause::Or(_) - | WhereClause::OrJoin { .. } => {} } - } - #[cfg_attr(feature = "wasm", allow(unused_mut))] - let mut not_clauses: Vec> = rule - .body - .iter() - .filter_map(|c| match c { - WhereClause::Not(inner) => Some(inner.clone()), - _ => None, - }) - .collect(); - - #[cfg_attr(feature = "wasm", allow(unused_mut))] - let mut not_join_clauses: Vec<(Vec, Vec)> = rule - .body - .iter() - .filter_map(|c| match c { - WhereClause::NotJoin { join_vars, clauses } => { - Some((join_vars.clone(), clauses.clone())) - } - _ => None, - }) - .collect(); - - // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - not_clauses.sort_by_key(|body| { - crate::query::datalog::optimizer::clause_cost(&WhereClause::Not(body.clone())) - }); - // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - not_join_clauses.sort_by_key(|(vars, clauses)| { - crate::query::datalog::optimizer::clause_cost(&WhereClause::NotJoin { - join_vars: vars.clone(), - clauses: clauses.clone(), - }) - }); - - // Compute once; reuse for plan loop, apply_or_clauses, not-body matching. - let accumulated_facts: Arc<[Fact]> = Arc::from(accumulated.get_asserted_facts()?); - - let matcher = PatternMatcher::from_slice_with_valid_at( - accumulated_facts.clone(), - self.valid_at.clone(), - ); + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_clauses: Vec> = rule + .body + .iter() + .filter_map(|c| match c { + WhereClause::Not(inner) => Some(inner.clone()), + _ => None, + }) + .collect(); - // Plan: assigns index hints + pushes Expr to earliest binding position. - // Not/NotJoin are excluded from plan_clauses above, so `deferred` holds - // only expressions whose variables an Or/OrJoin binds (#625); they run - // after the or pass. Rule bodies keep their existing not-filter path. - let (planned, deferred) = crate::query::datalog::optimizer::plan( - plan_clauses, - &crate::storage::index::Indexes::new(), - ); + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_join_clauses: Vec<( + Vec, + Vec, + )> = rule + .body + .iter() + .filter_map(|c| match c { + WhereClause::NotJoin { join_vars, clauses } => { + Some((join_vars.clone(), clauses.clone())) + } + _ => None, + }) + .collect(); - // Process planned clauses in order: Pattern → join, Expr → filter/extend. - let fn_guard = self - .functions - .read() - .map_err(|_| err_coded!(ErrorCode::Qry008))?; - let mut candidates: Vec = vec![Bindings::new()]; - for (clause, hint) in planned { - match clause { - WhereClause::Pattern(p) => { - candidates = matcher.match_with_hint_seeded( - candidates, - &p, - hint.as_ref() - .unwrap_or(&crate::query::datalog::optimizer::IndexHint::Eavt), - ); - } - WhereClause::Expr { expr, binding: out } => { - use crate::query::datalog::executor::{eval_expr, is_truthy}; - candidates = candidates - .into_iter() - .filter_map(|mut b| match eval_expr(&expr, &b, Some(&fn_guard)) { - Ok(v) => { - if let Some(var) = &out { - b.insert(var.clone(), v); - Some(b) - } else if is_truthy(&v) { - Some(b) - } else { - None - } - } - Err(_) => None, - }) - .collect(); - } - _ => {} - } - } - drop(fn_guard); - - // Apply Or/OrJoin clauses (unchanged, applied after the plan loop). - let candidates = { - use crate::query::datalog::executor::apply_or_clauses; - use crate::query::datalog::functions::FunctionRegistry; - let registry_guard = self - .rules - .read() - .map_err(|_| err_coded!(ErrorCode::Qry009))?; - // Rule bodies in the semi-naive evaluator don't have access to a - // FunctionRegistry (UDF registration happens at the db layer). Use the - // built-in-only registry so or-branches can still use built-in predicates. - let fn_registry = FunctionRegistry::with_builtins(); - // An or branch binds `:db/valid-at` from a `ValidAt`, the - // inverse of the executor's mapping to `self.valid_at`. - let branch_valid_at = match &self.valid_at { - Value::Integer(t) => ValidAt::Timestamp(*t), - _ => ValidAt::AnyValidTime, - }; - let expanded = apply_or_clauses( - &rule.body, - candidates, + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_clauses.sort_by_key(|body| { + crate::query::datalog::optimizer::clause_cost(&WhereClause::Not( + body.clone(), + )) + }); + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_join_clauses.sort_by_key(|(vars, clauses)| { + crate::query::datalog::optimizer::clause_cost(&WhereClause::NotJoin { + join_vars: vars.clone(), + clauses: clauses.clone(), + }) + }); + + // Compute once; reuse for plan loop, apply_or_clauses, not-body matching. + let accumulated_facts: Arc<[Fact]> = + Arc::from(accumulated.get_asserted_facts()?); + + let matcher = PatternMatcher::from_slice_with_valid_at( accumulated_facts.clone(), - ®istry_guard, - None, - Some(branch_valid_at), - &fn_registry, - )?; - drop(registry_guard); - expanded - }; - let candidates = { + self.valid_at.clone(), + ); + + // Plan: assigns index hints + pushes Expr to earliest binding position. + // Not/NotJoin are excluded from plan_clauses above, so `deferred` holds + // only expressions whose variables an Or/OrJoin binds (#625); they run + // after the or pass. Rule bodies keep their existing not-filter path. + let (planned, deferred) = crate::query::datalog::optimizer::plan( + plan_clauses, + &crate::storage::index::Indexes::new(), + ); + + // Process planned clauses in order: Pattern → join, Expr → filter/extend. let fn_guard = self .functions .read() .map_err(|_| err_coded!(ErrorCode::Qry008))?; - let exprs: Vec<&WhereClause> = deferred.iter().collect(); - apply_expr_clauses_in_evaluator(candidates, &exprs, &fn_guard) - }; - - // Build temp_eval once per rule (outside the binding loop); - // instantiate_head_public only uses storage, not the registry. - let temp_eval = RecursiveEvaluator::new( - accumulated.clone(), - Arc::clone(&self.rules), - Arc::clone(&self.functions), - 1, - self.max_derived_facts, - self.max_results, - ); + let mut candidates: Vec = vec![Bindings::new()]; + for (clause, hint) in planned { + match clause { + WhereClause::Pattern(p) => { + candidates = matcher.match_with_hint_seeded( + candidates, + &p, + hint.as_ref().unwrap_or( + &crate::query::datalog::optimizer::IndexHint::Eavt, + ), + ); + } + WhereClause::Expr { expr, binding: out } => { + use crate::query::datalog::executor::{eval_expr, is_truthy}; + candidates = candidates + .into_iter() + .filter_map(|mut b| { + match eval_expr(&expr, &b, Some(&fn_guard)) { + Ok(v) => { + if let Some(var) = &out { + b.insert(var.clone(), v); + Some(b) + } else if is_truthy(&v) { + Some(b) + } else { + None + } + } + Err(_) => None, + } + }) + .collect(); + } + _ => {} + } + } + drop(fn_guard); + + // Apply Or/OrJoin clauses (unchanged, applied after the plan loop). + let candidates = { + use crate::query::datalog::executor::apply_or_clauses; + use crate::query::datalog::functions::FunctionRegistry; + let registry_guard = self + .rules + .read() + .map_err(|_| err_coded!(ErrorCode::Qry009))?; + // Rule bodies in the semi-naive evaluator don't have access to a + // FunctionRegistry (UDF registration happens at the db layer). Use the + // built-in-only registry so or-branches can still use built-in predicates. + let fn_registry = FunctionRegistry::with_builtins(); + // An or branch binds `:db/valid-at` from a `ValidAt`, the + // inverse of the executor's mapping to `self.valid_at`. + let branch_valid_at = match &self.valid_at { + Value::Integer(t) => ValidAt::Timestamp(*t), + _ => ValidAt::AnyValidTime, + }; + let expanded = apply_or_clauses( + &rule.body, + candidates, + accumulated_facts.clone(), + ®istry_guard, + None, + Some(branch_valid_at), + &fn_registry, + )?; + drop(registry_guard); + expanded + }; + let candidates = { + let fn_guard = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + let exprs: Vec<&WhereClause> = deferred.iter().collect(); + apply_expr_clauses_in_evaluator(candidates, &exprs, &fn_guard) + }; - 'binding: for binding in candidates { - for not_body in ¬_clauses { - let substituted: Vec = not_body - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(substitute_pattern(p, &binding)), - WhereClause::RuleInvocation { predicate, args } => { - let subst_args: Vec = args - .iter() - .map(|a| substitute_value(a, &binding)) - .collect(); - match subst_args.len() { - 1 => subst_args.first().map(|a0| { - Pattern::new( - a0.clone(), - EdnValue::Keyword(format!(":{}", predicate)), - EdnValue::Symbol("?_rule_value".to_string()), - ) - }), - 2 => subst_args.first().and_then(|a0| { - subst_args.get(1).map(|a1| { + // Build temp_eval once per rule (outside the binding loop); + // instantiate_head_public only uses storage, not the registry. + let temp_eval = RecursiveEvaluator::new( + accumulated.clone(), + Arc::clone(&self.rules), + Arc::clone(&self.functions), + 1, + self.max_derived_facts, + self.max_results, + ); + + 'binding: for binding in candidates { + for not_body in ¬_clauses { + let substituted: Vec = not_body + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => { + Some(substitute_pattern(p, &binding)) + } + WhereClause::RuleInvocation { predicate, args } => { + let subst_args: Vec = args + .iter() + .map(|a| substitute_value(a, &binding)) + .collect(); + match subst_args.len() { + 1 => subst_args.first().map(|a0| { Pattern::new( a0.clone(), EdnValue::Keyword(format!(":{}", predicate)), - a1.clone(), + EdnValue::Symbol("?_rule_value".to_string()), ) - }) - }), - _ => None, - } - } - WhereClause::Not(_) | WhereClause::NotJoin { .. } => None, - WhereClause::Expr { .. } => None, - WhereClause::Or(_) | WhereClause::OrJoin { .. } => None, // Or/OrJoin inside not bodies: rejected at parse time (see parser.rs). - }) - .collect(); - - let not_matcher = PatternMatcher::from_slice_with_valid_at( - accumulated_facts.clone(), - self.valid_at.clone(), - ); - let mut not_bindings: Vec = if substituted.is_empty() { - vec![binding.clone()] - } else { - not_matcher - .match_patterns(&substituted) - .into_iter() - .map(|mut nb| { - for (k, v) in &binding { - nb.entry(k.clone()).or_insert_with(|| v.clone()); + }), + 2 => subst_args.first().and_then(|a0| { + subst_args.get(1).map(|a1| { + Pattern::new( + a0.clone(), + EdnValue::Keyword(format!( + ":{}", + predicate + )), + a1.clone(), + ) + }) + }), + _ => None, + } } - nb + WhereClause::Not(_) | WhereClause::NotJoin { .. } => None, + WhereClause::Expr { .. } => None, + WhereClause::Or(_) | WhereClause::OrJoin { .. } => None, // Or/OrJoin inside not bodies: rejected at parse time (see parser.rs). }) - .collect() - }; + .collect(); - // Apply Expr clauses from the not body - let not_body_expr_clauses: Vec<&WhereClause> = not_body - .iter() - .filter(|c| matches!(c, WhereClause::Expr { .. })) - .collect(); - let fn_guard = self - .functions - .read() - .map_err(|_| err_coded!(ErrorCode::Qry008))?; - not_bindings = apply_expr_clauses_in_evaluator( - not_bindings, - ¬_body_expr_clauses, - &fn_guard, - ); - drop(fn_guard); - if !not_bindings.is_empty() { - continue 'binding; // not condition violated -> discard binding + let not_matcher = PatternMatcher::from_slice_with_valid_at( + accumulated_facts.clone(), + self.valid_at.clone(), + ); + let mut not_bindings: Vec = if substituted.is_empty() { + vec![binding.clone()] + } else { + not_matcher + .match_patterns(&substituted) + .into_iter() + .map(|mut nb| { + for (k, v) in &binding { + nb.entry(k.clone()).or_insert_with(|| v.clone()); + } + nb + }) + .collect() + }; + + // Apply Expr clauses from the not body + let not_body_expr_clauses: Vec<&WhereClause> = not_body + .iter() + .filter(|c| matches!(c, WhereClause::Expr { .. })) + .collect(); + let fn_guard = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + not_bindings = apply_expr_clauses_in_evaluator( + not_bindings, + ¬_body_expr_clauses, + &fn_guard, + ); + drop(fn_guard); + if !not_bindings.is_empty() { + continue 'binding; // not condition violated -> discard binding + } } - } - for (join_vars, nj_clauses) in ¬_join_clauses { - let fn_guard = self - .functions - .read() - .map_err(|_| err_coded!(ErrorCode::Qry008))?; - if evaluate_not_join( - join_vars, - nj_clauses, - &binding, - accumulated_facts.clone(), - self.valid_at.clone(), - &fn_guard, - ) { - continue 'binding; + for (join_vars, nj_clauses) in ¬_join_clauses { + let fn_guard = self + .functions + .read() + .map_err(|_| err_coded!(ErrorCode::Qry008))?; + if evaluate_not_join( + join_vars, + nj_clauses, + &binding, + accumulated_facts.clone(), + self.valid_at.clone(), + &fn_guard, + ) { + continue 'binding; + } } - } - // All Not / NotJoin conditions held -> derive head fact - if let Ok(fact) = temp_eval.instantiate_head_public(&rule.head, &binding) { - // Use transact (not load_fact) so derived facts get a proper - // tx_id and incremented tx_count, matching spec step (d). - let _ = accumulated - .transact(vec![(fact.entity, fact.attribute, fact.value)], None); + // All Not / NotJoin conditions held -> derive head fact + if let Ok(fact) = temp_eval.instantiate_head_public(&rule.head, &binding) { + let key = ( + fact.entity, + fact.attribute.clone(), + encode_value(&fact.value), + ); + if !known.insert(key) { + continue; + } + new_in_pass += 1; + if new_in_pass > self.max_derived_facts { + return Err(err_coded!( + ErrorCode::Int020, + format!( + "Max derived facts per iteration ({}) exceeded. Rule may be generating too many facts.", + self.max_derived_facts + ) + )); + } + derived_total += 1; + if derived_total > self.max_results { + return Err(err_coded!( + ErrorCode::Int020, + format!("Max query results ({}) exceeded.", self.max_results) + )); + } + // Use transact (not load_fact) so derived facts get a proper + // tx_id and incremented tx_count, matching spec step (d). + let _ = accumulated + .transact(vec![(fact.entity, fact.attribute, fact.value)], None); + } } } + + if !repeat || new_in_pass == 0 { + break; + } } } @@ -1677,4 +1770,94 @@ mod tests { .collect(); assert_eq!(eligible.len(), 1, "only e2 is eligible (e3 is blocked)"); } + + /// A counter that recurses through a rule with `not` (#633). + fn counter_evaluator( + guard: &str, + max_iterations: usize, + max_results: usize, + ) -> StratifiedEvaluator { + let storage = FactStorage::new(); + storage + .transact( + vec![(Uuid::new_v4(), ":start".to_string(), Value::Integer(0))], + None, + ) + .unwrap(); + let rules = Arc::new(RwLock::new(RuleRegistry::new())); + let functions = Arc::new(RwLock::new(FunctionRegistry::with_builtins())); + register_test_rule(&rules, "(rule [(n ?x ?v) [?x :start ?v]])"); + register_test_rule( + &rules, + &format!("(rule [(n ?x ?w) (n ?x ?v) {guard} [(+ ?v 1) ?w] (not [?x :stop true])])"), + ); + StratifiedEvaluator::new( + storage, + rules, + functions, + max_iterations, + DEFAULT_MAX_DERIVED_FACTS, + max_results, + ) + } + + #[test] + fn test_recursion_through_mixed_rule_reaches_fixpoint() { + let derived = counter_evaluator("[(< ?v 3)]", DEFAULT_MAX_ITERATIONS, DEFAULT_MAX_RESULTS) + .evaluate(&["n".to_string()]) + .unwrap(); + let n = derived + .get_asserted_facts() + .unwrap() + .into_iter() + .filter(|f| f.attribute == ":n") + .count(); + assert_eq!(n, 4, "n is 0, 1, 2 and 3"); + } + + #[test] + fn test_recursion_through_mixed_rule_max_iterations() { + let result = counter_evaluator("", 5, DEFAULT_MAX_RESULTS).evaluate(&["n".to_string()]); + assert_eq!(expect_err_code(result), "INT-020"); + } + + #[test] + fn test_recursion_through_mixed_rule_max_results() { + let result = counter_evaluator("", DEFAULT_MAX_ITERATIONS, 3).evaluate(&["n".to_string()]); + assert_eq!(expect_err_code(result), "INT-020"); + } + + #[test] + fn test_recursion_through_mixed_rule_max_results_counts_every_pass() { + // n0 → m0 → n1 → m1 → n2 → m2 → n3: seven facts, three from the mixed + // rule and one from each positive pass. + let rules = Arc::new(RwLock::new(RuleRegistry::new())); + register_test_rule(&rules, "(rule [(n ?x ?v) [?x :start ?v]])"); + register_test_rule(&rules, "(rule [(n ?x ?w) (m ?x ?v) [(+ ?v 1) ?w]])"); + register_test_rule( + &rules, + "(rule [(m ?x ?v) (n ?x ?v) [(< ?v 3)] (not [?x :stop true])])", + ); + let evaluator = |max_results| { + // The evaluator adds what it derives to this storage. + let storage = FactStorage::new(); + storage + .transact( + vec![(Uuid::new_v4(), ":start".to_string(), Value::Integer(0))], + None, + ) + .unwrap(); + StratifiedEvaluator::new( + storage, + Arc::clone(&rules), + Arc::new(RwLock::new(FunctionRegistry::with_builtins())), + DEFAULT_MAX_ITERATIONS, + DEFAULT_MAX_DERIVED_FACTS, + max_results, + ) + }; + evaluator(7).evaluate(&["n".to_string()]).unwrap(); + let result = evaluator(6).evaluate(&["n".to_string()]); + assert_eq!(expect_err_code(result), "INT-020"); + } } diff --git a/tests/not_join_test.rs b/tests/not_join_test.rs index b173e0e4a7..4b892826a4 100644 --- a/tests/not_join_test.rs +++ b/tests/not_join_test.rs @@ -641,3 +641,63 @@ fn test_rule_calling_or_rule() { .unwrap(); assert_eq!(result_count(&r), 2, "rule calling the or rule"); } + +// ── #633: recursion through a rule with `not` / `not-join` / `or` ──────────── + +fn issue_633_db() -> Minigraf { + let db = in_memory_db(); + db.execute("(transact [[:a :e :b] [:b :e :c] [:c :e :d] [:d :e :f]])") + .unwrap(); + db +} + +#[test] +fn test_recursion_through_not_rule() { + let db = issue_633_db(); + db.execute("(rule [(reach ?x ?y) [?x :e ?y]])").unwrap(); + db.execute("(rule [(reach ?x ?y) [?x :e ?z] (reach ?z ?y) (not [?y :blocked true])])") + .unwrap(); + let r = db + .execute("(query [:find ?x ?y :where (reach ?x ?y)])") + .unwrap(); + assert_eq!(result_count(&r), 10, "every pair along the chain"); + + // The `not` still filters what the recursion derives: (a d) and (b d) go. + db.execute("(transact [[:d :blocked true]])").unwrap(); + let r = db + .execute("(query [:find ?x ?y :where (reach ?x ?y)])") + .unwrap(); + assert_eq!(result_count(&r), 8, "pairs ending at :d only by one edge"); +} + +#[test] +fn test_mutual_recursion_through_not_join_rule() { + let db = issue_633_db(); + db.execute("(rule [(p ?x ?y) [?x :e ?y]])").unwrap(); + db.execute("(rule [(p ?x ?y) [?x :e ?z] (q ?z ?y)])") + .unwrap(); + db.execute("(rule [(q ?x ?y) (p ?x ?y) (not-join [?y] [?y :blocked true])])") + .unwrap(); + let r = db + .execute("(query [:find ?x ?y :where (p ?x ?y)])") + .unwrap(); + assert_eq!(result_count(&r), 10, "p through q"); + let r = db + .execute("(query [:find ?x ?y :where (q ?x ?y)])") + .unwrap(); + assert_eq!(result_count(&r), 10, "q through p"); +} + +#[test] +fn test_recursion_through_or_rule() { + // The `or` reads `?x`, which an entity pattern binds: on v2.x an `or` + // branch compares a keyword and a ref exactly (changed in v3.0.0, #546). + let db = issue_633_db(); + db.execute("(rule [(reach ?x ?y) [?x :e ?y]])").unwrap(); + db.execute("(rule [(reach ?x ?y) [?x :e ?z] (reach ?z ?y) (or [?x :e _] [?x :tail true])])") + .unwrap(); + let r = db + .execute("(query [:find ?x ?y :where (reach ?x ?y)])") + .unwrap(); + assert_eq!(result_count(&r), 10, "every pair along the chain"); +}