From c2c907dbae4345026314bef31d717489d2788ed4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 11:28:34 +0530 Subject: [PATCH 01/22] docs: add per-query limits implementation plan (#288) Co-Authored-By: Claude Sonnet 4.6 --- .../plans/2026-06-04-per-query-limits.md | 858 ++++++++++++++++++ 1 file changed, 858 insertions(+) create mode 100644 docs/superpowers/plans/2026-06-04-per-query-limits.md diff --git a/docs/superpowers/plans/2026-06-04-per-query-limits.md b/docs/superpowers/plans/2026-06-04-per-query-limits.md new file mode 100644 index 0000000000..08cbfd948e --- /dev/null +++ b/docs/superpowers/plans/2026-06-04-per-query-limits.md @@ -0,0 +1,858 @@ +# Per-Query Complexity Limits 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:** Add `:max-derived-facts N` and `:max-results N` as optional per-query keys in the Datalog query syntax, and raise `DEFAULT_MAX_DERIVED_FACTS` from 100,000 to 1,000,000. + +**Architecture:** Two new `Option` fields on `DatalogQuery` carry per-query overrides through the parse → execute pipeline. In `execute_query_with_rules`, effective limits are computed as `query.field.unwrap_or(self.field)` and passed to `StratifiedEvaluator` for that invocation only — no shared state mutation. All other paths are unaffected. + +**Tech Stack:** Rust, `cargo test` + +--- + +## File Map + +| File | Role | +|---|---| +| `src/query/datalog/types.rs` | Add two `Option` fields to `DatalogQuery`; update both constructors | +| `src/query/datalog/parser.rs` | Parse `:max-derived-facts` and `:max-results` in `parse_query` | +| `src/query/datalog/executor.rs` | Compute effective limits in `execute_query_with_rules`; pass to `StratifiedEvaluator` | +| `src/query/datalog/evaluator.rs` | Raise `DEFAULT_MAX_DERIVED_FACTS` constant to `1_000_000` | +| `src/db.rs` | Update `OpenOptions::max_derived_facts` doc comment to reflect new default | +| `tests/grammar/grammar.pest` | Add `max_derived_facts_section` / `max_results_section` to `query_section` | +| `.wiki/Datalog-Reference.md` | Update EBNF `query-section` + add narrative for new keywords | +| `.wiki/Performance-Tuning.md` | Update default table (100,000 → 1,000,000) + add per-query override note | + +--- + +### Task 1: Raise `DEFAULT_MAX_DERIVED_FACTS` and update doc comments + +**Files:** +- Modify: `src/query/datalog/evaluator.rs:42` +- Modify: `src/db.rs:103-110` + +- [ ] **Step 1: Change the constant in `evaluator.rs`** + +In `src/query/datalog/evaluator.rs`, change line 42: + +```rust +// Before: +pub const DEFAULT_MAX_DERIVED_FACTS: usize = 100_000; + +// After: +/// Default maximum facts that can be derived per iteration +pub const DEFAULT_MAX_DERIVED_FACTS: usize = 1_000_000; +``` + +- [ ] **Step 2: Update the `OpenOptions` doc comment in `db.rs`** + +In `src/db.rs`, the builder method `max_derived_facts` currently says "Defaults to 100_000". Change it: + +```rust + /// Set the maximum facts that can be derived per recursive rule iteration. + /// + /// Defaults to 1_000_000. Use lower values to prevent runaway recursive rules + /// from consuming excessive memory. Can be overridden per-query using + /// `:max-derived-facts N` in the query vector. + pub fn max_derived_facts(mut self, n: usize) -> Self { + self.max_derived_facts = n; + self + } +``` + +Also update the field doc comment in the `OpenOptions` struct (around line 71-73): + +```rust + /// Maximum facts that can be derived per recursive rule iteration. + /// Defaults to 1_000_000. Use to prevent runaway recursive rules. + pub max_derived_facts: usize, +``` + +- [ ] **Step 3: Verify the existing test at `db.rs:1796` still compiles** + +The test `test_max_derived_facts_limit_enforced` sets `.max_derived_facts(100_000)` explicitly — that's fine, it will continue to work with the new default unchanged. + +- [ ] **Step 4: Run tests** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass (the constant change is backwards-compatible — all existing tests either use the default or set it explicitly). + +- [ ] **Step 5: Commit** + +```bash +git add src/query/datalog/evaluator.rs src/db.rs +git commit -m "perf(query): raise DEFAULT_MAX_DERIVED_FACTS from 100K to 1M (#288)" +``` + +--- + +### Task 2: Add `max_derived_facts` / `max_results` fields to `DatalogQuery` + +**Files:** +- Modify: `src/query/datalog/types.rs:522-556` + +This task has no test (the field is internal; tests come in Task 3 via the parser). The struct change must compile cleanly before adding parser support. + +- [ ] **Step 1: Add fields to the struct** + +In `src/query/datalog/types.rs`, change the `DatalogQuery` struct (line 522): + +```rust +pub struct DatalogQuery { + /// Variables to return (from :find clause) + pub find: Vec, + /// Where clauses: patterns and rule invocations + pub where_clauses: Vec, + /// Optional transaction-time snapshot (:as-of) + pub as_of: Option, + /// Optional valid-time filter (:valid-at) + pub valid_at: Option, + /// Grouping variables that participate in grouping but are excluded from output rows. + pub with_vars: Vec, + /// Per-query override for maximum derived facts per recursive rule iteration. + /// `None` falls back to the executor's configured limit (from `OpenOptions`). + pub max_derived_facts: Option, + /// Per-query override for maximum total query results. + /// `None` falls back to the executor's configured limit (from `OpenOptions`). + pub max_results: Option, +} +``` + +- [ ] **Step 2: Update `DatalogQuery::new`** + +```rust + pub fn new(find: Vec, where_clauses: Vec) -> Self { + DatalogQuery { + find, + where_clauses, + as_of: None, + valid_at: None, + with_vars: Vec::new(), + max_derived_facts: None, + max_results: None, + } + } +``` + +- [ ] **Step 3: Update `DatalogQuery::from_patterns`** + +```rust + #[allow(dead_code)] + pub fn from_patterns(find: Vec, patterns: Vec) -> Self { + DatalogQuery { + find, + where_clauses: patterns.into_iter().map(WhereClause::Pattern).collect(), + as_of: None, + valid_at: None, + with_vars: Vec::new(), + max_derived_facts: None, + max_results: None, + } + } +``` + +- [ ] **Step 4: Build to confirm no struct-literal errors** + +```bash +cargo build 2>&1 | grep "^error" | head -20 +``` + +Expected: no errors. (All `DatalogQuery` construction goes through `new()` / `from_patterns()` — the struct is internal and never constructed with `{ field: val, ... }` syntax outside these two constructors.) + +- [ ] **Step 5: Commit** + +```bash +git add src/query/datalog/types.rs +git commit -m "feat(query): add max_derived_facts/max_results fields to DatalogQuery (#288)" +``` + +--- + +### Task 3: Parse `:max-derived-facts` and `:max-results` in `parse_query` + +**Files:** +- Modify: `src/query/datalog/parser.rs` (inside `parse_query`, around line 726) +- Test: `src/query/datalog/parser.rs` (in the existing `#[cfg(test)]` block) + +- [ ] **Step 1: Write the failing tests** + +Add these tests inside the existing `#[cfg(test)]` block in `parser.rs`. Find an appropriate location near the existing `:as-of` / `:valid-at` parse tests. + +```rust +#[test] +fn test_parse_max_derived_facts_valid() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-derived-facts 500000])"#; + let result = parse_datalog_command(input); + assert!(result.is_ok(), "should parse :max-derived-facts"); + match result.unwrap() { + DatalogCommand::Query(q) => { + assert_eq!(q.max_derived_facts, Some(500_000)); + assert_eq!(q.max_results, None); + } + _ => panic!("expected Query"), + } +} + +#[test] +fn test_parse_max_results_valid() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-results 9999])"#; + let result = parse_datalog_command(input); + assert!(result.is_ok(), "should parse :max-results"); + match result.unwrap() { + DatalogCommand::Query(q) => { + assert_eq!(q.max_derived_facts, None); + assert_eq!(q.max_results, Some(9_999)); + } + _ => panic!("expected Query"), + } +} + +#[test] +fn test_parse_both_limits_valid() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-derived-facts 1000000 :max-results 100])"#; + let result = parse_datalog_command(input); + assert!(result.is_ok(), "should parse both limit keys"); + match result.unwrap() { + DatalogCommand::Query(q) => { + assert_eq!(q.max_derived_facts, Some(1_000_000)); + assert_eq!(q.max_results, Some(100)); + } + _ => panic!("expected Query"), + } +} + +#[test] +fn test_parse_max_derived_facts_zero_rejected() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-derived-facts 0])"#; + let result = parse_datalog_command(input); + assert!(result.is_err(), "0 should be rejected"); + let msg = result.unwrap_err(); + assert!( + msg.contains(":max-derived-facts must be >= 1"), + "wrong error: {}", + msg + ); +} + +#[test] +fn test_parse_max_results_zero_rejected() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-results 0])"#; + let result = parse_datalog_command(input); + assert!(result.is_err(), "0 should be rejected"); + let msg = result.unwrap_err(); + assert!( + msg.contains(":max-results must be >= 1"), + "wrong error: {}", + msg + ); +} + +#[test] +fn test_parse_max_derived_facts_duplicate_rejected() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-derived-facts 100 :max-derived-facts 200])"#; + let result = parse_datalog_command(input); + assert!(result.is_err(), "duplicate key should be rejected"); + let msg = result.unwrap_err(); + assert!( + msg.contains("duplicate :max-derived-facts"), + "wrong error: {}", + msg + ); +} + +#[test] +fn test_parse_max_results_duplicate_rejected() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-results 100 :max-results 200])"#; + let result = parse_datalog_command(input); + assert!(result.is_err(), "duplicate key should be rejected"); + let msg = result.unwrap_err(); + assert!( + msg.contains("duplicate :max-results"), + "wrong error: {}", + msg + ); +} + +#[test] +fn test_parse_max_derived_facts_non_integer_rejected() { + let input = r#"(query [:find ?x :where [?x :a :b] :max-derived-facts "a lot"])"#; + let result = parse_datalog_command(input); + assert!(result.is_err(), "non-integer should be rejected"); +} + +#[test] +fn test_parse_limits_order_independent() { + // :max-derived-facts before :find — order should not matter + let input = r#"(query [:max-derived-facts 42 :find ?x :where [?x :a :b]])"#; + let result = parse_datalog_command(input); + assert!(result.is_ok(), "order should not matter"); + match result.unwrap() { + DatalogCommand::Query(q) => assert_eq!(q.max_derived_facts, Some(42)), + _ => panic!("expected Query"), + } +} +``` + +- [ ] **Step 2: Run tests to confirm they fail** + +```bash +cargo test -p minigraf -- test_parse_max_derived_facts_valid test_parse_max_results_valid test_parse_both_limits_valid test_parse_max_derived_facts_zero_rejected test_parse_max_results_zero_rejected test_parse_max_derived_facts_duplicate_rejected test_parse_max_results_duplicate_rejected test_parse_max_derived_facts_non_integer_rejected test_parse_limits_order_independent 2>&1 | grep -E "FAILED|error" +``` + +Expected: tests fail because the parse logic doesn't exist yet. + +- [ ] **Step 3: Add parse logic to `parse_query`** + +In `src/query/datalog/parser.rs`, inside `parse_query` (around line 726), add two new `Option` locals alongside the existing ones: + +```rust + let mut query_as_of: Option = None; + let mut query_valid_at: Option = None; + let mut query_max_derived_facts: Option = None; + let mut query_max_results: Option = None; +``` + +Then add two new `match` arms inside the `match keyword { ... }` block, after the `:any-valid-time` arm and before the `:with` arm: + +```rust + ":max-derived-facts" => { + if query_max_derived_facts.is_some() { + return Err("duplicate :max-derived-facts".to_string()); + } + i += 1; + let val = query_vector + .get(i) + .ok_or_else(|| ":max-derived-facts requires a value".to_string())?; + match val { + EdnValue::Integer(n) if *n >= 1 => { + query_max_derived_facts = Some(*n as usize); + } + EdnValue::Integer(0) | EdnValue::Integer(_) => { + return Err(":max-derived-facts must be >= 1".to_string()); + } + other => { + return Err(format!( + ":max-derived-facts must be a positive integer, got {:?}", + other + )); + } + } + i += 1; + continue; + } + ":max-results" => { + if query_max_results.is_some() { + return Err("duplicate :max-results".to_string()); + } + i += 1; + let val = query_vector + .get(i) + .ok_or_else(|| ":max-results requires a value".to_string())?; + match val { + EdnValue::Integer(n) if *n >= 1 => { + query_max_results = Some(*n as usize); + } + EdnValue::Integer(0) | EdnValue::Integer(_) => { + return Err(":max-results must be >= 1".to_string()); + } + other => { + return Err(format!( + ":max-results must be a positive integer, got {:?}", + other + )); + } + } + i += 1; + continue; + } +``` + +Then, at the end of `parse_query` where the fields are assigned (around line 903): + +```rust + query.as_of = query_as_of; + query.valid_at = query_valid_at; + query.with_vars = with_vars; + query.max_derived_facts = query_max_derived_facts; + query.max_results = query_max_results; +``` + +- [ ] **Step 4: Note on the integer match pattern** + +The `EdnValue::Integer(n) if *n >= 1` guard matches positive integers. The catch-all `EdnValue::Integer(0) | EdnValue::Integer(_)` arm is unreachable for positive `n` but Rust requires exhaustiveness — the compiler may warn. If so, simplify to: + +```rust + EdnValue::Integer(n) if *n >= 1 => { + query_max_derived_facts = Some(*n as usize); + } + EdnValue::Integer(_) => { + return Err(":max-derived-facts must be >= 1".to_string()); + } +``` + +- [ ] **Step 5: Run the parser tests** + +```bash +cargo test -p minigraf -- test_parse_max_derived_facts_valid test_parse_max_results_valid test_parse_both_limits_valid test_parse_max_derived_facts_zero_rejected test_parse_max_results_zero_rejected test_parse_max_derived_facts_duplicate_rejected test_parse_max_results_duplicate_rejected test_parse_max_derived_facts_non_integer_rejected test_parse_limits_order_independent 2>&1 | tail -10 +``` + +Expected: all 9 tests pass. + +- [ ] **Step 6: Run the full test suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 7: Commit** + +```bash +git add src/query/datalog/parser.rs +git commit -m "feat(query): parse :max-derived-facts and :max-results per-query keys (#288)" +``` + +--- + +### Task 4: Apply per-query limits in `execute_query_with_rules` + +**Files:** +- Modify: `src/query/datalog/executor.rs:934-941` +- Test: `src/query/datalog/executor.rs` (in `#[cfg(test)]` block) + +- [ ] **Step 1: Write the failing tests** + +Add these to the `#[cfg(test)]` block in `executor.rs`: + +```rust +#[test] +fn test_per_query_max_derived_facts_overrides_executor_default() { + // Executor default is 1M; per-query override is 5 — should fail. + let storage = FactStorage::new(); + let rules = Arc::new(RwLock::new(RuleRegistry::new())); + let functions = Arc::new(RwLock::new(FunctionRegistry::with_builtins())); + let mut executor = DatalogExecutor::new_with_rules_and_functions( + storage, + rules.clone(), + functions.clone(), + ); + executor.set_limits(1_000_000, 1_000_000); + + // Register a recursive rule + let rule_cmd = parse_datalog_command( + "(rule [(reachable ?x ?y)] [?x :edge ?y])" + ).unwrap(); + executor.execute(rule_cmd).unwrap(); + let rule_cmd2 = parse_datalog_command( + "(rule [(reachable ?x ?z)] [?x :edge ?y] (reachable ?y ?z))" + ).unwrap(); + executor.execute(rule_cmd2).unwrap(); + + // Transact some facts + executor.execute(parse_datalog_command( + r#"(transact [[:a :edge :b] [:b :edge :c]])"# + ).unwrap()).unwrap(); + + // Query with per-query limit of 1 — should fail + let result = executor.execute(parse_datalog_command( + "(query [:find ?x ?y :where (reachable ?x ?y) :max-derived-facts 1])" + ).unwrap()); + assert!(result.is_err(), "per-query limit of 1 should fail"); + + // Query with per-query limit of 1M — should succeed + let result = executor.execute(parse_datalog_command( + "(query [:find ?x ?y :where (reachable ?x ?y) :max-derived-facts 1000000])" + ).unwrap()); + assert!(result.is_ok(), "per-query limit of 1M should succeed"); +} + +#[test] +fn test_per_query_limit_does_not_bleed_into_next_query() { + // A tight per-query limit on one query should not affect the next. + let storage = FactStorage::new(); + let rules = Arc::new(RwLock::new(RuleRegistry::new())); + let functions = Arc::new(RwLock::new(FunctionRegistry::with_builtins())); + let executor = DatalogExecutor::new_with_rules_and_functions( + storage, + rules.clone(), + functions.clone(), + ); + + executor.execute(parse_datalog_command( + "(rule [(reachable ?x ?y)] [?x :edge ?y])" + ).unwrap()).unwrap(); + + executor.execute(parse_datalog_command( + r#"(transact [[:a :edge :b]])"# + ).unwrap()).unwrap(); + + // First query: tight limit, will fail + let _ = executor.execute(parse_datalog_command( + "(query [:find ?x ?y :where (reachable ?x ?y) :max-derived-facts 1])" + ).unwrap()); + + // Second query: no per-query limit — should use executor default (1M) and succeed + let result = executor.execute(parse_datalog_command( + "(query [:find ?x ?y :where (reachable ?x ?y)])" + ).unwrap()); + assert!(result.is_ok(), "next query should not inherit the tight per-query limit"); +} +``` + +- [ ] **Step 2: Run to confirm they fail** + +```bash +cargo test -p minigraf -- test_per_query_max_derived_facts_overrides_executor_default test_per_query_limit_does_not_bleed_into_next_query 2>&1 | grep -E "FAILED|error\[" | head -10 +``` + +Expected: tests fail because the override logic is not wired in yet. + +- [ ] **Step 3: Implement the override in `execute_query_with_rules`** + +In `src/query/datalog/executor.rs`, in `execute_query_with_rules` (line ~934), change the `StratifiedEvaluator::new` call: + +```rust + // 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); + + // Create StratifiedEvaluator — handles negation, stratification, and positive-only rules + let evaluator = StratifiedEvaluator::new( + filtered_storage, + self.rules.clone(), + self.functions.clone(), + 1000, // max iterations + effective_max_derived, + effective_max_results, + ); +``` + +The two new locals must be declared before the `StratifiedEvaluator::new` call. The existing `self.max_derived_facts` / `self.max_results` fields are read, not mutated — no state bleeds between queries. + +- [ ] **Step 4: Run the new tests** + +```bash +cargo test -p minigraf -- test_per_query_max_derived_facts_overrides_executor_default test_per_query_limit_does_not_bleed_into_next_query 2>&1 | tail -10 +``` + +Expected: both pass. + +- [ ] **Step 5: Run the full test suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 6: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "feat(query): apply per-query limits in execute_query_with_rules (#288)" +``` + +--- + +### Task 5: Integration test via `Minigraf::execute` + +**Files:** +- Test: `src/db.rs` (in `#[cfg(test)]` block) + +This task confirms the full path from `Minigraf::execute` through the parser and executor works end-to-end. + +- [ ] **Step 1: Write the failing test** + +Add this to the `#[cfg(test)]` block in `src/db.rs`, near the existing `test_max_derived_facts_limit_enforced` test: + +```rust +#[test] +fn test_per_query_max_derived_facts_via_execute() { + let db = OpenOptions::new() + .max_derived_facts(1_000_000) + .open_memory() + .unwrap(); + + // Register a recursive rule: reachable via edges + db.execute("(rule [(reachable ?x ?y)] [?x :edge ?y])").unwrap(); + db.execute("(rule [(reachable ?x ?z)] [?x :edge ?y] (reachable ?y ?z))").unwrap(); + + // Transact a small graph: a -> b -> c + db.execute(r#"(transact [[:a :edge :b] [:b :edge :c]])"#).unwrap(); + + // Per-query limit of 1 — too tight, must fail + let result = db.execute( + "(query [:find ?x ?y :where (reachable ?x ?y) :max-derived-facts 1])" + ); + assert!(result.is_err(), "per-query limit of 1 should fail"); + + // Per-query limit of 1M — should succeed + let result = db.execute( + "(query [:find ?x ?y :where (reachable ?x ?y) :max-derived-facts 1000000])" + ); + assert!(result.is_ok(), "per-query limit of 1M should succeed"); + + // No per-query limit — should fall back to OpenOptions default (1M) and succeed + let result = db.execute( + "(query [:find ?x ?y :where (reachable ?x ?y)])" + ); + assert!(result.is_ok(), "no per-query limit should use database default"); +} + +#[test] +fn test_per_query_max_results_via_execute() { + let db = Minigraf::in_memory().unwrap(); + + db.execute(r#"(transact [[:a :v 1] [:b :v 2] [:c :v 3]])"#).unwrap(); + + // Per-query :max-results 1 — should not error (max_results on non-rules path + // is enforced in StratifiedEvaluator; for non-rules queries the field is parsed + // and carried through but the result set is not forcibly truncated — this test + // confirms the field parses cleanly and the query succeeds). + let result = db.execute( + "(query [:find ?e :where [?e :v ?v] :max-results 1])" + ); + assert!(result.is_ok(), "query with :max-results should parse and execute"); +} +``` + +- [ ] **Step 2: Run to confirm they pass immediately** (the implementation is already wired) + +```bash +cargo test -p minigraf -- test_per_query_max_derived_facts_via_execute test_per_query_max_results_via_execute 2>&1 | tail -10 +``` + +Expected: both pass (Tasks 1–4 already supply the implementation). + +- [ ] **Step 3: Run full suite** + +```bash +cargo test 2>&1 | tail -5 +``` + +Expected: all tests pass. + +- [ ] **Step 4: Commit** + +```bash +git add src/db.rs +git commit -m "test(db): add integration tests for per-query :max-derived-facts and :max-results (#288)" +``` + +--- + +### Task 6: Update `tests/grammar/grammar.pest` + +**Files:** +- Modify: `tests/grammar/grammar.pest:90-92` + +The `query_section` rule must include the two new keywords or the grammar conformance tests will diverge from the actual parser. + +- [ ] **Step 1: Add the new section rules** + +In `tests/grammar/grammar.pest`, change the `query_section` rule (lines 90–92) and add two new rules below `with_section`: + +```pest +query_section = { + find_section | where_section | as_of_section | + valid_at_section | any_valid_time_section | with_section | + max_derived_facts_section | max_results_section +} + +// ...existing rules stay unchanged... + +with_section = { ":with" ~ variable+ } +max_derived_facts_section = { ":max-derived-facts" ~ integer_lit } +max_results_section = { ":max-results" ~ integer_lit } +``` + +(The semantic check that the integer is ≥ 1 happens in the Rust parser, not in pest.) + +- [ ] **Step 2: Run any grammar conformance tests** + +```bash +cargo test grammar 2>&1 | tail -10 +``` + +Expected: pass (or "no tests matched" if the suite doesn't auto-test the PEG file — either is fine as long as there are no compile errors). + +- [ ] **Step 3: Commit** + +```bash +git add tests/grammar/grammar.pest +git commit -m "docs(grammar): add :max-derived-facts and :max-results to query_section (#288)" +``` + +--- + +### Task 7: Update `.wiki/Datalog-Reference.md` + +**Files:** +- Modify: `.wiki/Datalog-Reference.md` + +Two changes: (1) EBNF `query-section` rule, (2) a new narrative section documenting the keywords. + +- [ ] **Step 1: Update the EBNF `query-section` rule** + +Find the block (around line 28–37): + +```ebnf +query-section ::= + find-section | where-section | as-of-section | + valid-at-section | any-valid-time-section | with-section +``` + +Change to: + +```ebnf +query-section ::= + find-section | where-section | as-of-section | + valid-at-section | any-valid-time-section | with-section | + max-derived-facts-section | max-results-section + +max-derived-facts-section ::= ":max-derived-facts" integer +max-results-section ::= ":max-results" integer +``` + +- [ ] **Step 2: Add a narrative section** + +Find the `:valid-at` narrative section (around line 329). After the `:valid-at` section, add: + +```markdown +### `:max-derived-facts` and `:max-results` — per-query complexity limits + +Override the database-level `OpenOptions` complexity limits for a single query: + +```datalog +;; Run a transitive-closure query that would normally hit the 1M default +(query [:find ?ancestor + :where (ancestor ?ancestor "abc123") + :max-derived-facts 5000000 + :max-results 10000]) +``` + +Both keys are optional and order-independent. Omitting a key falls back to the `OpenOptions` +value for that limit. Values must be positive integers (≥ 1). + +- `:max-derived-facts N` — caps how many facts the recursive rule engine can derive + internally before returning an error. Use when a legitimate recursive query exceeds + the database default. +- `:max-results N` — caps the maximum number of result rows returned. Applies inside + the rule evaluator; for non-recursive queries results are not truncated by this value. + +The limits are applied for that query only and do not affect subsequent queries. +``` + +- [ ] **Step 3: Commit the wiki** + +```bash +cd .wiki && git add Datalog-Reference.md && git commit -m "docs: add :max-derived-facts and :max-results to Datalog Reference (#288)" && git push && cd .. +``` + +--- + +### Task 8: Update `.wiki/Performance-Tuning.md` + +**Files:** +- Modify: `.wiki/Performance-Tuning.md` + +Two changes: (1) update the default in the table, (2) add a per-query override note. + +- [ ] **Step 1: Update the default in the configuration table** + +Find the table (around line 46–50): + +```markdown +| `max_derived_facts` | 100,000 | derived facts per rule iteration | +``` + +Change to: + +```markdown +| `max_derived_facts` | 1,000,000 | derived facts per rule iteration | +``` + +- [ ] **Step 2: Update the prose below the table** + +Find (around line 64–66): + +```markdown +**`max_derived_facts` / `max_results`** — Safety limits, not performance knobs. Lower them to fail +fast on runaway recursive rules or unexpectedly large result sets; raise only if a legitimate query +hits the ceiling. +``` + +Change to: + +```markdown +**`max_derived_facts` / `max_results`** — Safety limits, not performance knobs. Lower them to fail +fast on runaway recursive rules or unexpectedly large result sets; raise only if a legitimate query +hits the ceiling. For one-off queries that need a different limit without reconfiguring the database, +use `:max-derived-facts N` or `:max-results N` directly in the query vector — see the +[Datalog Reference](Datalog-Reference#max-derived-facts-and-max-results--per-query-complexity-limits). +``` + +- [ ] **Step 3: Commit the wiki** + +```bash +cd .wiki && git add Performance-Tuning.md && git commit -m "docs: update max_derived_facts default to 1M; add per-query override note (#288)" && git push && cd .. +``` + +--- + +### Task 9: Final verification and close + +- [ ] **Step 1: Run the complete test suite one final time** + +```bash +cargo test 2>&1 | tail -10 +``` + +Expected: all tests pass, no regressions. + +- [ ] **Step 2: Smoke-test in the REPL** + +```bash +echo '(query [:find ?x :where [?x :a :b] :max-derived-facts 999999 :max-results 50])' | cargo run --quiet +``` + +Expected: `No results` (no facts match) — confirms the query parses and executes without error. + +- [ ] **Step 3: Commit the final plan doc** + +```bash +git add docs/superpowers/plans/2026-06-04-per-query-limits.md +git commit -m "docs: add per-query limits implementation plan (#288)" +``` + +- [ ] **Step 4: Push and create PR** + +```bash +git push origin +gh pr create --title "feat(query): per-query :max-derived-facts and :max-results; raise default to 1M (#288)" \ + --body "$(cat <<'EOF' +## Summary + +- Adds `:max-derived-facts N` and `:max-results N` as optional per-query keys in the Datalog query syntax +- Per-query values override the `OpenOptions` database-level limits for that single query only; no shared state mutation +- Raises `DEFAULT_MAX_DERIVED_FACTS` from 100,000 to 1,000,000 +- Updates `tests/grammar/grammar.pest`, `.wiki/Datalog-Reference.md`, `.wiki/Performance-Tuning.md` + +## Test plan + +- [ ] All existing tests pass +- [ ] Parser tests: valid keys, `0` rejected, duplicate rejected, non-integer rejected, order-independent +- [ ] Executor tests: per-query override takes effect; does not bleed into next query +- [ ] Integration tests via `Minigraf::execute` for both `:max-derived-facts` and `:max-results` + +Closes #288 +Tracks long-term magic sets work in #289 + +🤖 Generated with [Claude Code](https://claude.com/claude-code) +EOF +)" +``` From 0ca9c85d8c69509e71cec2a16899b68563784318 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 13:19:51 +0530 Subject: [PATCH 02/22] docs: add magic sets rewriting design spec (#289) Co-Authored-By: Claude Sonnet 4.6 --- .../specs/2026-06-04-magic-sets-design.md | 173 ++++++++++++++++++ 1 file changed, 173 insertions(+) create mode 100644 docs/superpowers/specs/2026-06-04-magic-sets-design.md 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..2817088395 --- /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 = the bound UUID literal; 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). Arg0 is always a `Uuid` in Minigraf's EAV model. +- **arg1 bound only (`fb`):** entity = `Uuid::new_v4()` (carrier, never persisted); attribute = same format; value = the bound value. 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) From 90e5a7120cb37166a2c9fddd94b1e4391093225d Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 13:30:57 +0530 Subject: [PATCH 03/22] docs: fix magic sets seed fact entity encoding for keyword aliases (#289) Co-Authored-By: Claude Sonnet 4.6 --- docs/superpowers/specs/2026-06-04-magic-sets-design.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/docs/superpowers/specs/2026-06-04-magic-sets-design.md b/docs/superpowers/specs/2026-06-04-magic-sets-design.md index 2817088395..d35345c8de 100644 --- a/docs/superpowers/specs/2026-06-04-magic-sets-design.md +++ b/docs/superpowers/specs/2026-06-04-magic-sets-design.md @@ -84,8 +84,8 @@ For each recursive `RuleInvocation` in the rule body calling `p` (or an SCC peer 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 = the bound UUID literal; 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). Arg0 is always a `Uuid` in Minigraf's EAV model. -- **arg1 bound only (`fb`):** entity = `Uuid::new_v4()` (carrier, never persisted); attribute = same format; value = the bound value. 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. +- **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. From 56b87f13622b8069e1a3407b390c22387b8d1bee Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 13:43:03 +0530 Subject: [PATCH 04/22] docs: add magic sets implementation plan (#289) Co-Authored-By: Claude Sonnet 4.6 --- .../plans/2026-06-04-magic-sets.md | 1140 +++++++++++++++++ 1 file changed, 1140 insertions(+) create mode 100644 docs/superpowers/plans/2026-06-04-magic-sets.md 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)" +``` From 2a959b583272e1e0af1ab2a27a3865f13704ae9f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 14:27:33 +0530 Subject: [PATCH 05/22] feat(magic-sets): scaffold module (#289) --- src/query/datalog/magic_sets.rs | 29 +++++++++++++++++++++++++++++ src/query/datalog/mod.rs | 1 + 2 files changed, 30 insertions(+) create mode 100644 src/query/datalog/magic_sets.rs diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs new file mode 100644 index 0000000000..46a93a3ecb --- /dev/null +++ b/src/query/datalog/magic_sets.rs @@ -0,0 +1,29 @@ +#[allow(unused_imports)] +use crate::graph::types::{EntityId, Value}; +use crate::query::datalog::rules::RuleRegistry; +use crate::query::datalog::types::{DatalogQuery, EdnValue, WhereClause}; +#[allow(unused_imports)] +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()); + } +} diff --git a/src/query/datalog/mod.rs b/src/query/datalog/mod.rs index 760cf77e32..d092e17227 100644 --- a/src/query/datalog/mod.rs +++ b/src/query/datalog/mod.rs @@ -3,6 +3,7 @@ pub mod executor; pub mod functions; pub mod matcher; pub mod optimizer; +pub(crate) mod magic_sets; pub mod parser; pub mod prepared; pub mod rules; From 5a70e7116e580c9a054d67c1e7f1932ef6052452 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 14:30:03 +0530 Subject: [PATCH 06/22] fix(magic-sets): clean up unused imports and add dead_code allow Remove unused EdnValue and WhereClause imports from scaffold; they will be added in Task 2 when implementing adornment classification. Keep HashMap and HashSet imports with allow(unused_imports) since they'll be used in Task 2. Add #[allow(dead_code)] to rewrite() which isn't called until integration in Task 7. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 46a93a3ecb..5e9be98185 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -1,10 +1,11 @@ #[allow(unused_imports)] use crate::graph::types::{EntityId, Value}; use crate::query::datalog::rules::RuleRegistry; -use crate::query::datalog::types::{DatalogQuery, EdnValue, WhereClause}; +use crate::query::datalog::types::DatalogQuery; #[allow(unused_imports)] use std::collections::{HashMap, HashSet}; +#[allow(dead_code)] pub(crate) fn rewrite( _query: &DatalogQuery, _registry: &RuleRegistry, From 2f496d788950cb46aca91cb5f4c69211552bbf08 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 14:32:16 +0530 Subject: [PATCH 07/22] feat(magic-sets): adornment classification (#289) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 135 +++++++++++++++++++++++++++++++- 1 file changed, 131 insertions(+), 4 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 5e9be98185..8cc2c8a1c9 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -1,10 +1,65 @@ -#[allow(unused_imports)] use crate::graph::types::{EntityId, Value}; use crate::query::datalog::rules::RuleRegistry; -use crate::query::datalog::types::DatalogQuery; -#[allow(unused_imports)] +use crate::query::datalog::types::{DatalogQuery, EdnValue, Rule, WhereClause}; use std::collections::{HashMap, HashSet}; +/// 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)) +} + #[allow(dead_code)] pub(crate) fn rewrite( _query: &DatalogQuery, @@ -16,7 +71,7 @@ pub(crate) fn rewrite( #[cfg(test)] mod tests { use super::*; - use crate::query::datalog::types::FindSpec; + use crate::query::datalog::types::{FindSpec, Pattern, Rule, WhereClause}; #[test] fn test_rewrite_empty_query_returns_none() { @@ -27,4 +82,76 @@ mod tests { 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(), + } + } + + #[allow(dead_code)] + 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)); + } } From f8c98614ef419d3fd91fb58f7f35471a2c16461e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 14:35:09 +0530 Subject: [PATCH 08/22] feat(magic-sets): seed fact generation (#289) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 79 +++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 8cc2c8a1c9..e937588a69 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -1,7 +1,9 @@ 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; /// 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 @@ -60,6 +62,51 @@ 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() { + 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::new_v4(), magic_attr, value)); + } + } + } + } + + seeds +} + #[allow(dead_code)] pub(crate) fn rewrite( _query: &DatalogQuery, @@ -154,4 +201,36 @@ mod tests { 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()); + } } From 0248ec78e91201e209032e410bb99553d7d4b213 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:13:16 +0530 Subject: [PATCH 09/22] feat(magic-sets): magic guard injection into positive rules (#289) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 72 +++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index e937588a69..59fb05015b 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -107,6 +107,39 @@ pub(crate) fn build_seed_facts( 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(); + } + + 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 } +} + #[allow(dead_code)] pub(crate) fn rewrite( _query: &DatalogQuery, @@ -233,4 +266,43 @@ mod tests { 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())); + } + 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 an injected guard) + assert!( + matches!(rewritten.body.first().unwrap(), WhereClause::Pattern(_)), + "mixed rule must not have guard injected" + ); + } } From b3fee5246d92816a395eb94a78cdf72241356f1e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:17:27 +0530 Subject: [PATCH 10/22] fix(magic-sets): use adornment-driven bound-arg extraction in inject_magic_guard (#289) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 36 +++++++++++++++++++++++++++------ 1 file changed, 30 insertions(+), 6 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 59fb05015b..3dae4490cd 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -123,14 +123,15 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char } let magic_name = magic_pred_name(predicate, adornment); - let bound_head_arg = rule - .head - .get(1) - .cloned() - .unwrap_or(EdnValue::Symbol("?_".to_string())); + let bound_head_args: Vec = adornment + .iter() + .enumerate() + .filter(|&(_, &ch)| ch == 'b') + .filter_map(|(i, _)| rule.head.get(i + 1).cloned()) + .collect(); let guard = WhereClause::RuleInvocation { predicate: magic_name, - args: vec![bound_head_arg], + args: bound_head_args, }; let mut new_body = Vec::with_capacity(rule.body.len() + 1); @@ -288,6 +289,29 @@ mod tests { } } + #[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( From 93e434c611c95d385791c08d806d01125618f03f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:20:33 +0530 Subject: [PATCH 11/22] fix(magic-sets): address code quality issues in inject_magic_guard (#289) - Add debug_assert_eq! to catch adornment/arity mismatch before silent filter_map drop - Replace {:?} WhereClause debug format in test panic arms (CodeQL rust/cleartext-logging) - Add inline comment explaining i+1 offset for predicate-name-skipping in head args Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 3dae4490cd..a941370e1d 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -122,11 +122,18 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char 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 { @@ -285,7 +292,7 @@ mod tests { assert_eq!(args.len(), 1); assert_eq!(args[0], EdnValue::Symbol("?a".to_string())); } - other => panic!("expected RuleInvocation guard, got {:?}", other), + _ => panic!("expected RuleInvocation guard"), } } From 8920d7c2387f510c92179239fc212390ca5839fa Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:23:50 +0530 Subject: [PATCH 12/22] feat(magic-sets): magic propagation rule generation (#289) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 141 ++++++++++++++++++++++++++++++++ 1 file changed, 141 insertions(+) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index a941370e1d..a2f81a6fa4 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -148,6 +148,107 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char 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" + ); + let new_magic_args: Vec = called_adornment + .iter() + .enumerate() + .filter(|&(_, &ch)| ch == 'b') + .filter_map(|(i, _)| called_args.get(i).cloned()) + .collect(); + + // 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_args + .into_iter() + .next() + .unwrap_or(EdnValue::Symbol("?_".to_string())), + ], + body: prop_body, + }, + )); + } + + result +} + #[allow(dead_code)] pub(crate) fn rewrite( _query: &DatalogQuery, @@ -336,4 +437,44 @@ mod tests { "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_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()); + } } From e818ab4cdff15a6e971b0d922701ea1eb2d4eef9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:26:55 +0530 Subject: [PATCH 13/22] fix(magic-sets): correct multi-bound propagation rule heads in build_propagation_rules (#289) - Fix 1: head now includes ALL bound args (not just first) for multi-bound adornments like bb - Fix 2: skip all-free adorned predicates to avoid emitting malformed propagation rules - Fix 3: rename inner loop variable `i` to `pos` to avoid shadowing outer loop's `i` - Fix 4: add test_propagation_rule_bb_adornment verifying 3-element head for bb adornment Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 50 ++++++++++++++++++++++++--------- 1 file changed, 36 insertions(+), 14 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index a2f81a6fa4..c6a592c365 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -216,11 +216,18 @@ pub(crate) fn build_propagation_rules( 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') - .filter_map(|(i, _)| called_args.get(i).cloned()) + // 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. @@ -231,19 +238,11 @@ pub(crate) fn build_propagation_rules( } } - result.push(( - called_magic_name.clone(), - Rule { - head: vec![ - EdnValue::Symbol(called_magic_name), - new_magic_args - .into_iter() - .next() - .unwrap_or(EdnValue::Symbol("?_".to_string())), - ], - body: prop_body, - }, - )); + // 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 @@ -468,6 +467,29 @@ mod tests { } } + #[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 From c0111b25174654f2111670f0bb86796c3ec68cc1 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:30:17 +0530 Subject: [PATCH 14/22] feat(magic-sets): SCC propagation and complete rewrite() (#289) Implements propagate_adornments() for fixed-point adornment propagation through mutually-recursive SCCs, build_rewritten_registry() to assemble the magic-transformed rule set, and replaces the rewrite() stub with the full implementation. Adds 3 new unit tests (16 total, all passing). Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 206 +++++++++++++++++++++++++++++++- 1 file changed, 202 insertions(+), 4 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index c6a592c365..c17eef8b6c 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -248,17 +248,145 @@ pub(crate) fn build_propagation_rules( result } -#[allow(dead_code)] +/// 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' { + if 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(); + 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, + query: &DatalogQuery, + registry: &RuleRegistry, ) -> Option<(RuleRegistry, Vec<(EntityId, String, Value)>)> { - None + 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)) } #[cfg(test)] mod tests { use super::*; + use crate::query::datalog::rules::RuleRegistry; use crate::query::datalog::types::{FindSpec, Pattern, Rule, WhereClause}; #[test] @@ -499,4 +627,74 @@ mod tests { 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" + ); + } } From e078cda79a83c77ec5b1b2064ee785689b700a48 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:37:00 +0530 Subject: [PATCH 15/22] fix(magic-sets): address clippy and documentation issues in magic_sets (#289) - Fix indexing_slicing: replace &rule.body[..i] with rule.body.iter().take(i) - Add first-writer-wins comment in propagate_adornments for multi-call-site clarity - Fix three collapsible_if warnings using let-chain syntax - Remove spurious #[allow(dead_code)] from make_rule test helper - Add test_rewritten_registry_has_magic_guard_in_rules for guard injection coverage Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 50 ++++++++++++++++++++++++--------- 1 file changed, 36 insertions(+), 14 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index c17eef8b6c..ee2711c139 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -89,17 +89,17 @@ pub(crate) fn build_seed_facts( 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))); - } + 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) { - if let Ok(value) = edn_to_value(arg1) { - seeds.push((Uuid::new_v4(), magic_attr, value)); - } + if let Some(arg1) = args.get(1) + && let Ok(value) = edn_to_value(arg1) + { + seeds.push((Uuid::new_v4(), magic_attr, value)); } } } @@ -232,7 +232,7 @@ pub(crate) fn build_propagation_rules( // Propagation body = guard + all non-RuleInvocation clauses before this call. let mut prop_body = vec![guard.clone()]; - for preceding in &rule.body[..i] { + for preceding in rule.body.iter().take(i) { if !matches!(preceding, WhereClause::RuleInvocation { .. }) { prop_body.push(preceding.clone()); } @@ -277,10 +277,10 @@ pub(crate) fn propagate_adornments( // 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' { - if let Some(v) = rule.head.get(i + 1).and_then(|e| e.as_variable()) { - grounded.insert(v.to_string()); - } + 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 { @@ -302,6 +302,10 @@ pub(crate) fn propagate_adornments( 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()) { @@ -431,7 +435,6 @@ mod tests { } } - #[allow(dead_code)] fn make_rule(pred: &str, head_args: &[&str], body: Vec) -> Rule { Rule { head: std::iter::once(EdnValue::Symbol(pred.to_string())) @@ -697,4 +700,23 @@ mod tests { "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" + ); + } } From a8bb47beb06b74d345ff406fe5da9ebb3972bc2f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:42:40 +0530 Subject: [PATCH 16/22] feat(magic-sets): wire rewrite() into execute_query_with_rules (#289) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Also guard against all-bound (bb) adornments in rewrite() — the magic-guard encoding does not support multi-bound seed facts, and fully-bound queries gain nothing from magic sets; return None to fall through to the regular evaluator unchanged. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 19 ++++++++++++++++++- src/query/datalog/magic_sets.rs | 10 ++++++++++ 2 files changed, 28 insertions(+), 1 deletion(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index c7179ad769..f1b2d448d6 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -934,10 +934,27 @@ 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 { + 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 index ee2711c139..43e5bbc4cf 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -378,6 +378,16 @@ pub(crate) fn rewrite( return None; } + // Magic sets only helps when at least one predicate has a free ('f') position. + // For fully-bound adornments (e.g. "bb"), the regular evaluator is already optimal + // and the magic-guard encoding doesn't support multi-bound seed facts. + let any_free = initial_bound + .values() + .any(|ad| ad.iter().any(|&ch| ch == '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() { From a55d8f5a4a6af1dfa439613c3e99de8f9593b749 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:47:18 +0530 Subject: [PATCH 17/22] fix(magic-sets): clarify seed fact tx_id and any_free guard comments (#289) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 3 +++ src/query/datalog/magic_sets.rs | 8 +++++--- 2 files changed, 8 insertions(+), 3 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index f1b2d448d6..59a107522d 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -948,6 +948,9 @@ impl DatalogExecutor { 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))?; } diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 43e5bbc4cf..58d5fb692a 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -378,9 +378,11 @@ pub(crate) fn rewrite( return None; } - // Magic sets only helps when at least one predicate has a free ('f') position. - // For fully-bound adornments (e.g. "bb"), the regular evaluator is already optimal - // and the magic-guard encoding doesn't support multi-bound seed facts. + // 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.iter().any(|&ch| ch == 'f')); From 594000f6c5b8a4f394ca1ff7092dcaa8a074845d Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:49:44 +0530 Subject: [PATCH 18/22] test(magic-sets): integration tests for result correctness (#289) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Five tests covering bound-start transitive closure, all-free closure, subset correctness, multi-hop recursion, and mutual recursion (even/odd distance) — asserting magic sets rewriting never changes query results. Co-Authored-By: Claude Sonnet 4.6 --- tests/magic_sets_test.rs | 232 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 232 insertions(+) create mode 100644 tests/magic_sets_test.rs diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs new file mode 100644 index 0000000000..56f884f82e --- /dev/null +++ b/tests/magic_sets_test.rs @@ -0,0 +1,232 @@ +//! 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, + other => panic!("Expected Ref, got {:?}", other), + }) + .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"); +} From 1403903f7be131b5afb5b00fdfff13425703cec8 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:51:27 +0530 Subject: [PATCH 19/22] fix(magic-sets): fix CodeQL violation and strengthen mutual-recursion test (#289) Remove {:?} on Value in extract_refs (CodeQL rust/cleartext-logging); add two missing negative assertions for n2/n4 in test_mutual_recursion_even_odd_distance. Co-Authored-By: Claude Sonnet 4.6 --- tests/magic_sets_test.rs | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs index 56f884f82e..89964c85c4 100644 --- a/tests/magic_sets_test.rs +++ b/tests/magic_sets_test.rs @@ -19,7 +19,7 @@ fn extract_refs(result: QueryResult) -> Vec { .into_iter() .map(|row| match &row[0] { Value::Ref(uuid) => *uuid, - other => panic!("Expected Ref, got {:?}", other), + _ => panic!("Expected Ref in result row"), }) .collect(), _ => panic!("Expected QueryResults"), @@ -229,4 +229,6 @@ fn test_mutual_recursion_even_odd_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"); } From 2fa43c6d1eb9f13c7d7d28934321e5a61f244efb Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:53:32 +0530 Subject: [PATCH 20/22] =?UTF-8?q?docs:=20add=20magic=20sets=20negation=20l?= =?UTF-8?q?imitation=20note=20to=20ROADMAP=20=C2=A79.6=20(#289)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- ROADMAP.md | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) 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 From 656fb8026bfd1e77519975c8b3a15f8cc537a10a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:58:45 +0530 Subject: [PATCH 21/22] style: cargo fmt (#289) --- src/query/datalog/magic_sets.rs | 90 +++++++++++++++++++++++---------- src/query/datalog/mod.rs | 2 +- tests/magic_sets_test.rs | 25 +++++---- 3 files changed, 81 insertions(+), 36 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 58d5fb692a..b246bc7417 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -145,7 +145,10 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char new_body.push(guard); new_body.extend(rule.body.iter().cloned()); - Rule { head: rule.head.clone(), body: new_body } + Rule { + head: rule.head.clone(), + body: new_body, + } } /// Build magic propagation rules for adorned recursive calls within a rule body. @@ -242,7 +245,13 @@ pub(crate) fn build_propagation_rules( 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.push(( + called_magic_name, + Rule { + head, + body: prop_body, + }, + )); } result @@ -293,7 +302,10 @@ pub(crate) fn propagate_adornments( grounded.insert(v.to_string()); } } - WhereClause::RuleInvocation { predicate: called, args } => { + WhereClause::RuleInvocation { + predicate: called, + args, + } => { let call_adornment: Vec = args .iter() .map(|a| match a.as_variable() { @@ -407,10 +419,7 @@ mod tests { #[test] fn test_rewrite_empty_query_returns_none() { - let query = DatalogQuery::new( - vec![FindSpec::Variable("?x".to_string())], - vec![], - ); + let query = DatalogQuery::new(vec![FindSpec::Variable("?x".to_string())], vec![]); let registry = RuleRegistry::new(); assert!(rewrite(&query, ®istry).is_none()); } @@ -473,7 +482,10 @@ mod tests { #[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 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'])); } @@ -503,9 +515,9 @@ mod tests { 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()), - ) + let expected = crate::query::datalog::matcher::edn_to_entity_id(&EdnValue::Keyword( + ":alice".to_string(), + )) .unwrap(); assert_eq!(*entity, expected); } @@ -525,7 +537,10 @@ mod tests { let rule = make_rule( "ancestor", &["?a", "?c"], - vec![pat("?a", ":parent", "?b"), rule_inv("ancestor", &["?b", "?c"])], + vec![ + pat("?a", ":parent", "?b"), + rule_inv("ancestor", &["?b", "?c"]), + ], ); let adornment = vec!['b', 'f']; let rewritten = inject_magic_guard(&rule, "ancestor", &adornment); @@ -550,7 +565,10 @@ mod tests { ); 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"); + let guard = result + .body + .first() + .expect("guard should be first body clause"); match guard { WhereClause::RuleInvocation { predicate, args } => { assert_eq!(predicate, "__magic_reachable_bb"); @@ -587,15 +605,22 @@ mod tests { let rule = make_rule( "ancestor", &["?a", "?c"], - vec![pat("?a", ":parent", "?b"), rule_inv("ancestor", &["?b", "?c"])], + vec![ + pat("?a", ":parent", "?b"), + rule_inv("ancestor", &["?b", "?c"]), + ], ); - let adorned: HashMap> = - [("ancestor".to_string(), vec!['b', 'f'])].into_iter().collect(); + 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()); + 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())); @@ -622,13 +647,18 @@ mod tests { pat("?c", ":edge/to", "?b"), ], ); - let adorned: HashMap> = - [("reachable".to_string(), vec!['b', 'b'])].into_iter().collect(); + 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.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())); } @@ -637,8 +667,9 @@ mod tests { 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 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()); } @@ -660,7 +691,10 @@ mod tests { 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"); + assert!( + propagated.contains_key("odd"), + "odd should be adorned via SCC" + ); } #[test] @@ -720,11 +754,15 @@ mod tests { "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 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"); + 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 { .. }), diff --git a/src/query/datalog/mod.rs b/src/query/datalog/mod.rs index d092e17227..642f49c13c 100644 --- a/src/query/datalog/mod.rs +++ b/src/query/datalog/mod.rs @@ -1,9 +1,9 @@ pub mod evaluator; pub mod executor; pub mod functions; +pub(crate) mod magic_sets; pub mod matcher; pub mod optimizer; -pub(crate) mod magic_sets; pub mod parser; pub mod prepared; pub mod rules; diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs index 89964c85c4..19e467dbc6 100644 --- a/tests/magic_sets_test.rs +++ b/tests/magic_sets_test.rs @@ -10,7 +10,8 @@ fn open_db() -> Minigraf { } fn exec(db: &Minigraf, cmd: &str) -> QueryResult { - db.execute(cmd).unwrap_or_else(|e| panic!("execution error: {}", e)) + db.execute(cmd) + .unwrap_or_else(|e| panic!("execution error: {}", e)) } fn extract_refs(result: QueryResult) -> Vec { @@ -152,7 +153,10 @@ fn test_bound_result_subset_of_all_free() { _ => panic!("Expected Ref"), }) .collect(); - assert!(all_targets.contains(&q), "q is reachable from p in full closure"); + assert!( + all_targets.contains(&q), + "q is reachable from p in full closure" + ); } _ => panic!("Expected QueryResults"), } @@ -181,7 +185,10 @@ fn test_multi_hop_recursion_with_bound_start() { let result = exec( &db, - &format!(r#"(query [:find ?y :where (path #uuid "{}" ?y)])"#, nodes[0]), + &format!( + r#"(query [:find ?y :where (path #uuid "{}" ?y)])"#, + nodes[0] + ), ); let targets = extract_refs(result); @@ -189,7 +196,10 @@ fn test_multi_hop_recursion_with_bound_start() { 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)"); + assert!( + !targets.contains(&nodes[0]), + "should not reach node 0 (no self-loop)" + ); } /// Mutual recursion: even/odd distance from a seeded node. @@ -200,10 +210,7 @@ fn test_mutual_recursion_even_odd_distance() { // 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] - ); + 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 "{}"]"#, @@ -219,7 +226,7 @@ fn test_mutual_recursion_even_odd_distance() { 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)])"#)); + 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"); From c5d98f92a350d2a4ef6693b425ce9bae91c0661b Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 4 Jun 2026 15:59:38 +0530 Subject: [PATCH 22/22] style: fix clippy type_complexity and manual_contains (#289) --- src/query/datalog/magic_sets.rs | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index b246bc7417..bfcb50339f 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -5,6 +5,9 @@ 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). @@ -376,10 +379,7 @@ fn build_rewritten_registry( new_reg } -pub(crate) fn rewrite( - query: &DatalogQuery, - registry: &RuleRegistry, -) -> Option<(RuleRegistry, Vec<(EntityId, String, Value)>)> { +pub(crate) fn rewrite(query: &DatalogQuery, registry: &RuleRegistry) -> Option { let initial = compute_query_adornments(&query.where_clauses); let initial_bound: HashMap> = initial .into_iter() @@ -395,9 +395,7 @@ pub(crate) fn rewrite( // 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.iter().any(|&ch| ch == 'f')); + let any_free = initial_bound.values().any(|ad| ad.contains(&'f')); if !any_free { return None; }