rust_rule_engine/backward/
search.rs

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

rust_rule_engine/backward/
search.rs
