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

rust_rule_engine/backward/
backward_engine.rs
