From 94265d7f96ca50f065b79c8670b078ed97bdaaab Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 16 Oct 2026 12:23:31 +0530 Subject: [PATCH] fix(magic-sets): guard a rule only by demand every call site supplies (#608) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Backport of #609 from v3. Adornments were taken from the first call to each rule and assumed for every other call. A call that did not match — a rule-body call whose argument nothing had bound yet, the same rule called with free arguments, a call inside or/not, or a call from an unguarded rule — failed with INT-022 or silently got only the demanded facts. solve_adornments now starts each reachable rule all-bound and weakens it to the meet of every call site's adornment until a fixpoint; a rule left with no bound position is evaluated unguarded. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +- src/query/datalog/magic_sets.rs | 487 +++++++++++++++++++++++--------- tests/magic_sets_test.rs | 154 ++++++++++ 6 files changed, 509 insertions(+), 141 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 05877fe912..f2f05d28a5 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -9,6 +9,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed +- **Rule queries with a literal argument return every row** (#608). Magic-sets rewriting restricts a rule to the facts its callers demand, but it took each rule's bound arguments from the first call it saw and assumed every other call matched. A call that did not — the same rule called with free arguments elsewhere in the query, a call inside `or` or `not`, a call from a rule the query calls with free arguments, or a rule-body call whose argument nothing bound yet — either failed with `INT-022` (`(chain ?x :c)` with `(chain ?x ?y) :- (link ?x ?m) (chain ?m ?y)`) or silently returned too few rows (`(link ?x :c) (link ?p ?q)` returned only the `:c` edges for `?p ?q`). A query with both arguments literal next to another rule call also lost its rows. The demand on each rule is now the one every call site supplies, and a rule some call site reads in full is evaluated in full. Present since v1.2.0; also fixed on v3. - **A prepared query keeps a literal `:as-of`, `:valid-at` or `:any-valid-time`** (#603). Binding a prepared query's slots dropped any `:as-of` or `:valid-at` that was not itself a slot, so `PreparedQuery::execute` ran at the current transaction time and valid now: `(query [:find ?v :as-of 1 :where [:a :n ?v]])` prepared returned the current rows, not those at transaction 1, and a prepared per-fact pseudo-attribute query with `:any-valid-time` failed with `INT-026`. Slot forms (`:as-of $tx`, `:valid-at $t`) were not affected. Present since 2026-04-04 (v1.x and every v2.x release). ## v2.0.6 — 2026-10-14 diff --git a/CLAUDE.md b/CLAUDE.md index d9b22c6a2c..3c81541679 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 -**1253 tests** (1244 passing, 9 ignored; unit + integration + doc). +**1267 tests** (1258 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 a677549a85..04860a0156 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 1253 tests +cargo test # run 1267 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 68a26b7310..5caa5dce4d 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-14 with `cargo test` -**Result**: 1,244 passing tests and 9 ignored tests (1,253 total), including the golden-file corpus (#391) +**Result**: 1,258 passing tests and 9 ignored tests (1,267 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). @@ -14,6 +14,8 @@ For v2.0.5, torn-WAL-tail tests (#513) check that opening a WAL writer cuts off `tests/crash_kill_test.rs` kills a child process running a seeded workload under five checkpoint modes at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries, again after a second reopen and after a checkpoint plus reopen (#384). The workload leaves out the v2.x known issues #371 and #435. +`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. + 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. The v2.0.6 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). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). For v2.0.3, storage unit tests and two `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed, before and after a checkpoint, and that the widened `FactRef` encodes to the same bytes as before (#445). A WAL test reopens a database next to a WAL whose entries are all checkpointed, writes again, and checks that `:as-of` history is unchanged before and after another reopen; a unit test checks that restoring the transaction counter never lowers it (#447). Since v2.0.3, `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). A recursive-rules test runs rule queries on a database with more live facts than `max_results` and checks that they answer, and that the limit still stops a rule that derives more facts than it allows (#528). A WAL test restores a WAL whose entries are all checkpointed and checks that an explicit `checkpoint()` removes it, keeps the fact, and that the next write does not reuse tx 1; the golden-corpus test now requires `v7_stale_wal` to have no WAL after a checkpoint too (#457). A WAL test checks that dropping a handle opened with `wal_checkpoint_threshold(usize::MAX)` leaves the `.graph` file byte for byte unchanged under `Full` and `Normal` sync, keeps the WAL, and that a reopen replays it (#476). diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 48660baa43..29621c1080 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -8,43 +8,26 @@ use uuid::Uuid; /// Return type for `rewrite()`: rewritten rule registry + seed facts to preload. type RewriteResult = (RuleRegistry, Vec<(EntityId, String, Value)>); -/// Classify each arg in rule invocations as bound ('b') or free ('f'). -/// Single left-to-right pass; all variables in Pattern entity/value positions are -/// considered grounded after the pattern (Datalog: pattern binds all its variables). -pub(crate) fn compute_query_adornments( - where_clauses: &[WhereClause], -) -> HashMap> { - let mut grounded: HashSet = HashSet::new(); - let mut adornments: HashMap> = HashMap::new(); +/// Adornment of a rule call in the query's top-level `:where`: `'b'` where the +/// argument is a literal a seed fact can carry (an entity for arg0, a value for +/// arg1), `'f'` elsewhere. A variable is `'f'` even when an earlier pattern binds +/// it: its values are not known when the seeds are built. +pub(crate) fn query_call_adornment(args: &[EdnValue]) -> Vec { + args.iter() + .enumerate() + .map(|(i, arg)| if is_carried_literal(i, arg) { 'b' } else { 'f' }) + .collect() +} - for clause in where_clauses { - match clause { - WhereClause::Pattern(p) => { - if let Some(var) = p.entity.as_variable() { - grounded.insert(var.to_string()); - } - if let Some(var) = p.value.as_variable() { - grounded.insert(var.to_string()); - } - } - WhereClause::RuleInvocation { predicate, args } => { - let adornment: Vec = args - .iter() - .map(|arg| { - if let Some(var) = arg.as_variable() { - if grounded.contains(var) { 'b' } else { 'f' } - } else { - 'b' // literal - } - }) - .collect(); - adornments.entry(predicate.clone()).or_insert(adornment); - } - _ => {} +/// True if `arg` is a literal a seed or magic fact can carry in argument position +/// `i`: an entity for arg0, a value for arg1. +fn is_carried_literal(i: usize, arg: &EdnValue) -> bool { + arg.as_variable().is_none() + && match i { + 0 => edn_to_entity_id(arg).is_ok(), + 1 => edn_to_value(arg).is_ok(), + _ => false, } - } - - adornments } /// Returns true if at least one position in the adornment is bound. @@ -321,88 +304,183 @@ pub(crate) fn build_propagation_rules( result } -/// Propagate adornments transitively through rule bodies (handles mutual recursion). -/// Starting from `initial`, expands until fixed point. -pub(crate) fn propagate_adornments( - initial: &HashMap>, +/// Position-wise meet: `'b'` only where both adornments are bound. +fn meet(a: &[char], b: &[char]) -> Vec { + if a.len() != b.len() { + return vec!['f'; a.len().max(b.len())]; + } + a.iter() + .zip(b) + .map(|(&x, &y)| if x == 'b' && y == 'b' { 'b' } else { 'f' }) + .collect() +} + +/// Keep the first bound position only, and only arg0 or arg1: a seed or magic +/// fact carries one bound value (entity for `bf`, value for `fb`). `None` when no +/// position is left bound — the predicate is then evaluated unguarded. +fn normalize(adornment: &[char]) -> Option> { + let first = adornment + .iter() + .position(|&c| c == 'b') + .filter(|&i| i < 2)?; + Some( + (0..adornment.len()) + .map(|i| if i == first { 'b' } else { 'f' }) + .collect(), + ) +} + +fn has_negation(rule: &Rule) -> bool { + rule.body + .iter() + .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) +} + +/// Predicates the query can reach through rule calls, at any nesting depth. +fn reachable_predicates(query: &DatalogQuery, registry: &RuleRegistry) -> Vec { + let mut seen: HashSet = HashSet::new(); + let mut order = Vec::new(); + let mut stack: Vec = query + .where_clauses + .iter() + .flat_map(|c| c.rule_invocations()) + .map(str::to_string) + .collect(); + while let Some(pred) = stack.pop() { + if !seen.insert(pred.clone()) { + continue; + } + for rule in registry.get_rules(&pred) { + stack.extend( + rule.body + .iter() + .flat_map(|c| c.rule_invocations()) + .map(str::to_string), + ); + } + order.push(pred); + } + order +} + +/// Adornment of each predicate whose rules get a magic guard. +/// +/// A guarded predicate derives only the facts its magic predicate demands, so the +/// rewrite is sound only if every call site that reads it supplies that demand: a +/// seeded call in the query, or a call in the body of a guarded rule (which gets a +/// propagation rule) with every guarded position bound before the call (#608). +/// Any other call site — a call with that argument free, a call inside `or`, +/// `or-join`, `not` or `not-join`, or a call from an unguarded rule — needs every +/// fact, and weakens the adornment. +/// +/// Starts from all-bound and weakens to the greatest fixpoint: each round the +/// adornment becomes its meet with every call site's, then `normalize`; a +/// predicate with no bound position left is dropped. Adornments only lose bound +/// positions, so this terminates. +pub(crate) fn solve_adornments( + query: &DatalogQuery, registry: &RuleRegistry, ) -> HashMap> { - let mut adorned = initial.clone(); - let mut changed = true; + let reachable = reachable_predicates(query, registry); + let mut adorned: HashMap> = reachable + .iter() + .filter_map(|pred| { + let arity = registry + .get_rules(pred) + .first()? + .head + .len() + .checked_sub(1)?; + Some((pred.clone(), vec!['b'; arity])) + }) + .collect(); - while changed { - changed = false; - // Collect to avoid borrowing issues in the loop - let preds_with_adornments: Vec<(String, Vec)> = adorned - .iter() - .map(|(k, v)| (k.clone(), v.clone())) - .collect(); + loop { + let mut demand: HashMap> = HashMap::new(); + let mut note = |pred: &str, ad: Vec| { + demand + .entry(pred.to_string()) + .and_modify(|d| *d = meet(d, &ad)) + .or_insert(ad); + }; + let free = |n: usize| vec!['f'; n]; - for (pred, adornment) in &preds_with_adornments { - for rule in registry.get_rules(pred) { - if rule - .body - .iter() - .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) - { - continue; + for clause in &query.where_clauses { + match clause { + WhereClause::RuleInvocation { predicate, args } => { + note(predicate, query_call_adornment(args)); } - // Seed grounded vars with bound-position vars from the rule head + nested => nested + .rule_invocations() + .into_iter() + .for_each(|p| note(p, free(0))), + } + } + + for pred in &reachable { + let head_adornment = adorned.get(pred); + for rule in registry.get_rules(pred) { + let guarded = head_adornment.filter(|_| !has_negation(&rule)); let mut grounded: HashSet = HashSet::new(); - for (i, &ch) in adornment.iter().enumerate() { - if ch == 'b' - && let Some(v) = rule.head.get(i + 1).and_then(|e| e.as_variable()) - { - grounded.insert(v.to_string()); + if let Some(ad) = guarded { + for (i, &ch) in ad.iter().enumerate() { + if ch == 'b' + && let Some(v) = rule.head.get(i + 1).and_then(|e| e.as_variable()) + { + grounded.insert(v.to_string()); + } } } for clause in &rule.body { match clause { WhereClause::Pattern(p) => { - if let Some(v) = p.entity.as_variable() { - grounded.insert(v.to_string()); - } - if let Some(v) = p.value.as_variable() { + for v in [p.entity.as_variable(), p.value.as_variable()] + .into_iter() + .flatten() + { grounded.insert(v.to_string()); } } - WhereClause::RuleInvocation { - predicate: called, - args, - } => { - let call_adornment: Vec = args - .iter() - .map(|a| match a.as_variable() { - Some(v) if grounded.contains(v) => 'b', - Some(_) => 'f', - None => 'b', // literals are always bound - }) - .collect(); - // First-writer-wins: if a predicate is already adorned from another call site, - // we keep the first adornment. In programs with multiple call sites for the same - // predicate, this may miss more-permissive adornments from later call sites. - // This is an acceptable simplification — worst case is less pruning, not wrong results. - if has_bound_arg(&call_adornment) - && !adorned.contains_key(called.as_str()) - { - adorned.insert(called.clone(), call_adornment); - changed = true; - } - // After a RuleInvocation, the output vars become grounded - for a in args { - if let Some(v) = a.as_variable() { - grounded.insert(v.to_string()); - } + WhereClause::RuleInvocation { predicate, args } => { + let ad = if guarded.is_some() { + args.iter() + .enumerate() + .map(|(i, a)| match a.as_variable() { + Some(v) if grounded.contains(v) => 'b', + Some(_) => 'f', + None if is_carried_literal(i, a) => 'b', + None => 'f', + }) + .collect() + } else { + free(args.len()) + }; + note(predicate, ad); + for v in args.iter().filter_map(|a| a.as_variable()) { + grounded.insert(v.to_string()); } } - _ => {} + nested => nested + .rule_invocations() + .into_iter() + .for_each(|p| note(p, free(0))), } } } } - } - adorned + let next: HashMap> = adorned + .iter() + .filter_map(|(pred, ad)| { + let site = demand.get(pred)?; + normalize(&meet(ad, site)).map(|n| (pred.clone(), n)) + }) + .collect(); + if next == adorned { + return adorned; + } + adorned = next; + } } /// Build rewritten registry: copy all rules with magic guards injected for adorned @@ -441,27 +519,16 @@ fn build_rewritten_registry( } pub(crate) fn rewrite(query: &DatalogQuery, registry: &RuleRegistry) -> Option { - let initial = compute_query_adornments(&query.where_clauses); - let initial_bound: HashMap> = initial - .into_iter() - .filter(|(_, ad)| has_bound_arg(ad)) - .collect(); - - if initial_bound.is_empty() { + // Only a literal argument in a top-level call can seed demand. + let any_seedable = query.where_clauses.iter().any(|c| { + matches!(c, WhereClause::RuleInvocation { args, .. } + if has_bound_arg(&query_call_adornment(args))) + }); + if !any_seedable { return None; } - // Fast-path: magic sets only helps when at least one adorned predicate has a free - // position. Fully-bound adornments (e.g. "bb") provide no demand-driven benefit - // and the current seed encoding only supports arg0-bound or arg1-only-bound cases. - // NOTE: this guard is redundant with the downstream `seeds.is_empty()` check, but - // is retained as an early exit that avoids the `propagate_adornments` traversal. - let any_free = initial_bound.values().any(|ad| ad.contains(&'f')); - if !any_free { - return None; - } - - let adorned = propagate_adornments(&initial_bound, registry); + let adorned = solve_adornments(query, registry); let seeds = build_seed_facts(&query.where_clauses, &adorned); if seeds.is_empty() { return None; @@ -524,37 +591,77 @@ mod tests { } } + fn kw(k: &str) -> EdnValue { + EdnValue::Keyword(k.to_string()) + } + + fn var(v: &str) -> EdnValue { + EdnValue::Symbol(v.to_string()) + } + + /// Adornments of the query's top-level calls, as `rewrite` seeds them. + fn query_adornments(clauses: &[WhereClause]) -> HashMap> { + clauses + .iter() + .filter_map(|c| match c { + WhereClause::RuleInvocation { predicate, args } => { + Some((predicate.clone(), query_call_adornment(args))) + } + _ => None, + }) + .collect() + } + #[test] fn test_literal_arg_is_bound() { - let clauses = vec![rule_inv("ancestor", &["abc123", "?y"])]; - let adornments = compute_query_adornments(&clauses); - assert_eq!(adornments.get("ancestor"), Some(&vec!['b', 'f'])); + assert_eq!( + query_call_adornment(&[kw(":alice"), var("?y")]), + vec!['b', 'f'] + ); + assert_eq!( + query_call_adornment(&[var("?x"), kw(":alice")]), + vec!['f', 'b'] + ); } #[test] fn test_free_var_is_free() { - let clauses = vec![rule_inv("ancestor", &["?x", "?y"])]; - let adornments = compute_query_adornments(&clauses); - assert_eq!(adornments.get("ancestor"), Some(&vec!['f', 'f'])); + assert_eq!( + query_call_adornment(&[var("?x"), var("?y")]), + vec!['f', 'f'] + ); } #[test] - fn test_var_grounded_by_preceding_pattern() { - // [?x :name "Alice"] (ancestor ?x ?y) → ?x grounded → bf - let clauses = vec![ - pat("?x", ":name", "Alice"), - rule_inv("ancestor", &["?x", "?y"]), - ]; - let adornments = compute_query_adornments(&clauses); - assert_eq!(adornments.get("ancestor"), Some(&vec!['b', 'f'])); + fn test_var_grounded_by_preceding_pattern_is_free() { + // [?x :name "Alice"] (ancestor ?x ?y): ?x is bound, but no seed can carry + // its values, so the call is not demand-restricted. + assert_eq!( + query_call_adornment(&[var("?x"), var("?y")]), + vec!['f', 'f'] + ); } #[test] - fn test_all_free_has_no_bound() { - let clauses = vec![rule_inv("ancestor", &["?x", "?y"])]; - let adornments = compute_query_adornments(&clauses); - let ad = adornments.get("ancestor").unwrap(); - assert!(!has_bound_arg(ad)); + fn test_unseedable_literal_is_free() { + // A string cannot name an entity, so it cannot seed arg0. + let args = [EdnValue::String("abc".to_string()), var("?y")]; + assert_eq!(query_call_adornment(&args), vec!['f', 'f']); + } + + #[test] + fn test_normalize_keeps_one_bound_position() { + assert_eq!(normalize(&['b', 'b']), Some(vec!['b', 'f'])); + assert_eq!(normalize(&['f', 'b']), Some(vec!['f', 'b'])); + assert_eq!(normalize(&['b']), Some(vec!['b'])); + assert_eq!(normalize(&['f', 'f']), None); + assert_eq!(normalize(&['f', 'f', 'b']), None); + } + + #[test] + fn test_meet_of_different_lengths_is_free() { + assert_eq!(meet(&['b', 'b'], &[]), vec!['f', 'f']); + assert_eq!(meet(&['b', 'f'], &['b', 'b']), vec!['b', 'f']); } #[test] @@ -568,7 +675,7 @@ mod tests { EdnValue::Symbol("?y".to_string()), ], }]; - let adornments = compute_query_adornments(&clauses); + let adornments = query_adornments(&clauses); let seeds = build_seed_facts(&clauses, &adornments); assert_eq!(seeds.len(), 1); let (entity, attr, value) = &seeds[0]; @@ -584,7 +691,7 @@ mod tests { #[test] fn test_no_seed_for_all_free() { let clauses = vec![rule_inv("ancestor", &["?x", "?y"])]; - let adornments = compute_query_adornments(&clauses); + let adornments = query_adornments(&clauses); let seeds = build_seed_facts(&clauses, &adornments); assert!(seeds.is_empty()); } @@ -777,15 +884,119 @@ mod tests { "odd".to_string(), make_rule("odd", &["?n"], vec![rule_inv("even", &["?n"])]), ); - let initial: HashMap> = - [("even".to_string(), vec!['b'])].into_iter().collect(); - let propagated = propagate_adornments(&initial, ®istry); + let query = DatalogQuery::new( + vec![FindSpec::Variable("?x".to_string())], + vec![WhereClause::RuleInvocation { + predicate: "even".to_string(), + args: vec![kw(":n")], + }], + ); + let propagated = solve_adornments(&query, ®istry); + assert_eq!(propagated.get("even"), Some(&vec!['b'])); assert!( propagated.contains_key("odd"), "odd should be adorned via SCC" ); } + /// `a → b → c` shapes from #608: `link`, `chain` calling only rules, `any`. + fn chain_registry() -> RuleRegistry { + let mut registry = RuleRegistry::new(); + let reg = |r: &mut RuleRegistry, pred: &str, rule: Rule| { + r.register_rule_unchecked(pred.to_string(), rule) + }; + reg( + &mut registry, + "link", + make_rule("link", &["?x", "?y"], vec![pat("?x", ":edge", "?y")]), + ); + reg( + &mut registry, + "chain", + make_rule( + "chain", + &["?x", "?y"], + vec![rule_inv("link", &["?x", "?y"])], + ), + ); + reg( + &mut registry, + "chain", + make_rule( + "chain", + &["?x", "?y"], + vec![ + rule_inv("link", &["?x", "?m"]), + rule_inv("chain", &["?m", "?y"]), + ], + ), + ); + reg( + &mut registry, + "any", + make_rule("any", &["?x", "?y"], vec![rule_inv("link", &["?x", "?y"])]), + ); + registry + } + + fn query_of(clauses: Vec) -> DatalogQuery { + DatalogQuery::new(vec![FindSpec::Variable("?x".to_string())], clauses) + } + + fn call(pred: &str, args: Vec) -> WhereClause { + WhereClause::RuleInvocation { + predicate: pred.to_string(), + args, + } + } + + #[test] + fn test_608_unbound_call_argument_unguards_callee() { + // (chain ?x :c): chain is fb, but `(link ?x ?m)` in its body has ?m + // unbound, so link must stay unguarded. + let query = query_of(vec![call("chain", vec![var("?x"), kw(":c")])]); + let adorned = solve_adornments(&query, &chain_registry()); + assert_eq!(adorned.get("chain"), Some(&vec!['f', 'b'])); + assert!(!adorned.contains_key("link")); + } + + #[test] + fn test_608_bound_first_argument_keeps_callee_guarded() { + // (chain :a ?y): every call to link and chain has arg0 bound. + let query = query_of(vec![call("chain", vec![kw(":a"), var("?y")])]); + let adorned = solve_adornments(&query, &chain_registry()); + assert_eq!(adorned.get("chain"), Some(&vec!['b', 'f'])); + assert_eq!(adorned.get("link"), Some(&vec!['b', 'f'])); + } + + #[test] + fn test_608_free_query_call_unguards_predicate() { + let query = query_of(vec![ + call("link", vec![var("?x"), kw(":c")]), + call("link", vec![var("?p"), var("?q")]), + ]); + assert!(solve_adornments(&query, &chain_registry()).is_empty()); + assert!(rewrite(&query, &chain_registry()).is_none()); + } + + #[test] + fn test_608_unguarded_caller_unguards_callee() { + let query = query_of(vec![ + call("link", vec![var("?x"), kw(":c")]), + call("any", vec![var("?p"), var("?q")]), + ]); + assert!(solve_adornments(&query, &chain_registry()).is_empty()); + } + + #[test] + fn test_608_nested_call_unguards_predicate() { + let query = query_of(vec![ + call("link", vec![var("?x"), kw(":c")]), + WhereClause::Not(vec![call("link", vec![kw(":a"), var("?x")])]), + ]); + assert!(solve_adornments(&query, &chain_registry()).is_empty()); + } + #[test] fn test_rewrite_none_when_all_free() { let mut registry = RuleRegistry::new(); diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs index 7f035b46fb..d4f90fb351 100644 --- a/tests/magic_sets_test.rs +++ b/tests/magic_sets_test.rs @@ -373,3 +373,157 @@ fn test_left_recursive_intermediate_variable_bound_by_rule_call() { let bound = extract_keywords(exec(&db, r#"(query [:find ?y :where (path :a ?y)])"#)); assert_eq!(bound, vec![":b".to_string(), ":c".to_string()]); } + +// ── #608: every call site of a guarded predicate must be covered by its demand ── + +/// Rows of a query result as sorted strings. Entities named by the keywords +/// `:a`..`:d` (their UUIDs are derived from the keyword) print as the keyword. +fn rows(result: QueryResult) -> Vec { + let QueryResult::QueryResults { results, .. } = result else { + panic!("Expected QueryResults"); + }; + let name = |u: &Uuid| { + [":a", ":b", ":c", ":d"] + .into_iter() + .find(|k| Uuid::new_v5(&Uuid::NAMESPACE_OID, k.as_bytes()) == *u) + .expect("entity named by a test keyword") + .to_string() + }; + let mut rows: Vec = results + .into_iter() + .map(|row| { + row.iter() + .map(|v| match v { + Value::Ref(u) => name(u), + Value::Keyword(k) => k.clone(), + _ => panic!("unexpected value type in result"), + }) + .collect::>() + .join(" ") + }) + .collect(); + rows.sort(); + rows +} + +fn query_rows(db: &Minigraf, query: &str) -> Vec { + rows(exec(db, query)) +} + +/// `a → b → c`, a one-step `link`, its transitive `chain` written with a rule +/// call only, and `any`, which calls `link` with both arguments free. +fn edge_db() -> Minigraf { + let db = open_db(); + exec(&db, r#"(transact [[:a :edge :b] [:b :edge :c]])"#); + exec(&db, r#"(rule [(link ?x ?y) [?x :edge ?y]])"#); + exec(&db, r#"(rule [(chain ?x ?y) (link ?x ?y)])"#); + exec(&db, r#"(rule [(chain ?x ?y) (link ?x ?m) (chain ?m ?y)])"#); + exec(&db, r#"(rule [(any ?x ?y) (link ?x ?y)])"#); + db +} + +/// #608 — `chain` adorned `fb` calls `link` with `?m`, which nothing binds before +/// the call: the demand on `link` cannot be propagated (it was INT-022). +#[test] +fn test_608_rule_call_with_unbound_argument() { + let db = edge_db(); + assert_eq!( + query_rows(&db, r#"(query [:find ?x :where (chain ?x :c)])"#), + vec![":a", ":b"] + ); + assert_eq!( + query_rows(&db, r#"(query [:find ?y :where (chain :a ?y)])"#), + vec![":b", ":c"] + ); +} + +/// #608 — the same predicate called twice in a query, once with a literal and +/// once with free arguments: the free call needs every `link` fact. +#[test] +fn test_608_same_predicate_bound_and_free_in_query() { + let db = edge_db(); + assert_eq!( + query_rows( + &db, + r#"(query [:find ?x ?p ?q :where (link ?x :c) (link ?p ?q)])"# + ), + vec![":b :a :b", ":b :b :c"] + ); + assert_eq!( + query_rows( + &db, + r#"(query [:find ?y ?p ?q :where (link :a ?y) (link ?p ?q)])"# + ), + vec![":b :a :b", ":b :b :c"] + ); +} + +/// #608 — a rule the query calls with free arguments (`any`) calls a predicate +/// the query also calls with a literal. +#[test] +fn test_608_unadorned_rule_calls_adorned_predicate() { + let db = edge_db(); + assert_eq!( + query_rows( + &db, + r#"(query [:find ?x ?p ?q :where (link ?x :c) (any ?p ?q)])"# + ), + vec![":b :a :b", ":b :b :c"] + ); +} + +/// #608 — a call inside `or` is not seeded, so it needs every fact. +#[test] +fn test_608_call_inside_or() { + let db = edge_db(); + exec(&db, r#"(transact [[:b :edge :e]])"#); + assert_eq!( + query_rows( + &db, + r#"(query [:find ?x :where (link ?x :c) (or (link ?x :e) (link ?x :d))])"# + ), + vec![":b"] + ); +} + +/// #608 — a call inside `not` is not seeded either. +#[test] +fn test_608_call_inside_not() { + let db = edge_db(); + // link(:a, :b) holds, so ?x = :b is removed. + assert_eq!( + query_rows( + &db, + r#"(query [:find ?x :where (link ?x :c) (not (link :a ?x))])"# + ), + Vec::::new() + ); +} + +/// #608 — a query call with both arguments literal (`bb`) beside one that has a +/// free argument. +#[test] +fn test_608_fully_bound_call_beside_bound_free_call() { + let db = edge_db(); + assert_eq!( + query_rows( + &db, + r#"(query [:find ?x :where (link ?x :c) (chain :a :c)])"# + ), + vec![":b"] + ); +} + +/// #608 — a call bound only by a variable cannot be seeded; it must not be +/// guarded when another call in the query is seeded. +#[test] +fn test_608_variable_bound_call_beside_literal_call() { + let db = edge_db(); + assert_eq!( + query_rows( + &db, + r#"(query [:find ?s ?y ?q :where [?s :edge :b] (link ?s ?y) (chain ?q :c)])"# + ), + vec![":a :b :a", ":a :b :b"] + ); +}