From 8b3615e89aa4a8851f509e97f2ef0353fe9bdeab Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 18 Oct 2026 13:24:11 +0530 Subject: [PATCH] fix(or): seed an or branch whose expression reads an outer variable (#620) Backport of the v3 fix (#622). apply_or_clauses evaluated plain or / or-join branches from an empty binding and joined the union back onto the incoming rows. A branch whose expression reads a variable only the outer row binds -- [(> ?v 1)] after [?e :n ?v] -- saw it unbound and matched nothing, so the or dropped rows silently, in queries and in rule bodies. branch_outer_reads names the variables a branch's expressions (its own and its nested branches') read but the branch does not bind by a pattern, rule invocation or expression output. A branch with any now takes a seeded path: each incoming row seeds a plain or's branches, and an or-join's join variables seed its branches per row (a new per-row path on v2, the one v3 uses for metadata reads). 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/executor.rs | 134 ++++++++++++++++++++++++++++++++- src/query/datalog/optimizer.rs | 4 +- tests/disjunction_test.rs | 112 +++++++++++++++++++++++++++ 7 files changed, 252 insertions(+), 7 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 993d3f9b77..fbe08f0643 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 `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 6f8ded8ac8..19c3996821 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 -**1283 tests** (1274 passing, 9 ignored; unit + integration + doc). +**1289 tests** (1280 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 ff147e2761..c9efbc7c1e 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 1283 tests +cargo test # run 1289 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 41e098e931..fe6c3daf20 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-16 with `cargo test` -**Result**: 1,274 passing tests and 9 ignored tests (1,283 total), including the golden-file corpus (#391) +**Result**: 1,280 passing tests and 9 ignored tests (1,289 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. +`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`. 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/executor.rs b/src/query/datalog/executor.rs index 95455e1b15..7cd7343966 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1300,6 +1300,49 @@ fn apply_not_clause_derived( .collect() } +/// The variables an `or` / `or-join` branch's expressions read that the branch +/// itself never binds — by a pattern, a rule invocation or an expression output, +/// its own or an enclosing nested branch's. Only the outer row can bind them, so +/// a branch with any must be seeded with that row, not evaluated from an empty +/// binding and joined afterwards (#620). +pub(crate) fn branch_outer_reads(branch: &[WhereClause]) -> std::collections::HashSet { + let mut bound = std::collections::HashSet::new(); + for c in branch { + match c { + WhereClause::Pattern(p) => bound.extend(optimizer::pattern_bound_vars(p)), + WhereClause::RuleInvocation { args, .. } => { + for a in args { + if let EdnValue::Symbol(s) = a + && s.starts_with('?') + { + bound.insert(s.clone()); + } + } + } + WhereClause::Expr { + binding: Some(b), .. + } => { + bound.insert(b.clone()); + } + _ => {} + } + } + let mut reads = std::collections::HashSet::new(); + for c in branch { + match c { + WhereClause::Expr { expr, .. } => reads.extend(optimizer::expr_vars(expr)), + WhereClause::Or(branches) | WhereClause::OrJoin { branches, .. } => { + for b in branches { + reads.extend(branch_outer_reads(b)); + } + } + _ => {} + } + } + reads.retain(|v| !bound.contains(v)); + reads +} + /// Filter `bindings` through a single `(not-join [...] ...)` body for the rules query /// path — no exclusion-set fast path here (matches the pre-#248 post-filter, which /// never had one for this path either). @@ -1858,10 +1901,12 @@ pub(crate) fn apply_or_clauses( }; // If any branch contains Not/NotJoin clauses (which need bound variables // from the outer scope to evaluate correctly), fall back to the classic - // seeded-branch evaluation to preserve correctness. + // seeded-branch evaluation to preserve correctness. So does a branch + // whose expression reads a variable only the outer row binds (#620). let any_branch_has_not = sorted_or_branches.iter().any(|b| { b.iter() .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) + || !branch_outer_reads(b).is_empty() }); if any_branch_has_not { @@ -2077,6 +2122,53 @@ pub(crate) fn apply_or_clauses( } } + // A branch whose expression reads a join variable it does not + // bind itself (#620) needs it from the outer row: evaluate the + // branches per row, seeded with its join variables only (the + // others are fresh inside), and keep the distinct rows some + // branch matches, as the joined path below does. + if sorted_oj_branches + .iter() + .any(|b| !branch_outer_reads(b).is_empty()) + { + let mut seen: std::collections::HashSet> = + std::collections::HashSet::new(); + let mut result: Vec = Vec::new(); + for incoming in &bindings { + let seed: Binding = join_vars + .iter() + .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + let mut matched = false; + for branch in &sorted_oj_branches { + if !evaluate_branch( + branch, + vec![seed.clone()], + storage.clone(), + rules, + as_of.clone(), + valid_at.clone(), + registry, + )? + .is_empty() + { + matched = true; + break; + } + } + let mut key: Vec<_> = incoming + .iter() + .map(|(k, v)| (k.clone(), v.clone())) + .collect(); + key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if matched && seen.insert(key) { + result.push(incoming.clone()); + } + } + bindings = result; + continue; + } + let empty_seed: Vec = vec![HashMap::new()]; let mut seen_proj: std::collections::HashSet> = std::collections::HashSet::new(); @@ -5046,6 +5138,46 @@ mod expr_eval_tests { // ── evaluate_branch / apply_or_clauses edge cases ──────────────────────── + /// The branches of the query's last `or` / `or-join` clause. + fn last_or_branches(q: &str) -> Vec> { + let DatalogCommand::Query(query) = parse_datalog_command(q).expect("parse failed") else { + panic!("expected a query"); + }; + match query.where_clauses.last() { + Some(WhereClause::Or(b)) | Some(WhereClause::OrJoin { branches: b, .. }) => b.clone(), + _ => panic!("expected an or clause last"), + } + } + + #[test] + fn test_branch_outer_reads() { + let b = last_or_branches( + "(query [:find ?v :where [?e :n ?v] (or [(> ?v 1)] (and [?e :n ?v] [(< ?v 0)]))])", + ); + assert!(branch_outer_reads(&b[0]).contains("?v"), "reads outer ?v"); + assert!(branch_outer_reads(&b[1]).is_empty(), "binds ?v itself"); + + // A nested branch's private variable is not an outer read; the + // enclosing branch's variable is bound for the nested one. + let b = last_or_branches( + "(query [:find ?v :where [?e :n ?v] (or (and [?e :n ?v] (or-join [?v] (and [?x :n ?y] [(> ?y ?v)]))) [?e :n 5])])", + ); + assert!(branch_outer_reads(&b[0]).is_empty(), "nested reads bound"); + let b = last_or_branches( + "(query [:find ?v :where [?e :n ?v] (or (or [(> ?v 1)] [(< ?v 0)]) [?e :n 5])])", + ); + assert!( + branch_outer_reads(&b[0]).contains("?v"), + "nested reads outer" + ); + + // An expression output is bound by the branch. + let b = last_or_branches( + "(query [:find ?w :where [?e :n ?v] (or (and [?e :n ?v] [(+ ?v 1) ?w] [(> ?w 1)]) [?e :n ?w])])", + ); + assert!(branch_outer_reads(&b[0]).is_empty(), "?w bound by output"); + } + #[test] fn test_evaluate_branch_with_timestamp_valid_at() { // Exercises executor.rs lines 930-931: evaluate_branch with Timestamp/AnyValidTime diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index ed4e959c2a..69b78ccea3 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -81,7 +81,7 @@ pub fn select_index(p: &Pattern) -> IndexHint { } /// Collect all logic-variable names (`?foo`) referenced in an Expr tree. -fn expr_vars(expr: &Expr) -> Vec { +pub(crate) fn expr_vars(expr: &Expr) -> Vec { match expr { Expr::Var(s) => vec![s.clone()], Expr::Lit(_) | Expr::Slot(_) => vec![], @@ -96,7 +96,7 @@ fn expr_vars(expr: &Expr) -> Vec { /// Collect the logic-variable names bound (output) by a Pattern. /// Only Symbol values starting with `?` count — literals never bind. -fn pattern_bound_vars(p: &Pattern) -> Vec { +pub(crate) fn pattern_bound_vars(p: &Pattern) -> Vec { let mut vars = Vec::new(); if is_variable(&p.entity) && let EdnValue::Symbol(s) = &p.entity diff --git a/tests/disjunction_test.rs b/tests/disjunction_test.rs index af9c14ba4c..a5fd64701d 100644 --- a/tests/disjunction_test.rs +++ b/tests/disjunction_test.rs @@ -754,3 +754,115 @@ fn test_or_cross_product_after_pseudo_attribute() { .unwrap(); assert_eq!(result_count(&r), 2, "two edges, one tx-count each, one ?p"); } + +// ── #620: an `or` branch whose expression reads an outer variable ──────────── + +fn n_db() -> Minigraf { + let db = db(); + db.execute("(transact [[:a :n 1] [:b :n 2]])").unwrap(); + db +} + +/// The query's rows, each as comma-joined integers, sorted. +fn int_rows(db: &Minigraf, q: &str) -> Vec { + let QueryResult::QueryResults { results, .. } = db.execute(q).unwrap() else { + panic!("expected QueryResults"); + }; + let mut rows: Vec = results + .iter() + .map(|r| { + r.iter() + .map(|v| match v { + Value::Integer(i) => i.to_string(), + _ => panic!("expected integers"), + }) + .collect::>() + .join(",") + }) + .collect(); + rows.sort(); + rows +} + +#[test] +fn test_or_branch_expression_reads_outer_variable() { + let db = n_db(); + let r = int_rows( + &db, + "(query [:find ?v :where [?e :n ?v] (or [(> ?v 1)] [(< ?v 0)])])", + ); + assert_eq!(r, vec!["2"], "only ?v = 2 is over 1"); + let r = int_rows( + &db, + "(query [:find ?w :where [?e :n ?v] (or (and [(= ?v 1)] [?e :n ?w]) (and [(= ?v 2)] [?e :n ?w]))])", + ); + assert_eq!(r, vec!["1", "2"], "each row matches one branch"); + let r = int_rows( + &db, + "(query [:find ?v :where [?e :n ?v] (or (and [?e :n ?v] [(> ?v 1)]) [(< ?v 0)])])", + ); + assert_eq!(r, vec!["2"], "mixed branches"); +} + +#[test] +fn test_or_branch_expression_binds_from_outer_variable() { + let db = n_db(); + let r = int_rows( + &db, + "(query [:find ?v ?w :where [?e :n ?v] (or [(+ ?v 10) ?w] [(- ?v 10) ?w])])", + ); + assert_eq!( + r, + vec!["1,-9", "1,11", "2,-8", "2,12"], + "both branches bind ?w from ?v" + ); +} + +#[test] +fn test_nested_or_expression_reads_variable_of_enclosing_branch() { + let db = n_db(); + let r = int_rows( + &db, + "(query [:find ?v :where [?e :n ?v] (or (and [?e :n ?v] (or [(> ?v 1)] [(< ?v 0)])) [?e :n 5])])", + ); + assert_eq!(r, vec!["2"], "the inner or sees ?v"); + let r = int_rows( + &db, + "(query [:find ?v :where [?e :n ?v] (or (or [(> ?v 1)] [(< ?v 0)]) [?e :n 5])])", + ); + assert_eq!(r, vec!["2"], "the inner or sees the outer ?v"); +} + +#[test] +fn test_or_join_branch_expression_reads_join_variable() { + let db = n_db(); + let r = int_rows( + &db, + "(query [:find ?v :where [?e :n ?v] (or-join [?v] [(> ?v 1)] [(< ?v 0)])])", + ); + assert_eq!(r, vec!["2"], "only ?v = 2 is over 1"); + let r = int_rows( + &db, + "(query [:find ?v :where [?e :n ?v] (or-join [?v] (and [?x :n ?y] [(> ?v ?y)]) [(< ?v 0)])])", + ); + assert_eq!(r, vec!["2"], "2 is over some ?y, 1 is not"); +} + +#[test] +fn test_or_branch_expression_reads_outer_variable_in_rule_body() { + let db = n_db(); + db.execute("(rule [(big ?e) [?e :n ?v] (or [(> ?v 1)] [(< ?v 0)])])") + .unwrap(); + db.execute("(rule [(big2 ?e) [?e :n ?v] (or-join [?v] [(> ?v 1)] [(< ?v 0)])])") + .unwrap(); + db.execute( + "(rule [(pick ?e ?w) [?e :n ?v] (or (and [(= ?v 1)] [?e :n ?w]) (and [(= ?v 2)] [?e :n ?w]))])", + ) + .unwrap(); + let r = int_rows(&db, "(query [:find ?v :where (big ?e) [?e :n ?v]])"); + assert_eq!(r, vec!["2"], "or in a rule body"); + let r = int_rows(&db, "(query [:find ?v :where (big2 ?e) [?e :n ?v]])"); + assert_eq!(r, vec!["2"], "or-join in a 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"); +}