mathhook_core/calculus/integrals/
strategy.rs

1//! Integration strategy dispatcher
2//!
3//! Orchestrates all integration techniques in optimal order (fast to slow).
4//!
5//! # Strategy Layers
6//!
7//! 1. **Table lookup** - O(1) exact pattern matching for common integrals
8//! 2. **Rational functions** - Partial fraction decomposition for P(x)/Q(x)
9//! 3. **Function registry** - Known antiderivatives (sin, cos, exp, ln, etc.)
10//! 4. **Integration by parts** - Product rule in reverse using LIATE heuristic
11//! 5. **Substitution** - Chain rule in reverse (u-substitution)
12//! 6. **Trigonometric** - Trig identities and power reduction formulas
13//! 7. **Risch algorithm** - Decision procedure for elementary functions
14//! 8. **Basic rules** - Power rule, constants, sums, constant multiples
15//! 9. **Symbolic fallback** - Return unevaluated integral expression
16//!
17//! # Strategy Tracking
18//!
19//! To prevent infinite recursion, we track which strategies are currently active
20//! in the call stack. A strategy cannot recursively call itself.
21//!
22//! # Recursion Depth Limit
23//!
24//! Maximum integration depth is 10 to prevent infinite recursion in pathological cases.
25use crate::calculus::integrals::{
26    basic::BasicIntegrals, by_parts::IntegrationByParts, function_integrals::FunctionIntegrals,
27    rational, risch, substitution, table, trigonometric,
28};
29use crate::core::{Expression, Number, Symbol};
30use std::collections::HashSet;
31/// Maximum integration recursion depth
32///
33/// This prevents infinite recursion in cases where integration strategies
34/// recursively call each other without terminating.
35const MAX_DEPTH: usize = 10;
36/// Integration strategy identifier
37///
38/// Each integration technique is assigned a unique identifier to track
39/// which strategies are currently active in the call stack.
40#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
41pub enum IntegrationStrategy {
42    TableLookup,
43    RationalFunction,
44    FunctionRegistry,
45    IntegrationByParts,
46    Substitution,
47    Trigonometric,
48    Risch,
49    BasicRules,
50}
51/// Strategy execution context
52///
53/// Tracks which integration strategies are currently active to prevent
54/// infinite recursion and improve strategy selection.
55#[derive(Debug, Clone)]
56pub struct StrategyContext {
57    active_strategies: HashSet<IntegrationStrategy>,
58    depth: usize,
59}
60impl StrategyContext {
61    /// Create a new strategy context with no active strategies
62    pub fn new() -> Self {
63        Self {
64            active_strategies: HashSet::new(),
65            depth: 0,
66        }
67    }
68    /// Check if a strategy is currently active (would cause recursion)
69    pub fn is_active(&self, strategy: IntegrationStrategy) -> bool {
70        self.active_strategies.contains(&strategy)
71    }
72    /// Execute a strategy, marking it as active during execution
73    pub fn with_strategy<F>(&self, strategy: IntegrationStrategy, f: F) -> Option<Expression>
74    where
75        F: FnOnce(&Self) -> Option<Expression>,
76    {
77        if self.is_active(strategy) {
78            return None;
79        }
80        let mut child_context = self.clone();
81        child_context.active_strategies.insert(strategy);
82        child_context.depth += 1;
83        f(&child_context)
84    }
85    /// Get current recursion depth
86    pub fn depth(&self) -> usize {
87        self.depth
88    }
89}
90impl Default for StrategyContext {
91    fn default() -> Self {
92        Self::new()
93    }
94}
95/// Main integration strategy dispatcher
96///
97/// Tries strategies in order from fast to slow, returning first success.
98///
99/// # Recursion Depth Limit
100///
101/// Returns symbolic integral if depth >= MAX_DEPTH (10) to prevent infinite recursion.
102pub fn integrate_with_strategy(expr: &Expression, var: Symbol, depth: usize) -> Expression {
103    if depth >= MAX_DEPTH {
104        return Expression::integral(expr.clone(), var);
105    }
106    let context = StrategyContext {
107        active_strategies: HashSet::new(),
108        depth,
109    };
110    integrate_with_context(expr, var, &context)
111}
112/// Integration with explicit strategy context
113///
114/// Used by recursive calls to track which strategies are currently active.
115fn integrate_with_context(expr: &Expression, var: Symbol, ctx: &StrategyContext) -> Expression {
116    if let Some(result) = try_table_lookup_with_context(expr, &var, ctx) {
117        return result;
118    }
119    if is_rational_function(expr, &var) {
120        if let Some(result) = try_rational_function(expr, &var) {
121            return result;
122        }
123    }
124    if let Some(result) = try_registry_integration_with_context(expr, &var, ctx) {
125        return result;
126    }
127    if let Some(result) = ctx.with_strategy(IntegrationStrategy::IntegrationByParts, |child_ctx| {
128        try_by_parts_with_context(expr, &var, child_ctx, child_ctx.depth())
129    }) {
130        return result;
131    }
132    if let Some(result) = ctx.with_strategy(IntegrationStrategy::Substitution, |child_ctx| {
133        try_substitution_with_context(expr, &var, child_ctx)
134    }) {
135        return result;
136    }
137    if let Some(result) = ctx.with_strategy(IntegrationStrategy::Trigonometric, |child_ctx| {
138        try_trigonometric_with_context(expr, &var, child_ctx)
139    }) {
140        return result;
141    }
142    if let Some(result) = ctx.with_strategy(IntegrationStrategy::Risch, |child_ctx| {
143        try_risch_with_context(expr, &var, child_ctx)
144    }) {
145        return result;
146    }
147    if let Some(result) = try_basic_rules_with_context(expr, &var, ctx) {
148        return result;
149    }
150    Expression::integral(expr.clone(), var)
151}
152/// Table lookup with strategy context
153fn try_table_lookup_with_context(
154    expr: &Expression,
155    var: &Symbol,
156    _context: &StrategyContext,
157) -> Option<Expression> {
158    table::try_table_lookup(expr, var)
159}
160/// Rational function integration with strategy context
161fn try_rational_function(expr: &Expression, var: &Symbol) -> Option<Expression> {
162    rational::integrate_rational(expr, var)
163}
164/// Try function registry integration using known antiderivatives
165///
166/// Uses the function intelligence registry for elementary functions.
167pub fn try_registry_integration(expr: &Expression, var: &Symbol) -> Option<Expression> {
168    match expr {
169        Expression::Function { name, args } => {
170            let result = FunctionIntegrals::integrate(name, args, var.clone());
171            if is_symbolic_integral(&result) {
172                None
173            } else {
174                Some(result)
175            }
176        }
177        _ => None,
178    }
179}
180/// Function registry integration with strategy context
181fn try_registry_integration_with_context(
182    expr: &Expression,
183    var: &Symbol,
184    _context: &StrategyContext,
185) -> Option<Expression> {
186    try_registry_integration(expr, var)
187}
188/// Try integration by parts using the LIATE heuristic
189///
190/// Applies the product rule in reverse for expressions like x*exp(x).
191pub fn try_by_parts(expr: &Expression, var: &Symbol, depth: usize) -> Option<Expression> {
192    IntegrationByParts::integrate(expr, var.clone(), depth)
193}
194/// Integration by parts with strategy context
195///
196/// This prevents recursive application of integration by parts.
197fn try_by_parts_with_context(
198    expr: &Expression,
199    var: &Symbol,
200    context: &StrategyContext,
201    depth: usize,
202) -> Option<Expression> {
203    IntegrationByParts::integrate_with_context(expr, var.clone(), context, depth)
204}
205/// U-substitution with strategy context
206fn try_substitution_with_context(
207    expr: &Expression,
208    var: &Symbol,
209    context: &StrategyContext,
210) -> Option<Expression> {
211    substitution::try_substitution(expr, var, context.depth())
212}
213/// Trigonometric integration with strategy context
214fn try_trigonometric_with_context(
215    expr: &Expression,
216    var: &Symbol,
217    _context: &StrategyContext,
218) -> Option<Expression> {
219    trigonometric::try_trigonometric_integration(expr, var)
220}
221/// Risch algorithm with strategy context
222fn try_risch_with_context(
223    expr: &Expression,
224    var: &Symbol,
225    _context: &StrategyContext,
226) -> Option<Expression> {
227    risch::try_risch_integration(expr, var)
228}
229/// Check if expression is a polynomial in the given variable
230///
231/// Polynomial: only var, constants, +, *, and non-negative integer powers.
232pub fn is_polynomial(expr: &Expression, _var: &Symbol) -> bool {
233    match expr {
234        Expression::Number(_) | Expression::Constant(_) => true,
235        Expression::Symbol(_sym) => true,
236        Expression::Add(terms) => terms.iter().all(|t| is_polynomial(t, _var)),
237        Expression::Mul(factors) => factors.iter().all(|f| is_polynomial(f, _var)),
238        Expression::Pow(base, exp) => {
239            if !is_polynomial(base, _var) {
240                return false;
241            }
242            matches!(exp.as_ref(), Expression::Number(Number::Integer(n)) if * n >= 0)
243        }
244        _ => false,
245    }
246}
247/// Check if expression is a rational function P(x)/Q(x)
248///
249/// Rational: ratio of two polynomials
250fn is_rational_function(expr: &Expression, var: &Symbol) -> bool {
251    let result = match expr {
252        _ if is_polynomial(expr, var) => true,
253        Expression::Pow(base, exp) => {
254            if let Expression::Number(Number::Integer(_)) = exp.as_ref() {
255                let poly_check = is_polynomial(base.as_ref(), var);
256                poly_check
257            } else {
258                false
259            }
260        }
261        Expression::Mul(factors) => {
262            for factor in factors.iter() {
263                if let Expression::Pow(base, exp) = factor {
264                    if let Expression::Number(Number::Integer(n)) = exp.as_ref() {
265                        if *n < 0 && !is_polynomial(base.as_ref(), var) {
266                            return false;
267                        }
268                    } else {
269                        return false;
270                    }
271                }
272            }
273            factors.iter().all(|f| match f {
274                Expression::Pow(base, _) => is_polynomial(base.as_ref(), var),
275                _ => is_polynomial(f, var),
276            })
277        }
278        _ => false,
279    };
280    result
281}
282/// Basic integration rules with strategy context
283///
284/// CRITICAL: Calls helper functions that recursively call integrate_with_strategy.
285/// Depth limit at entry point prevents infinite recursion.
286fn try_basic_rules_with_context(
287    expr: &Expression,
288    var: &Symbol,
289    context: &StrategyContext,
290) -> Option<Expression> {
291    match expr {
292        Expression::Number(_) => Some(BasicIntegrals::handle_constant(expr, var.clone())),
293        Expression::Symbol(sym) => Some(BasicIntegrals::handle_symbol(sym, var)),
294        Expression::Add(terms) => Some(BasicIntegrals::handle_sum(terms, var, context.depth())),
295        Expression::Mul(factors) => Some(BasicIntegrals::handle_product(
296            factors,
297            var.clone(),
298            context.depth(),
299        )),
300        Expression::Pow(base, exp) => Some(BasicIntegrals::handle_power(base, exp, var.clone())),
301        Expression::Calculus(data) => {
302            Some(BasicIntegrals::handle_calculus(expr, data, var.clone()))
303        }
304        _ => None,
305    }
306}
307/// Check if result is a symbolic integral (unevaluated)
308fn is_symbolic_integral(expr: &Expression) -> bool {
309    matches!(expr, Expression::Calculus(_))
310}
311#[cfg(test)]
312mod tests {
313    use super::*;
314    use crate::symbol;
315    #[test]
316    fn test_is_polynomial_constant() {
317        let x = symbol!(x);
318        assert!(is_polynomial(&Expression::integer(5), &x));
319    }
320    #[test]
321    fn test_is_polynomial_variable() {
322        let x = symbol!(x);
323        assert!(is_polynomial(&Expression::symbol(x.clone()), &x));
324    }
325    #[test]
326    fn test_is_polynomial_sum() {
327        let x = symbol!(x);
328        let poly = Expression::add(vec![
329            Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
330            Expression::symbol(x.clone()),
331            Expression::integer(1),
332        ]);
333        assert!(is_polynomial(&poly, &x));
334    }
335    #[test]
336    fn test_is_polynomial_product() {
337        let x = symbol!(x);
338        let poly = Expression::mul(vec![
339            Expression::integer(3),
340            Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
341        ]);
342        assert!(is_polynomial(&poly, &x));
343    }
344    #[test]
345    fn test_is_not_polynomial_negative_power() {
346        let x = symbol!(x);
347        let expr = Expression::pow(Expression::symbol(x.clone()), Expression::integer(-1));
348        assert!(!is_polynomial(&expr, &x));
349    }
350    #[test]
351    fn test_is_not_polynomial_function() {
352        let x = symbol!(x);
353        let expr = Expression::function("sin", vec![Expression::symbol(x.clone())]);
354        assert!(!is_polynomial(&expr, &x));
355    }
356}
mathhook_core/calculus/integrals/strategy.rs

mathhook_core/calculus/integrals/
strategy.rs
