rust_rule_engine/backward/
backward_engine.rs

1//! Backward chaining engine implementation
2
3use super::goal::{Goal, GoalManager, GoalStatus};
4use super::search::{DepthFirstSearch, BreadthFirstSearch, IterativeDeepeningSearch, SearchStrategy, SearchResult};
5use super::query::{QueryParser, QueryResult, QueryStats, ProofTrace};
6use super::conclusion_index::ConclusionIndex;
7use crate::{Facts, KnowledgeBase};
8use crate::errors::Result;
9use std::sync::Arc;
10
11/// Configuration for backward chaining engine
12#[derive(Debug, Clone)]
13pub struct BackwardConfig {
14    /// Maximum depth for goal search
15    pub max_depth: usize,
16    
17    /// Search strategy to use
18    pub strategy: SearchStrategy,
19    
20    /// Enable memoization of proven goals
21    pub enable_memoization: bool,
22    
23    /// Maximum number of solutions to find
24    pub max_solutions: usize,
25}
26
27impl Default for BackwardConfig {
28    fn default() -> Self {
29        Self {
30            max_depth: 10,
31            strategy: SearchStrategy::DepthFirst,
32            enable_memoization: true,
33            max_solutions: 1,
34        }
35    }
36}
37
38/// Backward chaining engine for goal-driven reasoning
39pub struct BackwardEngine {
40    knowledge_base: Arc<KnowledgeBase>,
41    config: BackwardConfig,
42    goal_manager: GoalManager,
43    /// RETE-style conclusion index for O(1) rule lookup
44    conclusion_index: ConclusionIndex,
45}
46
47impl BackwardEngine {
48    /// Create a new backward chaining engine
49    pub fn new(kb: KnowledgeBase) -> Self {
50        let rules = kb.get_rules();
51        let conclusion_index = ConclusionIndex::from_rules(&rules);
52
53        Self {
54            knowledge_base: Arc::new(kb),
55            config: BackwardConfig::default(),
56            goal_manager: GoalManager::default(),
57            conclusion_index,
58        }
59    }
60
61    /// Create with custom configuration
62    pub fn with_config(kb: KnowledgeBase, config: BackwardConfig) -> Self {
63        let rules = kb.get_rules();
64        let conclusion_index = ConclusionIndex::from_rules(&rules);
65
66        Self {
67            knowledge_base: Arc::new(kb),
68            goal_manager: GoalManager::new(config.max_depth),
69            config,
70            conclusion_index,
71        }
72    }
73    
74    /// Update configuration
75    pub fn set_config(&mut self, config: BackwardConfig) {
76        self.goal_manager = GoalManager::new(config.max_depth);
77        self.config = config;
78    }
79    
80    /// Query whether a goal can be proven
81    ///
82    /// # Example
83    ///
84    /// ```ignore
85    /// let engine = BackwardEngine::new(kb);
86    /// let result = engine.query("User.IsVIP == true", &mut facts)?;
87    ///
88    /// if result.provable {
89    ///     println!("User is VIP!");
90    /// }
91    /// ```
92    pub fn query(&mut self, query_str: &str, facts: &mut Facts) -> Result<QueryResult> {
93        // Backward-compatible: no RETE engine provided
94        self.query_with_rete_engine(query_str, facts, None)
95    }
96
97    /// Query with optional RETE IncrementalEngine for TMS integration
98    pub fn query_with_rete_engine(
99        &mut self,
100        query_str: &str,
101        facts: &mut Facts,
102        rete_engine: Option<std::sync::Arc<std::sync::Mutex<crate::rete::propagation::IncrementalEngine>>>,
103    ) -> Result<QueryResult> {
104        // Parse query into goal
105        let mut goal = QueryParser::parse(query_str)
106            .map_err(|e| crate::errors::RuleEngineError::ParseError { message: e })?;
107
108        // Check cache if memoization enabled
109        if self.config.enable_memoization {
110            if let Some(cached) = self.goal_manager.is_cached(query_str) {
111                return Ok(if cached {
112                    QueryResult::success(
113                        goal.bindings.to_map(), // Convert Bindings to HashMap
114                        ProofTrace::from_goal(&goal),
115                        QueryStats::default(),
116                    )
117                } else {
118                    QueryResult::failure(vec![], QueryStats::default())
119                });
120            }
121        }
122
123        // Find candidate rules that can prove this goal
124        self.find_candidate_rules(&mut goal)?;
125
126        // Execute search strategy with optional rete_engine
127        let search_result = match self.config.strategy {
128            SearchStrategy::DepthFirst => {
129                let mut dfs = DepthFirstSearch::new_with_engine(self.config.max_depth, (*self.knowledge_base).clone(), rete_engine.clone());
130                dfs.search_with_execution(&mut goal, facts, &self.knowledge_base)
131            }
132            SearchStrategy::BreadthFirst => {
133                let mut bfs = BreadthFirstSearch::new_with_engine(self.config.max_depth, (*self.knowledge_base).clone(), rete_engine.clone());
134                bfs.search_with_execution(&mut goal, facts, &self.knowledge_base)
135            }
136            SearchStrategy::Iterative => {
137                let mut ids = IterativeDeepeningSearch::new_with_engine(self.config.max_depth, (*self.knowledge_base).clone(), rete_engine.clone());
138                ids.search_with_execution(&mut goal, facts, &self.knowledge_base)
139            }
140        };
141
142        // Cache result if enabled
143        if self.config.enable_memoization {
144            self.goal_manager.cache_result(query_str.to_string(), search_result.success);
145        }
146
147        // Build query result
148        let stats = QueryStats {
149            goals_explored: search_result.goals_explored,
150            rules_evaluated: search_result.path.len(),
151            max_depth: search_result.max_depth_reached,
152            duration_ms: None,
153        };
154
155        Ok(if search_result.success {
156            QueryResult::success(
157                search_result.bindings,
158                ProofTrace::from_goal(&goal),
159                stats,
160            )
161        } else {
162            QueryResult::failure(self.find_missing_facts(&goal), stats)
163        })
164    }
165    
166    /// Find all candidate rules that could prove a goal
167    ///
168    /// This uses the RETE-style conclusion index for O(1) lookup
169    /// instead of O(n) iteration through all rules.
170    fn find_candidate_rules(&self, goal: &mut Goal) -> Result<()> {
171        // Use conclusion index for O(1) lookup
172        let candidates = self.conclusion_index.find_candidates(&goal.pattern);
173
174        // Add candidate rules to goal
175        for rule_name in candidates {
176            goal.add_candidate_rule(rule_name);
177        }
178
179        // If no candidates found via index, fall back to checking all rules
180        // This handles edge cases where index might miss some patterns
181        if goal.candidate_rules.is_empty() {
182            for rule in self.knowledge_base.get_rules() {
183                if self.rule_could_prove_goal(&rule, goal) {
184                    goal.add_candidate_rule(rule.name.clone());
185                }
186            }
187        }
188
189        Ok(())
190    }
191    
192    /// Check if a rule could potentially prove a goal
193    fn rule_could_prove_goal(&self, rule: &crate::engine::rule::Rule, goal: &Goal) -> bool {
194        // Simple heuristic: check if goal pattern appears in rule actions
195        // In a full implementation, this would be more sophisticated
196
197        // Check rule name
198        if goal.pattern.contains(&rule.name) {
199            return true;
200        }
201
202        // Check actions
203        for action in &rule.actions {
204            match action {
205                crate::types::ActionType::Set { field, .. } => {
206                    if goal.pattern.contains(field) {
207                        return true;
208                    }
209                }
210                crate::types::ActionType::MethodCall { object, method, .. } => {
211                    if goal.pattern.contains(object) || goal.pattern.contains(method) {
212                        return true;
213                    }
214                }
215                _ => {}
216            }
217        }
218
219        false
220    }
221
222    /// Find what facts are missing to prove a goal
223    fn find_missing_facts(&self, goal: &Goal) -> Vec<String> {
224        let mut missing = Vec::new();
225        
226        // Collect unprovable sub-goals
227        self.collect_missing_recursive(goal, &mut missing);
228        
229        missing
230    }
231    
232    fn collect_missing_recursive(&self, goal: &Goal, missing: &mut Vec<String>) {
233        if goal.status == GoalStatus::Unprovable {
234            missing.push(goal.pattern.clone());
235        }
236        
237        for sub_goal in &goal.sub_goals {
238            self.collect_missing_recursive(sub_goal, missing);
239        }
240    }
241    
242    /// Explain why a goal was proven (or not)
243    pub fn explain_why(&mut self, query_str: &str, facts: &mut Facts) -> Result<String> {
244        let result = self.query(query_str, facts)?;
245
246        if result.provable {
247            Ok(format!(
248                "Goal '{}' is PROVABLE\nProof trace:\n{:#?}",
249                query_str, result.proof_trace
250            ))
251        } else {
252            Ok(format!(
253                "Goal '{}' is NOT provable\nMissing facts: {:?}",
254                query_str, result.missing_facts
255            ))
256        }
257    }
258    
259    /// Get the configuration
260    pub fn config(&self) -> &BackwardConfig {
261        &self.config
262    }
263    
264    /// Get the knowledge base
265    pub fn knowledge_base(&self) -> &KnowledgeBase {
266        &self.knowledge_base
267    }
268
269    /// Get conclusion index statistics
270    pub fn index_stats(&self) -> super::conclusion_index::IndexStats {
271        self.conclusion_index.stats()
272    }
273
274    /// Rebuild the conclusion index (call after modifying knowledge base)
275    pub fn rebuild_index(&mut self) {
276        let rules = self.knowledge_base.get_rules();
277        self.conclusion_index = ConclusionIndex::from_rules(&rules);
278    }
279}
280
281#[cfg(test)]
282mod tests {
283    use super::*;
284    use crate::KnowledgeBase;
285    use crate::types::Value;
286    
287    #[test]
288    fn test_engine_creation() {
289        let kb = KnowledgeBase::new("test");
290        let engine = BackwardEngine::new(kb);
291        
292        assert_eq!(engine.config.max_depth, 10);
293        assert_eq!(engine.config.strategy, SearchStrategy::DepthFirst);
294    }
295    
296    #[test]
297    fn test_config_customization() {
298        let kb = KnowledgeBase::new("test");
299        let config = BackwardConfig {
300            max_depth: 5,
301            strategy: SearchStrategy::BreadthFirst,
302            enable_memoization: false,
303            max_solutions: 10,
304        };
305        
306        let engine = BackwardEngine::with_config(kb, config);
307        assert_eq!(engine.config.max_depth, 5);
308        assert_eq!(engine.config.strategy, SearchStrategy::BreadthFirst);
309        assert!(!engine.config.enable_memoization);
310    }
311    
312    #[test]
313    fn test_query_simple() {
314        let kb = KnowledgeBase::new("test");
315        let mut engine = BackwardEngine::new(kb);
316        let mut facts = Facts::new();
317
318        // This will fail because no rules, but tests the flow
319        let result = engine.query("User.IsVIP == true", &mut facts);
320        assert!(result.is_ok());
321    }
322
323    #[test]
324    fn test_function_call_condition_len() {
325        use crate::engine::rule::{Rule, Condition, ConditionGroup};
326        use crate::types::{Operator, ActionType};
327
328        let mut kb = KnowledgeBase::new("test");
329
330        // Rule: If User.Name length > 3, then User.HasLongName = true
331        let conditions = ConditionGroup::Single(
332            Condition::with_function(
333                "len".to_string(),
334                vec!["User.Name".to_string()],
335                Operator::GreaterThan,
336                Value::Number(3.0),
337            )
338        );
339        let actions = vec![ActionType::Set {
340            field: "User.HasLongName".to_string(),
341            value: Value::Boolean(true),
342        }];
343
344        let rule = Rule::new("CheckNameLength".to_string(), conditions, actions);
345        kb.add_rule(rule);
346
347        let mut engine = BackwardEngine::new(kb);
348        let mut facts = Facts::new();
349        facts.set("User.Name", Value::String("John".to_string()));
350
351        // Query if User.HasLongName == true
352        let result = engine.query("User.HasLongName == true", &mut facts);
353        assert!(result.is_ok());
354        let query_result = result.unwrap();
355
356        // Should be provable because "John".len() = 4 > 3
357        assert!(query_result.provable, "Query should be provable with len() function");
358    }
359
360    #[test]
361    fn test_function_call_condition_isempty() {
362        use crate::engine::rule::{Rule, Condition, ConditionGroup};
363        use crate::types::{Operator, ActionType};
364
365        let mut kb = KnowledgeBase::new("test");
366
367        // Rule: If User.Description is NOT empty, then User.HasDescription = true
368        let conditions = ConditionGroup::Single(
369            Condition::with_function(
370                "isEmpty".to_string(),
371                vec!["User.Description".to_string()],
372                Operator::Equal,
373                Value::Boolean(false),
374            )
375        );
376        let actions = vec![ActionType::Set {
377            field: "User.HasDescription".to_string(),
378            value: Value::Boolean(true),
379        }];
380
381        let rule = Rule::new("CheckDescription".to_string(), conditions, actions);
382        kb.add_rule(rule);
383
384        let mut engine = BackwardEngine::new(kb);
385        let mut facts = Facts::new();
386        facts.set("User.Description", Value::String("A great user".to_string()));
387
388        let result = engine.query("User.HasDescription == true", &mut facts);
389        assert!(result.is_ok());
390        let query_result = result.unwrap();
391
392        // Should be provable because description is not empty
393        assert!(query_result.provable, "Query should be provable with isEmpty() function");
394    }
395
396    #[test]
397    fn test_test_expression_exists() {
398        use crate::engine::rule::{Rule, Condition, ConditionGroup, ConditionExpression};
399        use crate::types::{Operator, ActionType};
400
401        let mut kb = KnowledgeBase::new("test");
402
403        // Rule: If User.Email exists, then User.HasEmail = true
404        let condition = Condition {
405            field: "User.Email".to_string(),  // Required field
406            expression: ConditionExpression::Test {
407                name: "exists".to_string(),
408                args: vec!["User.Email".to_string()],
409            },
410            operator: Operator::Equal,
411            value: Value::Boolean(true),
412        };
413        let conditions = ConditionGroup::Single(condition);
414        let actions = vec![ActionType::Set {
415            field: "User.HasEmail".to_string(),
416            value: Value::Boolean(true),
417        }];
418
419        let rule = Rule::new("CheckEmail".to_string(), conditions, actions);
420        kb.add_rule(rule);
421
422        let mut engine = BackwardEngine::new(kb);
423        let mut facts = Facts::new();
424        facts.set("User.Email", Value::String("user@example.com".to_string()));
425
426        let result = engine.query("User.HasEmail == true", &mut facts);
427        assert!(result.is_ok());
428        let query_result = result.unwrap();
429
430        // Should be provable because User.Email exists
431        assert!(query_result.provable, "Query should be provable with exists test");
432    }
433
434    #[test]
435    fn test_multifield_count_operation() {
436        use crate::engine::rule::{Rule, Condition, ConditionGroup, ConditionExpression};
437        use crate::types::{Operator, ActionType};
438
439        let mut kb = KnowledgeBase::new("test");
440
441        // Rule: If User.Orders count > 5, then User.IsFrequentBuyer = true
442        let condition = Condition {
443            field: "User.Orders".to_string(),  // Required field
444            expression: ConditionExpression::MultiField {
445                field: "User.Orders".to_string(),
446                operation: "count".to_string(),
447                variable: None,
448            },
449            operator: Operator::GreaterThan,
450            value: Value::Number(5.0),
451        };
452        let conditions = ConditionGroup::Single(condition);
453        let actions = vec![ActionType::Set {
454            field: "User.IsFrequentBuyer".to_string(),
455            value: Value::Boolean(true),
456        }];
457
458        let rule = Rule::new("CheckFrequentBuyer".to_string(), conditions, actions);
459        kb.add_rule(rule);
460
461        let mut engine = BackwardEngine::new(kb);
462        let mut facts = Facts::new();
463
464        // Create array of 6 orders
465        let orders = Value::Array(vec![
466            Value::Number(1.0),
467            Value::Number(2.0),
468            Value::Number(3.0),
469            Value::Number(4.0),
470            Value::Number(5.0),
471            Value::Number(6.0),
472        ]);
473        facts.set("User.Orders", orders);
474
475        let result = engine.query("User.IsFrequentBuyer == true", &mut facts);
476        assert!(result.is_ok());
477        let query_result = result.unwrap();
478
479        // Should be provable because orders.count() = 6 > 5
480        assert!(query_result.provable, "Query should be provable with count multifield operation");
481    }
482
483    #[test]
484    fn test_fact_derivation_basic() {
485        use crate::engine::rule::{Rule, Condition, ConditionGroup};
486        use crate::types::{Operator, ActionType};
487
488        let mut kb = KnowledgeBase::new("test");
489
490        // Rule: If User.Age > 18, then User.IsAdult = true
491        let conditions = ConditionGroup::Single(
492            Condition::new(
493                "User.Age".to_string(),
494                Operator::GreaterThan,
495                Value::Number(18.0),
496            )
497        );
498        let actions = vec![ActionType::Set {
499            field: "User.IsAdult".to_string(),
500            value: Value::Boolean(true),
501        }];
502
503        let rule = Rule::new("DetermineAdult".to_string(), conditions, actions);
504        kb.add_rule(rule);
505
506        let mut engine = BackwardEngine::new(kb);
507        let mut facts = Facts::new();
508        facts.set("User.Age", Value::Number(25.0));
509
510        // Query will trigger rule execution which should set User.IsAdult
511        let result = engine.query("User.IsAdult == true", &mut facts);
512        assert!(result.is_ok());
513        let query_result = result.unwrap();
514
515        assert!(query_result.provable, "Fact should be derived by rule action");
516    }
517
518    #[test]
519    fn test_rule_chaining_two_levels() {
520        use crate::engine::rule::{Rule, Condition, ConditionGroup};
521        use crate::types::{Operator, ActionType, LogicalOperator};
522
523        let mut kb = KnowledgeBase::new("test");
524
525        // Rule 1: If User.LoyaltyPoints > 100, then User.IsVIP = true
526        let conditions1 = ConditionGroup::Single(
527            Condition::new(
528                "User.LoyaltyPoints".to_string(),
529                Operator::GreaterThan,
530                Value::Number(100.0),
531            )
532        );
533        let actions1 = vec![ActionType::Set {
534            field: "User.IsVIP".to_string(),
535            value: Value::Boolean(true),
536        }];
537        let rule1 = Rule::new("DetermineVIP".to_string(), conditions1, actions1);
538
539        // Rule 2: If User.IsVIP == true AND Order.Amount < 10000, then Order.AutoApproved = true
540        let conditions2 = ConditionGroup::Compound {
541            left: Box::new(ConditionGroup::Single(
542                Condition::new(
543                    "User.IsVIP".to_string(),
544                    Operator::Equal,
545                    Value::Boolean(true),
546                )
547            )),
548            operator: LogicalOperator::And,
549            right: Box::new(ConditionGroup::Single(
550                Condition::new(
551                    "Order.Amount".to_string(),
552                    Operator::LessThan,
553                    Value::Number(10000.0),
554                )
555            )),
556        };
557        let actions2 = vec![ActionType::Set {
558            field: "Order.AutoApproved".to_string(),
559            value: Value::Boolean(true),
560        }];
561        let rule2 = Rule::new("AutoApproveVIP".to_string(), conditions2, actions2);
562
563        kb.add_rule(rule1);
564        kb.add_rule(rule2);
565
566        let mut engine = BackwardEngine::new(kb);
567        let mut facts = Facts::new();
568        facts.set("User.LoyaltyPoints", Value::Number(150.0));
569        facts.set("Order.Amount", Value::Number(5000.0));
570
571        // Query Order.AutoApproved - should chain through:
572        // 1. Check Order.AutoApproved rule (rule2)
573        // 2. Needs User.IsVIP == true
574        // 3. Check User.IsVIP rule (rule1)
575        // 4. Verify User.LoyaltyPoints > 100 (satisfied)
576        // 5. Execute rule1 action -> sets User.IsVIP = true
577        // 6. Now rule2 conditions satisfied -> sets Order.AutoApproved = true
578        let result = engine.query("Order.AutoApproved == true", &mut facts);
579        assert!(result.is_ok());
580        let query_result = result.unwrap();
581
582        assert!(query_result.provable, "Query should be provable through 2-level rule chaining");
583    }
584
585    #[test]
586    fn test_fact_derivation_with_log_action() {
587        use crate::engine::rule::{Rule, Condition, ConditionGroup};
588        use crate::types::{Operator, ActionType};
589
590        let mut kb = KnowledgeBase::new("test");
591
592        // Rule: If User.Score > 90, log message and set HighScore
593        let conditions = ConditionGroup::Single(
594            Condition::new(
595                "User.Score".to_string(),
596                Operator::GreaterThan,
597                Value::Number(90.0),
598            )
599        );
600        let actions = vec![
601            ActionType::Log {
602                message: "High score achieved!".to_string(),
603            },
604            ActionType::Set {
605                field: "User.HasHighScore".to_string(),
606                value: Value::Boolean(true),
607            }
608        ];
609
610        let rule = Rule::new("HighScoreRule".to_string(), conditions, actions);
611        kb.add_rule(rule);
612
613        let mut engine = BackwardEngine::new(kb);
614        let mut facts = Facts::new();
615        facts.set("User.Score", Value::Number(95.0));
616
617        let result = engine.query("User.HasHighScore == true", &mut facts);
618        assert!(result.is_ok());
619        let query_result = result.unwrap();
620
621        // Should be provable and log action should have been executed
622        assert!(query_result.provable, "Query should be provable with log action");
623    }
624}
rust_rule_engine/backward/backward_engine.rs

rust_rule_engine/backward/
backward_engine.rs
