From 7f9f00e3e6145c8df65d12a8455f8d65e677e6b7 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 28 Jun 2026 16:02:50 +0530 Subject: [PATCH 1/4] test(magic-sets): add failing tests for #297 and #298 --- tests/magic_sets_test.rs | 64 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs index 19e467dbc..eca565c14 100644 --- a/tests/magic_sets_test.rs +++ b/tests/magic_sets_test.rs @@ -239,3 +239,67 @@ fn test_mutual_recursion_even_odd_distance() { assert!(!odds.contains(&nodes[2]), "n2 should not be odd-distance"); assert!(!odds.contains(&nodes[4]), "n4 should not be odd-distance"); } + +/// #298 — value-position keyword binding: (reports-to ?emp :alice) must return +/// employees whose manager is :alice. Previously returned empty due to broken +/// fb seed encoding. +#[test] +fn test_value_position_keyword_binding() { + let db = open_db(); + let bob = Uuid::new_v4(); + let carol = Uuid::new_v4(); + + exec( + &db, + &format!( + r#"(transact [[#uuid "{}" :employee/manager :alice] + [#uuid "{}" :employee/manager :alice]])"#, + bob, carol + ), + ); + exec( + &db, + r#"(rule [(reports-to ?emp ?mgr) [?emp :employee/manager ?mgr]])"#, + ); + + let result = exec(&db, r#"(query [:find ?emp :where (reports-to ?emp :alice)])"#); + let targets = extract_refs(result); + + assert_eq!(targets.len(), 2, "expected 2 employees reporting to alice"); + assert!(targets.contains(&bob), "bob should report to alice"); + assert!(targets.contains(&carol), "carol should report to alice"); +} + +/// #297 — recursive rule with intermediate variable and entity-position keyword: +/// (reach :a ?y) must return the values reachable from :a via :edge. +/// Previously failed with "Unbound variable in rule head: ?mid". +#[test] +fn test_recursive_intermediate_variable_with_keyword_entity() { + let db = open_db(); + + exec(&db, r#"(transact [[:a :edge :b] [:b :edge :c]])"#); + exec(&db, r#"(rule [(reach ?x ?y) [?x :edge ?y]])"#); + exec( + &db, + r#"(rule [(reach ?x ?y) [?x :edge ?mid] (reach ?mid ?y)])"#, + ); + + let result = exec(&db, r#"(query [:find ?y :where (reach :a ?y)])"#); + + match result { + minigraf::QueryResult::QueryResults { results, .. } => { + let values: Vec = + results.into_iter().map(|row| row[0].clone()).collect(); + assert_eq!(values.len(), 2, "expected 2 results"); + assert!( + values.contains(&minigraf::Value::Keyword(":b".to_string())), + "expected :b in results" + ); + assert!( + values.contains(&minigraf::Value::Keyword(":c".to_string())), + "expected :c in results" + ); + } + _ => panic!("expected QueryResults"), + } +} From bf3aa98cbba4e20124e430df21766877fbc0123c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 28 Jun 2026 16:39:53 +0530 Subject: [PATCH 2/4] fix(magic-sets): fix fb adornment seed encoding and guard injection (#297, #298) Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/magic_sets.rs | 106 ++++++++++++++++++++++++++------ 1 file changed, 86 insertions(+), 20 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index bfcb50339..b5aa45081 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -65,11 +65,20 @@ pub(crate) fn magic_pred_name(pred: &str, adornment: &[char]) -> String { format!("__magic_{}_{}", pred, adornment_string(adornment)) } +/// Return a deterministic sentinel entity UUID for an `fb`-adorned magic predicate. +/// +/// Using a stable UUID (v5, OID namespace, keyed on the magic attribute name) +/// means the seed fact entity and the guard literal always match, without +/// requiring the bound variable to be coerced through `edn_to_entity_id`. +fn sentinel_entity(magic_attr: &str) -> EntityId { + Uuid::new_v5(&Uuid::NAMESPACE_OID, magic_attr.as_bytes()) +} + /// 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) +/// arg1-only bound (fb): entity = sentinel_entity(...), value = edn_to_value(arg1) #[allow(dead_code)] pub(crate) fn build_seed_facts( where_clauses: &[WhereClause], @@ -98,11 +107,13 @@ pub(crate) fn build_seed_facts( seeds.push((entity, magic_attr, Value::Boolean(true))); } } else if adornment.get(1) == Some(&'b') { - // arg1-only bound (fb) — ephemeral carrier UUID + // arg1-only bound (fb) — deterministic sentinel entity so the guard + // can match via entity position while the bound value stays in value + // position, preserving its original type (e.g. Keyword). if let Some(arg1) = args.get(1) && let Ok(value) = edn_to_value(arg1) { - seeds.push((Uuid::new_v4(), magic_attr, value)); + seeds.push((sentinel_entity(&magic_attr), magic_attr, value)); } } } @@ -132,16 +143,38 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char ); let magic_name = magic_pred_name(predicate, adornment); - let bound_head_args: Vec = adornment - .iter() - .enumerate() - .filter(|&(_, &ch)| ch == 'b') - // rule.head[0] is the predicate name; args start at index 1 - .filter_map(|(i, _)| rule.head.get(i + 1).cloned()) - .collect(); - let guard = WhereClause::RuleInvocation { - predicate: magic_name, - args: bound_head_args, + // For fb adornments (entity position free, value position bound): emit a + // 2-arg guard [sentinel, bound_var] so the pattern matches value position, + // keeping the bound variable's original type (e.g. Keyword) intact. + // For bf/bb adornments: 1-arg guard with entity-position bound vars (unchanged). + let guard = if adornment.first() == Some(&'f') && has_bound_arg(adornment) { + let magic_attr = format!(":{}", magic_name); + let sentinel = EdnValue::Uuid(sentinel_entity(&magic_attr)); + let bound_var = 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()) + .next(); + WhereClause::RuleInvocation { + predicate: magic_name, + args: bound_var + .map(|v| vec![sentinel, v]) + .unwrap_or_default(), + } + } else { + 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(); + WhereClause::RuleInvocation { + predicate: magic_name, + args: bound_head_args, + } }; let mut new_body = Vec::with_capacity(rule.body.len() + 1); @@ -194,9 +227,28 @@ pub(crate) fn build_propagation_rules( .collect(); // Guard clause reused in every propagation rule body. - let guard = WhereClause::RuleInvocation { - predicate: magic_name, - args: bound_head_vars, + // fb adornment: 2-arg sentinel guard (mirrors inject_magic_guard fix). + // bf/bb: 1-arg entity-position guard (unchanged). + let guard = if adornment.first() == Some(&'f') && has_bound_arg(adornment) { + let magic_attr_str = format!(":{}", magic_name); + let sentinel = EdnValue::Uuid(sentinel_entity(&magic_attr_str)); + let bound_var = adornment + .iter() + .enumerate() + .filter(|&(_, &ch)| ch == 'b') + .filter_map(|(i, _)| rule.head.get(i + 1).cloned()) + .next(); + WhereClause::RuleInvocation { + predicate: magic_name, + args: bound_var + .map(|v| vec![sentinel, v]) + .unwrap_or_default(), + } + } else { + WhereClause::RuleInvocation { + predicate: magic_name, + args: bound_head_vars, + } }; let mut result = Vec::new(); @@ -244,10 +296,24 @@ pub(crate) fn build_propagation_rules( } } - // 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); + // Build the propagation rule head. + // For fb-adorned called predicates: head = [pred, sentinel, bound_val_var] + // so the derived magic fact lands in value position. + // For bf/bb: head = [pred, bound_entity_vars...] (unchanged). + let head = if called_adornment.first() == Some(&'f') && has_bound_arg(called_adornment) { + let called_magic_attr = format!(":{}", called_magic_name); + let sentinel = EdnValue::Uuid(sentinel_entity(&called_magic_attr)); + let mut h = Vec::with_capacity(3); + h.push(EdnValue::Symbol(called_magic_name.clone())); + h.push(sentinel); + h.extend(new_magic_args); + h + } else { + let mut h = Vec::with_capacity(1 + new_magic_args.len()); + h.push(EdnValue::Symbol(called_magic_name.clone())); + h.extend(new_magic_args); + h + }; result.push(( called_magic_name, Rule { From f173f2167acb8fd0db0711acea3e13ba4e772f10 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 28 Jun 2026 16:57:38 +0530 Subject: [PATCH 3/4] test(magic-sets): add unit tests for fb sentinel entity and guard format --- src/query/datalog/magic_sets.rs | 91 +++++++++++++++++++++++++++++++++ 1 file changed, 91 insertions(+) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index b5aa45081..6ba339733 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -833,4 +833,95 @@ mod tests { "first body clause of adorned rule should be magic guard" ); } + + #[test] + fn test_fb_seed_uses_sentinel_entity() { + // Same keyword arg must produce the same entity UUID on repeated calls + // (deterministic sentinel, not random UUID). + let clauses = vec![WhereClause::RuleInvocation { + predicate: "reports-to".to_string(), + args: vec![ + EdnValue::Symbol("?emp".to_string()), + EdnValue::Keyword(":alice".to_string()), + ], + }]; + let adornments: HashMap> = + [("reports-to".to_string(), vec!['f', 'b'])].into_iter().collect(); + + let seeds1 = build_seed_facts(&clauses, &adornments); + let seeds2 = build_seed_facts(&clauses, &adornments); + + assert_eq!(seeds1.len(), 1, "expected 1 seed"); + assert_eq!(seeds2.len(), 1, "expected 1 seed"); + assert_eq!( + seeds1[0].0, seeds2[0].0, + "sentinel entity must be deterministic" + ); + } + + #[test] + fn test_fb_guard_is_two_arg() { + // inject_magic_guard for ['f','b'] must emit a 2-arg RuleInvocation: + // [Uuid(sentinel), Symbol("?mgr")] + // so the pattern matches value position rather than entity position. + let rule = make_rule( + "reports-to", + &["?emp", "?mgr"], + vec![pat("?emp", ":employee/manager", "?mgr")], + ); + let adornment = vec!['f', 'b']; + let rewritten = inject_magic_guard(&rule, "reports-to", &adornment); + let guard = rewritten.body.first().expect("guard must be first body clause"); + match guard { + WhereClause::RuleInvocation { predicate, args } => { + assert_eq!(predicate, "__magic_reports-to_fb"); + assert_eq!(args.len(), 2, "fb guard must be 2-arg"); + assert!( + matches!(args[0], EdnValue::Uuid(_)), + "first arg must be sentinel UUID" + ); + assert_eq!(args[1], EdnValue::Symbol("?mgr".to_string())); + } + _ => panic!("expected RuleInvocation guard"), + } + } + + #[test] + fn test_fb_sentinel_matches_seed() { + // The sentinel UUID in the guard must equal the entity in the seed fact, + // so that pattern matching can find the seed. + let clauses = vec![WhereClause::RuleInvocation { + predicate: "reports-to".to_string(), + args: vec![ + EdnValue::Symbol("?emp".to_string()), + EdnValue::Keyword(":alice".to_string()), + ], + }]; + let adornments: HashMap> = + [("reports-to".to_string(), vec!['f', 'b'])].into_iter().collect(); + + let seeds = build_seed_facts(&clauses, &adornments); + assert_eq!(seeds.len(), 1, "expected 1 seed"); + let seed_entity = seeds[0].0; + + let rule = make_rule( + "reports-to", + &["?emp", "?mgr"], + vec![pat("?emp", ":employee/manager", "?mgr")], + ); + let adornment = vec!['f', 'b']; + let rewritten = inject_magic_guard(&rule, "reports-to", &adornment); + let guard = rewritten.body.first().expect("guard must be first body clause"); + match guard { + WhereClause::RuleInvocation { predicate: _, args } => { + match &args[0] { + EdnValue::Uuid(u) => { + assert_eq!(*u, seed_entity, "sentinel in guard must match seed entity"); + } + _ => panic!("expected UUID as first guard arg"), + } + } + _ => panic!("expected RuleInvocation guard"), + } + } } From 219e07400e838745b5c258bf12fa0a2d5cb8f7de Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 28 Jun 2026 17:57:05 +0530 Subject: [PATCH 4/4] style: apply cargo fmt to magic_sets fix and tests --- src/query/datalog/magic_sets.rs | 40 +++++++++++++++++---------------- tests/magic_sets_test.rs | 5 ++++- 2 files changed, 25 insertions(+), 20 deletions(-) diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 6ba339733..2ba77b140 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -159,9 +159,7 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char .next(); WhereClause::RuleInvocation { predicate: magic_name, - args: bound_var - .map(|v| vec![sentinel, v]) - .unwrap_or_default(), + args: bound_var.map(|v| vec![sentinel, v]).unwrap_or_default(), } } else { let bound_head_args: Vec = adornment @@ -240,9 +238,7 @@ pub(crate) fn build_propagation_rules( .next(); WhereClause::RuleInvocation { predicate: magic_name, - args: bound_var - .map(|v| vec![sentinel, v]) - .unwrap_or_default(), + args: bound_var.map(|v| vec![sentinel, v]).unwrap_or_default(), } } else { WhereClause::RuleInvocation { @@ -845,8 +841,9 @@ mod tests { EdnValue::Keyword(":alice".to_string()), ], }]; - let adornments: HashMap> = - [("reports-to".to_string(), vec!['f', 'b'])].into_iter().collect(); + let adornments: HashMap> = [("reports-to".to_string(), vec!['f', 'b'])] + .into_iter() + .collect(); let seeds1 = build_seed_facts(&clauses, &adornments); let seeds2 = build_seed_facts(&clauses, &adornments); @@ -871,7 +868,10 @@ mod tests { ); let adornment = vec!['f', 'b']; let rewritten = inject_magic_guard(&rule, "reports-to", &adornment); - let guard = rewritten.body.first().expect("guard must be first body clause"); + let guard = rewritten + .body + .first() + .expect("guard must be first body clause"); match guard { WhereClause::RuleInvocation { predicate, args } => { assert_eq!(predicate, "__magic_reports-to_fb"); @@ -897,8 +897,9 @@ mod tests { EdnValue::Keyword(":alice".to_string()), ], }]; - let adornments: HashMap> = - [("reports-to".to_string(), vec!['f', 'b'])].into_iter().collect(); + let adornments: HashMap> = [("reports-to".to_string(), vec!['f', 'b'])] + .into_iter() + .collect(); let seeds = build_seed_facts(&clauses, &adornments); assert_eq!(seeds.len(), 1, "expected 1 seed"); @@ -911,16 +912,17 @@ mod tests { ); let adornment = vec!['f', 'b']; let rewritten = inject_magic_guard(&rule, "reports-to", &adornment); - let guard = rewritten.body.first().expect("guard must be first body clause"); + let guard = rewritten + .body + .first() + .expect("guard must be first body clause"); match guard { - WhereClause::RuleInvocation { predicate: _, args } => { - match &args[0] { - EdnValue::Uuid(u) => { - assert_eq!(*u, seed_entity, "sentinel in guard must match seed entity"); - } - _ => panic!("expected UUID as first guard arg"), + WhereClause::RuleInvocation { predicate: _, args } => match &args[0] { + EdnValue::Uuid(u) => { + assert_eq!(*u, seed_entity, "sentinel in guard must match seed entity"); } - } + _ => panic!("expected UUID as first guard arg"), + }, _ => panic!("expected RuleInvocation guard"), } } diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs index eca565c14..2191b4ab8 100644 --- a/tests/magic_sets_test.rs +++ b/tests/magic_sets_test.rs @@ -262,7 +262,10 @@ fn test_value_position_keyword_binding() { r#"(rule [(reports-to ?emp ?mgr) [?emp :employee/manager ?mgr]])"#, ); - let result = exec(&db, r#"(query [:find ?emp :where (reports-to ?emp :alice)])"#); + let result = exec( + &db, + r#"(query [:find ?emp :where (reports-to ?emp :alice)])"#, + ); let targets = extract_refs(result); assert_eq!(targets.len(), 2, "expected 2 employees reporting to alice");