diff --git a/ROADMAP.md b/ROADMAP.md index f3650f00e6..c27bca3efc 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -1401,6 +1401,14 @@ branched_db.execute("(transact [[:x :y 1]])")?; --- +### 9.6 Magic Sets with Stratified Negation (Exploratory) + +Magic sets rewriting (#289) is not applied to mixed rules containing `not`/`not-join` — those continue to use full semi-naive evaluation. Extending to negation is well-studied (Beeri & Ramakrishnan 1991, §5) but adds significant complexity: negated subgoals require care to avoid unsound propagation across stratification boundaries. + +**Only worth pursuing if**: profiling shows that negation-heavy recursive rules are a bottleneck in a real workload. No issue is tracked — investigate if and when the need arises. + +--- + ## Performance Backlog Known O(N²) hotspots discovered during benchmarking (v0.13.0). The first post-1.0 performance batch (#208, #202, #203, #204) eliminated four of them. @@ -1717,4 +1725,4 @@ See [GitHub Issues](https://github.com/project-minigraf/minigraf/issues) for spe --- -**Last Updated**: May 2026 — 962 tests passing, v1.1.1; all post-1.0 work complete; #185 deferred to 2.0; ecosystem, developer tools, and integration examples fully transferred to external repos +**Last Updated**: June 2026 — magic sets rewriting (#289) implemented (967 tests passing); #185 deferred to 2.0; ecosystem, developer tools, and integration examples fully transferred to external repos diff --git a/docs/superpowers/plans/2026-06-04-magic-sets.md b/docs/superpowers/plans/2026-06-04-magic-sets.md new file mode 100644 index 0000000000..6eaeae4d3d --- /dev/null +++ b/docs/superpowers/plans/2026-06-04-magic-sets.md @@ -0,0 +1,1140 @@ +# Magic Sets Rewriting Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Implement demand-driven recursive rule evaluation via magic sets rewriting (#289), reducing O(N²) derivations to O(N) for point queries over recursive rules. + +**Architecture:** New `magic_sets.rs` module with a single `pub(crate) fn rewrite(query, registry) -> Option<(RuleRegistry, Vec)>` function. Called from `execute_query_with_rules` in `executor.rs` before `StratifiedEvaluator` is constructed. Rewrites positive recursive rules to add magic-predicate guards, emits seed facts for bound query args, propagates adornments through SCCs for mutual recursion. Mixed rules (containing `not`/`not-join`) are left untouched. + +**Tech Stack:** Rust; `types::{DatalogQuery, Rule, WhereClause, EdnValue, Pattern}`; `rules::RuleRegistry`; `graph::types::{Fact, Value, EntityId}`; `query::datalog::matcher::{edn_to_entity_id, edn_to_value}` + +--- + +## File Map + +| File | Action | Responsibility | +|---|---|---| +| `src/query/datalog/magic_sets.rs` | Create | Adornment, seed facts, rule transformation, `rewrite()` | +| `src/query/datalog/mod.rs` | Modify | Add `pub(crate) mod magic_sets;` | +| `src/query/datalog/executor.rs` | Modify | Wire `magic_sets::rewrite()` into `execute_query_with_rules` | +| `tests/magic_sets_test.rs` | Create | End-to-end correctness tests | +| `ROADMAP.md` | Modify | Negation limitation note (§9.6) | + +--- + +### Task 1: Scaffold the module + +**Files:** +- Create: `src/query/datalog/magic_sets.rs` +- Modify: `src/query/datalog/mod.rs` + +- [ ] **Step 1: Create `magic_sets.rs` with stub and first test** + +```rust +// src/query/datalog/magic_sets.rs +use crate::graph::types::{EntityId, Value}; +use crate::query::datalog::rules::RuleRegistry; +use crate::query::datalog::types::{DatalogQuery, EdnValue, WhereClause}; +use std::collections::{HashMap, HashSet}; + +pub(crate) fn rewrite( + _query: &DatalogQuery, + _registry: &RuleRegistry, +) -> Option<(RuleRegistry, Vec<(EntityId, String, Value)>)> { + None +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::query::datalog::types::FindSpec; + + #[test] + fn test_rewrite_empty_query_returns_none() { + let query = DatalogQuery::new( + vec![FindSpec::Variable("?x".to_string())], + vec![], + ); + let registry = RuleRegistry::new(); + assert!(rewrite(&query, ®istry).is_none()); + } +} +``` + +- [ ] **Step 2: Add module to `src/query/datalog/mod.rs`** + +After the `pub mod optimizer;` line, add: + +```rust +pub(crate) mod magic_sets; +``` + +- [ ] **Step 3: Run test to verify it passes** + +```bash +cargo test magic_sets::tests::test_rewrite_empty_query_returns_none -- --nocapture +``` +Expected: PASS + +- [ ] **Step 4: Commit** + +```bash +git add src/query/datalog/magic_sets.rs src/query/datalog/mod.rs +git commit -m "feat(magic-sets): scaffold module (#289)" +``` + +--- + +### Task 2: Adornment classification + +**Files:** +- Modify: `src/query/datalog/magic_sets.rs` + +- [ ] **Step 1: Write failing tests** + +Add these helper functions and tests to the `#[cfg(test)]` block in `magic_sets.rs`: + +```rust + use crate::query::datalog::types::{AttributeSpec, Pattern, Rule, WhereClause}; + + fn pat(entity: &str, attr: &str, value: &str) -> WhereClause { + WhereClause::Pattern(Pattern::new( + if entity.starts_with('?') { + EdnValue::Symbol(entity.to_string()) + } else { + EdnValue::Keyword(entity.to_string()) + }, + EdnValue::Keyword(attr.to_string()), + if value.starts_with('?') { + EdnValue::Symbol(value.to_string()) + } else { + EdnValue::String(value.to_string()) + }, + )) + } + + fn rule_inv(pred: &str, args: &[&str]) -> WhereClause { + WhereClause::RuleInvocation { + predicate: pred.to_string(), + args: args + .iter() + .map(|a| { + if a.starts_with('?') { + EdnValue::Symbol(a.to_string()) + } else { + EdnValue::String(a.to_string()) + } + }) + .collect(), + } + } + + fn make_rule(pred: &str, head_args: &[&str], body: Vec) -> Rule { + Rule { + head: std::iter::once(EdnValue::Symbol(pred.to_string())) + .chain(head_args.iter().map(|a| EdnValue::Symbol(a.to_string()))) + .collect(), + body, + } + } + + #[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'])); + } + + #[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'])); + } + + #[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'])); + } + + #[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)); + } +``` + +- [ ] **Step 2: Run to confirm failure** + +```bash +cargo test magic_sets::tests::test_literal_arg_is_bound -- --nocapture +``` +Expected: FAIL — `cannot find function compute_query_adornments` + +- [ ] **Step 3: Implement adornment helpers** + +Add these functions to `magic_sets.rs` (above `rewrite`): + +```rust +/// 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(); + + 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); + } + _ => {} + } + } + + adornments +} + +/// Returns true if at least one position in the adornment is bound. +pub(crate) fn has_bound_arg(adornment: &[char]) -> bool { + adornment.contains(&'b') +} + +/// Convert adornment to string: ['b','f'] → "bf". +pub(crate) fn adornment_string(adornment: &[char]) -> String { + adornment.iter().collect() +} + +/// Magic predicate name: "__magic_ancestor_bf". +pub(crate) fn magic_pred_name(pred: &str, adornment: &[char]) -> String { + format!("__magic_{}_{}", pred, adornment_string(adornment)) +} +``` + +- [ ] **Step 4: Run all unit tests** + +```bash +cargo test magic_sets::tests -- --nocapture +``` +Expected: all PASS + +- [ ] **Step 5: Commit** + +```bash +git add src/query/datalog/magic_sets.rs +git commit -m "feat(magic-sets): adornment classification (#289)" +``` + +--- + +### Task 3: Seed fact generation + +**Files:** +- Modify: `src/query/datalog/magic_sets.rs` + +- [ ] **Step 1: Write failing tests** + +Add to `#[cfg(test)]`: + +```rust + #[test] + fn test_seed_fact_for_keyword_entity_arg() { + // (ancestor :alice ?y) — arg0 bound (keyword alias) + // seed: entity = edn_to_entity_id(:alice), attr = ":__magic_ancestor_bf", value = true + let clauses = vec![WhereClause::RuleInvocation { + predicate: "ancestor".to_string(), + args: vec![ + EdnValue::Keyword(":alice".to_string()), + EdnValue::Symbol("?y".to_string()), + ], + }]; + let adornments = compute_query_adornments(&clauses); + let seeds = build_seed_facts(&clauses, &adornments); + assert_eq!(seeds.len(), 1); + let (entity, attr, value) = &seeds[0]; + assert_eq!(attr, ":__magic_ancestor_bf"); + assert_eq!(value, &Value::Boolean(true)); + let expected = crate::query::datalog::matcher::edn_to_entity_id( + &EdnValue::Keyword(":alice".to_string()), + ) + .unwrap(); + assert_eq!(*entity, expected); + } + + #[test] + fn test_no_seed_for_all_free() { + let clauses = vec![rule_inv("ancestor", &["?x", "?y"])]; + let adornments = compute_query_adornments(&clauses); + let seeds = build_seed_facts(&clauses, &adornments); + assert!(seeds.is_empty()); + } +``` + +- [ ] **Step 2: Run to confirm failure** + +```bash +cargo test magic_sets::tests::test_seed_fact_for_keyword_entity_arg -- --nocapture +``` +Expected: FAIL — `cannot find function build_seed_facts` + +- [ ] **Step 3: Implement `build_seed_facts`** + +Add to `magic_sets.rs`: + +```rust +use crate::query::datalog::matcher::{edn_to_entity_id, edn_to_value}; + +/// Build seed facts for adorned rule invocations with at least one bound arg. +/// +/// Encoding: +/// arg0 bound: entity = edn_to_entity_id(arg0), attr = ":__magic_p_ad", value = Boolean(true) +/// arg1-only bound (fb): entity = Uuid::new_v4() (ephemeral carrier), value = edn_to_value(arg1) +pub(crate) fn build_seed_facts( + where_clauses: &[WhereClause], + adornments: &HashMap>, +) -> Vec<(EntityId, String, Value)> { + let mut seeds = Vec::new(); + + for clause in where_clauses { + let WhereClause::RuleInvocation { predicate, args } = clause else { + continue; + }; + let Some(adornment) = adornments.get(predicate) else { + continue; + }; + if !has_bound_arg(adornment) { + continue; + } + + let magic_attr = format!(":{}", magic_pred_name(predicate, adornment)); + + if adornment.first() == Some(&'b') { + // arg0 bound — dominant case + if let Some(arg0) = args.first() { + if let Ok(entity) = edn_to_entity_id(arg0) { + seeds.push((entity, magic_attr, Value::Boolean(true))); + } + } + } else if adornment.get(1) == Some(&'b') { + // arg1-only bound (fb) — ephemeral carrier UUID + if let Some(arg1) = args.get(1) { + if let Ok(value) = edn_to_value(arg1) { + seeds.push((uuid::Uuid::new_v4(), magic_attr, value)); + } + } + } + } + + seeds +} +``` + +- [ ] **Step 4: Run all unit tests** + +```bash +cargo test magic_sets::tests -- --nocapture +``` +Expected: all PASS + +- [ ] **Step 5: Commit** + +```bash +git add src/query/datalog/magic_sets.rs +git commit -m "feat(magic-sets): seed fact generation (#289)" +``` + +--- + +### Task 4: Magic guard injection + +**Files:** +- Modify: `src/query/datalog/magic_sets.rs` + +- [ ] **Step 1: Write failing tests** + +Add to `#[cfg(test)]`: + +```rust + #[test] + fn test_magic_guard_prepended_to_positive_rule() { + // (ancestor ?a ?c) :- [?a :parent ?b] (ancestor ?b ?c) + // adornment bf → guard (__magic_ancestor_bf ?a) prepended + let rule = make_rule( + "ancestor", + &["?a", "?c"], + vec![pat("?a", ":parent", "?b"), rule_inv("ancestor", &["?b", "?c"])], + ); + let adornment = vec!['b', 'f']; + let rewritten = inject_magic_guard(&rule, "ancestor", &adornment); + match rewritten.body.first().unwrap() { + WhereClause::RuleInvocation { predicate, args } => { + assert_eq!(predicate, &magic_pred_name("ancestor", &adornment)); + assert_eq!(args.len(), 1); + assert_eq!(args[0], EdnValue::Symbol("?a".to_string())); + } + other => panic!("expected RuleInvocation guard, got {:?}", other), + } + } + + #[test] + fn test_mixed_rule_not_touched_by_guard() { + let rule = make_rule( + "eligible", + &["?x"], + vec![ + pat("?x", ":applied", "true"), + WhereClause::Not(vec![pat("?x", ":rejected", "true")]), + ], + ); + let rewritten = inject_magic_guard(&rule, "eligible", &['b']); + // First body clause must still be Pattern (not injected guard) + assert!( + matches!(rewritten.body.first().unwrap(), WhereClause::Pattern(_)), + "mixed rule must not have guard injected" + ); + } +``` + +- [ ] **Step 2: Run to confirm failure** + +```bash +cargo test magic_sets::tests::test_magic_guard_prepended_to_positive_rule -- --nocapture +``` +Expected: FAIL — `cannot find function inject_magic_guard` + +- [ ] **Step 3: Implement `inject_magic_guard`** + +Add to `magic_sets.rs`: + +```rust +use crate::query::datalog::types::Rule; + +/// Prepend a magic-predicate guard to a positive rule's body. +/// Rules containing Not/NotJoin are returned unchanged. +/// +/// The guard uses head[1] (the entity-position variable) as its argument, +/// which is always the bound position for the dominant `bf` adornment. +pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char]) -> Rule { + let has_negation = rule + .body + .iter() + .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })); + if has_negation { + return rule.clone(); + } + + let magic_name = magic_pred_name(predicate, adornment); + let bound_head_arg = rule + .head + .get(1) + .cloned() + .unwrap_or(EdnValue::Symbol("?_".to_string())); + let guard = WhereClause::RuleInvocation { + predicate: magic_name, + args: vec![bound_head_arg], + }; + + let mut new_body = Vec::with_capacity(rule.body.len() + 1); + new_body.push(guard); + new_body.extend(rule.body.iter().cloned()); + + Rule { head: rule.head.clone(), body: new_body } +} +``` + +- [ ] **Step 4: Run all unit tests** + +```bash +cargo test magic_sets::tests -- --nocapture +``` +Expected: all PASS + +- [ ] **Step 5: Commit** + +```bash +git add src/query/datalog/magic_sets.rs +git commit -m "feat(magic-sets): magic guard injection into positive rules (#289)" +``` + +--- + +### Task 5: Magic propagation rules + +**Files:** +- Modify: `src/query/datalog/magic_sets.rs` + +- [ ] **Step 1: Write failing tests** + +Add to `#[cfg(test)]`: + +```rust + #[test] + fn test_propagation_rule_emitted_for_recursive_call() { + // (ancestor ?a ?c) :- [?a :parent ?b] (ancestor ?b ?c) + // bf → (__magic_ancestor_bf ?b) :- (__magic_ancestor_bf ?a) [?a :parent ?b] + let rule = make_rule( + "ancestor", + &["?a", "?c"], + vec![pat("?a", ":parent", "?b"), rule_inv("ancestor", &["?b", "?c"])], + ); + let adorned: HashMap> = + [("ancestor".to_string(), vec!['b', 'f'])].into_iter().collect(); + let prop_rules = build_propagation_rules(&rule, "ancestor", &adorned); + assert_eq!(prop_rules.len(), 1); + + let (pred, prop) = &prop_rules[0]; + assert_eq!(pred, &magic_pred_name("ancestor", &['b', 'f'])); + // Head: [Symbol("__magic_ancestor_bf"), Symbol("?b")] + assert_eq!(prop.head.len(), 2); + assert_eq!(prop.head[1], EdnValue::Symbol("?b".to_string())); + // Body: [magic_guard(?a), [?a :parent ?b]] + assert_eq!(prop.body.len(), 2); + match &prop.body[0] { + WhereClause::RuleInvocation { predicate, args } => { + assert_eq!(predicate, &magic_pred_name("ancestor", &['b', 'f'])); + assert_eq!(args[0], EdnValue::Symbol("?a".to_string())); + } + other => panic!("expected magic guard, got {:?}", other), + } + } + + #[test] + fn test_no_propagation_for_non_recursive_rule() { + // (ancestor ?a ?b) :- [?a :parent ?b] — no recursive call + let rule = make_rule("ancestor", &["?a", "?b"], vec![pat("?a", ":parent", "?b")]); + let adorned: HashMap> = + [("ancestor".to_string(), vec!['b', 'f'])].into_iter().collect(); + let prop_rules = build_propagation_rules(&rule, "ancestor", &adorned); + assert!(prop_rules.is_empty()); + } +``` + +- [ ] **Step 2: Run to confirm failure** + +```bash +cargo test magic_sets::tests::test_propagation_rule_emitted_for_recursive_call -- --nocapture +``` +Expected: FAIL — `cannot find function build_propagation_rules` + +- [ ] **Step 3: Implement `build_propagation_rules`** + +Add to `magic_sets.rs`: + +```rust +/// 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) +/// +/// Returns Vec<(predicate_name, Rule)> to be registered with `register_rule_unchecked`. +pub(crate) fn build_propagation_rules( + rule: &Rule, + predicate: &str, + adorned: &HashMap>, +) -> Vec<(String, Rule)> { + if rule + .body + .iter() + .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) + { + return vec![]; + } + + let Some(adornment) = adorned.get(predicate) else { + return vec![]; + }; + let magic_name = magic_pred_name(predicate, adornment); + + // The bound-position variable from the rule head (head[1] = entity arg). + let bound_head_var = rule + .head + .get(1) + .cloned() + .unwrap_or(EdnValue::Symbol("?_".to_string())); + + // Guard clause reused in every propagation rule body. + let guard = WhereClause::RuleInvocation { + predicate: magic_name.clone(), + args: vec![bound_head_var], + }; + + let mut result = Vec::new(); + + for (i, clause) in rule.body.iter().enumerate() { + let WhereClause::RuleInvocation { + predicate: called_pred, + args: called_args, + } = clause + else { + continue; + }; + + // Only emit propagation for calls to an adorned predicate. + let Some(called_adornment) = adorned.get(called_pred.as_str()) else { + continue; + }; + let called_magic_name = magic_pred_name(called_pred, called_adornment); + + // New magic head arg = bound-position arg of the recursive call (arg0 for bf). + let new_magic_arg = called_args + .first() + .cloned() + .unwrap_or(EdnValue::Symbol("?_".to_string())); + + // Propagation body = guard + all non-RuleInvocation clauses before this call. + let mut prop_body = vec![guard.clone()]; + for preceding in &rule.body[..i] { + if !matches!(preceding, WhereClause::RuleInvocation { .. }) { + prop_body.push(preceding.clone()); + } + } + + result.push(( + called_magic_name.clone(), + Rule { + head: vec![EdnValue::Symbol(called_magic_name), new_magic_arg], + body: prop_body, + }, + )); + } + + result +} +``` + +- [ ] **Step 4: Run all unit tests** + +```bash +cargo test magic_sets::tests -- --nocapture +``` +Expected: all PASS + +- [ ] **Step 5: Commit** + +```bash +git add src/query/datalog/magic_sets.rs +git commit -m "feat(magic-sets): magic propagation rule generation (#289)" +``` + +--- + +### Task 6: SCC adornment propagation + assemble `rewrite()` + +**Files:** +- Modify: `src/query/datalog/magic_sets.rs` + +- [ ] **Step 1: Write failing tests** + +Add to `#[cfg(test)]`: + +```rust + #[test] + fn test_scc_peer_adornment_propagates() { + // even ?n :- (odd ?n) + // odd ?n :- (even ?n) + // Initial: even adorned 'b' → odd should also be adorned via propagation + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked( + "even".to_string(), + make_rule("even", &["?n"], vec![rule_inv("odd", &["?n"])]), + ); + registry.register_rule_unchecked( + "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); + assert!(propagated.contains_key("odd"), "odd should be adorned via SCC"); + } + + #[test] + fn test_rewrite_none_when_all_free() { + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked( + "reach".to_string(), + make_rule("reach", &["?a", "?b"], vec![pat("?a", ":edge", "?b")]), + ); + let query = DatalogQuery::new( + vec![FindSpec::Variable("?x".to_string())], + vec![rule_inv("reach", &["?a", "?b"])], + ); + assert!(rewrite(&query, ®istry).is_none()); + } + + #[test] + fn test_rewrite_some_when_bound_arg() { + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked( + "reach".to_string(), + make_rule("reach", &["?a", "?b"], vec![pat("?a", ":edge", "?b")]), + ); + registry.register_rule_unchecked( + "reach".to_string(), + make_rule( + "reach", + &["?a", "?c"], + vec![rule_inv("reach", &["?a", "?b"]), pat("?b", ":edge", "?c")], + ), + ); + let query = DatalogQuery::new( + vec![FindSpec::Variable("?x".to_string())], + vec![WhereClause::RuleInvocation { + predicate: "reach".to_string(), + args: vec![ + EdnValue::Keyword(":start".to_string()), + EdnValue::Symbol("?x".to_string()), + ], + }], + ); + let result = rewrite(&query, ®istry); + assert!(result.is_some(), "should rewrite when arg0 is literal"); + let (rewritten_reg, seeds) = result.unwrap(); + assert!(!seeds.is_empty(), "should produce seed facts"); + let magic_name = magic_pred_name("reach", &['b', 'f']); + assert!( + !rewritten_reg.get_rules(&magic_name).is_empty(), + "magic propagation rules should be registered" + ); + } +``` + +- [ ] **Step 2: Run to confirm failure** + +```bash +cargo test magic_sets::tests::test_rewrite_some_when_bound_arg -- --nocapture +``` +Expected: FAIL + +- [ ] **Step 3: Implement `propagate_adornments`, `build_rewritten_registry`, and update `rewrite()`** + +Replace the current stub `rewrite()` and add these functions to `magic_sets.rs`: + +```rust +/// Propagate adornments transitively through rule bodies (handles mutual recursion). +/// Starting from `initial`, expands until fixed point. +pub(crate) fn propagate_adornments( + initial: &HashMap>, + registry: &RuleRegistry, +) -> HashMap> { + let mut adorned = initial.clone(); + let mut changed = true; + + while changed { + changed = false; + for (pred, rules) in registry.all_rules() { + let Some(adornment) = adorned.get(pred).cloned() else { + continue; + }; + for rule in rules { + if rule + .body + .iter() + .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) + { + continue; + } + // Seed grounded vars with the head's bound-position var. + let mut grounded: HashSet = HashSet::new(); + if adornment.first() == Some(&'b') { + if let Some(EdnValue::Symbol(v)) = rule.head.get(1) { + grounded.insert(v.clone()); + } + } + 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() { + grounded.insert(v.to_string()); + } + } + WhereClause::RuleInvocation { + predicate: called, + args, + } => { + let call_adornment: Vec = args + .iter() + .map(|a| { + if let Some(v) = a.as_variable() { + if grounded.contains(v) { 'b' } else { 'f' } + } else { + 'b' + } + }) + .collect(); + if has_bound_arg(&call_adornment) + && !adorned.contains_key(called.as_str()) + { + adorned.insert(called.clone(), call_adornment); + changed = true; + } + for a in args { + if let Some(v) = a.as_variable() { + grounded.insert(v.to_string()); + } + } + } + _ => {} + } + } + } + } + } + + adorned +} + +/// Build rewritten registry: copy all rules with magic guards injected for adorned +/// predicates, then register magic propagation rules for all adorned predicates. +/// Uses `register_rule_unchecked` because magic rules are self-recursive (positive cycle). +fn build_rewritten_registry( + registry: &RuleRegistry, + adorned: &HashMap>, +) -> RuleRegistry { + let mut new_reg = RuleRegistry::new(); + + // Copy existing rules, injecting magic guards where adorned. + for (pred, rules) in registry.all_rules() { + for rule in rules { + let rewritten = if let Some(adornment) = adorned.get(pred) { + inject_magic_guard(rule, pred, adornment) + } else { + rule.clone() + }; + new_reg.register_rule_unchecked(pred.to_string(), rewritten); + } + } + + // Emit magic propagation rules for adorned predicates. + for (pred, rules) in registry.all_rules() { + if let Some(adornment) = adorned.get(pred) { + for rule in rules { + for (magic_pred, prop_rule) in build_propagation_rules(rule, pred, adorned) { + new_reg.register_rule_unchecked(magic_pred, prop_rule); + } + } + } + } + + new_reg +} + +pub(crate) fn rewrite( + query: &DatalogQuery, + registry: &RuleRegistry, +) -> Option<(RuleRegistry, Vec<(EntityId, String, Value)>)> { + 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() { + return None; + } + + let adorned = propagate_adornments(&initial_bound, registry); + let seeds = build_seed_facts(&query.where_clauses, &adorned); + if seeds.is_empty() { + return None; + } + + Some((build_rewritten_registry(registry, &adorned), seeds)) +} +``` + +- [ ] **Step 4: Run all unit tests** + +```bash +cargo test magic_sets::tests -- --nocapture +``` +Expected: all PASS + +- [ ] **Step 5: Run full suite (no regressions before wiring)** + +```bash +cargo test +``` +Expected: all PASS + +- [ ] **Step 6: Commit** + +```bash +git add src/query/datalog/magic_sets.rs +git commit -m "feat(magic-sets): SCC propagation and complete rewrite() (#289)" +``` + +--- + +### Task 7: Wire into `execute_query_with_rules` + +**Files:** +- Modify: `src/query/datalog/executor.rs` + +- [ ] **Step 1: Replace the StratifiedEvaluator construction block** + +In `executor.rs`, locate the comment `// Apply temporal filters before evaluating recursive rules` (around line 922). Replace everything from that comment down to (and including) `let derived_storage = evaluator.evaluate(&predicates)?;` with: + +```rust + // Apply temporal filters before evaluating recursive rules + let filtered_facts = self.filter_facts_for_query(&query)?; + + // Convert to FactStorage for StratifiedEvaluator (needs mutable accumulation) + // TODO (post-1.0): use FactStorage::new_noindex() once profiling confirms rules-path + // index rebuild is also a bottleneck. + let filtered_storage = FactStorage::new(); + for fact in filtered_facts.iter().cloned() { + filtered_storage.load_fact(fact)?; + } + + // Compute effective limits: per-query override takes precedence over executor default. + let effective_max_derived = query.max_derived_facts.unwrap_or(self.max_derived_facts); + let effective_max_results = query.max_results.unwrap_or(self.max_results); + + // Apply magic sets rewriting for demand-driven recursive evaluation. + // Returns None for all-free queries — zero overhead path. + let rewritten = { + let reg = self + .rules + .read() + .map_err(|_| anyhow!("rule registry lock poisoned"))?; + crate::query::datalog::magic_sets::rewrite(&query, ®) + }; + let (eval_rules, seed_facts) = match rewritten { + Some((rewritten_registry, seeds)) => (Arc::new(RwLock::new(rewritten_registry)), seeds), + None => (self.rules.clone(), vec![]), + }; + for (entity, attribute, value) in seed_facts { + filtered_storage.load_fact(Fact::new(entity, attribute, value, 0))?; + } + + // Create StratifiedEvaluator — handles negation, stratification, and positive-only rules + let evaluator = StratifiedEvaluator::new( + filtered_storage, + eval_rules, + self.functions.clone(), + 1000, // max iterations + effective_max_derived, + effective_max_results, + ); + + let derived_storage = evaluator.evaluate(&predicates)?; +``` + +- [ ] **Step 2: Run full test suite** + +```bash +cargo test +``` +Expected: all existing tests PASS — magic sets returns `None` for most queries (no bound args), so behaviour is unchanged for them. + +- [ ] **Step 3: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "feat(magic-sets): wire rewrite() into execute_query_with_rules (#289)" +``` + +--- + +### Task 8: Integration tests + +**Files:** +- Create: `tests/magic_sets_test.rs` + +- [ ] **Step 1: Create the test file** + +```rust +//! Integration tests for magic sets rewriting (#289). +//! +//! Asserts result *correctness* only — magic sets must never change query results. + +use minigraf::Minigraf; + +fn open_db() -> Minigraf { + Minigraf::open(":memory:").expect("open db") +} + +fn exec(db: &Minigraf, cmd: &str) -> String { + db.execute(cmd).expect("execute").to_string() +} + +/// Transitive closure with bound start: only reachable nodes returned. +#[test] +fn test_bound_start_transitive_closure() { + let db = open_db(); + exec(&db, "(transact [[:a :edge :b] [:b :edge :c] [:c :edge :d]])"); + exec(&db, "(rule [(reach ?x ?y) [?x :edge ?y]])"); + exec(&db, "(rule [(reach ?x ?z) (reach ?x ?y) [?y :edge ?z]])"); + + let result = exec(&db, "(query [:find ?y :where (reach :a ?y)])"); + assert!(result.contains(":b"), "should reach :b"); + assert!(result.contains(":c"), "should reach :c"); + assert!(result.contains(":d"), "should reach :d"); + assert!(!result.contains(":a"), "should not reach :a (no self-loop)"); +} + +/// All-free transitive closure: magic sets skipped, full result returned correctly. +#[test] +fn test_all_free_transitive_closure() { + let db = open_db(); + exec(&db, "(transact [[:a :edge :b] [:b :edge :c]])"); + exec(&db, "(rule [(reach ?x ?y) [?x :edge ?y]])"); + exec(&db, "(rule [(reach ?x ?z) (reach ?x ?y) [?y :edge ?z]])"); + + let result = exec(&db, "(query [:find ?x ?y :where (reach ?x ?y)])"); + assert!(result.contains(":a")); + assert!(result.contains(":b")); + assert!(result.contains(":c")); +} + +/// Bound result is a subset of all-free result — no extra nodes returned. +#[test] +fn test_bound_result_subset_of_all_free() { + let db = open_db(); + exec(&db, "(transact [[:x :link :y] [:y :link :z] [:p :link :q]])"); + exec(&db, "(rule [(conn ?a ?b) [?a :link ?b]])"); + exec(&db, "(rule [(conn ?a ?c) (conn ?a ?b) [?b :link ?c]])"); + + let bound = exec(&db, "(query [:find ?b :where (conn :x ?b)])"); + let all_free = exec(&db, "(query [:find ?a ?b :where (conn ?a ?b)])"); + + assert!(bound.contains(":y")); + assert!(bound.contains(":z")); + assert!(!bound.contains(":q"), ":q is unreachable from :x"); + assert!(all_free.contains(":q"), ":q is reachable from :p in full closure"); +} + +/// Multi-hop: 4 levels of recursion with a bound start. +#[test] +fn test_multi_hop_recursion_with_bound_start() { + let db = open_db(); + exec(&db, "(transact [[:a :hop :b] [:b :hop :c] [:c :hop :d] [:d :hop :e]])"); + exec(&db, "(rule [(path ?x ?y) [?x :hop ?y]])"); + exec(&db, "(rule [(path ?x ?z) (path ?x ?y) [?y :hop ?z]])"); + + let result = exec(&db, "(query [:find ?y :where (path :a ?y)])"); + assert!(result.contains(":b")); + assert!(result.contains(":c")); + assert!(result.contains(":d")); + assert!(result.contains(":e")); +} + +/// Mutual recursion: even/odd distance from a seeded node. +#[test] +fn test_mutual_recursion_even_odd_distance() { + let db = open_db(); + // Chain: n0 → n1 → n2 → n3 → n4; mark n0 as the even-distance seed + exec(&db, "(transact [ + [:n0 :is-start true] + [:n0 :next :n1] + [:n1 :next :n2] + [:n2 :next :n3] + [:n3 :next :n4] + ])"); + exec(&db, "(rule [(even-d ?x) [?x :is-start true]])"); + exec(&db, "(rule [(even-d ?y) (odd-d ?x) [?x :next ?y]])"); + exec(&db, "(rule [(odd-d ?y) (even-d ?x) [?x :next ?y]])"); + + let evens = exec(&db, "(query [:find ?x :where (even-d ?x)])"); + let odds = exec(&db, "(query [:find ?x :where (odd-d ?x)])"); + + assert!(evens.contains(":n0"), "n0 should be even-distance"); + assert!(evens.contains(":n2"), "n2 should be even-distance"); + assert!(evens.contains(":n4"), "n4 should be even-distance"); + assert!(!evens.contains(":n1"), "n1 should not be even-distance"); + + assert!(odds.contains(":n1"), "n1 should be odd-distance"); + assert!(odds.contains(":n3"), "n3 should be odd-distance"); + assert!(!odds.contains(":n0"), "n0 should not be odd-distance"); +} +``` + +- [ ] **Step 2: Run integration tests** + +```bash +cargo test --test magic_sets_test -- --nocapture +``` +Expected: all 5 PASS + +- [ ] **Step 3: Run full test suite** + +```bash +cargo test +``` +Expected: all PASS + +- [ ] **Step 4: Commit** + +```bash +git add tests/magic_sets_test.rs +git commit -m "test(magic-sets): integration tests for result correctness (#289)" +``` + +--- + +### Task 9: ROADMAP negation note + +**Files:** +- Modify: `ROADMAP.md` + +- [ ] **Step 1: Add §9.6 after the §9.5 branching section** + +Find the `### 9.5 Database Branching / Forking (Exploratory)` section in `ROADMAP.md`. After the closing paragraph of that section (and before whatever comes next), add: + +```markdown +### 9.6 Magic Sets with Stratified Negation (Exploratory) + +Magic sets rewriting (#289) is not applied to mixed rules containing `not`/`not-join` — those continue to use full semi-naive evaluation. Extending to negation is well-studied (Beeri & Ramakrishnan 1991, §5) but adds significant complexity: negated subgoals require care to avoid unsound propagation across stratification boundaries. + +**Only worth pursuing if**: profiling shows that negation-heavy recursive rules are a bottleneck in a real workload. No issue is tracked — investigate if and when the need arises. +``` + +- [ ] **Step 2: Update the "Last Updated" footer** + +Find the last line of `ROADMAP.md`: +``` +**Last Updated**: May 2026 — 962 tests passing, v1.1.1; all post-1.0 work complete; #185 deferred to 2.0; ecosystem, developer tools, and integration examples fully transferred to external repos +``` + +Replace with: +``` +**Last Updated**: June 2026 — magic sets rewriting (#289) implemented; #185 deferred to 2.0; ecosystem, developer tools, and integration examples fully transferred to external repos +``` + +(Update the test count after Task 8 confirms all tests passing.) + +- [ ] **Step 3: Commit** + +```bash +git add ROADMAP.md +git commit -m "docs: add magic sets negation limitation note to ROADMAP §9.6 (#289)" +``` diff --git a/docs/superpowers/specs/2026-06-04-magic-sets-design.md b/docs/superpowers/specs/2026-06-04-magic-sets-design.md new file mode 100644 index 0000000000..d35345c8de --- /dev/null +++ b/docs/superpowers/specs/2026-06-04-magic-sets-design.md @@ -0,0 +1,173 @@ +# Magic Sets Rewriting for Demand-Driven Recursive Rule Evaluation + +**Issue:** #289 +**Date:** 2026-06-04 +**Status:** Approved + +## Problem + +The semi-naive bottom-up evaluator in `RecursiveEvaluator` / `StratifiedEvaluator` computes the complete fixed-point closure of all recursive rules before any query-level filtering is applied. For a transitive-closure rule over a large graph (e.g., a 986-commit git history), a point query like `(ancestor "abc123" ?d)` derives ~500K ancestor pairs even though only O(N) derivations along the relevant path are needed. + +Magic sets rewriting (Beeri & Ramakrishnan 1991) is a compile-time rule transformation that pushes the *bound* variables of the top-level query back into the recursive rules as "magic predicates," restricting derivation to facts reachable from the actual query bindings. + +## Scope + +- Applies to **positive-only recursive rules** (the `RecursiveEvaluator` path). Mixed rules containing `not`/`not-join` are left untransformed and continue to use normal semi-naive evaluation. See the roadmap note in §8. +- Handles **mutual recursion** across an SCC — adornment propagates transitively through the dependency graph. +- **Always on** — no query option or configuration knob. When no bound args exist (all-free query), `rewrite()` returns `None` and evaluation proceeds unchanged with zero overhead. +- **Zero user-visible API changes** — transformation is internal to the query engine. +- **No file format changes** — magic predicates exist only in memory during query execution and are never persisted. + +## Module Structure + +New file: `src/query/datalog/magic_sets.rs` + +Public entry point: + +```rust +pub(crate) fn rewrite( + query: &DatalogQuery, + registry: &RuleRegistry, +) -> Option<(RuleRegistry, Vec<(EntityId, String, Value)>)> +``` + +Returns `None` when all rule invocations in the query have all-free adornment (no bound args → no benefit). Otherwise returns: +- A rewritten `RuleRegistry` containing adorned rules and magic-propagation rules. +- A `Vec` of seed facts `(entity, attribute, value)` to be loaded into `filtered_storage` before evaluation. + +The module is `pub(crate)`. Exposed via `mod magic_sets;` in `src/query/datalog/mod.rs`. + +## Magic Predicate Naming + +Magic predicate attributes use the format `__magic__`, e.g., `__magic_ancestor_bf`. The `__` prefix ensures no collision with user attributes (which conventionally start with `:`). When stored as derived facts by the evaluator the attribute becomes `:__magic_ancestor_bf`. + +Adornment strings use `b` (bound) and `f` (free) per arg position, left-to-right. Examples: `bf`, `bb`, `fb`, `b` (1-arg). + +## Adornment Algorithm + +A single left-to-right pass over the query's where clauses tracks a `HashSet` of grounded variables: + +1. For each `WhereClause::Pattern`: after processing it, add any variable that appears in the entity or value position where at least one sibling position is already concrete or grounded to the grounded set. +2. For each `WhereClause::RuleInvocation { predicate, args }`: classify each arg: + - Non-variable `EdnValue` (literal UUID, string, integer, keyword, etc.) → `b` + - Variable `?x` in the grounded set → `b` + - Variable `?x` not in the grounded set → `f` +3. If all positions are `f`, skip this invocation (no magic treatment). + +For mutual recursion across an SCC: if predicate `p` is adorned and its rules invoke SCC-peer `q`, the adornment propagates to `q` using the bound positions reachable at the point of the `q` invocation in `p`'s rules. + +## Rule Transformation + +For each positive rule (no `not`/`not-join`) defining a predicate `p` with adornment `ad`: + +### 1. Magic guard + +Prepend a `WhereClause::RuleInvocation` for `__magic_p_ad` as the first body clause, using the head's bound-position args: + +``` +// Before: +(ancestor ?a ?c) :- [?a :commit/parent ?b] (ancestor ?b ?c) + +// After (adornment bf — arg0 bound): +(ancestor ?a ?c) :- (__magic_ancestor_bf ?a) [?a :commit/parent ?b] (ancestor ?b ?c) +``` + +### 2. Magic propagation rules + +For each recursive `RuleInvocation` in the rule body calling `p` (or an SCC peer), emit a new rule propagating the magic predicate to the recursive call's bound-position arg. The new rule body is: the magic guard + all non-recursive body clauses preceding the recursive call: + +``` +(__magic_ancestor_bf ?b) :- (__magic_ancestor_bf ?a) [?a :commit/parent ?b] +``` + +### 3. Seed facts + +For each top-level rule invocation in the query with at least one bound arg, emit one seed fact. Encoding depends on which arg is bound: + +- **arg0 bound (`bf` or `bb`):** entity = `edn_to_entity_id(bound_arg)` (handles both UUID literals and keyword aliases like `:alice` via `Uuid::new_v5`); attribute = `format!(":__magic_{}_{}", predname, adornment)`; value = `Value::Boolean(true)` sentinel. The 1-arg magic guard pattern `[?a :__magic_p_ad _]` then binds `?a` to the correct entity. This is the dominant use case (point queries by start node). +- **arg1 bound only (`fb`):** entity = `Uuid::new_v4()` (ephemeral carrier, never persisted); attribute = same format; value = `edn_to_value(bound_arg)`. The magic guard becomes a 2-arg match `[?_ :__magic_p_fb ?b]`. Less common; implementer may treat `fb` as unadorned (all-free fallback) in the first iteration if the encoding complexity is not worth it. + +Seed facts are loaded into `filtered_storage` before `StratifiedEvaluator` runs, making the demand signal available on iteration 1. + +## Integration Point + +In `executor.rs`, `execute_query_with_rules`, after `filtered_storage` is populated and before `StratifiedEvaluator` is constructed: + +```rust +let rewritten = { + let reg = self.rules.read().map_err(|_| anyhow!("rule registry lock poisoned"))?; + magic_sets::rewrite(&query, ®) +}; + +let (eval_rules, seed_facts) = match rewritten { + Some((rewritten_registry, seeds)) => (Arc::new(RwLock::new(rewritten_registry)), seeds), + None => (self.rules.clone(), vec![]), +}; + +for (entity, attribute, value) in seed_facts { + filtered_storage.load_fact(Fact::new(entity, attribute, value, 0))?; +} + +let evaluator = StratifiedEvaluator::new( + filtered_storage, + eval_rules, + self.functions.clone(), + 1000, + effective_max_derived, + effective_max_results, +); +``` + +The post-evaluator result-processing code (pattern matching, result projection, ~100 lines) is unchanged — it operates on `derived_storage` from `evaluator.evaluate(&predicates)?` regardless of which path was taken. + +To avoid duplicating the post-evaluator code, a small refactor extracts evaluator construction into a local variable before the result-processing section. No logic changes. + +## Testing + +### Unit tests — `magic_sets.rs` inline `#[cfg(test)]` + +Test the transformation in isolation (no evaluator): + +- Literal arg → classified `b`; free variable → classified `f` +- Variable grounded by preceding pattern → classified `b` +- All-free adornment → `rewrite()` returns `None` +- Seed facts generated with correct attribute and value for each bound position +- Magic guard rule prepended to rewritten rules +- Magic propagation rules emitted correctly +- SCC peer adornment propagates (mutual recursion case) +- Mixed rules (containing `not`/`not-join`) are left untouched + +### Integration tests — `tests/magic_sets_test.rs` + +End-to-end via `Minigraf::open` / `db.execute()`, asserting **result correctness** (not internal fact counts): + +- Transitive closure with bound start: `(ancestor "abc123" ?d)` returns exactly the correct reachable set +- Transitive closure with all-free: `(ancestor ?a ?b)` returns full closure correctly (magic sets skipped) +- Mutual recursion: `even`/`odd` with bound seed returns only reachable values +- Multi-hop graph: 3+ levels of recursion with bound start produces correct results +- Query result identity: results with magic sets = results without magic sets for same inputs + +The correctness invariant — magic sets must never change query results, only reduce intermediate derivations — is the sole test criterion. Internal derived-fact counts are not asserted (too brittle; subject to evaluation order). + +## Roadmap Note for Negation + +Magic sets rewriting is not applied to mixed rules containing `not`/`not-join`. These continue to use normal semi-naive evaluation. A note will be added to `ROADMAP.md` (following the style of §9.5 branching) marking this as a known limitation: if profiling shows that negation-heavy recursive rules are a bottleneck in practice, the adornment algorithm can be extended per Beeri & Ramakrishnan §5 (magic sets with stratified negation). No issue is created now — this is exploratory. + +## Files Changed + +| File | Change | +|---|---| +| `src/query/datalog/magic_sets.rs` | New module — adornment, transformation, `rewrite()` | +| `src/query/datalog/mod.rs` | Add `pub(crate) mod magic_sets;` | +| `src/query/datalog/executor.rs` | Wire `magic_sets::rewrite()` into `execute_query_with_rules` | +| `tests/magic_sets_test.rs` | New integration test file | +| `ROADMAP.md` | Add negation limitation note | + +## References + +- Beeri, C. & Ramakrishnan, R. (1991). *On the power of magic.* Journal of Logic Programming. +- `src/query/datalog/evaluator.rs` — `RecursiveEvaluator`, `StratifiedEvaluator` +- `src/query/datalog/executor.rs` — `execute_query_with_rules` (integration point) +- `src/query/datalog/optimizer.rs` — precedent for a pure transformation module +- `src/query/datalog/stratification.rs` — `DependencyGraph` (SCC structure reused for mutual recursion) +- Issue #288 — per-query limits (workaround for the symptom this design addresses at the root) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index c7179ad769..59a107522d 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -934,10 +934,30 @@ impl DatalogExecutor { let effective_max_derived = query.max_derived_facts.unwrap_or(self.max_derived_facts); let effective_max_results = query.max_results.unwrap_or(self.max_results); + // Apply magic sets rewriting for demand-driven recursive evaluation. + // Returns None for all-free queries — zero overhead path. + let rewritten = { + let reg = self + .rules + .read() + .map_err(|_| anyhow!("rule registry lock poisoned"))?; + crate::query::datalog::magic_sets::rewrite(&query, ®) + }; + let (eval_rules, seed_facts) = match rewritten { + Some((rewritten_registry, seeds)) => (Arc::new(RwLock::new(rewritten_registry)), seeds), + None => (self.rules.clone(), vec![]), + }; + for (entity, attribute, value) in seed_facts { + // tx_id=0 is intentional: magic seed facts are synthetic EAV triples that carry + // no temporal semantics. They are inserted after temporal filtering has completed, + // so they never participate in valid-time or tx-time queries. + filtered_storage.load_fact(Fact::new(entity, attribute, value, 0))?; + } + // Create StratifiedEvaluator — handles negation, stratification, and positive-only rules let evaluator = StratifiedEvaluator::new( filtered_storage, - self.rules.clone(), + eval_rules, self.functions.clone(), 1000, // max iterations effective_max_derived, diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs new file mode 100644 index 0000000000..bfcb50339f --- /dev/null +++ b/src/query/datalog/magic_sets.rs @@ -0,0 +1,770 @@ +use crate::graph::types::{EntityId, Value}; +use crate::query::datalog::matcher::{edn_to_entity_id, edn_to_value}; +use crate::query::datalog::rules::RuleRegistry; +use crate::query::datalog::types::{DatalogQuery, EdnValue, Rule, WhereClause}; +use std::collections::{HashMap, HashSet}; +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(); + + 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); + } + _ => {} + } + } + + adornments +} + +/// Returns true if at least one position in the adornment is bound. +#[allow(dead_code)] +pub(crate) fn has_bound_arg(adornment: &[char]) -> bool { + adornment.contains(&'b') +} + +/// Convert adornment to string: ['b','f'] → "bf". +#[allow(dead_code)] +pub(crate) fn adornment_string(adornment: &[char]) -> String { + adornment.iter().collect() +} + +/// Magic predicate name: "__magic_ancestor_bf". +#[allow(dead_code)] +pub(crate) fn magic_pred_name(pred: &str, adornment: &[char]) -> String { + format!("__magic_{}_{}", pred, adornment_string(adornment)) +} + +/// Build seed facts for adorned rule invocations with at least one bound arg. +/// +/// Encoding: +/// arg0 bound: entity = edn_to_entity_id(arg0), attr = ":__magic_p_ad", value = Boolean(true) +/// arg1-only bound (fb): entity = Uuid::new_v4() (ephemeral carrier), value = edn_to_value(arg1) +#[allow(dead_code)] +pub(crate) fn build_seed_facts( + where_clauses: &[WhereClause], + adornments: &HashMap>, +) -> Vec<(EntityId, String, Value)> { + let mut seeds = Vec::new(); + + for clause in where_clauses { + let WhereClause::RuleInvocation { predicate, args } = clause else { + continue; + }; + let Some(adornment) = adornments.get(predicate) else { + continue; + }; + if !has_bound_arg(adornment) { + continue; + } + + let magic_attr = format!(":{}", magic_pred_name(predicate, adornment)); + + if adornment.first() == Some(&'b') { + // arg0 bound — dominant case + if let Some(arg0) = args.first() + && let Ok(entity) = edn_to_entity_id(arg0) + { + seeds.push((entity, magic_attr, Value::Boolean(true))); + } + } else if adornment.get(1) == Some(&'b') { + // arg1-only bound (fb) — ephemeral carrier UUID + if let Some(arg1) = args.get(1) + && let Ok(value) = edn_to_value(arg1) + { + seeds.push((Uuid::new_v4(), magic_attr, value)); + } + } + } + + seeds +} + +/// Prepend a magic-predicate guard to a positive rule's body. +/// Rules containing Not/NotJoin are returned unchanged. +/// +/// The guard uses head[1] (the entity-position variable) as its argument, +/// which is always the bound position for the dominant `bf` adornment. +#[allow(dead_code)] +pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char]) -> Rule { + let has_negation = rule + .body + .iter() + .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })); + if has_negation { + return rule.clone(); + } + + debug_assert_eq!( + adornment.len(), + rule.head.len().saturating_sub(1), + "adornment length must equal rule arity" + ); + + let magic_name = magic_pred_name(predicate, adornment); + let bound_head_args: Vec = adornment + .iter() + .enumerate() + .filter(|&(_, &ch)| ch == 'b') + // rule.head[0] is the predicate name; args start at index 1 + .filter_map(|(i, _)| rule.head.get(i + 1).cloned()) + .collect(); + let guard = WhereClause::RuleInvocation { + predicate: magic_name, + args: bound_head_args, + }; + + let mut new_body = Vec::with_capacity(rule.body.len() + 1); + new_body.push(guard); + new_body.extend(rule.body.iter().cloned()); + + Rule { + head: rule.head.clone(), + body: new_body, + } +} + +/// 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) +/// +/// Returns Vec<(predicate_name, Rule)> to be registered with `register_rule_unchecked`. +#[allow(dead_code)] +pub(crate) fn build_propagation_rules( + rule: &Rule, + predicate: &str, + adorned: &HashMap>, +) -> Vec<(String, Rule)> { + if rule + .body + .iter() + .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) + { + return vec![]; + } + + let Some(adornment) = adorned.get(predicate) else { + return vec![]; + }; + let magic_name = magic_pred_name(predicate, adornment); + + // Bound-position variables from the rule head (same logic as inject_magic_guard). + debug_assert_eq!( + adornment.len(), + rule.head.len().saturating_sub(1), + "adornment length must equal rule arity" + ); + let bound_head_vars: Vec = adornment + .iter() + .enumerate() + .filter(|&(_, &ch)| ch == 'b') + // rule.head[0] is the predicate name; args start at index 1 + .filter_map(|(i, _)| rule.head.get(i + 1).cloned()) + .collect(); + + // Guard clause reused in every propagation rule body. + let guard = WhereClause::RuleInvocation { + predicate: magic_name, + args: bound_head_vars, + }; + + let mut result = Vec::new(); + + for (i, clause) in rule.body.iter().enumerate() { + let WhereClause::RuleInvocation { + predicate: called_pred, + args: called_args, + } = clause + else { + continue; + }; + + // Only emit propagation for calls to an adorned predicate. + let Some(called_adornment) = adorned.get(called_pred.as_str()) else { + continue; + }; + let called_magic_name = magic_pred_name(called_pred, called_adornment); + + // New magic head args = bound-position args of the recursive call. + debug_assert_eq!( + called_adornment.len(), + called_args.len(), + "called adornment length must equal called args length" + ); + + // Fix 2: Skip all-free adorned predicates — no bound args means no magic head. + if !has_bound_arg(called_adornment) { + continue; + } + + let new_magic_args: Vec = called_adornment + .iter() + .enumerate() + .filter(|&(_, &ch)| ch == 'b') + // Fix 3: Rename inner `i` to `pos` to avoid shadowing the outer loop variable. + .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()); + } + } + + // Fix 1: Head must include ALL bound args, not just the first. + let mut head = Vec::with_capacity(1 + new_magic_args.len()); + head.push(EdnValue::Symbol(called_magic_name.clone())); + head.extend(new_magic_args); + result.push(( + called_magic_name, + Rule { + head, + body: prop_body, + }, + )); + } + + result +} + +/// Propagate adornments transitively through rule bodies (handles mutual recursion). +/// Starting from `initial`, expands until fixed point. +pub(crate) fn propagate_adornments( + initial: &HashMap>, + registry: &RuleRegistry, +) -> HashMap> { + let mut adorned = initial.clone(); + let mut changed = true; + + 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(); + + 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; + } + // Seed grounded vars with bound-position vars from the rule head + 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()); + } + } + 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() { + 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()); + } + } + } + _ => {} + } + } + } + } + } + + adorned +} + +/// Build rewritten registry: copy all rules with magic guards injected for adorned +/// predicates, then register magic propagation rules for all adorned predicates. +/// Uses `register_rule_unchecked` because magic rules are self-recursive (positive cycle). +fn build_rewritten_registry( + registry: &RuleRegistry, + adorned: &HashMap>, +) -> RuleRegistry { + let mut new_reg = RuleRegistry::new(); + + // Copy existing rules, injecting magic guards where adorned. + for (pred, rules) in registry.all_rules() { + for rule in rules { + let rewritten = if let Some(adornment) = adorned.get(pred) { + inject_magic_guard(rule, pred, adornment) + } else { + rule.clone() + }; + new_reg.register_rule_unchecked(pred.to_string(), rewritten); + } + } + + // Emit magic propagation rules for adorned predicates. + for (pred, rules) in registry.all_rules() { + if adorned.contains_key(pred) { + for rule in rules { + for (magic_pred, prop_rule) in build_propagation_rules(rule, pred, adorned) { + new_reg.register_rule_unchecked(magic_pred, prop_rule); + } + } + } + } + + new_reg +} + +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() { + 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 seeds = build_seed_facts(&query.where_clauses, &adorned); + if seeds.is_empty() { + return None; + } + + Some((build_rewritten_registry(registry, &adorned), seeds)) +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::query::datalog::rules::RuleRegistry; + use crate::query::datalog::types::{FindSpec, Pattern, Rule, WhereClause}; + + #[test] + fn test_rewrite_empty_query_returns_none() { + let query = DatalogQuery::new(vec![FindSpec::Variable("?x".to_string())], vec![]); + let registry = RuleRegistry::new(); + assert!(rewrite(&query, ®istry).is_none()); + } + + fn pat(entity: &str, attr: &str, value: &str) -> WhereClause { + WhereClause::Pattern(Pattern::new( + if entity.starts_with('?') { + EdnValue::Symbol(entity.to_string()) + } else { + EdnValue::Keyword(entity.to_string()) + }, + EdnValue::Keyword(attr.to_string()), + if value.starts_with('?') { + EdnValue::Symbol(value.to_string()) + } else { + EdnValue::String(value.to_string()) + }, + )) + } + + fn rule_inv(pred: &str, args: &[&str]) -> WhereClause { + WhereClause::RuleInvocation { + predicate: pred.to_string(), + args: args + .iter() + .map(|a| { + if a.starts_with('?') { + EdnValue::Symbol(a.to_string()) + } else { + EdnValue::String(a.to_string()) + } + }) + .collect(), + } + } + + fn make_rule(pred: &str, head_args: &[&str], body: Vec) -> Rule { + Rule { + head: std::iter::once(EdnValue::Symbol(pred.to_string())) + .chain(head_args.iter().map(|a| EdnValue::Symbol(a.to_string()))) + .collect(), + body, + } + } + + #[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'])); + } + + #[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'])); + } + + #[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'])); + } + + #[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)); + } + + #[test] + fn test_seed_fact_for_keyword_entity_arg() { + // (ancestor :alice ?y) — arg0 bound (keyword alias) + // seed: entity = edn_to_entity_id(:alice), attr = ":__magic_ancestor_bf", value = true + let clauses = vec![WhereClause::RuleInvocation { + predicate: "ancestor".to_string(), + args: vec![ + EdnValue::Keyword(":alice".to_string()), + EdnValue::Symbol("?y".to_string()), + ], + }]; + let adornments = compute_query_adornments(&clauses); + let seeds = build_seed_facts(&clauses, &adornments); + assert_eq!(seeds.len(), 1); + let (entity, attr, value) = &seeds[0]; + assert_eq!(attr, ":__magic_ancestor_bf"); + assert_eq!(value, &Value::Boolean(true)); + let expected = crate::query::datalog::matcher::edn_to_entity_id(&EdnValue::Keyword( + ":alice".to_string(), + )) + .unwrap(); + assert_eq!(*entity, expected); + } + + #[test] + fn test_no_seed_for_all_free() { + let clauses = vec![rule_inv("ancestor", &["?x", "?y"])]; + let adornments = compute_query_adornments(&clauses); + let seeds = build_seed_facts(&clauses, &adornments); + assert!(seeds.is_empty()); + } + + #[test] + fn test_magic_guard_prepended_to_positive_rule() { + // (ancestor ?a ?c) :- [?a :parent ?b] (ancestor ?b ?c) + // adornment bf → guard (__magic_ancestor_bf ?a) prepended + let rule = make_rule( + "ancestor", + &["?a", "?c"], + vec![ + pat("?a", ":parent", "?b"), + rule_inv("ancestor", &["?b", "?c"]), + ], + ); + let adornment = vec!['b', 'f']; + let rewritten = inject_magic_guard(&rule, "ancestor", &adornment); + match rewritten.body.first().unwrap() { + WhereClause::RuleInvocation { predicate, args } => { + assert_eq!(predicate, &magic_pred_name("ancestor", &adornment)); + assert_eq!(args.len(), 1); + assert_eq!(args[0], EdnValue::Symbol("?a".to_string())); + } + _ => panic!("expected RuleInvocation guard"), + } + } + + #[test] + fn test_magic_guard_bb_adornment() { + // Rule: (reachable ?a ?b) :- [?a :edge/to ?b] + // adornment bb — both args bound → guard gets both args + let rule = make_rule( + "reachable", + &["?a", "?b"], + vec![pat("?a", ":edge/to", "?b")], + ); + let ad = vec!['b', 'b']; + let result = inject_magic_guard(&rule, "reachable", &ad); + let guard = result + .body + .first() + .expect("guard should be first body clause"); + match guard { + WhereClause::RuleInvocation { predicate, args } => { + assert_eq!(predicate, "__magic_reachable_bb"); + assert_eq!(args.len(), 2, "bb adornment should produce 2 guard args"); + assert_eq!(args[0], EdnValue::Symbol("?a".to_string())); + assert_eq!(args[1], EdnValue::Symbol("?b".to_string())); + } + _ => panic!("expected RuleInvocation guard"), + } + } + + #[test] + fn test_mixed_rule_not_touched_by_guard() { + let rule = make_rule( + "eligible", + &["?x"], + vec![ + pat("?x", ":applied", "true"), + WhereClause::Not(vec![pat("?x", ":rejected", "true")]), + ], + ); + let rewritten = inject_magic_guard(&rule, "eligible", &['b']); + // First body clause must still be Pattern (not an injected guard) + assert!( + matches!(rewritten.body.first().unwrap(), WhereClause::Pattern(_)), + "mixed rule must not have guard injected" + ); + } + + #[test] + fn test_propagation_rule_emitted_for_recursive_call() { + // (ancestor ?a ?c) :- [?a :parent ?b] (ancestor ?b ?c) + // bf → (__magic_ancestor_bf ?b) :- (__magic_ancestor_bf ?a) [?a :parent ?b] + let rule = make_rule( + "ancestor", + &["?a", "?c"], + vec![ + pat("?a", ":parent", "?b"), + rule_inv("ancestor", &["?b", "?c"]), + ], + ); + let adorned: HashMap> = [("ancestor".to_string(), vec!['b', 'f'])] + .into_iter() + .collect(); + let prop_rules = build_propagation_rules(&rule, "ancestor", &adorned); + assert_eq!(prop_rules.len(), 1); + + let (pred, prop) = &prop_rules[0]; + assert_eq!( + pred.as_str(), + magic_pred_name("ancestor", &['b', 'f']).as_str() + ); + // Head: [Symbol("__magic_ancestor_bf"), Symbol("?b")] + assert_eq!(prop.head.len(), 2); + assert_eq!(prop.head[1], EdnValue::Symbol("?b".to_string())); + // Body: [magic_guard(?a), [?a :parent ?b]] + assert_eq!(prop.body.len(), 2); + match &prop.body[0] { + WhereClause::RuleInvocation { predicate, args } => { + assert_eq!(predicate, &magic_pred_name("ancestor", &['b', 'f'])); + assert_eq!(args[0], EdnValue::Symbol("?a".to_string())); + } + _ => panic!("expected magic guard in propagation body"), + } + } + + #[test] + fn test_propagation_rule_bb_adornment() { + // (reachable ?a ?b) :- (reachable ?a ?c) [?c :edge/to ?b] + // bb → propagation rule head must have BOTH bound args + let rule = make_rule( + "reachable", + &["?a", "?b"], + vec![ + rule_inv("reachable", &["?a", "?c"]), + pat("?c", ":edge/to", "?b"), + ], + ); + let adorned: HashMap> = [("reachable".to_string(), vec!['b', 'b'])] + .into_iter() + .collect(); + let prop_rules = build_propagation_rules(&rule, "reachable", &adorned); + assert_eq!(prop_rules.len(), 1); + let (_, prop) = &prop_rules[0]; + // Head must have predicate name + 2 args for bb + assert_eq!( + prop.head.len(), + 3, + "bb propagation rule head must have 3 elements (name + 2 args)" + ); + assert_eq!(prop.head[1], EdnValue::Symbol("?a".to_string())); + assert_eq!(prop.head[2], EdnValue::Symbol("?c".to_string())); + } + + #[test] + fn test_no_propagation_for_non_recursive_rule() { + // (ancestor ?a ?b) :- [?a :parent ?b] — no recursive call + let rule = make_rule("ancestor", &["?a", "?b"], vec![pat("?a", ":parent", "?b")]); + let adorned: HashMap> = [("ancestor".to_string(), vec!['b', 'f'])] + .into_iter() + .collect(); + let prop_rules = build_propagation_rules(&rule, "ancestor", &adorned); + assert!(prop_rules.is_empty()); + } + + #[test] + fn test_scc_peer_adornment_propagates() { + // even ?n :- (odd ?n) + // odd ?n :- (even ?n) + // Initial: even adorned 'b' → odd should also be adorned via propagation + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked( + "even".to_string(), + make_rule("even", &["?n"], vec![rule_inv("odd", &["?n"])]), + ); + registry.register_rule_unchecked( + "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); + assert!( + propagated.contains_key("odd"), + "odd should be adorned via SCC" + ); + } + + #[test] + fn test_rewrite_none_when_all_free() { + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked( + "reach".to_string(), + make_rule("reach", &["?a", "?b"], vec![pat("?a", ":edge", "?b")]), + ); + let query = DatalogQuery::new( + vec![FindSpec::Variable("?x".to_string())], + vec![rule_inv("reach", &["?a", "?b"])], + ); + assert!(rewrite(&query, ®istry).is_none()); + } + + #[test] + fn test_rewrite_some_when_bound_arg() { + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked( + "reach".to_string(), + make_rule("reach", &["?a", "?b"], vec![pat("?a", ":edge", "?b")]), + ); + registry.register_rule_unchecked( + "reach".to_string(), + make_rule( + "reach", + &["?a", "?c"], + vec![rule_inv("reach", &["?a", "?b"]), pat("?b", ":edge", "?c")], + ), + ); + let query = DatalogQuery::new( + vec![FindSpec::Variable("?x".to_string())], + vec![WhereClause::RuleInvocation { + predicate: "reach".to_string(), + args: vec![ + EdnValue::Keyword(":start".to_string()), + EdnValue::Symbol("?x".to_string()), + ], + }], + ); + let result = rewrite(&query, ®istry); + assert!(result.is_some(), "should rewrite when arg0 is literal"); + let (rewritten_reg, seeds) = result.unwrap(); + assert!(!seeds.is_empty(), "should produce seed facts"); + let magic_name = magic_pred_name("reach", &['b', 'f']); + assert!( + !rewritten_reg.get_rules(&magic_name).is_empty(), + "magic propagation rules should be registered" + ); + } + + #[test] + fn test_rewritten_registry_has_magic_guard_in_rules() { + let mut registry = RuleRegistry::new(); + registry.register_rule_unchecked( + "reach".to_string(), + make_rule("reach", &["?a", "?b"], vec![pat("?a", ":edge", "?b")]), + ); + let adorned: HashMap> = [("reach".to_string(), vec!['b', 'f'])] + .into_iter() + .collect(); + let new_reg = build_rewritten_registry(®istry, &adorned); + let rules = new_reg.get_rules("reach"); + assert!( + !rules.is_empty(), + "rewritten registry should contain reach rules" + ); + let first_body = rules[0].body.first().expect("rule should have body"); + assert!( + matches!(first_body, WhereClause::RuleInvocation { .. }), + "first body clause of adorned rule should be magic guard" + ); + } +} diff --git a/src/query/datalog/mod.rs b/src/query/datalog/mod.rs index 760cf77e32..642f49c13c 100644 --- a/src/query/datalog/mod.rs +++ b/src/query/datalog/mod.rs @@ -1,6 +1,7 @@ pub mod evaluator; pub mod executor; pub mod functions; +pub(crate) mod magic_sets; pub mod matcher; pub mod optimizer; pub mod parser; diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs new file mode 100644 index 0000000000..19e467dbc6 --- /dev/null +++ b/tests/magic_sets_test.rs @@ -0,0 +1,241 @@ +//! Integration tests for magic sets rewriting (#289). +//! +//! Asserts result *correctness* only — magic sets must never change query results. + +use minigraf::{Minigraf, QueryResult, Value}; +use uuid::Uuid; + +fn open_db() -> Minigraf { + Minigraf::in_memory().expect("open db") +} + +fn exec(db: &Minigraf, cmd: &str) -> QueryResult { + db.execute(cmd) + .unwrap_or_else(|e| panic!("execution error: {}", e)) +} + +fn extract_refs(result: QueryResult) -> Vec { + match result { + QueryResult::QueryResults { results, .. } => results + .into_iter() + .map(|row| match &row[0] { + Value::Ref(uuid) => *uuid, + _ => panic!("Expected Ref in result row"), + }) + .collect(), + _ => panic!("Expected QueryResults"), + } +} + +/// Transitive closure with bound start: only reachable nodes returned. +#[test] +fn test_bound_start_transitive_closure() { + let db = open_db(); + + let a = Uuid::new_v4(); + let b = Uuid::new_v4(); + let c = Uuid::new_v4(); + let d = Uuid::new_v4(); + + exec( + &db, + &format!( + r#"(transact [[#uuid "{}" :edge #uuid "{}"] + [#uuid "{}" :edge #uuid "{}"] + [#uuid "{}" :edge #uuid "{}"]])"#, + a, b, b, c, c, d + ), + ); + exec(&db, r#"(rule [(reach ?x ?y) [?x :edge ?y]])"#); + exec(&db, r#"(rule [(reach ?x ?z) (reach ?x ?y) [?y :edge ?z]])"#); + + let result = exec( + &db, + &format!(r#"(query [:find ?y :where (reach #uuid "{}" ?y)])"#, a), + ); + let targets = extract_refs(result); + + assert!(targets.contains(&b), "should reach b"); + assert!(targets.contains(&c), "should reach c"); + assert!(targets.contains(&d), "should reach d"); + assert!(!targets.contains(&a), "should not reach a (no self-loop)"); +} + +/// All-free transitive closure: magic sets skipped, full result returned correctly. +#[test] +fn test_all_free_transitive_closure() { + let db = open_db(); + + let a = Uuid::new_v4(); + let b = Uuid::new_v4(); + let c = Uuid::new_v4(); + + exec( + &db, + &format!( + r#"(transact [[#uuid "{}" :edge #uuid "{}"] + [#uuid "{}" :edge #uuid "{}"]])"#, + a, b, b, c + ), + ); + exec(&db, r#"(rule [(reach ?x ?y) [?x :edge ?y]])"#); + exec(&db, r#"(rule [(reach ?x ?z) (reach ?x ?y) [?y :edge ?z]])"#); + + let result = exec(&db, r#"(query [:find ?x ?y :where (reach ?x ?y)])"#); + match result { + QueryResult::QueryResults { results, .. } => { + // Should have: (a,b), (b,c), (a,c) + assert_eq!(results.len(), 3, "expected 3 pairs in full closure"); + + let pairs: Vec<(Uuid, Uuid)> = results + .into_iter() + .map(|row| { + let from = match &row[0] { + Value::Ref(u) => *u, + _ => panic!("Expected Ref for ?x"), + }; + let to = match &row[1] { + Value::Ref(u) => *u, + _ => panic!("Expected Ref for ?y"), + }; + (from, to) + }) + .collect(); + + assert!(pairs.contains(&(a, b)), "a->b expected"); + assert!(pairs.contains(&(b, c)), "b->c expected"); + assert!(pairs.contains(&(a, c)), "a->c expected (transitive)"); + } + _ => panic!("Expected QueryResults"), + } +} + +/// Bound result is a subset of all-free result — no extra nodes returned. +#[test] +fn test_bound_result_subset_of_all_free() { + let db = open_db(); + + let x = Uuid::new_v4(); + let y = Uuid::new_v4(); + let z = Uuid::new_v4(); + let p = Uuid::new_v4(); + let q = Uuid::new_v4(); + + exec( + &db, + &format!( + r#"(transact [[#uuid "{}" :link #uuid "{}"] + [#uuid "{}" :link #uuid "{}"] + [#uuid "{}" :link #uuid "{}"]])"#, + x, y, y, z, p, q + ), + ); + exec(&db, r#"(rule [(conn ?a ?b) [?a :link ?b]])"#); + exec(&db, r#"(rule [(conn ?a ?c) (conn ?a ?b) [?b :link ?c]])"#); + + let bound_result = exec( + &db, + &format!(r#"(query [:find ?b :where (conn #uuid "{}" ?b)])"#, x), + ); + let bound_targets = extract_refs(bound_result); + + assert!(bound_targets.contains(&y), "y is reachable from x"); + assert!(bound_targets.contains(&z), "z is reachable from x"); + assert!(!bound_targets.contains(&q), "q is unreachable from x"); + + let all_free_result = exec(&db, r#"(query [:find ?a ?b :where (conn ?a ?b)])"#); + match all_free_result { + QueryResult::QueryResults { results, .. } => { + let all_targets: Vec = results + .into_iter() + .map(|row| match &row[1] { + Value::Ref(u) => *u, + _ => panic!("Expected Ref"), + }) + .collect(); + assert!( + all_targets.contains(&q), + "q is reachable from p in full closure" + ); + } + _ => panic!("Expected QueryResults"), + } +} + +/// Multi-hop: 4 levels of recursion with a bound start. +#[test] +fn test_multi_hop_recursion_with_bound_start() { + let db = open_db(); + + let nodes: Vec = (0..5).map(|_| Uuid::new_v4()).collect(); + + let mut transact = String::from("(transact ["); + for i in 0..4 { + transact.push_str(&format!( + r#"[#uuid "{}" :hop #uuid "{}"]"#, + nodes[i], + nodes[i + 1] + )); + } + transact.push_str("])"); + exec(&db, &transact); + + exec(&db, r#"(rule [(path ?x ?y) [?x :hop ?y]])"#); + exec(&db, r#"(rule [(path ?x ?z) (path ?x ?y) [?y :hop ?z]])"#); + + let result = exec( + &db, + &format!( + r#"(query [:find ?y :where (path #uuid "{}" ?y)])"#, + nodes[0] + ), + ); + let targets = extract_refs(result); + + assert!(targets.contains(&nodes[1]), "should reach node 1"); + assert!(targets.contains(&nodes[2]), "should reach node 2"); + assert!(targets.contains(&nodes[3]), "should reach node 3"); + assert!(targets.contains(&nodes[4]), "should reach node 4"); + assert!( + !targets.contains(&nodes[0]), + "should not reach node 0 (no self-loop)" + ); +} + +/// Mutual recursion: even/odd distance from a seeded node. +#[test] +fn test_mutual_recursion_even_odd_distance() { + let db = open_db(); + + // Chain: n0 → n1 → n2 → n3 → n4; mark n0 as the even-distance seed + let nodes: Vec = (0..5).map(|_| Uuid::new_v4()).collect(); + + let mut transact = format!(r#"(transact [[#uuid "{}" :is-start true]"#, nodes[0]); + for i in 0..4 { + transact.push_str(&format!( + r#" [#uuid "{}" :next #uuid "{}"]"#, + nodes[i], + nodes[i + 1] + )); + } + transact.push_str("])"); + exec(&db, &transact); + + exec(&db, r#"(rule [(even-d ?x) [?x :is-start true]])"#); + exec(&db, r#"(rule [(even-d ?y) (odd-d ?x) [?x :next ?y]])"#); + exec(&db, r#"(rule [(odd-d ?y) (even-d ?x) [?x :next ?y]])"#); + + let evens = extract_refs(exec(&db, r#"(query [:find ?x :where (even-d ?x)])"#)); + let odds = extract_refs(exec(&db, r#"(query [:find ?x :where (odd-d ?x)])"#)); + + assert!(evens.contains(&nodes[0]), "n0 should be even-distance"); + assert!(evens.contains(&nodes[2]), "n2 should be even-distance"); + assert!(evens.contains(&nodes[4]), "n4 should be even-distance"); + assert!(!evens.contains(&nodes[1]), "n1 should not be even-distance"); + + assert!(odds.contains(&nodes[1]), "n1 should be odd-distance"); + assert!(odds.contains(&nodes[3]), "n3 should be odd-distance"); + assert!(!odds.contains(&nodes[0]), "n0 should not be odd-distance"); + assert!(!odds.contains(&nodes[2]), "n2 should not be odd-distance"); + assert!(!odds.contains(&nodes[4]), "n4 should not be odd-distance"); +}