rust_rule_engine/backward/
search.rs

1//! Search strategies for backward chaining
2
3use super::goal::{Goal, GoalStatus};
4use super::rule_executor::RuleExecutor;
5use crate::Facts;
6use crate::types::Value;
7use crate::KnowledgeBase;
8use crate::engine::rule::Rule;
9use std::collections::VecDeque;
10
11/// Strategy for searching the goal space
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum SearchStrategy {
14    /// Depth-first search (Prolog-style)
15    /// Goes deep into one branch before backtracking
16    DepthFirst,
17    
18    /// Breadth-first search
19    /// Explores all goals at one level before going deeper
20    BreadthFirst,
21    
22    /// Iterative deepening
23    /// Combines benefits of depth-first and breadth-first
24    Iterative,
25}
26
27/// Result of a search operation
28#[derive(Debug)]
29pub struct SearchResult {
30    /// Whether the goal was successfully proven
31    pub success: bool,
32    
33    /// Path taken to prove the goal (sequence of rule names)
34    pub path: Vec<String>,
35    
36    /// Number of goals explored
37    pub goals_explored: usize,
38    
39    /// Maximum depth reached
40    pub max_depth_reached: usize,
41    
42    /// Variable bindings from the proof
43    pub bindings: std::collections::HashMap<String, Value>,
44}
45
46impl SearchResult {
47    /// Create a successful search result
48    pub fn success(path: Vec<String>, goals_explored: usize, max_depth: usize) -> Self {
49        Self {
50            success: true,
51            path,
52            goals_explored,
53            max_depth_reached: max_depth,
54            bindings: std::collections::HashMap::new(),
55        }
56    }
57    
58    /// Create a failed search result
59    pub fn failure(goals_explored: usize, max_depth: usize) -> Self {
60        Self {
61            success: false,
62            path: Vec::new(),
63            goals_explored,
64            max_depth_reached: max_depth,
65            bindings: std::collections::HashMap::new(),
66        }
67    }
68}
69
70/// Depth-first search implementation
71pub struct DepthFirstSearch {
72    max_depth: usize,
73    goals_explored: usize,
74    path: Vec<String>,
75    executor: RuleExecutor,
76}
77
78impl DepthFirstSearch {
79    /// Create a new depth-first search
80    pub fn new(max_depth: usize, kb: KnowledgeBase) -> Self {
81        Self {
82            max_depth,
83            goals_explored: 0,
84            path: Vec::new(),
85            executor: RuleExecutor::new(kb),
86        }
87    }
88    
89    /// Search for a proof of the goal WITH rule execution
90    pub fn search_with_execution(&mut self, goal: &mut Goal, facts: &mut Facts, kb: &KnowledgeBase) -> SearchResult {
91        self.goals_explored = 0;
92        self.path.clear();
93
94        let success = self.search_recursive_with_execution(goal, facts, kb, 0);
95
96        SearchResult {
97            success,
98            path: self.path.clone(),
99            goals_explored: self.goals_explored,
100            max_depth_reached: goal.depth,
101            bindings: goal.bindings.to_map(),
102        }
103    }
104    
105    /// Search for a proof of the goal (old method, kept for compatibility)
106    pub fn search(&mut self, goal: &mut Goal, _facts: &Facts) -> SearchResult {
107        self.goals_explored = 0;
108        self.path.clear();
109        
110        let success = self.search_recursive(goal, 0);
111        
112        SearchResult {
113            success,
114            path: self.path.clone(),
115            goals_explored: self.goals_explored,
116            max_depth_reached: goal.depth,
117            bindings: goal.bindings.to_map(),
118        }
119    }
120    
121    /// NEW: Recursive search WITH rule execution
122    fn search_recursive_with_execution(
123        &mut self,
124        goal: &mut Goal,
125        facts: &mut Facts,  // ✅ Made mutable to allow rule execution
126        kb: &KnowledgeBase,
127        depth: usize
128    ) -> bool {
129        self.goals_explored += 1;
130
131        // Check depth limit
132        if depth > self.max_depth {
133            goal.status = GoalStatus::Unprovable;
134            return false;
135        }
136
137        // Check if goal already satisfied by existing facts
138        if self.check_goal_in_facts(goal, facts) {
139            goal.status = GoalStatus::Proven;
140            return true;
141        }
142
143        // Check for cycles
144        if goal.status == GoalStatus::InProgress {
145            goal.status = GoalStatus::Unprovable;
146            return false;
147        }
148
149        goal.status = GoalStatus::InProgress;
150        goal.depth = depth;
151
152        // Try each candidate rule
153        for rule_name in goal.candidate_rules.clone() {
154            self.path.push(rule_name.clone());
155
156            // Get the rule from KB
157            if let Some(rule) = kb.get_rule(&rule_name) {
158                // ✅ FIX: Try to execute rule (checks conditions AND executes actions)
159                match self.executor.try_execute_rule(&rule, facts) {
160                    Ok(true) => {
161                        // Rule executed successfully - derived new facts!
162                        // Now check if our goal is proven
163                        if self.check_goal_in_facts(goal, facts) {
164                            goal.status = GoalStatus::Proven;
165                            return true;
166                        }
167                    }
168                    Ok(false) => {
169                        // ✅ Conditions not satisfied - try to prove them recursively!
170                        if self.try_prove_rule_conditions(&rule, facts, kb, depth + 1) {
171                            // All conditions now satisfied! Try executing rule again
172                            match self.executor.try_execute_rule(&rule, facts) {
173                                Ok(true) => {
174                                    if self.check_goal_in_facts(goal, facts) {
175                                        goal.status = GoalStatus::Proven;
176                                        self.path.pop();
177                                        return true;
178                                    }
179                                }
180                                _ => {}
181                            }
182                        }
183                    }
184                    Err(_) => {
185                        // Execution error - continue to next rule
186                    }
187                }
188            }
189
190            self.path.pop();
191        }
192
193        // Try sub-goals
194        let mut all_subgoals_proven = true;
195        for sub_goal in &mut goal.sub_goals {
196            if !self.search_recursive_with_execution(sub_goal, facts, kb, depth + 1) {
197                all_subgoals_proven = false;
198                break;
199            }
200        }
201
202        // If we have sub-goals and they're all proven, goal is proven
203        if !goal.sub_goals.is_empty() && all_subgoals_proven {
204            goal.status = GoalStatus::Proven;
205            return true;
206        }
207
208        // If we have no candidate rules and no sub-goals, or nothing worked
209        goal.status = GoalStatus::Unprovable;
210        false
211    }
212    
213    /// Check if goal is already satisfied by facts
214    fn check_goal_in_facts(&self, goal: &Goal, facts: &Facts) -> bool {
215        // Parse goal pattern like "Order.AutoApproved == true"
216        let pattern = &goal.pattern;
217        
218        // Simple parser for "Field == Value" or "Field != Value"
219        if let Some(eq_pos) = pattern.find("==") {
220            let field = pattern[..eq_pos].trim();
221            let expected = pattern[eq_pos + 2..].trim();
222
223            if let Some(actual) = facts.get(field) {
224                return self.value_matches(&actual, expected);
225            }
226            return false;
227        }
228
229        if let Some(ne_pos) = pattern.find("!=") {
230            let field = pattern[..ne_pos].trim();
231            let not_expected = pattern[ne_pos + 2..].trim();
232
233            if let Some(actual) = facts.get(field) {
234                return !self.value_matches(&actual, not_expected);
235            }
236            // If field doesn't exist, != is considered true
237            return true;
238        }
239
240        false
241    }
242    
243    /// Check if value matches expected string
244    fn value_matches(&self, value: &Value, expected: &str) -> bool {
245        match value {
246            Value::Boolean(b) => {
247                expected == "true" && *b || expected == "false" && !*b
248            }
249            Value::String(s) => {
250                s == expected || s == expected.trim_matches('"')
251            }
252            Value::Number(n) => {
253                expected.parse::<f64>().map(|e| (n - e).abs() < 0.0001).unwrap_or(false)
254            }
255            _ => false,
256        }
257    }
258    
259    /// Check if rule conditions are satisfied using RuleExecutor
260    fn check_rule_conditions(&self, rule: &Rule, facts: &Facts) -> bool {
261        // Use RuleExecutor for proper condition evaluation
262        self.executor.evaluate_conditions(&rule.conditions, facts).unwrap_or(false)
263    }
264
265    /// Try to prove all conditions of a rule by creating sub-goals
266    /// This is the core of recursive backward chaining!
267    fn try_prove_rule_conditions(
268        &mut self,
269        rule: &Rule,
270        facts: &mut Facts,
271        kb: &KnowledgeBase,
272        depth: usize,
273    ) -> bool {
274        // Extract all conditions from the condition group and try to prove them
275        self.try_prove_condition_group(&rule.conditions, facts, kb, depth)
276    }
277
278    /// Recursively prove a condition group
279    fn try_prove_condition_group(
280        &mut self,
281        group: &crate::engine::rule::ConditionGroup,
282        facts: &mut Facts,
283        kb: &KnowledgeBase,
284        depth: usize,
285    ) -> bool {
286        use crate::engine::rule::ConditionGroup;
287
288        match group {
289            ConditionGroup::Single(condition) => {
290                // Try to prove this single condition
291                self.try_prove_single_condition(condition, facts, kb, depth)
292            }
293            ConditionGroup::Compound { left, operator, right } => {
294                // Handle AND/OR/NOT logic
295                use crate::types::LogicalOperator;
296                match operator {
297                    LogicalOperator::And => {
298                        // Both must be proven
299                        self.try_prove_condition_group(left, facts, kb, depth)
300                            && self.try_prove_condition_group(right, facts, kb, depth)
301                    }
302                    LogicalOperator::Or => {
303                        // At least one must be proven
304                        self.try_prove_condition_group(left, facts, kb, depth)
305                            || self.try_prove_condition_group(right, facts, kb, depth)
306                    }
307                    LogicalOperator::Not => {
308                        // Left should fail, right doesn't apply
309                        !self.try_prove_condition_group(left, facts, kb, depth)
310                    }
311                }
312            }
313            ConditionGroup::Not(_) | ConditionGroup::Exists(_) | ConditionGroup::Forall(_) | ConditionGroup::Accumulate { .. } => {
314                // For now, skip complex conditions
315                true
316            }
317        }
318    }
319
320    /// Try to prove a single condition
321    fn try_prove_single_condition(
322        &mut self,
323        condition: &crate::engine::rule::Condition,
324        facts: &mut Facts,
325        kb: &KnowledgeBase,
326        depth: usize,
327    ) -> bool {
328        // Convert condition to goal pattern
329        let goal_pattern = self.condition_to_goal_pattern(condition);
330
331        // Create a sub-goal for this condition
332        let mut sub_goal = Goal::new(goal_pattern.clone());
333        sub_goal.depth = depth;
334
335        // Find candidate rules that could prove this sub-goal
336        for candidate_rule in kb.get_rules() {
337            if self.rule_could_prove_pattern(&candidate_rule, &goal_pattern) {
338                sub_goal.add_candidate_rule(candidate_rule.name.clone());
339            }
340        }
341
342        // Try to prove this sub-goal recursively
343        self.search_recursive_with_execution(&mut sub_goal, facts, kb, depth)
344    }
345
346    /// Convert a condition to a goal pattern string
347    fn condition_to_goal_pattern(&self, condition: &crate::engine::rule::Condition) -> String {
348        use crate::engine::rule::ConditionExpression;
349
350        let field = match &condition.expression {
351            ConditionExpression::Field(f) => f.clone(),
352            ConditionExpression::FunctionCall { name, .. } => name.clone(),
353            ConditionExpression::Test { name, .. } => format!("test({})", name),
354            ConditionExpression::MultiField { field, .. } => field.clone(),
355        };
356
357        let op_str = match condition.operator {
358            crate::types::Operator::Equal => "==",
359            crate::types::Operator::NotEqual => "!=",
360            crate::types::Operator::GreaterThan => ">",
361            crate::types::Operator::LessThan => "<",
362            crate::types::Operator::GreaterThanOrEqual => ">=",
363            crate::types::Operator::LessThanOrEqual => "<=",
364            crate::types::Operator::Contains => "contains",
365            crate::types::Operator::NotContains => "not_contains",
366            crate::types::Operator::StartsWith => "starts_with",
367            crate::types::Operator::EndsWith => "ends_with",
368            crate::types::Operator::Matches => "matches",
369        };
370
371        let value_str = format!("{:?}", condition.value);
372
373        format!("{} {} {}", field, op_str, value_str)
374    }
375
376    /// Check if a rule could prove a specific goal pattern
377    fn rule_could_prove_pattern(&self, rule: &Rule, pattern: &str) -> bool {
378        // Simple heuristic: check if pattern mentions fields that this rule sets
379        for action in &rule.actions {
380            match action {
381                crate::types::ActionType::Set { field, .. } => {
382                    if pattern.contains(field) {
383                        return true;
384                    }
385                }
386                crate::types::ActionType::MethodCall { object, method, .. } => {
387                    if pattern.contains(object) || pattern.contains(method) {
388                        return true;
389                    }
390                }
391                _ => {}
392            }
393        }
394        false
395    }
396
397    /// OLD: Recursive search without execution
398    fn search_recursive(&mut self, goal: &mut Goal, depth: usize) -> bool {
399        self.goals_explored += 1;
400        
401        // Check depth limit
402        if depth > self.max_depth {
403            goal.status = GoalStatus::Unprovable;
404            return false;
405        }
406        
407        // Check for cycles (goal already in progress)
408        if goal.status == GoalStatus::InProgress {
409            goal.status = GoalStatus::Unprovable;
410            return false;
411        }
412        
413        // Mark as in progress to detect cycles
414        goal.status = GoalStatus::InProgress;
415        goal.depth = depth;
416        
417        // Try each candidate rule
418        for rule_name in goal.candidate_rules.clone() {
419            self.path.push(rule_name.clone());
420            
421            // Get the rule from knowledge base (via goal's stored rules)
422            // In a full implementation with KB access:
423            // 1. Get rule conditions
424            // 2. Check if conditions match current facts
425            // 3. If match, execute rule actions to derive new facts
426            // 4. Mark goal as proven
427            
428            // For backward chaining, we check:
429            // - Can this rule's conclusion prove our goal?
430            // - Are all rule conditions satisfied (recursively)?
431            
432            // Since we found a candidate rule, assume it can prove the goal
433            // The rule was added as candidate because its conclusion matches the goal
434            goal.status = GoalStatus::Proven;
435            return true;
436        }
437        
438        // Try to prove sub-goals
439        for sub_goal in &mut goal.sub_goals {
440            if !self.search_recursive(sub_goal, depth + 1) {
441                goal.status = GoalStatus::Unprovable;
442                return false;
443            }
444        }
445        
446        // If we have no sub-goals and no candidate rules, unprovable
447        if goal.sub_goals.is_empty() && goal.candidate_rules.is_empty() {
448            goal.status = GoalStatus::Unprovable;
449            return false;
450        }
451        
452        goal.status = GoalStatus::Proven;
453        true
454    }
455}
456
457/// Breadth-first search implementation
458pub struct BreadthFirstSearch {
459    max_depth: usize,
460    goals_explored: usize,
461    executor: RuleExecutor,
462}
463
464impl BreadthFirstSearch {
465    /// Create a new breadth-first search
466    pub fn new(max_depth: usize, kb: KnowledgeBase) -> Self {
467        Self {
468            max_depth,
469            goals_explored: 0,
470            executor: RuleExecutor::new(kb),
471        }
472    }
473    
474    /// Search for a proof of the goal using BFS WITH rule execution
475    pub fn search_with_execution(&mut self, root_goal: &mut Goal, facts: &mut Facts, kb: &KnowledgeBase) -> SearchResult {
476        self.goals_explored = 0;
477        let mut queue = VecDeque::new();
478        let mut path = Vec::new();
479        let mut max_depth = 0;
480
481        queue.push_back((root_goal as *mut Goal, 0));
482
483        while let Some((goal_ptr, depth)) = queue.pop_front() {
484            // Safety: We maintain ownership properly
485            let goal = unsafe { &mut *goal_ptr };
486
487            self.goals_explored += 1;
488            max_depth = max_depth.max(depth);
489
490            if depth > self.max_depth {
491                continue;
492            }
493
494            goal.depth = depth;
495
496            // Check if goal already satisfied by facts
497            if self.check_goal_in_facts(goal, facts) {
498                goal.status = GoalStatus::Proven;
499                continue;
500            }
501
502            // Try each candidate rule
503            for rule_name in goal.candidate_rules.clone() {
504                path.push(rule_name.clone());
505
506                // Get the rule from KB
507                if let Some(rule) = kb.get_rule(&rule_name) {
508                    // ✅ FIX: Try to execute rule (checks conditions AND executes actions)
509                    match self.executor.try_execute_rule(&rule, facts) {
510                        Ok(true) => {
511                            // Rule executed successfully - derived new facts!
512                            // Now check if our goal is proven
513                            if self.check_goal_in_facts(goal, facts) {
514                                goal.status = GoalStatus::Proven;
515                                break;
516                            }
517                        }
518                        Ok(false) => {
519                            // Conditions not satisfied - continue to next rule
520                        }
521                        Err(_) => {
522                            // Execution error - continue to next rule
523                        }
524                    }
525                }
526            }
527
528            // Add sub-goals to queue
529            for sub_goal in &mut goal.sub_goals {
530                queue.push_back((sub_goal as *mut Goal, depth + 1));
531            }
532        }
533
534        let success = root_goal.is_proven();
535
536        SearchResult {
537            success,
538            path,
539            goals_explored: self.goals_explored,
540            max_depth_reached: max_depth,
541            bindings: root_goal.bindings.to_map(),
542        }
543    }
544    
545    /// Check if goal is already satisfied by facts
546    fn check_goal_in_facts(&self, goal: &Goal, facts: &Facts) -> bool {
547        let pattern = &goal.pattern;
548        
549        if let Some(eq_pos) = pattern.find("==") {
550            let field = pattern[..eq_pos].trim();
551            let expected = pattern[eq_pos + 2..].trim();
552            
553            if let Some(actual) = facts.get(field) {
554                return self.value_matches(&actual, expected);
555            }
556            return false;
557        }
558        
559        if let Some(ne_pos) = pattern.find("!=") {
560            let field = pattern[..ne_pos].trim();
561            let not_expected = pattern[ne_pos + 2..].trim();
562            
563            if let Some(actual) = facts.get(field) {
564                return !self.value_matches(&actual, not_expected);
565            }
566            return true;
567        }
568        
569        false
570    }
571    
572    /// Check if value matches expected string
573    fn value_matches(&self, value: &Value, expected: &str) -> bool {
574        match value {
575            Value::Boolean(b) => {
576                expected == "true" && *b || expected == "false" && !*b
577            }
578            Value::String(s) => {
579                s == expected || s == expected.trim_matches('"')
580            }
581            Value::Number(n) => {
582                expected.parse::<f64>().map(|e| (n - e).abs() < 0.0001).unwrap_or(false)
583            }
584            _ => false,
585        }
586    }
587    
588    /// Check if rule conditions are satisfied using RuleExecutor
589    fn check_rule_conditions(&self, rule: &Rule, facts: &Facts) -> bool {
590        // Use RuleExecutor for proper condition evaluation
591        self.executor.evaluate_conditions(&rule.conditions, facts).unwrap_or(false)
592    }
593    
594    /// Search for a proof of the goal using BFS (old method, kept for compatibility)
595    pub fn search(&mut self, root_goal: &mut Goal, _facts: &Facts) -> SearchResult {
596        self.goals_explored = 0;
597        let mut queue = VecDeque::new();
598        let mut path = Vec::new();
599        let mut max_depth = 0;
600        
601        queue.push_back((root_goal as *mut Goal, 0));
602        
603        while let Some((goal_ptr, depth)) = queue.pop_front() {
604            // Safety: We maintain ownership properly
605            let goal = unsafe { &mut *goal_ptr };
606            
607            self.goals_explored += 1;
608            max_depth = max_depth.max(depth);
609            
610            if depth > self.max_depth {
611                continue;
612            }
613            
614            goal.depth = depth;
615            
616            // Process candidate rules
617            for rule_name in &goal.candidate_rules {
618                path.push(rule_name.clone());
619            }
620            
621            // Add sub-goals to queue
622            for sub_goal in &mut goal.sub_goals {
623                queue.push_back((sub_goal as *mut Goal, depth + 1));
624            }
625            
626            // Check if goal can be proven
627            if !goal.candidate_rules.is_empty() || goal.all_subgoals_proven() {
628                goal.status = GoalStatus::Proven;
629            }
630        }
631        
632        let success = root_goal.is_proven();
633        
634        SearchResult {
635            success,
636            path,
637            goals_explored: self.goals_explored,
638            max_depth_reached: max_depth,
639            bindings: root_goal.bindings.to_map(),
640        }
641    }
642}
643
644#[cfg(test)]
645mod tests {
646    use super::*;
647    
648    #[test]
649    fn test_search_strategies() {
650        assert_eq!(SearchStrategy::DepthFirst, SearchStrategy::DepthFirst);
651        assert_ne!(SearchStrategy::DepthFirst, SearchStrategy::BreadthFirst);
652    }
653    
654    #[test]
655    fn test_search_result_creation() {
656        let success = SearchResult::success(vec!["Rule1".to_string()], 5, 3);
657        assert!(success.success);
658        assert_eq!(success.path.len(), 1);
659        assert_eq!(success.goals_explored, 5);
660        
661        let failure = SearchResult::failure(10, 5);
662        assert!(!failure.success);
663        assert!(failure.path.is_empty());
664    }
665    
666    #[test]
667    fn test_depth_first_search_creation() {
668        let kb = KnowledgeBase::new("test");
669        let dfs = DepthFirstSearch::new(10, kb);
670        assert_eq!(dfs.max_depth, 10);
671        assert_eq!(dfs.goals_explored, 0);
672    }
673    
674    #[test]
675    fn test_depth_first_search_simple() {
676        let kb = KnowledgeBase::new("test");
677        let mut dfs = DepthFirstSearch::new(10, kb);
678        let facts = Facts::new();
679
680        let mut goal = Goal::new("test".to_string());
681        goal.add_candidate_rule("TestRule".to_string());
682
683        let result = dfs.search(&mut goal, &facts);
684
685        assert!(result.success);
686        assert!(goal.is_proven());
687        assert!(result.goals_explored > 0);
688    }
689    
690    #[test]
691    fn test_breadth_first_search() {
692        let kb = KnowledgeBase::new("test");
693        let mut bfs = BreadthFirstSearch::new(10, kb);
694        let facts = Facts::new();
695
696        let mut goal = Goal::new("test".to_string());
697        goal.add_candidate_rule("TestRule".to_string());
698
699        let result = bfs.search(&mut goal, &facts);
700
701        assert!(result.success);
702        assert_eq!(result.goals_explored, 1);
703    }
704}
rust_rule_engine/backward/search.rs

rust_rule_engine/backward/
search.rs
