From 918598f2242eff6f51044d2a5457c5393994bdd0 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Mon, 19 Oct 2026 19:51:44 +0530 Subject: [PATCH] fix(query): run an expression reading an or-bound variable after the ors (#625, backport) Backport of #629 from v3. optimizer::plan appended an expression whose variable only an or / or-join binds to the end of the planned list, and the ors run after that list, so the expression saw the variable unbound and dropped every row, in queries and in rule bodies. plan now defers an expression that reads a variable no pattern in the list and no expression placed before it binds, ahead of the deferred nots and in text order. Both executor deferred passes run it after apply_or_clauses (via apply_expr_clauses; expressions cost 0, so the stable cheapest-first sort keeps them first), and the rule-body evaluator applies it after its or pass. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +- src/query/datalog/evaluator.rs | 15 ++++-- src/query/datalog/executor.rs | 19 ++++++-- src/query/datalog/optimizer.rs | 88 ++++++++++++++++++++++++++-------- tests/disjunction_test.rs | 38 +++++++++++++++ 8 files changed, 136 insertions(+), 33 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index fbe08f0643..8eb9e4c3b0 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -11,6 +11,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. - **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 19c3996821..1fa2881644 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 -**1289 tests** (1280 passing, 9 ignored; unit + integration + doc). +**1293 tests** (1284 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 c9efbc7c1e..c1e4a6a563 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 1289 tests +cargo test # run 1293 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index fe6c3daf20..91a54696ae 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-16 with `cargo test` -**Result**: 1,280 passing tests and 9 ignored tests (1,289 total), including the golden-file corpus (#391) +**Result**: 1,284 passing tests and 9 ignored tests (1,293 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`. +`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. 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 1dad9eb488..110c21b612 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -868,9 +868,10 @@ impl StratifiedEvaluator { ); // Plan: assigns index hints + pushes Expr to earliest binding position. - // Not/NotJoin are excluded from plan_clauses above, so `deferred` is - // always empty here — rule bodies keep their existing not-filter path. - let (planned, _deferred) = crate::query::datalog::optimizer::plan( + // 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(), ); @@ -945,6 +946,14 @@ impl StratifiedEvaluator { 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) + }; // Build temp_eval once per rule (outside the binding loop); // instantiate_head_public only uses storage, not the registry. diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 7cd7343966..a4254f65ff 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -595,15 +595,20 @@ impl DatalogExecutor { )?; drop(rules_guard); - // Apply Not/NotJoin clauses the planner couldn't place inline (#248) — their - // variables are only bound by the Or/OrJoin pass above, so they must run here, - // after it. Sorted cheapest-first, same as the pre-#248 post-filter ordering. + // Apply Not/NotJoin clauses the planner couldn't place inline (#248), and + // expressions (#625) — their variables are only bound by the Or/OrJoin pass + // above, so they must run here, after it. Sorted cheapest-first, same as the + // pre-#248 post-filter ordering; expressions cost 0 and come first, so a + // stable sort keeps them ahead of the nots, in text order. #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut deferred_not_clauses = deferred_not_clauses; #[cfg(not(feature = "wasm"))] deferred_not_clauses.sort_by_key(optimizer::clause_cost); for clause in deferred_not_clauses { bindings = match clause { + c @ WhereClause::Expr { .. } => { + apply_expr_clauses(bindings, std::slice::from_ref(&c), ®istry)? + } WhereClause::Not(body) => apply_not_clause( bindings, &body, @@ -846,8 +851,9 @@ impl DatalogExecutor { )?; drop(rules_guard); - // Apply Not/NotJoin clauses the planner couldn't place inline (#248) — their - // variables are only bound by the Or/OrJoin pass above. (The StratifiedEvaluator + // Apply Not/NotJoin clauses the planner couldn't place inline (#248), and + // expressions (#625) — their variables are only bound by the Or/OrJoin pass + // above. Expressions come first, as above. (The StratifiedEvaluator // handles `not`/`not-join` in rule bodies; this handles them appearing directly // in the query body alongside rule invocations.) #[cfg_attr(feature = "wasm", allow(unused_mut))] @@ -856,6 +862,9 @@ impl DatalogExecutor { deferred_not_clauses.sort_by_key(optimizer::clause_cost); for clause in deferred_not_clauses { bindings = match clause { + c @ WhereClause::Expr { .. } => { + apply_expr_clauses(bindings, std::slice::from_ref(&c), ®istry)? + } WhereClause::Not(body) => apply_not_clause_derived( bindings, &body, diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index 69b78ccea3..f55461f870 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -165,6 +165,11 @@ fn clause_ref_vars(clauses: &[WhereClause]) -> std::collections::HashSet /// clause, which the executor applies after this plan) and must be evaluated by the /// executor's post-filter instead, to avoid running it before its dependency is bound. /// +/// An `Expr` reading a variable that no pattern in the list and no `Expr` placed +/// before it binds is deferred the same way (#625), ahead of the deferred +/// `Not`/`NotJoin` clauses and in text order, since a deferred `not` may read what +/// it binds. +/// /// Returns `(interleaved, deferred)` where `interleaved` pairs each Pattern with /// `Some(hint)` and each Expr/Not/NotJoin with `None`. pub fn plan( @@ -208,16 +213,33 @@ pub fn plan( .collect(); // Push each Expr to the earliest position where all its variables are bound. + // An Expr reading a variable that no pattern here and no Expr placed before + // it binds depends on a source outside this list (an Or/OrJoin, #625): it is + // deferred, ahead of the deferred nots, which may read what it binds. + let mut deferred: Vec = Vec::new(); + let mut placeable: std::collections::HashSet = result + .iter() + .flat_map(|(c, _)| match c { + WhereClause::Pattern(p) => pattern_bound_vars(p), + _ => Vec::new(), + }) + .collect(); for expr_clause in exprs { - let vars: std::collections::HashSet = - if let WhereClause::Expr { expr, .. } = &expr_clause { - expr_vars(expr).into_iter().collect() + let (vars, out): (std::collections::HashSet, Option) = + if let WhereClause::Expr { expr, binding } = &expr_clause { + (expr_vars(expr).into_iter().collect(), binding.clone()) } else { Default::default() }; + if !vars.is_subset(&placeable) { + deferred.push(expr_clause); + continue; + } + placeable.extend(out); let mut bound: std::collections::HashSet = Default::default(); - // Default: append at end (covers no-var Exprs and vars never bound by any pattern). + // Default: append at end (covers no-var Exprs and Exprs reading what an + // Expr placed earlier binds). let mut insert_pos = result.len(); if !vars.is_empty() { @@ -243,7 +265,6 @@ pub fn plan( #[cfg(not(feature = "wasm"))] not_clauses.sort_by_key(|c| std::cmp::Reverse(clause_cost(c))); - let mut deferred: Vec = Vec::new(); for nc in not_clauses { let required: std::collections::HashSet = match &nc { // `?_`-prefixed vars are the wildcard idiom (e.g. `(not [?e :attr ?_x])`) @@ -601,26 +622,51 @@ mod tests { ); } - #[cfg(not(feature = "wasm"))] - #[test] - fn test_expr_unbound_var_goes_to_end() { - use crate::storage::index::Indexes; - // ?x is never bound by any pattern - let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); - let expr = WhereClause::Expr { + fn gt(v: &str, n: i64, binding: Option<&str>) -> WhereClause { + WhereClause::Expr { expr: Expr::BinOp( BinOp::Gt, - Box::new(Expr::Var("?x".to_string())), - Box::new(Expr::Lit(Value::Integer(0))), + Box::new(Expr::Var(v.to_string())), + Box::new(Expr::Lit(Value::Integer(n))), ), - binding: None, - }; - let (planned, _deferred) = plan(vec![p1, expr], &Indexes::new()); - assert_eq!(planned.len(), 2); - assert!( - matches!(planned[1].0, WhereClause::Expr { .. }), - "Expr with unbound var must be last" + binding: binding.map(str::to_string), + } + } + + #[test] + fn test_expr_unbound_var_is_deferred() { + use crate::storage::index::Indexes; + // ?x is never bound by any pattern: an Or binds it, after the plan (#625). + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); + let expr = gt("?x", 0, None); + let (planned, deferred) = plan(vec![p1, expr.clone()], &Indexes::new()); + assert_eq!(planned.len(), 1, "the Expr must not be planned"); + assert_eq!(deferred, vec![expr]); + } + + #[test] + fn test_expr_reading_placed_expr_output_is_planned() { + use crate::storage::index::Indexes; + // ?y comes from an Expr whose input a pattern binds: both are planned. + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); + let (bind, read) = (gt("?v", 0, Some("?y")), gt("?y", 0, None)); + let (planned, deferred) = plan(vec![p1, bind, read], &Indexes::new()); + assert!(deferred.is_empty()); + assert_eq!(planned.len(), 3); + } + + #[test] + fn test_deferred_exprs_come_before_deferred_nots_in_text_order() { + use crate::storage::index::Indexes; + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); + let not_clause = WhereClause::Not(vec![gt("?y", 0, None)]); + let (bind, read) = (gt("?x", 0, Some("?y")), gt("?y", 0, None)); + let (planned, deferred) = plan( + vec![p1, not_clause.clone(), bind.clone(), read.clone()], + &Indexes::new(), ); + assert_eq!(planned.len(), 1); + assert_eq!(deferred, vec![bind, read, not_clause]); } // ── Not/NotJoin push-down (#248) ───────────────────────────────────── diff --git a/tests/disjunction_test.rs b/tests/disjunction_test.rs index a5fd64701d..ab39ce2b10 100644 --- a/tests/disjunction_test.rs +++ b/tests/disjunction_test.rs @@ -866,3 +866,41 @@ fn test_or_branch_expression_reads_outer_variable_in_rule_body() { let r = int_rows(&db, "(query [:find ?w :where (pick ?e ?w)])"); assert_eq!(r, vec!["1", "2"], "or-and in a rule body"); } + +// ── #625: an expression reading a variable only an `or` binds ──────────────── + +fn issue_625_db() -> Minigraf { + let db = db(); + db.execute("(transact [[:a :n 1] [:b :n 2] [:c :ok true]])") + .unwrap(); + db +} + +#[test] +fn test_expression_after_or_reads_or_bound_variable() { + let db = issue_625_db(); + let r = db + .execute("(query [:find ?e ?x :where [?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]])") + .unwrap(); + assert_eq!(result_count(&r), 1, "only :b has ?x over 1"); + let r = db + .execute( + "(query [:find ?y :where [?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(+ ?x 10) ?y] (not [(> ?y 11)])])", + ) + .unwrap(); + assert_eq!(result_count(&r), 1, "the not sees the expression's ?y"); +} + +#[test] +fn test_expression_after_or_reads_or_bound_variable_with_rules() { + let db = issue_625_db(); + db.execute("(rule [(num ?e) [?e :n _]])").unwrap(); + db.execute("(rule [(big ?e ?x) [?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]])") + .unwrap(); + let r = db + .execute("(query [:find ?x :where (num ?e) (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]])") + .unwrap(); + assert_eq!(result_count(&r), 1, "query calling a rule"); + let r = db.execute("(query [:find ?x :where (big ?e ?x)])").unwrap(); + assert_eq!(result_count(&r), 1, "rule body"); +}