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    /// Query with aggregation functions
284    ///
285    /// Supports: count, sum, avg, min, max, first, last
286    ///
287    /// # Example
288    ///
289    /// ```ignore
290    /// // Count all employees
291    /// let count = engine.query_aggregate(
292    ///     "count(?x) WHERE employee(?x)",
293    ///     &mut facts
294    /// )?;
295    ///
296    /// // Sum of salaries over 50000
297    /// let total = engine.query_aggregate(
298    ///     "sum(?salary) WHERE salary(?name, ?salary) AND ?salary > 50000",
299    ///     &mut facts
300    /// )?;
301    ///
302    /// // Average price
303    /// let avg_price = engine.query_aggregate(
304    ///     "avg(?price) WHERE product(?name, ?price)",
305    ///     &mut facts
306    /// )?;
307    /// ```
308    pub fn query_aggregate(
309        &mut self,
310        query: &str,
311        facts: &mut Facts,
312    ) -> Result<crate::types::Value> {
313        use super::aggregation::{parse_aggregate_query, apply_aggregate};
314
315        // Parse the aggregate query
316        let agg_query = parse_aggregate_query(query)?;
317
318        // Set max_solutions to unlimited for aggregation
319        let original_max = self.config.max_solutions;
320        self.config.max_solutions = usize::MAX;
321
322        // Execute the underlying pattern query to get all solutions
323        let result = self.query(&agg_query.pattern, facts)?;
324
325        // Restore original max_solutions
326        self.config.max_solutions = original_max;
327
328        // Apply aggregation to solutions
329        let value = apply_aggregate(&agg_query.function, &result.solutions)?;
330
331        Ok(value)
332    }
333}
334
335#[cfg(test)]
336mod tests {
337    use super::*;
338    use crate::KnowledgeBase;
339    use crate::types::Value;
340    
341    #[test]
342    fn test_engine_creation() {
343        let kb = KnowledgeBase::new("test");
344        let engine = BackwardEngine::new(kb);
345        
346        assert_eq!(engine.config.max_depth, 10);
347        assert_eq!(engine.config.strategy, SearchStrategy::DepthFirst);
348    }
349    
350    #[test]
351    fn test_config_customization() {
352        let kb = KnowledgeBase::new("test");
353        let config = BackwardConfig {
354            max_depth: 5,
355            strategy: SearchStrategy::BreadthFirst,
356            enable_memoization: false,
357            max_solutions: 10,
358        };
359        
360        let engine = BackwardEngine::with_config(kb, config);
361        assert_eq!(engine.config.max_depth, 5);
362        assert_eq!(engine.config.strategy, SearchStrategy::BreadthFirst);
363        assert!(!engine.config.enable_memoization);
364    }
365    
366    #[test]
367    fn test_query_simple() {
368        let kb = KnowledgeBase::new("test");
369        let mut engine = BackwardEngine::new(kb);
370        let mut facts = Facts::new();
371
372        // This will fail because no rules, but tests the flow
373        let result = engine.query("User.IsVIP == true", &mut facts);
374        assert!(result.is_ok());
375    }
376
377    #[test]
378    fn test_function_call_condition_len() {
379        use crate::engine::rule::{Rule, Condition, ConditionGroup};
380        use crate::types::{Operator, ActionType};
381
382        let mut kb = KnowledgeBase::new("test");
383
384        // Rule: If User.Name length > 3, then User.HasLongName = true
385        let conditions = ConditionGroup::Single(
386            Condition::with_function(
387                "len".to_string(),
388                vec!["User.Name".to_string()],
389                Operator::GreaterThan,
390                Value::Number(3.0),
391            )
392        );
393        let actions = vec![ActionType::Set {
394            field: "User.HasLongName".to_string(),
395            value: Value::Boolean(true),
396        }];
397
398        let rule = Rule::new("CheckNameLength".to_string(), conditions, actions);
399        kb.add_rule(rule);
400
401        let mut engine = BackwardEngine::new(kb);
402        let mut facts = Facts::new();
403        facts.set("User.Name", Value::String("John".to_string()));
404
405        // Query if User.HasLongName == true
406        let result = engine.query("User.HasLongName == true", &mut facts);
407        assert!(result.is_ok());
408        let query_result = result.unwrap();
409
410        // Should be provable because "John".len() = 4 > 3
411        assert!(query_result.provable, "Query should be provable with len() function");
412    }
413
414    #[test]
415    fn test_function_call_condition_isempty() {
416        use crate::engine::rule::{Rule, Condition, ConditionGroup};
417        use crate::types::{Operator, ActionType};
418
419        let mut kb = KnowledgeBase::new("test");
420
421        // Rule: If User.Description is NOT empty, then User.HasDescription = true
422        let conditions = ConditionGroup::Single(
423            Condition::with_function(
424                "isEmpty".to_string(),
425                vec!["User.Description".to_string()],
426                Operator::Equal,
427                Value::Boolean(false),
428            )
429        );
430        let actions = vec![ActionType::Set {
431            field: "User.HasDescription".to_string(),
432            value: Value::Boolean(true),
433        }];
434
435        let rule = Rule::new("CheckDescription".to_string(), conditions, actions);
436        kb.add_rule(rule);
437
438        let mut engine = BackwardEngine::new(kb);
439        let mut facts = Facts::new();
440        facts.set("User.Description", Value::String("A great user".to_string()));
441
442        let result = engine.query("User.HasDescription == true", &mut facts);
443        assert!(result.is_ok());
444        let query_result = result.unwrap();
445
446        // Should be provable because description is not empty
447        assert!(query_result.provable, "Query should be provable with isEmpty() function");
448    }
449
450    #[test]
451    fn test_test_expression_exists() {
452        use crate::engine::rule::{Rule, Condition, ConditionGroup, ConditionExpression};
453        use crate::types::{Operator, ActionType};
454
455        let mut kb = KnowledgeBase::new("test");
456
457        // Rule: If User.Email exists, then User.HasEmail = true
458        let condition = Condition {
459            field: "User.Email".to_string(),  // Required field
460            expression: ConditionExpression::Test {
461                name: "exists".to_string(),
462                args: vec!["User.Email".to_string()],
463            },
464            operator: Operator::Equal,
465            value: Value::Boolean(true),
466        };
467        let conditions = ConditionGroup::Single(condition);
468        let actions = vec![ActionType::Set {
469            field: "User.HasEmail".to_string(),
470            value: Value::Boolean(true),
471        }];
472
473        let rule = Rule::new("CheckEmail".to_string(), conditions, actions);
474        kb.add_rule(rule);
475
476        let mut engine = BackwardEngine::new(kb);
477        let mut facts = Facts::new();
478        facts.set("User.Email", Value::String("user@example.com".to_string()));
479
480        let result = engine.query("User.HasEmail == true", &mut facts);
481        assert!(result.is_ok());
482        let query_result = result.unwrap();
483
484        // Should be provable because User.Email exists
485        assert!(query_result.provable, "Query should be provable with exists test");
486    }
487
488    #[test]
489    fn test_multifield_count_operation() {
490        use crate::engine::rule::{Rule, Condition, ConditionGroup, ConditionExpression};
491        use crate::types::{Operator, ActionType};
492
493        let mut kb = KnowledgeBase::new("test");
494
495        // Rule: If User.Orders count > 5, then User.IsFrequentBuyer = true
496        let condition = Condition {
497            field: "User.Orders".to_string(),  // Required field
498            expression: ConditionExpression::MultiField {
499                field: "User.Orders".to_string(),
500                operation: "count".to_string(),
501                variable: None,
502            },
503            operator: Operator::GreaterThan,
504            value: Value::Number(5.0),
505        };
506        let conditions = ConditionGroup::Single(condition);
507        let actions = vec![ActionType::Set {
508            field: "User.IsFrequentBuyer".to_string(),
509            value: Value::Boolean(true),
510        }];
511
512        let rule = Rule::new("CheckFrequentBuyer".to_string(), conditions, actions);
513        kb.add_rule(rule);
514
515        let mut engine = BackwardEngine::new(kb);
516        let mut facts = Facts::new();
517
518        // Create array of 6 orders
519        let orders = Value::Array(vec![
520            Value::Number(1.0),
521            Value::Number(2.0),
522            Value::Number(3.0),
523            Value::Number(4.0),
524            Value::Number(5.0),
525            Value::Number(6.0),
526        ]);
527        facts.set("User.Orders", orders);
528
529        let result = engine.query("User.IsFrequentBuyer == true", &mut facts);
530        assert!(result.is_ok());
531        let query_result = result.unwrap();
532
533        // Should be provable because orders.count() = 6 > 5
534        assert!(query_result.provable, "Query should be provable with count multifield operation");
535    }
536
537    #[test]
538    fn test_fact_derivation_basic() {
539        use crate::engine::rule::{Rule, Condition, ConditionGroup};
540        use crate::types::{Operator, ActionType};
541
542        let mut kb = KnowledgeBase::new("test");
543
544        // Rule: If User.Age > 18, then User.IsAdult = true
545        let conditions = ConditionGroup::Single(
546            Condition::new(
547                "User.Age".to_string(),
548                Operator::GreaterThan,
549                Value::Number(18.0),
550            )
551        );
552        let actions = vec![ActionType::Set {
553            field: "User.IsAdult".to_string(),
554            value: Value::Boolean(true),
555        }];
556
557        let rule = Rule::new("DetermineAdult".to_string(), conditions, actions);
558        kb.add_rule(rule);
559
560        let mut engine = BackwardEngine::new(kb);
561        let mut facts = Facts::new();
562        facts.set("User.Age", Value::Number(25.0));
563
564        // Query will trigger rule execution which should set User.IsAdult
565        let result = engine.query("User.IsAdult == true", &mut facts);
566        assert!(result.is_ok());
567        let query_result = result.unwrap();
568
569        assert!(query_result.provable, "Fact should be derived by rule action");
570    }
571
572    #[test]
573    fn test_rule_chaining_two_levels() {
574        use crate::engine::rule::{Rule, Condition, ConditionGroup};
575        use crate::types::{Operator, ActionType, LogicalOperator};
576
577        let mut kb = KnowledgeBase::new("test");
578
579        // Rule 1: If User.LoyaltyPoints > 100, then User.IsVIP = true
580        let conditions1 = ConditionGroup::Single(
581            Condition::new(
582                "User.LoyaltyPoints".to_string(),
583                Operator::GreaterThan,
584                Value::Number(100.0),
585            )
586        );
587        let actions1 = vec![ActionType::Set {
588            field: "User.IsVIP".to_string(),
589            value: Value::Boolean(true),
590        }];
591        let rule1 = Rule::new("DetermineVIP".to_string(), conditions1, actions1);
592
593        // Rule 2: If User.IsVIP == true AND Order.Amount < 10000, then Order.AutoApproved = true
594        let conditions2 = ConditionGroup::Compound {
595            left: Box::new(ConditionGroup::Single(
596                Condition::new(
597                    "User.IsVIP".to_string(),
598                    Operator::Equal,
599                    Value::Boolean(true),
600                )
601            )),
602            operator: LogicalOperator::And,
603            right: Box::new(ConditionGroup::Single(
604                Condition::new(
605                    "Order.Amount".to_string(),
606                    Operator::LessThan,
607                    Value::Number(10000.0),
608                )
609            )),
610        };
611        let actions2 = vec![ActionType::Set {
612            field: "Order.AutoApproved".to_string(),
613            value: Value::Boolean(true),
614        }];
615        let rule2 = Rule::new("AutoApproveVIP".to_string(), conditions2, actions2);
616
617        kb.add_rule(rule1);
618        kb.add_rule(rule2);
619
620        let mut engine = BackwardEngine::new(kb);
621        let mut facts = Facts::new();
622        facts.set("User.LoyaltyPoints", Value::Number(150.0));
623        facts.set("Order.Amount", Value::Number(5000.0));
624
625        // Query Order.AutoApproved - should chain through:
626        // 1. Check Order.AutoApproved rule (rule2)
627        // 2. Needs User.IsVIP == true
628        // 3. Check User.IsVIP rule (rule1)
629        // 4. Verify User.LoyaltyPoints > 100 (satisfied)
630        // 5. Execute rule1 action -> sets User.IsVIP = true
631        // 6. Now rule2 conditions satisfied -> sets Order.AutoApproved = true
632        let result = engine.query("Order.AutoApproved == true", &mut facts);
633        assert!(result.is_ok());
634        let query_result = result.unwrap();
635
636        assert!(query_result.provable, "Query should be provable through 2-level rule chaining");
637    }
638
639    #[test]
640    fn test_fact_derivation_with_log_action() {
641        use crate::engine::rule::{Rule, Condition, ConditionGroup};
642        use crate::types::{Operator, ActionType};
643
644        let mut kb = KnowledgeBase::new("test");
645
646        // Rule: If User.Score > 90, log message and set HighScore
647        let conditions = ConditionGroup::Single(
648            Condition::new(
649                "User.Score".to_string(),
650                Operator::GreaterThan,
651                Value::Number(90.0),
652            )
653        );
654        let actions = vec![
655            ActionType::Log {
656                message: "High score achieved!".to_string(),
657            },
658            ActionType::Set {
659                field: "User.HasHighScore".to_string(),
660                value: Value::Boolean(true),
661            }
662        ];
663
664        let rule = Rule::new("HighScoreRule".to_string(), conditions, actions);
665        kb.add_rule(rule);
666
667        let mut engine = BackwardEngine::new(kb);
668        let mut facts = Facts::new();
669        facts.set("User.Score", Value::Number(95.0));
670
671        let result = engine.query("User.HasHighScore == true", &mut facts);
672        assert!(result.is_ok());
673        let query_result = result.unwrap();
674
675        // Should be provable and log action should have been executed
676        assert!(query_result.provable, "Query should be provable with log action");
677    }
678}
rust_rule_engine/backward/backward_engine.rs

rust_rule_engine/backward/
backward_engine.rs
