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            | ConditionGroup::StreamPattern { .. } => {
533                // Complex conditions (Not, Exists, Forall, Accumulate) cannot be proven backward;
534                // they can only be evaluated against current facts.
535                // Use the executor's condition evaluator to check them.
536                self.executor
537                    .evaluate_conditions(group, facts)
538                    .unwrap_or(false)
539            }
540        }
541    }
542
543    /// Try to prove a single condition
544    fn try_prove_single_condition(
545        &mut self,
546        condition: &crate::engine::rule::Condition,
547        facts: &mut Facts,
548        kb: &KnowledgeBase,
549        depth: usize,
550    ) -> bool {
551        // First check if condition is already satisfied by facts
552        if let Ok(satisfied) = self.executor.evaluate_condition(condition, facts) {
553            if satisfied {
554                return true;
555            }
556        }
557
558        // Condition not satisfied - try to prove it by finding rules that can derive it
559        let goal_pattern = self.condition_to_goal_pattern(condition);
560
561        // Create a sub-goal for this condition
562        let mut sub_goal = Goal::new(goal_pattern.clone());
563        sub_goal.depth = depth;
564
565        // Find candidate rules that could prove this sub-goal
566        for candidate_rule in kb.get_rules() {
567            if self.rule_could_prove_pattern(&candidate_rule, &goal_pattern) {
568                sub_goal.add_candidate_rule(candidate_rule.name.clone());
569            }
570        }
571
572        // Try to prove this sub-goal recursively
573        self.search_recursive_with_execution(&mut sub_goal, facts, kb, depth)
574    }
575
576    /// Convert a condition to a goal pattern string
577    fn condition_to_goal_pattern(&self, condition: &crate::engine::rule::Condition) -> String {
578        use crate::engine::rule::ConditionExpression;
579
580        let field = match &condition.expression {
581            ConditionExpression::Field(f) => f.clone(),
582            ConditionExpression::FunctionCall { name, .. } => name.clone(),
583            ConditionExpression::Test { name, .. } => format!("test({})", name),
584            ConditionExpression::MultiField { field, .. } => field.clone(),
585        };
586
587        let op_str = match condition.operator {
588            crate::types::Operator::Equal => "==",
589            crate::types::Operator::NotEqual => "!=",
590            crate::types::Operator::GreaterThan => ">",
591            crate::types::Operator::LessThan => "<",
592            crate::types::Operator::GreaterThanOrEqual => ">=",
593            crate::types::Operator::LessThanOrEqual => "<=",
594            crate::types::Operator::Contains => "contains",
595            crate::types::Operator::NotContains => "not_contains",
596            crate::types::Operator::StartsWith => "starts_with",
597            crate::types::Operator::EndsWith => "ends_with",
598            crate::types::Operator::Matches => "matches",
599        };
600
601        // Convert value to string format that matches goal patterns
602        let value_str = match &condition.value {
603            Value::Boolean(b) => b.to_string(),
604            Value::Number(n) => n.to_string(),
605            Value::Integer(i) => i.to_string(),
606            Value::String(s) => format!("\"{}\"", s),
607            Value::Null => "null".to_string(),
608            _ => format!("{:?}", condition.value),
609        };
610
611        format!("{} {} {}", field, op_str, value_str)
612    }
613
614    /// Check if a rule could prove a specific goal pattern
615    fn rule_could_prove_pattern(&self, rule: &Rule, pattern: &str) -> bool {
616        // Simple heuristic: check if pattern mentions fields that this rule sets
617        for action in &rule.actions {
618            match action {
619                crate::types::ActionType::Set { field, .. } => {
620                    if pattern.contains(field) {
621                        return true;
622                    }
623                }
624                crate::types::ActionType::MethodCall { object, method, .. } => {
625                    if pattern.contains(object) || pattern.contains(method) {
626                        return true;
627                    }
628                }
629                _ => {}
630            }
631        }
632        false
633    }
634
635    /// OLD: Recursive search without execution
636    fn search_recursive(&mut self, goal: &mut Goal, depth: usize) -> bool {
637        self.goals_explored += 1;
638
639        // Check depth limit
640        if depth > self.max_depth {
641            goal.status = GoalStatus::Unprovable;
642            return false;
643        }
644
645        // Check for cycles (goal already in progress)
646        if goal.status == GoalStatus::InProgress {
647            goal.status = GoalStatus::Unprovable;
648            return false;
649        }
650
651        // Mark as in progress to detect cycles
652        goal.status = GoalStatus::InProgress;
653        goal.depth = depth;
654
655        // Try each candidate rule
656        if let Some(rule_name) = goal.candidate_rules.clone().into_iter().next() {
657            self.path.push(rule_name.clone());
658
659            // Get the rule from knowledge base (via goal's stored rules)
660            // In a full implementation with KB access:
661            // 1. Get rule conditions
662            // 2. Check if conditions match current facts
663            // 3. If match, execute rule actions to derive new facts
664            // 4. Mark goal as proven
665
666            // For backward chaining, we check:
667            // - Can this rule's conclusion prove our goal?
668            // - Are all rule conditions satisfied (recursively)?
669
670            // Since we found a candidate rule, assume it can prove the goal
671            // The rule was added as candidate because its conclusion matches the goal
672            goal.status = GoalStatus::Proven;
673            return true;
674        }
675
676        // Try to prove sub-goals
677        for sub_goal in &mut goal.sub_goals {
678            if !self.search_recursive(sub_goal, depth + 1) {
679                goal.status = GoalStatus::Unprovable;
680                return false;
681            }
682        }
683
684        // If we have no sub-goals and no candidate rules, unprovable
685        if goal.sub_goals.is_empty() && goal.candidate_rules.is_empty() {
686            goal.status = GoalStatus::Unprovable;
687            return false;
688        }
689
690        goal.status = GoalStatus::Proven;
691        true
692    }
693}
694
695/// Breadth-first search implementation
696pub struct BreadthFirstSearch {
697    max_depth: usize,
698    goals_explored: usize,
699    executor: RuleExecutor,
700}
701
702/// Iterative deepening search implementation
703pub struct IterativeDeepeningSearch {
704    max_depth: usize,
705    goals_explored: usize,
706    kb: KnowledgeBase,
707    engine: Option<Arc<Mutex<IncrementalEngine>>>,
708}
709
710impl IterativeDeepeningSearch {
711    /// Create a new iterative deepening search
712    pub fn new(max_depth: usize, kb: KnowledgeBase) -> Self {
713        Self {
714            max_depth,
715            goals_explored: 0,
716            kb,
717            engine: None,
718        }
719    }
720
721    /// Create with optional IncrementalEngine for TMS integration
722    pub fn new_with_engine(
723        max_depth: usize,
724        kb: KnowledgeBase,
725        engine: Option<Arc<Mutex<IncrementalEngine>>>,
726    ) -> Self {
727        // Store the engine so we can pass it to DFS instances
728        Self {
729            max_depth,
730            goals_explored: 0,
731            kb,
732            engine,
733        }
734    }
735
736    /// Search with execution: probe with increasing depth using non-executing DFS,
737    /// then run a final executing DFS at the discovered depth to mutate facts.
738    pub fn search_with_execution(
739        &mut self,
740        root_goal: &mut Goal,
741        facts: &mut Facts,
742        kb: &KnowledgeBase,
743    ) -> SearchResult {
744        self.goals_explored = 0;
745        let mut cumulative_goals = 0usize;
746
747        // Try increasing depth limits
748        for depth_limit in 0..=self.max_depth {
749            // Probe using a non-executing depth-first search on a cloned goal
750            let mut probe_goal = root_goal.clone();
751            let probe_kb = self.kb.clone();
752            let mut probe_dfs = DepthFirstSearch::new(depth_limit, probe_kb);
753            let probe_result = probe_dfs.search(&mut probe_goal, facts);
754            cumulative_goals += probe_result.goals_explored;
755
756            if probe_result.success {
757                // Found a depth where a proof exists; execute for real at this depth
758                let exec_kb = self.kb.clone();
759                let mut exec_dfs =
760                    DepthFirstSearch::new_with_engine(depth_limit, exec_kb, self.engine.clone());
761                let exec_result = exec_dfs.search_with_execution(root_goal, facts, kb);
762                // Aggregate explored goals
763                let mut final_result = exec_result;
764                final_result.goals_explored += cumulative_goals - final_result.goals_explored;
765                return final_result;
766            }
767        }
768
769        // Nothing proved up to max_depth
770        SearchResult::failure(cumulative_goals, self.max_depth)
771    }
772
773    /// Non-executing search using iterative deepening (probes only)
774    pub fn search(&mut self, root_goal: &mut Goal, facts: &Facts) -> SearchResult {
775        self.goals_explored = 0;
776        let mut cumulative_goals = 0usize;
777
778        for depth_limit in 0..=self.max_depth {
779            let mut probe_goal = root_goal.clone();
780            let probe_kb = self.kb.clone();
781            let mut probe_dfs = DepthFirstSearch::new(depth_limit, probe_kb);
782            let probe_result = probe_dfs.search(&mut probe_goal, facts);
783            cumulative_goals += probe_result.goals_explored;
784            if probe_result.success {
785                // Return the successful probe result (with aggregated goals explored)
786                let mut res = probe_result;
787                res.goals_explored = cumulative_goals;
788                return res;
789            }
790        }
791
792        SearchResult::failure(cumulative_goals, self.max_depth)
793    }
794}
795
796impl BreadthFirstSearch {
797    /// Create a new breadth-first search
798    pub fn new(max_depth: usize, kb: KnowledgeBase) -> Self {
799        Self {
800            max_depth,
801            goals_explored: 0,
802            executor: RuleExecutor::new_with_inserter(kb, None),
803        }
804    }
805
806    /// Create BFS with optional engine for TMS integration
807    pub fn new_with_engine(
808        max_depth: usize,
809        kb: KnowledgeBase,
810        engine: Option<Arc<Mutex<IncrementalEngine>>>,
811    ) -> Self {
812        // If engine provided, create inserter closure
813        let inserter = engine.map(|eng| {
814            let eng = eng.clone();
815            std::sync::Arc::new(
816                move |fact_type: String,
817                      data: crate::rete::TypedFacts,
818                      rule_name: String,
819                      _premises: Vec<String>| {
820                    if let Ok(mut e) = eng.lock() {
821                        let _ = e.insert_logical(fact_type, data, rule_name, Vec::new());
822                    }
823                },
824            )
825                as std::sync::Arc<
826                    dyn Fn(String, crate::rete::TypedFacts, String, Vec<String>) + Send + Sync,
827                >
828        });
829
830        Self {
831            max_depth,
832            goals_explored: 0,
833            executor: RuleExecutor::new_with_inserter(kb, inserter),
834        }
835    }
836
837    /// Search for a proof of the goal using BFS WITH rule execution
838    pub fn search_with_execution(
839        &mut self,
840        root_goal: &mut Goal,
841        facts: &mut Facts,
842        kb: &KnowledgeBase,
843    ) -> SearchResult {
844        self.goals_explored = 0;
845        let mut queue = VecDeque::new();
846        let mut path = Vec::new();
847        let mut max_depth = 0;
848
849        queue.push_back((root_goal as *mut Goal, 0));
850
851        while let Some((goal_ptr, depth)) = queue.pop_front() {
852            // Safety: We maintain ownership properly
853            let goal = unsafe { &mut *goal_ptr };
854
855            self.goals_explored += 1;
856            max_depth = max_depth.max(depth);
857
858            if depth > self.max_depth {
859                continue;
860            }
861
862            goal.depth = depth;
863
864            // Check if goal already satisfied by facts
865            if self.check_goal_in_facts(goal, facts) {
866                goal.status = GoalStatus::Proven;
867                continue;
868            }
869
870            // Try each candidate rule
871            for rule_name in goal.candidate_rules.clone() {
872                path.push(rule_name.clone());
873
874                // Get the rule from KB
875                if let Some(rule) = kb.get_rule(&rule_name) {
876                    // ✅ FIX: Try to execute rule (checks conditions AND executes actions)
877                    match self.executor.try_execute_rule(&rule, facts) {
878                        Ok(true) => {
879                            // Rule executed successfully - derived new facts!
880                            // Now check if our goal is proven
881                            if self.check_goal_in_facts(goal, facts) {
882                                goal.status = GoalStatus::Proven;
883                                break;
884                            }
885                        }
886                        Ok(false) => {
887                            // Conditions not satisfied - continue to next rule
888                        }
889                        Err(_) => {
890                            // Execution error - continue to next rule
891                        }
892                    }
893                }
894            }
895
896            // Add sub-goals to queue
897            for sub_goal in &mut goal.sub_goals {
898                queue.push_back((sub_goal as *mut Goal, depth + 1));
899            }
900        }
901
902        let success = root_goal.is_proven();
903
904        SearchResult {
905            success,
906            path,
907            goals_explored: self.goals_explored,
908            max_depth_reached: max_depth,
909            bindings: root_goal.bindings.to_map(),
910            solutions: Vec::new(),
911        }
912    }
913
914    /// Check if goal is already satisfied by facts
915    ///
916    /// This method now reuses ConditionEvaluator for proper evaluation
917    fn check_goal_in_facts(&self, goal: &Goal, facts: &Facts) -> bool {
918        // For negated goals, use the expression directly (parser strips NOT)
919        if goal.is_negated {
920            if let Some(ref expr) = goal.expression {
921                // Expression.evaluate() returns Value, need to convert to bool
922                match expr.evaluate(facts) {
923                    Ok(Value::Boolean(b)) => return b,
924                    Ok(_) => return false, // Non-boolean values are false
925                    Err(_) => return false,
926                }
927            }
928            return false;
929        }
930
931        // Parse goal pattern into a Condition and use ConditionEvaluator
932        if let Some(condition) = self.parse_goal_pattern(&goal.pattern) {
933            // Use RuleExecutor's evaluator (which delegates to ConditionEvaluator)
934            self.executor
935                .evaluate_condition(&condition, facts)
936                .unwrap_or(false)
937        } else {
938            false
939        }
940    }
941
942    /// Parse goal pattern string into a Condition object
943    ///
944    /// Examples:
945    /// - "User.Score >= 80" → Condition { field: "User.Score", operator: GreaterThanOrEqual, value: Number(80) }
946    /// - "User.IsVIP == true" → Condition { field: "User.IsVIP", operator: Equal, value: Boolean(true) }
947    fn parse_goal_pattern(&self, pattern: &str) -> Option<crate::engine::rule::Condition> {
948        use crate::engine::rule::{Condition, ConditionExpression};
949        use crate::types::Operator;
950
951        // Try parsing operators in order (longest first to avoid conflicts)
952        let operators = [
953            (">=", Operator::GreaterThanOrEqual),
954            ("<=", Operator::LessThanOrEqual),
955            ("==", Operator::Equal),
956            ("!=", Operator::NotEqual),
957            (" > ", Operator::GreaterThan),
958            (" < ", Operator::LessThan),
959            (" contains ", Operator::Contains),
960            (" not_contains ", Operator::NotContains),
961            (" starts_with ", Operator::StartsWith),
962            (" startsWith ", Operator::StartsWith),
963            (" ends_with ", Operator::EndsWith),
964            (" endsWith ", Operator::EndsWith),
965            (" matches ", Operator::Matches),
966        ];
967
968        for (op_str, operator) in operators {
969            if let Some(pos) = pattern.find(op_str) {
970                let field = pattern[..pos].trim().to_string();
971                let value_str = pattern[pos + op_str.len()..].trim();
972
973                // Parse value
974                let value = self.parse_value_string(value_str);
975
976                return Some(Condition {
977                    field: field.clone(),
978                    expression: ConditionExpression::Field(field),
979                    operator,
980                    value,
981                });
982            }
983        }
984
985        None
986    }
987
988    /// Parse value string into a Value
989    fn parse_value_string(&self, s: &str) -> Value {
990        let s = s.trim();
991
992        // Boolean
993        if s == "true" {
994            return Value::Boolean(true);
995        }
996        if s == "false" {
997            return Value::Boolean(false);
998        }
999
1000        // Null
1001        if s == "null" {
1002            return Value::Null;
1003        }
1004
1005        // String (quoted)
1006        if (s.starts_with('"') && s.ends_with('"')) || (s.starts_with('\'') && s.ends_with('\'')) {
1007            return Value::String(s[1..s.len() - 1].to_string());
1008        }
1009
1010        // Number (float)
1011        if let Ok(n) = s.parse::<f64>() {
1012            return Value::Number(n);
1013        }
1014
1015        // Integer
1016        if let Ok(i) = s.parse::<i64>() {
1017            return Value::Integer(i);
1018        }
1019
1020        // Default to string
1021        Value::String(s.to_string())
1022    }
1023
1024    /// Search for a proof of the goal using BFS (old method, kept for compatibility)
1025    pub fn search(&mut self, root_goal: &mut Goal, _facts: &Facts) -> SearchResult {
1026        self.goals_explored = 0;
1027        let mut queue = VecDeque::new();
1028        let mut path = Vec::new();
1029        let mut max_depth = 0;
1030
1031        queue.push_back((root_goal as *mut Goal, 0));
1032
1033        while let Some((goal_ptr, depth)) = queue.pop_front() {
1034            // Safety: We maintain ownership properly
1035            let goal = unsafe { &mut *goal_ptr };
1036
1037            self.goals_explored += 1;
1038            max_depth = max_depth.max(depth);
1039
1040            if depth > self.max_depth {
1041                continue;
1042            }
1043
1044            goal.depth = depth;
1045
1046            // Process candidate rules
1047            for rule_name in &goal.candidate_rules {
1048                path.push(rule_name.clone());
1049            }
1050
1051            // Add sub-goals to queue
1052            for sub_goal in &mut goal.sub_goals {
1053                queue.push_back((sub_goal as *mut Goal, depth + 1));
1054            }
1055
1056            // Check if goal can be proven
1057            if !goal.candidate_rules.is_empty() || goal.all_subgoals_proven() {
1058                goal.status = GoalStatus::Proven;
1059            }
1060        }
1061
1062        let success = root_goal.is_proven();
1063
1064        SearchResult {
1065            success,
1066            path,
1067            goals_explored: self.goals_explored,
1068            max_depth_reached: max_depth,
1069            bindings: root_goal.bindings.to_map(),
1070            solutions: Vec::new(),
1071        }
1072    }
1073}
1074
1075#[cfg(test)]
1076mod tests {
1077    use super::*;
1078    use std::collections::HashMap;
1079
1080    #[test]
1081    fn test_search_strategies() {
1082        assert_eq!(SearchStrategy::DepthFirst, SearchStrategy::DepthFirst);
1083        assert_ne!(SearchStrategy::DepthFirst, SearchStrategy::BreadthFirst);
1084    }
1085
1086    #[test]
1087    fn test_search_result_creation() {
1088        let success = SearchResult::success(vec!["Rule1".to_string()], 5, 3);
1089        assert!(success.success);
1090        assert_eq!(success.path.len(), 1);
1091        assert_eq!(success.goals_explored, 5);
1092
1093        let failure = SearchResult::failure(10, 5);
1094        assert!(!failure.success);
1095        assert!(failure.path.is_empty());
1096    }
1097
1098    #[test]
1099    fn test_depth_first_search_creation() {
1100        let kb = KnowledgeBase::new("test");
1101        let dfs = DepthFirstSearch::new(10, kb);
1102        assert_eq!(dfs.max_depth, 10);
1103        assert_eq!(dfs.goals_explored, 0);
1104    }
1105
1106    #[test]
1107    fn test_depth_first_search_simple() {
1108        let kb = KnowledgeBase::new("test");
1109        let mut dfs = DepthFirstSearch::new(10, kb);
1110        let facts = Facts::new();
1111
1112        let mut goal = Goal::new("test".to_string());
1113        goal.add_candidate_rule("TestRule".to_string());
1114
1115        let result = dfs.search(&mut goal, &facts);
1116
1117        assert!(result.success);
1118        assert!(goal.is_proven());
1119        assert!(result.goals_explored > 0);
1120    }
1121
1122    #[test]
1123    fn test_breadth_first_search() {
1124        let kb = KnowledgeBase::new("test");
1125        let mut bfs = BreadthFirstSearch::new(10, kb);
1126        let facts = Facts::new();
1127
1128        let mut goal = Goal::new("test".to_string());
1129        goal.add_candidate_rule("TestRule".to_string());
1130
1131        let result = bfs.search(&mut goal, &facts);
1132
1133        assert!(result.success);
1134        assert_eq!(result.goals_explored, 1);
1135    }
1136
1137    #[test]
1138    fn test_iterative_deepening_search_success() {
1139        let kb = KnowledgeBase::new("test");
1140        let mut ids = IterativeDeepeningSearch::new(5, kb.clone());
1141        let mut root = Goal::new("test".to_string());
1142        root.add_candidate_rule("TestRule".to_string());
1143
1144        // Facts empty; DFS probe should succeed because candidate rules mark provable
1145        let facts = Facts::new();
1146        let res = ids.search(&mut root, &facts);
1147        assert!(res.success);
1148    }
1149
1150    #[test]
1151    fn test_iterative_deepening_search_depth_limit() {
1152        let kb = KnowledgeBase::new("test");
1153        // Set max_depth to 0 so even shallow proofs that require depth >0 fail
1154        let mut ids = IterativeDeepeningSearch::new(0, kb.clone());
1155        let mut root = Goal::new("test".to_string());
1156        // Add a subgoal to force depth > 0
1157        let mut sub = Goal::new("sub".to_string());
1158        sub.add_candidate_rule("SubRule".to_string());
1159        root.sub_goals.push(sub);
1160
1161        let facts = Facts::new();
1162        let res = ids.search(&mut root, &facts);
1163        assert!(!res.success);
1164    }
1165
1166    #[test]
1167    fn test_depth_first_search_max_depth_exceeded() {
1168        let kb = KnowledgeBase::new("test");
1169        let mut dfs = DepthFirstSearch::new(2, kb);
1170        let facts = Facts::new();
1171
1172        // Create nested goals exceeding max depth
1173        let mut root = Goal::new("level0".to_string());
1174        root.depth = 0;
1175        root.add_candidate_rule("Rule0".to_string());
1176
1177        let mut level1 = Goal::new("level1".to_string());
1178        level1.depth = 1;
1179        level1.add_candidate_rule("Rule1".to_string());
1180
1181        let mut level2 = Goal::new("level2".to_string());
1182        level2.depth = 2;
1183        level2.add_candidate_rule("Rule2".to_string());
1184
1185        let mut level3 = Goal::new("level3".to_string());
1186        level3.depth = 3; // Exceeds max_depth of 2
1187        level3.add_candidate_rule("Rule3".to_string());
1188
1189        level2.add_subgoal(level3);
1190        level1.add_subgoal(level2);
1191        root.add_subgoal(level1);
1192
1193        let result = dfs.search(&mut root, &facts);
1194
1195        // Verify search completed (max_depth_reached is set)
1196        assert!(result.max_depth_reached <= 3);
1197    }
1198
1199    #[test]
1200    fn test_breadth_first_search_multiple_candidates() {
1201        let kb = KnowledgeBase::new("test");
1202        let mut bfs = BreadthFirstSearch::new(10, kb);
1203        let facts = Facts::new();
1204
1205        let mut goal = Goal::new("multi_rule_goal".to_string());
1206        goal.add_candidate_rule("Rule1".to_string());
1207        goal.add_candidate_rule("Rule2".to_string());
1208        goal.add_candidate_rule("Rule3".to_string());
1209
1210        let result = bfs.search(&mut goal, &facts);
1211
1212        assert!(result.success);
1213        assert_eq!(goal.candidate_rules.len(), 3);
1214    }
1215
1216    #[test]
1217    fn test_depth_first_search_empty_goal() {
1218        let kb = KnowledgeBase::new("test");
1219        let mut dfs = DepthFirstSearch::new(10, kb);
1220        let facts = Facts::new();
1221
1222        let mut goal = Goal::new("".to_string());
1223        // No candidate rules, no subgoals
1224
1225        let result = dfs.search(&mut goal, &facts);
1226
1227        // Should fail - no way to prove empty goal
1228        assert!(!result.success);
1229    }
1230
1231    #[test]
1232    fn test_search_result_with_bindings() {
1233        use crate::types::Value;
1234        let mut bindings = HashMap::new();
1235        bindings.insert("X".to_string(), Value::String("test".to_string()));
1236        bindings.insert("Y".to_string(), Value::Number(42.0));
1237
1238        let result = SearchResult {
1239            success: true,
1240            path: vec!["Rule1".to_string()],
1241            goals_explored: 5,
1242            max_depth_reached: 3,
1243            bindings: bindings.clone(),
1244            solutions: Vec::new(),
1245        };
1246
1247        assert_eq!(result.bindings.len(), 2);
1248        assert_eq!(
1249            result.bindings.get("X"),
1250            Some(&Value::String("test".to_string()))
1251        );
1252    }
1253
1254    #[test]
1255    fn test_breadth_first_search_with_subgoals() {
1256        let kb = KnowledgeBase::new("test");
1257        let mut bfs = BreadthFirstSearch::new(10, kb);
1258        let facts = Facts::new();
1259
1260        let mut root = Goal::new("root".to_string());
1261        root.add_candidate_rule("RootRule".to_string());
1262
1263        let mut sub1 = Goal::new("sub1".to_string());
1264        sub1.add_candidate_rule("Sub1Rule".to_string());
1265
1266        let mut sub2 = Goal::new("sub2".to_string());
1267        sub2.add_candidate_rule("Sub2Rule".to_string());
1268
1269        root.add_subgoal(sub1);
1270        root.add_subgoal(sub2);
1271
1272        let result = bfs.search(&mut root, &facts);
1273
1274        assert!(result.success);
1275        assert!(result.goals_explored >= 3); // root + 2 subgoals
1276    }
1277
1278    #[test]
1279    fn test_iterative_deepening_search_no_candidates() {
1280        let kb = KnowledgeBase::new("test");
1281        let mut ids = IterativeDeepeningSearch::new(5, kb);
1282        let mut root = Goal::new("no_rules".to_string());
1283        // No candidate rules added
1284
1285        let facts = Facts::new();
1286        let result = ids.search(&mut root, &facts);
1287
1288        assert!(!result.success);
1289        assert!(result.path.is_empty());
1290    }
1291
1292    #[test]
1293    fn test_search_strategy_equality() {
1294        assert_eq!(SearchStrategy::BreadthFirst, SearchStrategy::BreadthFirst);
1295        assert_eq!(SearchStrategy::Iterative, SearchStrategy::Iterative);
1296        assert_ne!(SearchStrategy::BreadthFirst, SearchStrategy::Iterative);
1297    }
1298
1299    #[test]
1300    fn test_depth_first_search_goals_explored_count() {
1301        let kb = KnowledgeBase::new("test");
1302        let mut dfs = DepthFirstSearch::new(10, kb);
1303        let facts = Facts::new();
1304
1305        let mut root = Goal::new("root".to_string());
1306        root.add_candidate_rule("RootRule".to_string());
1307
1308        let mut sub = Goal::new("sub".to_string());
1309        sub.add_candidate_rule("SubRule".to_string());
1310
1311        root.add_subgoal(sub);
1312
1313        let result = dfs.search(&mut root, &facts);
1314
1315        // Search succeeded with candidate rules
1316        assert!(result.success);
1317        // Goals explored count is tracked (always >= 0 since it's usize)
1318        assert!(result.goals_explored > 0);
1319    }
1320}
rust_rule_engine/backward/search.rs

rust_rule_engine/backward/
search.rs
