1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#![allow(unused)]
#![cfg_attr(coverage_nightly, coverage(off))]
//! Big-O Complexity Analyzer - Phase 5 implementation
//!
//! Provides algorithmic complexity analysis for functions using
//! pattern matching and heuristic analysis. This analyzer examines source code
//! to estimate the time and space complexity of functions across multiple
//! programming languages.
//!
//! # Key Features
//!
//! - **Multi-language Support**: Analyzes Rust, JavaScript, TypeScript, Python, Go, Java, C/C++
//! - **Time Complexity Detection**: Identifies O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n)
//! - **Space Complexity Analysis**: Detects dynamic memory allocation patterns
//! - **Pattern Recognition**: Identifies common algorithmic patterns (sorting, searching, recursion)
//! - **Confidence Scoring**: Provides confidence levels for complexity estimates
//!
//! # Example
//!
//! ```no_run
//! use pmat::services::big_o_analyzer::{BigOAnalyzer, BigOAnalysisConfig};
//! use std::path::PathBuf;
//!
//! # async fn example() -> Result<(), Box<dyn std::error::Error>> {
//! let analyzer = BigOAnalyzer::new();
//!
//! let config = BigOAnalysisConfig {
//! project_path: PathBuf::from("./src"),
//! include_patterns: vec!["*.rs".to_string()],
//! exclude_patterns: vec!["test_*.rs".to_string()],
//! confidence_threshold: 70,
//! analyze_space_complexity: true,
//! };
//!
//! let report = analyzer.analyze(config).await?;
//!
//! println!("Analyzed {} functions", report.analyzed_functions);
//! println!("Found {} high-complexity functions", report.high_complexity_functions.len());
//!
//! // Print complexity distribution
//! println!("O(n^2) functions: {}", report.complexity_distribution.quadratic);
//! println!("O(n) functions: {}", report.complexity_distribution.linear);
//!
//! // Get recommendations
//! for recommendation in &report.recommendations {
//! println!(" {}", recommendation);
//! }
//! # Ok(())
//! # }
//! ```
use crate::models::complexity_bound::{BigOClass, ComplexityBound};
#[cfg(test)]
#[path = "big_o_analyzer_issue54_test.rs"]
mod issue54_tests;
use crate::services::complexity_patterns::{ComplexityAnalysisResult, ComplexityPatternMatcher};
use anyhow::Result;
use std::path::PathBuf;
use tracing::info;
/// Big-O complexity analyzer service
pub struct BigOAnalyzer {
pattern_matcher: ComplexityPatternMatcher,
}
/// Analysis configuration
#[derive(Debug, Clone)]
pub struct BigOAnalysisConfig {
pub project_path: PathBuf,
pub include_patterns: Vec<String>,
pub exclude_patterns: Vec<String>,
pub confidence_threshold: u8,
pub analyze_space_complexity: bool,
}
/// Big-O analysis report
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct BigOAnalysisReport {
pub analyzed_functions: usize,
pub complexity_distribution: ComplexityDistribution,
pub high_complexity_functions: Vec<FunctionComplexity>,
pub pattern_matches: Vec<PatternMatch>,
pub recommendations: Vec<String>,
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
/// Complexity distribution.
pub struct ComplexityDistribution {
pub constant: usize,
pub logarithmic: usize,
pub linear: usize,
pub linearithmic: usize,
pub quadratic: usize,
pub cubic: usize,
pub exponential: usize,
pub unknown: usize,
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
/// Function complexity.
pub struct FunctionComplexity {
pub file_path: PathBuf,
pub function_name: String,
pub line_number: usize,
pub time_complexity: ComplexityBound,
pub space_complexity: ComplexityBound,
pub confidence: u8,
pub notes: Vec<String>,
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
/// Pattern match.
pub struct PatternMatch {
pub pattern_name: String,
pub occurrences: usize,
pub typical_complexity: BigOClass,
}
impl BigOAnalyzer {
/// Create new Big-O analyzer
///
/// # Examples
///
/// ```
/// use pmat::services::big_o_analyzer::BigOAnalyzer;
///
/// let analyzer = BigOAnalyzer::new();
/// // Analyzer is ready to analyze code complexity
/// ```
#[must_use]
#[provable_contracts_macros::contract("pmat-core.yaml", equation = "check_compliance")]
pub fn new() -> Self {
Self {
pattern_matcher: ComplexityPatternMatcher::new(),
}
}
}
impl Default for BigOAnalyzer {
fn default() -> Self {
Self::new()
}
}
// Include implementation files
include!("big_o_analyzer_detection.rs");
include!("big_o_analyzer_analysis.rs");
include!("big_o_analyzer_report.rs");
include!("big_o_analyzer_inline_tests.rs");