From 44bad1a44a24be93c03a27b2e51da2393adffa6e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 20 Oct 2026 03:07:05 +0530 Subject: [PATCH] fix(or): an or branch meets a keyword value as the entity it names (#637) The joined or / or-join path keyed its hash join on exact values, so a keyword bound by an outer pattern never met the ref a branch bound for the entity it names (and the reverse): those rows were dropped with no error. Key the join, and the #250 short-circuit's coverage check, on normalize_value, as the not-join exclusion set already does. On v3 the same answer came with #546. The #633 or test goes back to the v3 form, which this makes 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/executor.rs | 31 +++++++++++++++----- tests/disjunction_test.rs | 55 +++++++++++++++++++++++++++++++++++ tests/not_join_test.rs | 8 ++--- 7 files changed, 87 insertions(+), 16 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 07ca128e88..417286d974 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -14,6 +14,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **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 meets a keyword value as the entity it names** (#637). Unless a branch held a `not` or an expression reading an outer variable, the executor ran each branch alone and joined its rows to the outer rows by exact value, so a keyword never met the ref of the entity it names: with `[:alice :friend :bob] [:bob :name "B"]`, `[:find ?e ?n :where [?e :friend ?f] (or [?f :name ?n] [?f :alias ?n])]` returned no rows instead of `:alice "B"`, with no error, in queries and in rule bodies. The join now compares them as a join between patterns and a `not-join` 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 9e8025f767..e1737cc894 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 -**1307 tests** (1298 passing, 9 ignored; unit + integration + doc). +**1311 tests** (1302 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 55d5a0b6ce..ae690d9291 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 1307 tests +cargo test # run 1311 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 8094bafcc6..1d1a4d2bba 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-16 with `cargo test` -**Result**: 1,298 passing tests and 9 ignored tests (1,307 total), including the golden-file corpus (#391) +**Result**: 1,302 passing tests and 9 ignored tests (1,311 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 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). +`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. An `or` / `or-join` branch meets a keyword value as the entity it names and the reverse, in a query and in a rule body (#637). 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 (the `or` binding the next step), 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/executor.rs b/src/query/datalog/executor.rs index a4254f65ff..8eef9f3be5 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -2017,7 +2017,9 @@ pub(crate) fn apply_or_clauses( let mut k: Vec<(String, Value)> = branch_var_names .iter() .filter_map(|v| { - b.get(*v).map(|val| (v.to_string(), val.clone())) + b.get(*v).map(|val| { + (v.to_string(), normalize_value(val)) + }) }) .collect(); k.sort_unstable_by(|a, b| a.0.cmp(&b.0)); @@ -2028,7 +2030,9 @@ pub(crate) fn apply_or_clauses( let mut k: Vec<(String, Value)> = branch_var_names .iter() .filter_map(|v| { - incoming.get(*v).map(|val| (v.to_string(), val.clone())) + incoming + .get(*v) + .map(|val| (v.to_string(), normalize_value(val))) }) .collect(); k.sort_unstable_by(|a, b| a.0.cmp(&b.0)); @@ -2059,14 +2063,16 @@ pub(crate) fn apply_or_clauses( .collect(); // With no shared variable every key is empty, so each incoming - // row joins every branch row: a cross product (#610). + // row joins every branch row: a cross product (#610). Keys hold + // `normalize_value`s, so a keyword meets the ref of the entity it + // names, as a join between patterns does (#637). // Build HashMap: shared-key tuple → Vec let mut branch_map: HashMap, Vec> = HashMap::new(); for b in union_bindings { let key: Vec<(String, Value)> = shared_vars .iter() - .filter_map(|v| b.get(v).map(|val| (v.clone(), val.clone()))) + .filter_map(|v| b.get(v).map(|val| (v.clone(), normalize_value(val)))) .collect(); branch_map.entry(key).or_default().push(b); } @@ -2078,7 +2084,9 @@ pub(crate) fn apply_or_clauses( for incoming in &bindings { let key: Vec<(String, Value)> = shared_vars .iter() - .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .filter_map(|v| { + incoming.get(v).map(|val| (v.clone(), normalize_value(val))) + }) .collect(); if let Some(matches) = branch_map.get(&key) { for branch_binding in matches { @@ -2178,6 +2186,7 @@ pub(crate) fn apply_or_clauses( continue; } + // Join keys hold `normalize_value`s, as for `or` (#637). let empty_seed: Vec = vec![HashMap::new()]; let mut seen_proj: std::collections::HashSet> = std::collections::HashSet::new(); @@ -2197,7 +2206,9 @@ pub(crate) fn apply_or_clauses( .map(|incoming| { join_vars .iter() - .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .filter_map(|v| { + incoming.get(v).map(|val| (v.clone(), normalize_value(val))) + }) .collect::>() }) .collect(); @@ -2224,7 +2235,9 @@ pub(crate) fn apply_or_clauses( if seen_proj.insert(key) { let bkey: Vec<(String, Value)> = join_vars .iter() - .filter_map(|v| b.get(v).map(|val| (v.clone(), val.clone()))) + .filter_map(|v| { + b.get(v).map(|val| (v.clone(), normalize_value(val))) + }) .collect(); branch_map.entry(bkey).or_default().push(b); } @@ -2242,7 +2255,9 @@ pub(crate) fn apply_or_clauses( for incoming in &bindings { let key: Vec<(String, Value)> = join_vars .iter() - .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .filter_map(|v| { + incoming.get(v).map(|val| (v.clone(), normalize_value(val))) + }) .collect(); if let Some(matches) = branch_map.get(&key) { for branch_binding in matches { diff --git a/tests/disjunction_test.rs b/tests/disjunction_test.rs index ab39ce2b10..1f0fb49307 100644 --- a/tests/disjunction_test.rs +++ b/tests/disjunction_test.rs @@ -904,3 +904,58 @@ fn test_expression_after_or_reads_or_bound_variable_with_rules() { let r = db.execute("(query [:find ?x :where (big ?e ?x)])").unwrap(); assert_eq!(result_count(&r), 1, "rule body"); } + +// ── #637: an `or` branch meets a keyword value as the entity it names ──────── + +fn issue_637_db() -> Minigraf { + let db = db(); + db.execute( + r#"(transact [[:alice :friend :bob] [:bob :name "B"] + [:a :e :b] [:b :e :c] [:c :e :d] [:d :e :f] [:f :tail true]])"#, + ) + .unwrap(); + db +} + +#[test] +fn test_or_branch_entity_from_keyword_value() { + let db = issue_637_db(); + let r = db + .execute("(query [:find ?e ?n :where [?e :friend ?f] (or [?f :name ?n] [?f :alias ?n])])") + .unwrap(); + assert_eq!(result_count(&r), 1, "keyword :bob meets entity :bob"); + let r = db + .execute("(query [:find ?x ?y :where [?x :e ?y] (or [?y :e _] [?y :tail true])])") + .unwrap(); + assert_eq!(result_count(&r), 4, "pure-filter or"); +} + +#[test] +fn test_or_branch_keyword_value_from_entity() { + // The other direction: the outer row holds the ref, the branch the keyword. + let db = issue_637_db(); + let r = db + .execute(r#"(query [:find ?e :where [?f :name "B"] (or [?e :friend ?f] [?e :enemy ?f])])"#) + .unwrap(); + assert_eq!(result_count(&r), 1, "entity :bob meets keyword :bob"); +} + +#[test] +fn test_or_join_entity_from_keyword_value() { + let db = issue_637_db(); + let r = db + .execute("(query [:find ?x ?y :where [?x :e ?y] (or-join [?y] [?y :e _] [?y :tail true])])") + .unwrap(); + assert_eq!(result_count(&r), 4, "or-join on a keyword value"); +} + +#[test] +fn test_or_in_rule_entity_from_keyword_value() { + let db = issue_637_db(); + db.execute("(rule [(next ?x ?y) [?x :e ?y] (or [?y :e _] [?y :tail true])])") + .unwrap(); + let r = db + .execute("(query [:find ?x ?y :where (next ?x ?y)])") + .unwrap(); + assert_eq!(result_count(&r), 4, "or in a rule body"); +} diff --git a/tests/not_join_test.rs b/tests/not_join_test.rs index 4b892826a4..994fa905c5 100644 --- a/tests/not_join_test.rs +++ b/tests/not_join_test.rs @@ -690,14 +690,14 @@ fn test_mutual_recursion_through_not_join_rule() { #[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("(transact [[:f :g :h]])").unwrap(); 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])])") + db.execute("(rule [(reach ?x ?y) (or [?x :e ?z] [?x :g ?z]) (reach ?z ?y)])") .unwrap(); + db.execute("(rule [(reach ?x ?y) [?x :g ?y]])").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"); + assert_eq!(result_count(&r), 15, "every pair along the chain a..h"); }