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

rust_rule_engine/backward/
search.rs
