From 086ae19012d6698302ca0551387eb410fd30f584 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 26 Sep 2026 14:36:39 +0530 Subject: [PATCH] fix(magic-sets): keep preceding rule calls in magic propagation rules (#297) A recursive rule whose intermediate variable is bound by a call to another user rule, e.g. (chain ?x ?y) :- (link ?x ?mid) (chain ?mid ?y), failed with "Unbound variable in rule head: ?mid" (INT-022) when queried with a literal first argument such as (chain :a ?y). build_propagation_rules built the magic rule for the recursive call from the guard plus only the non-RuleInvocation clauses preceding it, so it emitted (__magic_chain_bf ?mid) :- (__magic_chain_bf ?x) with ?mid unbound. #300 fixed only the case where a fact pattern binds the intermediate. Keep every preceding clause, including rule invocations, as standard magic-sets rewriting does. All rewritten rules are positive, so the added dependency on the (guarded) called predicate is safe. Adds integration tests for the reopened repro and a left-recursive variant, and a unit test pinning the propagation-rule body. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 2 +- src/query/datalog/magic_sets.rs | 45 ++++++++++++++++++---- tests/magic_sets_test.rs | 67 +++++++++++++++++++++++++++++++++ 6 files changed, 108 insertions(+), 11 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 1e4e2b955..f98645135 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -17,6 +17,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed - **A power loss could lose a new database or WAL file, or bring back a deleted WAL (#389).** On Linux and other POSIX systems, a created or deleted file survives a power loss only once its parent directory is fsynced; Minigraf fsynced file contents but never a directory. Creating the `.graph` file or the `.wal` sidecar, and deleting the WAL after a checkpoint, now fsync the parent directory after the file operation. A resurrected WAL was already harmless, since replay skips entries at or below the last checkpointed transaction, but a lost `.graph` or WAL lost committed data. Windows needs no directory sync and is unchanged. Process kills were never affected, because they leave the OS page cache intact. +- **Recursive rules failed with a literal start when the recursion goes through another rule (#297).** `(query [:find ?y :where (chain :a ?y)])` over `(chain ?x ?y) :- (link ?x ?mid) (chain ?mid ?y)` failed with `Unbound variable in rule head: ?mid` (INT-022). The magic-sets rewrite, which runs when a rule argument is given as a literal, dropped earlier rule calls from the rules that pass bindings to the next call, so a variable bound only by such a call (here `?mid`, bound by `link`) was never bound. #300 fixed the case where a fact pattern binds it. Those calls are now kept, and results match the same query without a literal start. - **Bound-entity queries could drop rows when one `WriteTransaction` wrote the same attribute in several valid-time windows (#323).** Both facts share a `tx_count`, and the selective lookup path de-duplicated on `(entity, attribute, tx_count, asserted)`, so one window's value was silently lost, while the same query via a full scan returned both. That de-duplication has been removed, and bound-entity queries now always match a full scan. ### Notes diff --git a/CLAUDE.md b/CLAUDE.md index b5c4609f4..2287bf0dd 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -168,7 +168,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1200 tests passing** (1192 passing, 8 ignored; unit + integration + doc). +**1203 tests passing** (1195 passing, 8 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 17778e53b..168cb0812 100644 --- a/README.md +++ b/README.md @@ -92,7 +92,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1200 tests +cargo test # run 1203 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 605e31317..905c1b043 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-09-26 with `cargo test` -**Result**: 1,192 passing tests and 8 ignored tests (1,200 total) +**Result**: 1,195 passing tests and 8 ignored tests (1,203 total) The v2.0.1 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 2ba77b140..48660baa4 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -188,7 +188,7 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char /// Build magic propagation rules for adorned recursive calls within a rule body. /// /// For each `RuleInvocation` in the body that calls an adorned predicate, -/// emits a rule: (magic-p-ad ?bound_arg) :- (magic-p-ad ?head_bound_var) +/// emits a rule: (magic-p-ad ?bound_arg) :- (magic-p-ad ?head_bound_var) /// /// Returns Vec<(predicate_name, Rule)> to be registered with `register_rule_unchecked`. #[allow(dead_code)] @@ -284,13 +284,12 @@ pub(crate) fn build_propagation_rules( .filter_map(|(pos, _)| called_args.get(pos).cloned()) .collect(); - // Propagation body = guard + all non-RuleInvocation clauses before this call. - let mut prop_body = vec![guard.clone()]; - for preceding in rule.body.iter().take(i) { - if !matches!(preceding, WhereClause::RuleInvocation { .. }) { - prop_body.push(preceding.clone()); - } - } + // Propagation body = guard + every clause before this call, including rule + // invocations: a preceding call may be the only binder of a variable passed + // in a bound position (e.g. `(link ?x ?mid) (chain ?mid ?y)`, #297). + let mut prop_body = Vec::with_capacity(1 + i); + prop_body.push(guard.clone()); + prop_body.extend(rule.body.iter().take(i).cloned()); // Build the propagation rule head. // For fb-adorned called predicates: head = [pred, sentinel, bound_val_var] @@ -695,6 +694,36 @@ mod tests { } } + #[test] + fn test_propagation_rule_keeps_preceding_rule_invocation() { + // (chain ?x ?y) :- (link ?x ?mid) (chain ?mid ?y) + // bf → (__magic_chain_bf ?mid) :- (__magic_chain_bf ?x) (link ?x ?mid) + // The preceding (link ...) call is the only binder of ?mid (#297). + let rule = make_rule( + "chain", + &["?x", "?y"], + vec![ + rule_inv("link", &["?x", "?mid"]), + rule_inv("chain", &["?mid", "?y"]), + ], + ); + let adorned: HashMap> = [ + ("chain".to_string(), vec!['b', 'f']), + ("link".to_string(), vec!['b', 'f']), + ] + .into_iter() + .collect(); + let prop_rules = build_propagation_rules(&rule, "chain", &adorned); + let chain_magic = magic_pred_name("chain", &['b', 'f']); + let (_, prop) = prop_rules + .iter() + .find(|(pred, _)| *pred == chain_magic) + .expect("propagation rule for the recursive chain call"); + assert_eq!(prop.head[1], EdnValue::Symbol("?mid".to_string())); + assert_eq!(prop.body.len(), 2, "guard + preceding link call"); + assert_eq!(prop.body[1], rule_inv("link", &["?x", "?mid"])); + } + #[test] fn test_propagation_rule_bb_adornment() { // (reachable ?a ?b) :- (reachable ?a ?c) [?c :edge/to ?b] diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs index 2191b4ab8..7f035b46f 100644 --- a/tests/magic_sets_test.rs +++ b/tests/magic_sets_test.rs @@ -306,3 +306,70 @@ fn test_recursive_intermediate_variable_with_keyword_entity() { _ => panic!("expected QueryResults"), } } + +fn extract_keywords(result: QueryResult) -> Vec { + match result { + QueryResult::QueryResults { results, .. } => { + let mut kws: Vec = results + .into_iter() + .map(|row| match &row[0] { + Value::Keyword(k) => k.clone(), + _ => panic!("Expected Keyword in result row"), + }) + .collect(); + kws.sort(); + kws + } + _ => panic!("Expected QueryResults"), + } +} + +/// #297 (reopened) — the intermediate variable is bound by a call to another +/// user-defined rule rather than a fact pattern. The magic propagation rule +/// must keep that call in its body, otherwise `?mid` is unbound in its head. +#[test] +fn test_recursive_intermediate_variable_bound_by_rule_call() { + let db = open_db(); + + exec( + &db, + r#"(transact [[:a :next :b] [:b :next :c] [:x :next :y]])"#, + ); + exec(&db, r#"(rule [(link ?x ?y) [?x :next ?y]])"#); + exec(&db, r#"(rule [(chain ?x ?y) (link ?x ?y)])"#); + exec( + &db, + r#"(rule [(chain ?x ?y) (link ?x ?mid) (chain ?mid ?y)])"#, + ); + + let bound = extract_keywords(exec(&db, r#"(query [:find ?y :where (chain :a ?y)])"#)); + assert_eq!(bound, vec![":b".to_string(), ":c".to_string()]); + + // Same answer as the pattern-bound form, which does not go through magic sets. + let via_pattern = extract_keywords(exec( + &db, + r#"(query [:find ?y :where [?a :next :b] (chain ?a ?y)])"#, + )); + assert_eq!(bound, via_pattern, "magic sets must not change results"); +} + +/// #297 (reopened) — left-recursive variant: the intermediate variable is bound +/// by a preceding recursive call and then fed into another user rule. +#[test] +fn test_left_recursive_intermediate_variable_bound_by_rule_call() { + let db = open_db(); + + exec( + &db, + r#"(transact [[:a :next :b] [:b :next :c] [:x :next :y]])"#, + ); + exec(&db, r#"(rule [(link ?x ?y) [?x :next ?y]])"#); + exec(&db, r#"(rule [(path ?x ?y) (link ?x ?y)])"#); + exec( + &db, + r#"(rule [(path ?x ?y) (path ?x ?mid) (link ?mid ?y)])"#, + ); + + let bound = extract_keywords(exec(&db, r#"(query [:find ?y :where (path :a ?y)])"#)); + assert_eq!(bound, vec![":b".to_string(), ":c".to_string()]); +}