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

rust_rule_engine/backward/
search.rs
