rust_rule_engine/backward/
search.rs

1//! Search strategies for backward chaining
2
3use super::goal::{Goal, GoalStatus};
4use super::rule_executor::RuleExecutor;
5use std::sync::{Arc, Mutex};
6use crate::rete::propagation::IncrementalEngine;
7use crate::rete::working_memory::FactHandle;
8use crate::Facts;
9use crate::types::Value;
10use crate::KnowledgeBase;
11use crate::engine::rule::Rule;
12use std::collections::VecDeque;
13
14/// Strategy for searching the goal space
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16pub enum SearchStrategy {
17    /// Depth-first search (Prolog-style)
18    /// Goes deep into one branch before backtracking
19    DepthFirst,
20    
21    /// Breadth-first search
22    /// Explores all goals at one level before going deeper
23    BreadthFirst,
24    
25    /// Iterative deepening
26    /// Combines benefits of depth-first and breadth-first
27    Iterative,
28}
29
30/// A single solution found during search
31#[derive(Debug, Clone)]
32pub struct Solution {
33    /// Path taken to prove the goal (sequence of rule names)
34    pub path: Vec<String>,
35
36    /// Variable bindings from this proof
37    pub bindings: std::collections::HashMap<String, Value>,
38}
39
40/// Result of a search operation
41#[derive(Debug)]
42pub struct SearchResult {
43    /// Whether the goal was successfully proven
44    pub success: bool,
45
46    /// Path taken to prove the goal (sequence of rule names)
47    pub path: Vec<String>,
48
49    /// Number of goals explored
50    pub goals_explored: usize,
51
52    /// Maximum depth reached
53    pub max_depth_reached: usize,
54
55    /// Variable bindings from the proof
56    pub bindings: std::collections::HashMap<String, Value>,
57
58    /// All solutions found (if max_solutions > 1)
59    pub solutions: Vec<Solution>,
60}
61
62impl SearchResult {
63    /// Create a successful search result
64    pub fn success(path: Vec<String>, goals_explored: usize, max_depth: usize) -> Self {
65        Self {
66            success: true,
67            path,
68            goals_explored,
69            max_depth_reached: max_depth,
70            bindings: std::collections::HashMap::new(),
71            solutions: Vec::new(),
72        }
73    }
74
75    /// Create a failed search result
76    pub fn failure(goals_explored: usize, max_depth: usize) -> Self {
77        Self {
78            success: false,
79            path: Vec::new(),
80            goals_explored,
81            max_depth_reached: max_depth,
82            bindings: std::collections::HashMap::new(),
83            solutions: Vec::new(),
84        }
85    }
86}
87
88/// Depth-first search implementation
89pub struct DepthFirstSearch {
90    max_depth: usize,
91    goals_explored: usize,
92    path: Vec<String>,
93    executor: RuleExecutor,
94    max_solutions: usize,
95    solutions: Vec<Solution>,
96}
97
98impl DepthFirstSearch {
99    /// Create a new depth-first search
100    pub fn new(max_depth: usize, kb: KnowledgeBase) -> Self {
101        Self {
102            max_depth,
103            goals_explored: 0,
104            path: Vec::new(),
105            executor: RuleExecutor::new_with_inserter(kb, None),
106            max_solutions: 1,
107            solutions: Vec::new(),
108        }
109    }
110
111    /// Set maximum number of solutions to find
112    pub fn with_max_solutions(mut self, max_solutions: usize) -> Self {
113        self.max_solutions = max_solutions;
114        self
115    }
116
117    /// Create a new depth-first search and wire an optional IncrementalEngine
118    /// to enable TMS logical insertion. The engine is provided as Arc<Mutex<>>
119    /// and the inserter closure will call `insert_logical` on it.
120    pub fn new_with_engine(
121        max_depth: usize,
122        kb: KnowledgeBase,
123        engine: Option<Arc<Mutex<IncrementalEngine>>>,
124    ) -> Self {
125        // Build inserter closure if engine is provided
126        let inserter = engine.map(|eng| {
127            let eng = eng.clone();
128            std::sync::Arc::new(move |fact_type: String, data: crate::rete::TypedFacts, rule_name: String, premises: Vec<String>| {
129                if let Ok(mut e) = eng.lock() {
130                    // Resolve premise keys into FactHandles when possible
131                    let handles = e.resolve_premise_keys(premises);
132                    let _ = e.insert_logical(fact_type, data, rule_name, handles);
133                }
134            }) as std::sync::Arc<dyn Fn(String, crate::rete::TypedFacts, String, Vec<String>) + Send + Sync>
135        });
136
137        Self {
138            max_depth,
139            goals_explored: 0,
140            path: Vec::new(),
141            executor: RuleExecutor::new_with_inserter(kb, inserter),
142            max_solutions: 1,
143            solutions: Vec::new(),
144        }
145    }
146    
147    /// Search for a proof of the goal WITH rule execution
148    pub fn search_with_execution(&mut self, goal: &mut Goal, facts: &mut Facts, kb: &KnowledgeBase) -> SearchResult {
149        self.goals_explored = 0;
150        self.path.clear();
151        self.solutions.clear();
152
153        let success = self.search_recursive_with_execution(goal, facts, kb, 0);
154
155        SearchResult {
156            success,
157            path: self.path.clone(),
158            goals_explored: self.goals_explored,
159            max_depth_reached: goal.depth,
160            bindings: goal.bindings.to_map(),
161            solutions: self.solutions.clone(),
162        }
163    }
164    
165    /// Search for a proof of the goal (old method, kept for compatibility)
166    pub fn search(&mut self, goal: &mut Goal, _facts: &Facts) -> SearchResult {
167        self.goals_explored = 0;
168        self.path.clear();
169
170        let success = self.search_recursive(goal, 0);
171
172        SearchResult {
173            success,
174            path: self.path.clone(),
175            goals_explored: self.goals_explored,
176            max_depth_reached: goal.depth,
177            bindings: goal.bindings.to_map(),
178            solutions: Vec::new(),
179        }
180    }
181    
182    /// NEW: Recursive search WITH rule execution
183    fn search_recursive_with_execution(
184        &mut self,
185        goal: &mut Goal,
186        facts: &mut Facts,  // ✅ Made mutable to allow rule execution
187        kb: &KnowledgeBase,
188        depth: usize
189    ) -> bool {
190        self.goals_explored += 1;
191
192        // Check depth limit
193        if depth > self.max_depth {
194            goal.status = GoalStatus::Unprovable;
195            return false;
196        }
197
198        // Check if goal already satisfied by existing facts
199        if self.check_goal_in_facts(goal, facts) {
200            goal.status = GoalStatus::Proven;
201            return true;
202        }
203
204        // Check for cycles
205        if goal.status == GoalStatus::InProgress {
206            goal.status = GoalStatus::Unprovable;
207            return false;
208        }
209
210        goal.status = GoalStatus::InProgress;
211        goal.depth = depth;
212
213        // Try each candidate rule
214        for rule_name in goal.candidate_rules.clone() {
215            self.path.push(rule_name.clone());
216
217            // Start an undo frame before trying this candidate so we can rollback
218            // any speculative changes if this candidate doesn't lead to a proof.
219            facts.begin_undo_frame();
220
221            // Get the rule from KB
222            if let Some(rule) = kb.get_rule(&rule_name) {
223                // Try to execute rule (checks conditions AND executes actions)
224                match self.executor.try_execute_rule(&rule, facts) {
225                    Ok(true) => {
226                        // Rule executed successfully - derived new facts!
227                        // Now check if our goal is proven
228                        if self.check_goal_in_facts(goal, facts) {
229                            goal.status = GoalStatus::Proven;
230
231                            // Save this solution
232                            self.solutions.push(Solution {
233                                path: self.path.clone(),
234                                bindings: goal.bindings.to_map(),
235                            });
236
237                            // If we only want one solution OR we've found enough, stop searching
238                            if self.max_solutions == 1 || self.solutions.len() >= self.max_solutions {
239                                return true; // keep changes
240                            }
241
242                            // Otherwise (max_solutions > 1 and not enough yet), rollback and continue
243                            // This allows us to find alternative proof paths
244                            facts.rollback_undo_frame();
245                            self.path.pop();
246                            continue;
247                        }
248                        // Not proven yet: fallthrough and rollback below
249                    }
250                    Ok(false) => {
251                        // Conditions not satisfied - try to prove them recursively!
252                        if self.try_prove_rule_conditions(&rule, facts, kb, depth + 1) {
253                            // All conditions now satisfied! Try executing rule again
254                            match self.executor.try_execute_rule(&rule, facts) {
255                                Ok(true) => {
256                                    if self.check_goal_in_facts(goal, facts) {
257                                        goal.status = GoalStatus::Proven;
258
259                                        // Save this solution
260                                        self.solutions.push(Solution {
261                                            path: self.path.clone(),
262                                            bindings: goal.bindings.to_map(),
263                                        });
264
265                                        // If we only want one solution OR we've found enough, stop searching
266                                        if self.max_solutions == 1 || self.solutions.len() >= self.max_solutions {
267                                            return true; // keep changes
268                                        }
269
270                                        // Otherwise, rollback and continue searching
271                                        facts.rollback_undo_frame();
272                                        self.path.pop();
273                                        continue;
274                                    }
275                                }
276                                _ => {
277                                    // execution failed on second attempt
278                                }
279                            }
280                        }
281                    }
282                    Err(_) => {
283                        // Execution error - continue to next rule
284                    }
285                }
286            }
287
288            // Candidate failed to prove goal — rollback speculative changes
289            facts.rollback_undo_frame();
290            self.path.pop();
291        }
292
293        // Try sub-goals (begin undo frame before attempting sub-goals so we can rollback
294        // if any sub-goal fails)
295        let mut all_subgoals_proven = true;
296        if !goal.sub_goals.is_empty() {
297            facts.begin_undo_frame();
298            for sub_goal in &mut goal.sub_goals {
299                if !self.search_recursive_with_execution(sub_goal, facts, kb, depth + 1) {
300                    all_subgoals_proven = false;
301                    break;
302                }
303            }
304
305            if all_subgoals_proven {
306                // commit sub-goal frame (keep changes)
307                facts.commit_undo_frame();
308                goal.status = GoalStatus::Proven;
309                return true;
310            }
311
312            // rollback any changes from failed sub-goal exploration
313            facts.rollback_undo_frame();
314        }
315
316        // If we found at least one solution (even if less than max_solutions), consider it proven
317        if !self.solutions.is_empty() {
318            goal.status = GoalStatus::Proven;
319            return true;
320        }
321
322        // If we have no candidate rules and no sub-goals, or nothing worked
323        goal.status = GoalStatus::Unprovable;
324        false
325    }
326    
327    /// Check if goal is already satisfied by facts
328    ///
329    /// This method now reuses ConditionEvaluator for proper evaluation
330    fn check_goal_in_facts(&self, goal: &Goal, facts: &Facts) -> bool {
331        // Parse goal pattern into a Condition and use ConditionEvaluator
332        if let Some(condition) = self.parse_goal_pattern(&goal.pattern) {
333            // Use RuleExecutor's evaluator (which delegates to ConditionEvaluator)
334            self.executor.evaluate_condition(&condition, facts).unwrap_or(false)
335        } else {
336            false
337        }
338    }
339
340    /// Parse goal pattern string into a Condition object
341    ///
342    /// Examples:
343    /// - "User.Score >= 80" → Condition { field: "User.Score", operator: GreaterThanOrEqual, value: Number(80) }
344    /// - "User.IsVIP == true" → Condition { field: "User.IsVIP", operator: Equal, value: Boolean(true) }
345    fn parse_goal_pattern(&self, pattern: &str) -> Option<crate::engine::rule::Condition> {
346        use crate::engine::rule::{Condition, ConditionExpression};
347        use crate::types::Operator;
348
349        // Try parsing operators in order (longest first to avoid conflicts)
350        let operators = [
351            (">=", Operator::GreaterThanOrEqual),
352            ("<=", Operator::LessThanOrEqual),
353            ("==", Operator::Equal),
354            ("!=", Operator::NotEqual),
355            (" > ", Operator::GreaterThan),
356            (" < ", Operator::LessThan),
357            (" contains ", Operator::Contains),
358            (" not_contains ", Operator::NotContains),
359            (" starts_with ", Operator::StartsWith),
360            (" startsWith ", Operator::StartsWith),
361            (" ends_with ", Operator::EndsWith),
362            (" endsWith ", Operator::EndsWith),
363            (" matches ", Operator::Matches),
364        ];
365
366        for (op_str, operator) in operators {
367            if let Some(pos) = pattern.find(op_str) {
368                let field = pattern[..pos].trim().to_string();
369                let value_str = pattern[pos + op_str.len()..].trim();
370
371                // Parse value
372                let value = self.parse_value_string(value_str);
373
374                return Some(Condition {
375                    field: field.clone(),
376                    expression: ConditionExpression::Field(field),
377                    operator,
378                    value,
379                });
380            }
381        }
382
383        None
384    }
385
386    /// Parse value string into a Value
387    fn parse_value_string(&self, s: &str) -> Value {
388        let s = s.trim();
389
390        // Boolean
391        if s == "true" {
392            return Value::Boolean(true);
393        }
394        if s == "false" {
395            return Value::Boolean(false);
396        }
397
398        // Null
399        if s == "null" {
400            return Value::Null;
401        }
402
403        // String (quoted)
404        if (s.starts_with('"') && s.ends_with('"')) || (s.starts_with('\'') && s.ends_with('\'')) {
405            return Value::String(s[1..s.len()-1].to_string());
406        }
407
408        // Number (float)
409        if let Ok(n) = s.parse::<f64>() {
410            return Value::Number(n);
411        }
412
413        // Integer
414        if let Ok(i) = s.parse::<i64>() {
415            return Value::Integer(i);
416        }
417
418        // Default to string
419        Value::String(s.to_string())
420    }
421
422    /// Try to prove all conditions of a rule by creating sub-goals
423    /// This is the core of recursive backward chaining!
424    fn try_prove_rule_conditions(
425        &mut self,
426        rule: &Rule,
427        facts: &mut Facts,
428        kb: &KnowledgeBase,
429        depth: usize,
430    ) -> bool {
431        // Extract all conditions from the condition group and try to prove them
432        self.try_prove_condition_group(&rule.conditions, facts, kb, depth)
433    }
434
435    /// Recursively prove a condition group
436    fn try_prove_condition_group(
437        &mut self,
438        group: &crate::engine::rule::ConditionGroup,
439        facts: &mut Facts,
440        kb: &KnowledgeBase,
441        depth: usize,
442    ) -> bool {
443        use crate::engine::rule::ConditionGroup;
444
445        match group {
446            ConditionGroup::Single(condition) => {
447                // Try to prove this single condition
448                self.try_prove_single_condition(condition, facts, kb, depth)
449            }
450            ConditionGroup::Compound { left, operator, right } => {
451                // Handle AND/OR/NOT logic
452                use crate::types::LogicalOperator;
453                match operator {
454                    LogicalOperator::And => {
455                        // Both must be proven
456                        self.try_prove_condition_group(left, facts, kb, depth)
457                            && self.try_prove_condition_group(right, facts, kb, depth)
458                    }
459                    LogicalOperator::Or => {
460                        // At least one must be proven
461                        self.try_prove_condition_group(left, facts, kb, depth)
462                            || self.try_prove_condition_group(right, facts, kb, depth)
463                    }
464                    LogicalOperator::Not => {
465                        // Left should fail, right doesn't apply
466                        !self.try_prove_condition_group(left, facts, kb, depth)
467                    }
468                }
469            }
470            ConditionGroup::Not(_) | ConditionGroup::Exists(_) | ConditionGroup::Forall(_) | ConditionGroup::Accumulate { .. } => {
471                // Complex conditions (Not, Exists, Forall, Accumulate) cannot be proven backward;
472                // they can only be evaluated against current facts.
473                // Use the executor's condition evaluator to check them.
474                self.executor.evaluate_conditions(group, facts).unwrap_or(false)
475            }
476        }
477    }
478
479    /// Try to prove a single condition
480    fn try_prove_single_condition(
481        &mut self,
482        condition: &crate::engine::rule::Condition,
483        facts: &mut Facts,
484        kb: &KnowledgeBase,
485        depth: usize,
486    ) -> bool {
487        // First check if condition is already satisfied by facts
488        if let Ok(satisfied) = self.executor.evaluate_condition(condition, facts) {
489            if satisfied {
490                return true;
491            }
492        }
493
494        // Condition not satisfied - try to prove it by finding rules that can derive it
495        let goal_pattern = self.condition_to_goal_pattern(condition);
496
497        // Create a sub-goal for this condition
498        let mut sub_goal = Goal::new(goal_pattern.clone());
499        sub_goal.depth = depth;
500
501        // Find candidate rules that could prove this sub-goal
502        for candidate_rule in kb.get_rules() {
503            if self.rule_could_prove_pattern(&candidate_rule, &goal_pattern) {
504                sub_goal.add_candidate_rule(candidate_rule.name.clone());
505            }
506        }
507
508        // Try to prove this sub-goal recursively
509        self.search_recursive_with_execution(&mut sub_goal, facts, kb, depth)
510    }
511
512    /// Convert a condition to a goal pattern string
513    fn condition_to_goal_pattern(&self, condition: &crate::engine::rule::Condition) -> String {
514        use crate::engine::rule::ConditionExpression;
515
516        let field = match &condition.expression {
517            ConditionExpression::Field(f) => f.clone(),
518            ConditionExpression::FunctionCall { name, .. } => name.clone(),
519            ConditionExpression::Test { name, .. } => format!("test({})", name),
520            ConditionExpression::MultiField { field, .. } => field.clone(),
521        };
522
523        let op_str = match condition.operator {
524            crate::types::Operator::Equal => "==",
525            crate::types::Operator::NotEqual => "!=",
526            crate::types::Operator::GreaterThan => ">",
527            crate::types::Operator::LessThan => "<",
528            crate::types::Operator::GreaterThanOrEqual => ">=",
529            crate::types::Operator::LessThanOrEqual => "<=",
530            crate::types::Operator::Contains => "contains",
531            crate::types::Operator::NotContains => "not_contains",
532            crate::types::Operator::StartsWith => "starts_with",
533            crate::types::Operator::EndsWith => "ends_with",
534            crate::types::Operator::Matches => "matches",
535        };
536
537        // Convert value to string format that matches goal patterns
538        let value_str = match &condition.value {
539            Value::Boolean(b) => b.to_string(),
540            Value::Number(n) => n.to_string(),
541            Value::Integer(i) => i.to_string(),
542            Value::String(s) => format!("\"{}\"", s),
543            Value::Null => "null".to_string(),
544            _ => format!("{:?}", condition.value),
545        };
546
547        format!("{} {} {}", field, op_str, value_str)
548    }
549
550    /// Check if a rule could prove a specific goal pattern
551    fn rule_could_prove_pattern(&self, rule: &Rule, pattern: &str) -> bool {
552        // Simple heuristic: check if pattern mentions fields that this rule sets
553        for action in &rule.actions {
554            match action {
555                crate::types::ActionType::Set { field, .. } => {
556                    if pattern.contains(field) {
557                        return true;
558                    }
559                }
560                crate::types::ActionType::MethodCall { object, method, .. } => {
561                    if pattern.contains(object) || pattern.contains(method) {
562                        return true;
563                    }
564                }
565                _ => {}
566            }
567        }
568        false
569    }
570
571    /// OLD: Recursive search without execution
572    fn search_recursive(&mut self, goal: &mut Goal, depth: usize) -> bool {
573        self.goals_explored += 1;
574        
575        // Check depth limit
576        if depth > self.max_depth {
577            goal.status = GoalStatus::Unprovable;
578            return false;
579        }
580        
581        // Check for cycles (goal already in progress)
582        if goal.status == GoalStatus::InProgress {
583            goal.status = GoalStatus::Unprovable;
584            return false;
585        }
586        
587        // Mark as in progress to detect cycles
588        goal.status = GoalStatus::InProgress;
589        goal.depth = depth;
590        
591        // Try each candidate rule
592        for rule_name in goal.candidate_rules.clone() {
593            self.path.push(rule_name.clone());
594            
595            // Get the rule from knowledge base (via goal's stored rules)
596            // In a full implementation with KB access:
597            // 1. Get rule conditions
598            // 2. Check if conditions match current facts
599            // 3. If match, execute rule actions to derive new facts
600            // 4. Mark goal as proven
601            
602            // For backward chaining, we check:
603            // - Can this rule's conclusion prove our goal?
604            // - Are all rule conditions satisfied (recursively)?
605            
606            // Since we found a candidate rule, assume it can prove the goal
607            // The rule was added as candidate because its conclusion matches the goal
608            goal.status = GoalStatus::Proven;
609            return true;
610        }
611        
612        // Try to prove sub-goals
613        for sub_goal in &mut goal.sub_goals {
614            if !self.search_recursive(sub_goal, depth + 1) {
615                goal.status = GoalStatus::Unprovable;
616                return false;
617            }
618        }
619        
620        // If we have no sub-goals and no candidate rules, unprovable
621        if goal.sub_goals.is_empty() && goal.candidate_rules.is_empty() {
622            goal.status = GoalStatus::Unprovable;
623            return false;
624        }
625        
626        goal.status = GoalStatus::Proven;
627        true
628    }
629}
630
631/// Breadth-first search implementation
632pub struct BreadthFirstSearch {
633    max_depth: usize,
634    goals_explored: usize,
635    executor: RuleExecutor,
636}
637
638/// Iterative deepening search implementation
639pub struct IterativeDeepeningSearch {
640    max_depth: usize,
641    goals_explored: usize,
642    kb: KnowledgeBase,
643    engine: Option<Arc<Mutex<IncrementalEngine>>>,
644}
645
646impl IterativeDeepeningSearch {
647    /// Create a new iterative deepening search
648    pub fn new(max_depth: usize, kb: KnowledgeBase) -> Self {
649        Self { max_depth, goals_explored: 0, kb, engine: None }
650    }
651
652    /// Create with optional IncrementalEngine for TMS integration
653    pub fn new_with_engine(max_depth: usize, kb: KnowledgeBase, engine: Option<Arc<Mutex<IncrementalEngine>>>) -> Self {
654        // Store the engine so we can pass it to DFS instances
655        Self { max_depth, goals_explored: 0, kb, engine }
656    }
657
658    /// Search with execution: probe with increasing depth using non-executing DFS,
659    /// then run a final executing DFS at the discovered depth to mutate facts.
660    pub fn search_with_execution(&mut self, root_goal: &mut Goal, facts: &mut Facts, kb: &KnowledgeBase) -> SearchResult {
661        self.goals_explored = 0;
662        let mut cumulative_goals = 0usize;
663
664        // Try increasing depth limits
665        for depth_limit in 0..=self.max_depth {
666            // Probe using a non-executing depth-first search on a cloned goal
667            let mut probe_goal = root_goal.clone();
668            let probe_kb = self.kb.clone();
669            let mut probe_dfs = DepthFirstSearch::new(depth_limit, probe_kb);
670            let probe_result = probe_dfs.search(&mut probe_goal, facts);
671            cumulative_goals += probe_result.goals_explored;
672
673            if probe_result.success {
674                // Found a depth where a proof exists; execute for real at this depth
675                let exec_kb = self.kb.clone();
676                let mut exec_dfs = DepthFirstSearch::new_with_engine(depth_limit, exec_kb, self.engine.clone());
677                let exec_result = exec_dfs.search_with_execution(root_goal, facts, kb);
678                // Aggregate explored goals
679                let mut final_result = exec_result;
680                final_result.goals_explored += cumulative_goals - final_result.goals_explored;
681                return final_result;
682            }
683        }
684
685        // Nothing proved up to max_depth
686        SearchResult::failure(cumulative_goals, self.max_depth)
687    }
688
689    /// Non-executing search using iterative deepening (probes only)
690    pub fn search(&mut self, root_goal: &mut Goal, facts: &Facts) -> SearchResult {
691        self.goals_explored = 0;
692        let mut cumulative_goals = 0usize;
693
694        for depth_limit in 0..=self.max_depth {
695            let mut probe_goal = root_goal.clone();
696            let probe_kb = self.kb.clone();
697            let mut probe_dfs = DepthFirstSearch::new(depth_limit, probe_kb);
698            let probe_result = probe_dfs.search(&mut probe_goal, facts);
699            cumulative_goals += probe_result.goals_explored;
700            if probe_result.success {
701                // Return the successful probe result (with aggregated goals explored)
702                let mut res = probe_result;
703                res.goals_explored = cumulative_goals;
704                return res;
705            }
706        }
707
708        SearchResult::failure(cumulative_goals, self.max_depth)
709    }
710}
711
712impl BreadthFirstSearch {
713    /// Create a new breadth-first search
714    pub fn new(max_depth: usize, kb: KnowledgeBase) -> Self {
715        Self {
716            max_depth,
717            goals_explored: 0,
718            executor: RuleExecutor::new_with_inserter(kb, None),
719        }
720    }
721
722    /// Create BFS with optional engine for TMS integration
723    pub fn new_with_engine(max_depth: usize, kb: KnowledgeBase, engine: Option<Arc<Mutex<IncrementalEngine>>>) -> Self {
724        // If engine provided, create inserter closure
725        let inserter = engine.map(|eng| {
726            let eng = eng.clone();
727            std::sync::Arc::new(move |fact_type: String, data: crate::rete::TypedFacts, rule_name: String, _premises: Vec<String>| {
728                if let Ok(mut e) = eng.lock() {
729                    let _ = e.insert_logical(fact_type, data, rule_name, Vec::new());
730                }
731            }) as std::sync::Arc<dyn Fn(String, crate::rete::TypedFacts, String, Vec<String>) + Send + Sync>
732        });
733
734        Self {
735            max_depth,
736            goals_explored: 0,
737            executor: RuleExecutor::new_with_inserter(kb, inserter),
738        }
739    }
740    
741    /// Search for a proof of the goal using BFS WITH rule execution
742    pub fn search_with_execution(&mut self, root_goal: &mut Goal, facts: &mut Facts, kb: &KnowledgeBase) -> SearchResult {
743        self.goals_explored = 0;
744        let mut queue = VecDeque::new();
745        let mut path = Vec::new();
746        let mut max_depth = 0;
747
748        queue.push_back((root_goal as *mut Goal, 0));
749
750        while let Some((goal_ptr, depth)) = queue.pop_front() {
751            // Safety: We maintain ownership properly
752            let goal = unsafe { &mut *goal_ptr };
753
754            self.goals_explored += 1;
755            max_depth = max_depth.max(depth);
756
757            if depth > self.max_depth {
758                continue;
759            }
760
761            goal.depth = depth;
762
763            // Check if goal already satisfied by facts
764            if self.check_goal_in_facts(goal, facts) {
765                goal.status = GoalStatus::Proven;
766                continue;
767            }
768
769            // Try each candidate rule
770            for rule_name in goal.candidate_rules.clone() {
771                path.push(rule_name.clone());
772
773                // Get the rule from KB
774                if let Some(rule) = kb.get_rule(&rule_name) {
775                    // ✅ FIX: Try to execute rule (checks conditions AND executes actions)
776                    match self.executor.try_execute_rule(&rule, facts) {
777                        Ok(true) => {
778                            // Rule executed successfully - derived new facts!
779                            // Now check if our goal is proven
780                            if self.check_goal_in_facts(goal, facts) {
781                                goal.status = GoalStatus::Proven;
782                                break;
783                            }
784                        }
785                        Ok(false) => {
786                            // Conditions not satisfied - continue to next rule
787                        }
788                        Err(_) => {
789                            // Execution error - continue to next rule
790                        }
791                    }
792                }
793            }
794
795            // Add sub-goals to queue
796            for sub_goal in &mut goal.sub_goals {
797                queue.push_back((sub_goal as *mut Goal, depth + 1));
798            }
799        }
800
801        let success = root_goal.is_proven();
802
803        SearchResult {
804            success,
805            path,
806            goals_explored: self.goals_explored,
807            max_depth_reached: max_depth,
808            bindings: root_goal.bindings.to_map(),
809            solutions: Vec::new(),
810        }
811    }
812    
813    /// Check if goal is already satisfied by facts
814    ///
815    /// This method now reuses ConditionEvaluator for proper evaluation
816    fn check_goal_in_facts(&self, goal: &Goal, facts: &Facts) -> bool {
817        // Parse goal pattern into a Condition and use ConditionEvaluator
818        if let Some(condition) = self.parse_goal_pattern(&goal.pattern) {
819            // Use RuleExecutor's evaluator (which delegates to ConditionEvaluator)
820            self.executor.evaluate_condition(&condition, facts).unwrap_or(false)
821        } else {
822            false
823        }
824    }
825
826    /// Parse goal pattern string into a Condition object
827    ///
828    /// Examples:
829    /// - "User.Score >= 80" → Condition { field: "User.Score", operator: GreaterThanOrEqual, value: Number(80) }
830    /// - "User.IsVIP == true" → Condition { field: "User.IsVIP", operator: Equal, value: Boolean(true) }
831    fn parse_goal_pattern(&self, pattern: &str) -> Option<crate::engine::rule::Condition> {
832        use crate::engine::rule::{Condition, ConditionExpression};
833        use crate::types::Operator;
834
835        // Try parsing operators in order (longest first to avoid conflicts)
836        let operators = [
837            (">=", Operator::GreaterThanOrEqual),
838            ("<=", Operator::LessThanOrEqual),
839            ("==", Operator::Equal),
840            ("!=", Operator::NotEqual),
841            (" > ", Operator::GreaterThan),
842            (" < ", Operator::LessThan),
843            (" contains ", Operator::Contains),
844            (" not_contains ", Operator::NotContains),
845            (" starts_with ", Operator::StartsWith),
846            (" startsWith ", Operator::StartsWith),
847            (" ends_with ", Operator::EndsWith),
848            (" endsWith ", Operator::EndsWith),
849            (" matches ", Operator::Matches),
850        ];
851
852        for (op_str, operator) in operators {
853            if let Some(pos) = pattern.find(op_str) {
854                let field = pattern[..pos].trim().to_string();
855                let value_str = pattern[pos + op_str.len()..].trim();
856
857                // Parse value
858                let value = self.parse_value_string(value_str);
859
860                return Some(Condition {
861                    field: field.clone(),
862                    expression: ConditionExpression::Field(field),
863                    operator,
864                    value,
865                });
866            }
867        }
868
869        None
870    }
871
872    /// Parse value string into a Value
873    fn parse_value_string(&self, s: &str) -> Value {
874        let s = s.trim();
875
876        // Boolean
877        if s == "true" {
878            return Value::Boolean(true);
879        }
880        if s == "false" {
881            return Value::Boolean(false);
882        }
883
884        // Null
885        if s == "null" {
886            return Value::Null;
887        }
888
889        // String (quoted)
890        if (s.starts_with('"') && s.ends_with('"')) || (s.starts_with('\'') && s.ends_with('\'')) {
891            return Value::String(s[1..s.len()-1].to_string());
892        }
893
894        // Number (float)
895        if let Ok(n) = s.parse::<f64>() {
896            return Value::Number(n);
897        }
898
899        // Integer
900        if let Ok(i) = s.parse::<i64>() {
901            return Value::Integer(i);
902        }
903
904        // Default to string
905        Value::String(s.to_string())
906    }
907    
908    /// Search for a proof of the goal using BFS (old method, kept for compatibility)
909    pub fn search(&mut self, root_goal: &mut Goal, _facts: &Facts) -> SearchResult {
910        self.goals_explored = 0;
911        let mut queue = VecDeque::new();
912        let mut path = Vec::new();
913        let mut max_depth = 0;
914        
915        queue.push_back((root_goal as *mut Goal, 0));
916        
917        while let Some((goal_ptr, depth)) = queue.pop_front() {
918            // Safety: We maintain ownership properly
919            let goal = unsafe { &mut *goal_ptr };
920            
921            self.goals_explored += 1;
922            max_depth = max_depth.max(depth);
923            
924            if depth > self.max_depth {
925                continue;
926            }
927            
928            goal.depth = depth;
929            
930            // Process candidate rules
931            for rule_name in &goal.candidate_rules {
932                path.push(rule_name.clone());
933            }
934            
935            // Add sub-goals to queue
936            for sub_goal in &mut goal.sub_goals {
937                queue.push_back((sub_goal as *mut Goal, depth + 1));
938            }
939            
940            // Check if goal can be proven
941            if !goal.candidate_rules.is_empty() || goal.all_subgoals_proven() {
942                goal.status = GoalStatus::Proven;
943            }
944        }
945        
946        let success = root_goal.is_proven();
947
948        SearchResult {
949            success,
950            path,
951            goals_explored: self.goals_explored,
952            max_depth_reached: max_depth,
953            bindings: root_goal.bindings.to_map(),
954            solutions: Vec::new(),
955        }
956    }
957}
958
959#[cfg(test)]
960mod tests {
961    use super::*;
962    use std::collections::HashMap;
963
964    #[test]
965    fn test_search_strategies() {
966        assert_eq!(SearchStrategy::DepthFirst, SearchStrategy::DepthFirst);
967        assert_ne!(SearchStrategy::DepthFirst, SearchStrategy::BreadthFirst);
968    }
969    
970    #[test]
971    fn test_search_result_creation() {
972        let success = SearchResult::success(vec!["Rule1".to_string()], 5, 3);
973        assert!(success.success);
974        assert_eq!(success.path.len(), 1);
975        assert_eq!(success.goals_explored, 5);
976        
977        let failure = SearchResult::failure(10, 5);
978        assert!(!failure.success);
979        assert!(failure.path.is_empty());
980    }
981    
982    #[test]
983    fn test_depth_first_search_creation() {
984        let kb = KnowledgeBase::new("test");
985        let dfs = DepthFirstSearch::new(10, kb);
986        assert_eq!(dfs.max_depth, 10);
987        assert_eq!(dfs.goals_explored, 0);
988    }
989    
990    #[test]
991    fn test_depth_first_search_simple() {
992        let kb = KnowledgeBase::new("test");
993        let mut dfs = DepthFirstSearch::new(10, kb);
994        let facts = Facts::new();
995
996        let mut goal = Goal::new("test".to_string());
997        goal.add_candidate_rule("TestRule".to_string());
998
999        let result = dfs.search(&mut goal, &facts);
1000
1001        assert!(result.success);
1002        assert!(goal.is_proven());
1003        assert!(result.goals_explored > 0);
1004    }
1005    
1006    #[test]
1007    fn test_breadth_first_search() {
1008        let kb = KnowledgeBase::new("test");
1009        let mut bfs = BreadthFirstSearch::new(10, kb);
1010        let facts = Facts::new();
1011
1012        let mut goal = Goal::new("test".to_string());
1013        goal.add_candidate_rule("TestRule".to_string());
1014
1015        let result = bfs.search(&mut goal, &facts);
1016
1017        assert!(result.success);
1018        assert_eq!(result.goals_explored, 1);
1019    }
1020
1021    #[test]
1022    fn test_iterative_deepening_search_success() {
1023        let kb = KnowledgeBase::new("test");
1024        let mut ids = IterativeDeepeningSearch::new(5, kb.clone());
1025        let mut root = Goal::new("test".to_string());
1026        root.add_candidate_rule("TestRule".to_string());
1027
1028        // Facts empty; DFS probe should succeed because candidate rules mark provable
1029        let mut facts = Facts::new();
1030        let res = ids.search(&mut root, &facts);
1031        assert!(res.success);
1032    }
1033
1034    #[test]
1035    fn test_iterative_deepening_search_depth_limit() {
1036        let kb = KnowledgeBase::new("test");
1037        // Set max_depth to 0 so even shallow proofs that require depth >0 fail
1038        let mut ids = IterativeDeepeningSearch::new(0, kb.clone());
1039        let mut root = Goal::new("test".to_string());
1040        // Add a subgoal to force depth > 0
1041        let mut sub = Goal::new("sub".to_string());
1042        sub.add_candidate_rule("SubRule".to_string());
1043        root.sub_goals.push(sub);
1044
1045        let facts = Facts::new();
1046        let res = ids.search(&mut root, &facts);
1047        assert!(!res.success);
1048    }
1049
1050    #[test]
1051    fn test_depth_first_search_max_depth_exceeded() {
1052        let kb = KnowledgeBase::new("test");
1053        let mut dfs = DepthFirstSearch::new(2, kb);
1054        let facts = Facts::new();
1055
1056        // Create nested goals exceeding max depth
1057        let mut root = Goal::new("level0".to_string());
1058        root.depth = 0;
1059        root.add_candidate_rule("Rule0".to_string());
1060
1061        let mut level1 = Goal::new("level1".to_string());
1062        level1.depth = 1;
1063        level1.add_candidate_rule("Rule1".to_string());
1064
1065        let mut level2 = Goal::new("level2".to_string());
1066        level2.depth = 2;
1067        level2.add_candidate_rule("Rule2".to_string());
1068
1069        let mut level3 = Goal::new("level3".to_string());
1070        level3.depth = 3; // Exceeds max_depth of 2
1071        level3.add_candidate_rule("Rule3".to_string());
1072
1073        level2.add_subgoal(level3);
1074        level1.add_subgoal(level2);
1075        root.add_subgoal(level1);
1076
1077        let result = dfs.search(&mut root, &facts);
1078
1079        // Verify search completed (max_depth_reached is set)
1080        assert!(result.max_depth_reached <= 3);
1081    }
1082
1083    #[test]
1084    fn test_breadth_first_search_multiple_candidates() {
1085        let kb = KnowledgeBase::new("test");
1086        let mut bfs = BreadthFirstSearch::new(10, kb);
1087        let facts = Facts::new();
1088
1089        let mut goal = Goal::new("multi_rule_goal".to_string());
1090        goal.add_candidate_rule("Rule1".to_string());
1091        goal.add_candidate_rule("Rule2".to_string());
1092        goal.add_candidate_rule("Rule3".to_string());
1093
1094        let result = bfs.search(&mut goal, &facts);
1095
1096        assert!(result.success);
1097        assert_eq!(goal.candidate_rules.len(), 3);
1098    }
1099
1100    #[test]
1101    fn test_depth_first_search_empty_goal() {
1102        let kb = KnowledgeBase::new("test");
1103        let mut dfs = DepthFirstSearch::new(10, kb);
1104        let facts = Facts::new();
1105
1106        let mut goal = Goal::new("".to_string());
1107        // No candidate rules, no subgoals
1108
1109        let result = dfs.search(&mut goal, &facts);
1110
1111        // Should fail - no way to prove empty goal
1112        assert!(!result.success);
1113    }
1114
1115    #[test]
1116    fn test_search_result_with_bindings() {
1117        use crate::types::Value;
1118        let mut bindings = HashMap::new();
1119        bindings.insert("X".to_string(), Value::String("test".to_string()));
1120        bindings.insert("Y".to_string(), Value::Number(42.0));
1121
1122        let result = SearchResult {
1123            success: true,
1124            path: vec!["Rule1".to_string()],
1125            goals_explored: 5,
1126            max_depth_reached: 3,
1127            bindings: bindings.clone(),
1128            solutions: Vec::new(),
1129        };
1130
1131        assert_eq!(result.bindings.len(), 2);
1132        assert_eq!(result.bindings.get("X"), Some(&Value::String("test".to_string())));
1133    }
1134
1135    #[test]
1136    fn test_breadth_first_search_with_subgoals() {
1137        let kb = KnowledgeBase::new("test");
1138        let mut bfs = BreadthFirstSearch::new(10, kb);
1139        let facts = Facts::new();
1140
1141        let mut root = Goal::new("root".to_string());
1142        root.add_candidate_rule("RootRule".to_string());
1143
1144        let mut sub1 = Goal::new("sub1".to_string());
1145        sub1.add_candidate_rule("Sub1Rule".to_string());
1146
1147        let mut sub2 = Goal::new("sub2".to_string());
1148        sub2.add_candidate_rule("Sub2Rule".to_string());
1149
1150        root.add_subgoal(sub1);
1151        root.add_subgoal(sub2);
1152
1153        let result = bfs.search(&mut root, &facts);
1154
1155        assert!(result.success);
1156        assert!(result.goals_explored >= 3); // root + 2 subgoals
1157    }
1158
1159    #[test]
1160    fn test_iterative_deepening_search_no_candidates() {
1161        let kb = KnowledgeBase::new("test");
1162        let mut ids = IterativeDeepeningSearch::new(5, kb);
1163        let mut root = Goal::new("no_rules".to_string());
1164        // No candidate rules added
1165
1166        let facts = Facts::new();
1167        let result = ids.search(&mut root, &facts);
1168
1169        assert!(!result.success);
1170        assert!(result.path.is_empty());
1171    }
1172
1173    #[test]
1174    fn test_search_strategy_equality() {
1175        assert_eq!(SearchStrategy::BreadthFirst, SearchStrategy::BreadthFirst);
1176        assert_eq!(SearchStrategy::Iterative, SearchStrategy::Iterative);
1177        assert_ne!(SearchStrategy::BreadthFirst, SearchStrategy::Iterative);
1178    }
1179
1180    #[test]
1181    fn test_depth_first_search_goals_explored_count() {
1182        let kb = KnowledgeBase::new("test");
1183        let mut dfs = DepthFirstSearch::new(10, kb);
1184        let facts = Facts::new();
1185
1186        let mut root = Goal::new("root".to_string());
1187        root.add_candidate_rule("RootRule".to_string());
1188
1189        let mut sub = Goal::new("sub".to_string());
1190        sub.add_candidate_rule("SubRule".to_string());
1191
1192        root.add_subgoal(sub);
1193
1194        let result = dfs.search(&mut root, &facts);
1195
1196        // Search succeeded with candidate rules
1197        assert!(result.success);
1198        // Goals explored count is tracked
1199        assert!(result.goals_explored >= 0);
1200    }
1201}
rust_rule_engine/backward/search.rs

rust_rule_engine/backward/
search.rs
