trueno_graph/algorithms/
pattern.rs

1//! Subgraph pattern matching for anti-pattern detection
2//!
3//! Find specific graph patterns (e.g., code smells, anti-patterns).
4//! Based on subgraph isomorphism and motif detection algorithms.
5//!
6//! # References
7//! - Kim et al. (2023): "Efficient Subgraph Matching on Large Graphs"
8//! - Cordella et al. (2004): "VF2 algorithm for subgraph isomorphism"
9
10use crate::{CsrGraph, NodeId};
11use anyhow::Result;
12use std::collections::{HashMap, HashSet};
13
14/// Pattern matching result
15#[derive(Debug, Clone)]
16pub struct PatternMatch {
17    /// Nodes involved in the pattern (pattern node → graph node mapping)
18    pub node_mapping: HashMap<u32, NodeId>,
19
20    /// Pattern name (e.g., "God Class", "Circular Dependency")
21    pub pattern_name: String,
22
23    /// Severity: Low, Medium, High, Critical
24    pub severity: Severity,
25}
26
27/// Severity level for anti-patterns
28#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
29pub enum Severity {
30    /// Low severity (minor code smell)
31    Low,
32    /// Medium severity (should be refactored)
33    Medium,
34    /// High severity (significant anti-pattern)
35    High,
36    /// Critical severity (architectural flaw)
37    Critical,
38}
39
40/// Pattern specification for matching
41#[derive(Debug, Clone)]
42pub struct Pattern {
43    /// Pattern name
44    pub name: String,
45
46    /// Pattern edges (source, target) - node IDs are local to the pattern
47    pub edges: Vec<(u32, u32)>,
48
49    /// Minimum number of nodes in the pattern
50    pub min_nodes: usize,
51
52    /// Maximum number of nodes (None = unbounded)
53    pub max_nodes: Option<usize>,
54
55    /// Severity if found
56    pub severity: Severity,
57}
58
59impl Pattern {
60    /// Create a new pattern
61    #[must_use]
62    pub fn new(name: String, edges: Vec<(u32, u32)>, severity: Severity) -> Self {
63        let num_nodes =
64            edges.iter().flat_map(|(s, t)| [*s, *t]).max().map_or(0, |max| max as usize + 1);
65
66        Self { name, edges, min_nodes: num_nodes, max_nodes: None, severity }
67    }
68
69    /// Create a "God Class" pattern (node with many outgoing edges)
70    ///
71    /// Detects functions that call too many other functions (high fan-out)
72    #[must_use]
73    pub fn god_class(min_callees: usize) -> Self {
74        Self {
75            name: "God Class".to_string(),
76            edges: Vec::new(), // Filled dynamically based on min_callees
77            min_nodes: min_callees + 1,
78            max_nodes: None,
79            severity: Severity::High,
80        }
81    }
82
83    /// Create a "Circular Dependency" pattern (cycle of length N)
84    ///
85    /// Detects function call cycles
86    #[must_use]
87    #[allow(clippy::cast_possible_truncation)] // Pattern length >4B nodes not realistic
88    pub fn circular_dependency(cycle_length: usize) -> Self {
89        let mut edges = Vec::new();
90        for i in 0..cycle_length {
91            let next = (i + 1) % cycle_length;
92            edges.push((i as u32, next as u32));
93        }
94
95        Self {
96            name: "Circular Dependency".to_string(),
97            edges,
98            min_nodes: cycle_length,
99            max_nodes: Some(cycle_length),
100            severity: Severity::Critical,
101        }
102    }
103
104    /// Create a "Dead Code" pattern (node with no incoming edges)
105    ///
106    /// Detects uncalled functions
107    #[must_use]
108    pub fn dead_code() -> Self {
109        Self {
110            name: "Dead Code".to_string(),
111            edges: Vec::new(),
112            min_nodes: 1,
113            max_nodes: Some(1),
114            severity: Severity::Medium,
115        }
116    }
117}
118
119/// Find all pattern matches in the graph
120///
121/// # Arguments
122///
123/// * `graph` - The graph to search
124/// * `pattern` - The pattern to find
125///
126/// # Returns
127///
128/// Vector of pattern matches
129///
130/// # Errors
131///
132/// Returns error if pattern is malformed
133///
134/// # Example
135///
136/// ```ignore
137/// # use trueno_graph::{CsrGraph, NodeId};
138/// # use trueno_graph::algorithms::pattern::{Pattern, find_patterns, Severity};
139/// let mut graph = CsrGraph::new();
140/// // Create a 3-node cycle: 0 -> 1 -> 2 -> 0
141/// graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
142/// graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
143/// graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
144///
145/// // Find circular dependencies of length 3
146/// let pattern = Pattern::circular_dependency(3);
147/// let matches = find_patterns(&graph, &pattern).unwrap();
148///
149/// assert_eq!(matches.len(), 1);
150/// ```
151pub fn find_patterns(graph: &CsrGraph, pattern: &Pattern) -> Result<Vec<PatternMatch>> {
152    match pattern.name.as_str() {
153        "God Class" => Ok(find_god_class_patterns(graph, pattern)),
154        "Circular Dependency" => Ok(find_cycle_patterns(graph, pattern)),
155        "Dead Code" => Ok(find_dead_code_patterns(graph, pattern)),
156        _ => find_generic_patterns(graph, pattern),
157    }
158}
159
160/// Find "God Class" patterns (high fan-out nodes)
161fn find_god_class_patterns(graph: &CsrGraph, pattern: &Pattern) -> Vec<PatternMatch> {
162    let mut matches = Vec::new();
163
164    for node_id in 0..graph.num_nodes() {
165        #[allow(clippy::cast_possible_truncation)]
166        let node = NodeId(node_id as u32);
167
168        if let Ok(neighbors) = graph.outgoing_neighbors(node) {
169            if neighbors.len() >= pattern.min_nodes - 1 {
170                // High fan-out detected
171                let mut node_mapping = HashMap::new();
172                node_mapping.insert(0, node); // Pattern node 0 = god class
173
174                matches.push(PatternMatch {
175                    node_mapping,
176                    pattern_name: pattern.name.clone(),
177                    severity: pattern.severity,
178                });
179            }
180        }
181    }
182
183    matches
184}
185
186/// Find "Circular Dependency" patterns (cycles)
187fn find_cycle_patterns(graph: &CsrGraph, pattern: &Pattern) -> Vec<PatternMatch> {
188    let cycle_length = pattern.min_nodes;
189    let mut matches = Vec::new();
190    let mut visited_cycles = HashSet::new();
191
192    // DFS to find cycles of specific length
193    for start_node in 0..graph.num_nodes() {
194        #[allow(clippy::cast_possible_truncation)]
195        let start = NodeId(start_node as u32);
196
197        let cycles = find_cycles_from_node(graph, start, cycle_length);
198
199        for cycle in cycles {
200            // Normalize cycle to avoid duplicates (start from smallest node)
201            let mut normalized = cycle.clone();
202            normalized.sort_unstable();
203
204            if visited_cycles.insert(normalized) {
205                // Create node mapping
206                let mut node_mapping = HashMap::new();
207                for (pattern_id, &graph_node) in cycle.iter().enumerate() {
208                    #[allow(clippy::cast_possible_truncation)]
209                    node_mapping.insert(pattern_id as u32, graph_node);
210                }
211
212                matches.push(PatternMatch {
213                    node_mapping,
214                    pattern_name: pattern.name.clone(),
215                    severity: pattern.severity,
216                });
217            }
218        }
219    }
220
221    matches
222}
223
224/// Find "Dead Code" patterns (nodes with no incoming edges)
225fn find_dead_code_patterns(graph: &CsrGraph, pattern: &Pattern) -> Vec<PatternMatch> {
226    let mut matches = Vec::new();
227
228    for node_id in 0..graph.num_nodes() {
229        #[allow(clippy::cast_possible_truncation)]
230        let node = NodeId(node_id as u32);
231
232        if let Ok(incoming) = graph.incoming_neighbors(node) {
233            if incoming.is_empty() {
234                // No callers = dead code
235                let mut node_mapping = HashMap::new();
236                node_mapping.insert(0, node);
237
238                matches.push(PatternMatch {
239                    node_mapping,
240                    pattern_name: pattern.name.clone(),
241                    severity: pattern.severity,
242                });
243            }
244        }
245    }
246
247    matches
248}
249
250/// Find generic patterns using simplified subgraph matching
251///
252/// Uses backtracking to find all subgraph isomorphisms. Suitable for small patterns
253/// (typical in code smell detection). For larger patterns, consider specialized algorithms.
254#[allow(clippy::unnecessary_wraps, clippy::cast_possible_truncation)]
255fn find_generic_patterns(graph: &CsrGraph, pattern: &Pattern) -> Result<Vec<PatternMatch>> {
256    let mut matches = Vec::new();
257
258    // Build pattern adjacency for quick lookup
259    let mut pattern_adj: HashMap<u32, HashSet<u32>> = HashMap::new();
260    for (src, dst) in &pattern.edges {
261        pattern_adj.entry(*src).or_default().insert(*dst);
262    }
263
264    // Try matching pattern starting from each node
265    for start_node in 0..graph.num_nodes() {
266        let mut mapping: HashMap<u32, NodeId> = HashMap::new();
267        let mut used_nodes: HashSet<NodeId> = HashSet::new();
268
269        if try_match_pattern(
270            graph,
271            &pattern_adj,
272            pattern.min_nodes,
273            0,
274            NodeId(start_node as u32),
275            &mut mapping,
276            &mut used_nodes,
277        ) {
278            // Found a match
279            matches.push(PatternMatch {
280                node_mapping: mapping.clone(),
281                pattern_name: pattern.name.clone(),
282                severity: pattern.severity,
283            });
284        }
285    }
286
287    Ok(matches)
288}
289
290/// Verify that all mapped edges in the pattern exist in the graph
291fn edges_consistent(
292    graph: &CsrGraph,
293    pattern_adj: &HashMap<u32, HashSet<u32>>,
294    mapping: &HashMap<u32, NodeId>,
295) -> bool {
296    for (&p_src, &g_src) in mapping {
297        let Some(p_targets) = pattern_adj.get(&p_src) else {
298            continue;
299        };
300        let g_targets: HashSet<u32> =
301            graph.outgoing_neighbors(g_src).unwrap_or_default().iter().copied().collect();
302        for &p_target in p_targets {
303            if let Some(&g_target) = mapping.get(&p_target) {
304                if !g_targets.contains(&g_target.0) {
305                    return false;
306                }
307            }
308        }
309    }
310    true
311}
312
313/// Remove a node from the mapping and used set (backtrack step)
314fn backtrack(
315    pattern_node: u32,
316    graph_node: NodeId,
317    mapping: &mut HashMap<u32, NodeId>,
318    used_nodes: &mut HashSet<NodeId>,
319) {
320    mapping.remove(&pattern_node);
321    used_nodes.remove(&graph_node);
322}
323
324/// Recursive helper for pattern matching (backtracking)
325#[allow(clippy::cast_possible_truncation)]
326fn try_match_pattern(
327    graph: &CsrGraph,
328    pattern_adj: &HashMap<u32, HashSet<u32>>,
329    pattern_size: usize,
330    pattern_node: u32,
331    graph_node: NodeId,
332    mapping: &mut HashMap<u32, NodeId>,
333    used_nodes: &mut HashSet<NodeId>,
334) -> bool {
335    if used_nodes.contains(&graph_node) {
336        return false;
337    }
338
339    mapping.insert(pattern_node, graph_node);
340    used_nodes.insert(graph_node);
341
342    if mapping.len() == pattern_size {
343        return true;
344    }
345
346    if !edges_consistent(graph, pattern_adj, mapping) {
347        backtrack(pattern_node, graph_node, mapping, used_nodes);
348        return false;
349    }
350
351    // Try extending mapping to unmapped pattern nodes
352    for next_pattern_node in 0..pattern_size as u32 {
353        if mapping.contains_key(&next_pattern_node) {
354            continue;
355        }
356        let found = (0..graph.num_nodes()).any(|next_graph_node| {
357            try_match_pattern(
358                graph,
359                pattern_adj,
360                pattern_size,
361                next_pattern_node,
362                NodeId(next_graph_node as u32),
363                mapping,
364                used_nodes,
365            )
366        });
367        if !found {
368            backtrack(pattern_node, graph_node, mapping, used_nodes);
369        }
370        return found;
371    }
372
373    backtrack(pattern_node, graph_node, mapping, used_nodes);
374    false
375}
376
377/// Helper: Find cycles of specific length starting from a node
378fn find_cycles_from_node(
379    graph: &CsrGraph,
380    start: NodeId,
381    target_length: usize,
382) -> Vec<Vec<NodeId>> {
383    let mut cycles = Vec::new();
384    let mut path = vec![start];
385    let mut visited = HashSet::new();
386    visited.insert(start.0);
387
388    dfs_find_cycles(graph, start, start, &mut path, &mut visited, target_length, &mut cycles);
389
390    cycles
391}
392
393/// DFS helper for cycle detection
394#[allow(clippy::too_many_arguments)]
395fn dfs_find_cycles(
396    graph: &CsrGraph,
397    current: NodeId,
398    start: NodeId,
399    path: &mut Vec<NodeId>,
400    visited: &mut HashSet<u32>,
401    target_length: usize,
402    cycles: &mut Vec<Vec<NodeId>>,
403) {
404    if path.len() == target_length {
405        // Check if current node connects back to start
406        if let Ok(neighbors) = graph.outgoing_neighbors(current) {
407            if neighbors.contains(&start.0) {
408                cycles.push(path.clone());
409            }
410        }
411        return;
412    }
413
414    // Explore neighbors
415    if let Ok(neighbors) = graph.outgoing_neighbors(current) {
416        for &neighbor_id in neighbors {
417            let neighbor = NodeId(neighbor_id);
418
419            if !visited.contains(&neighbor_id)
420                || (neighbor == start && path.len() == target_length - 1)
421            {
422                visited.insert(neighbor_id);
423                path.push(neighbor);
424
425                dfs_find_cycles(graph, neighbor, start, path, visited, target_length, cycles);
426
427                path.pop();
428                visited.remove(&neighbor_id);
429            }
430        }
431    }
432}
433
434#[cfg(test)]
435mod tests {
436    use super::*;
437
438    #[test]
439    fn test_god_class_pattern() {
440        // Node 0 calls 5 other functions (high fan-out)
441        let mut graph = CsrGraph::new();
442        for i in 1..=5 {
443            graph.add_edge(NodeId(0), NodeId(i), 1.0).unwrap();
444        }
445
446        let pattern = Pattern::god_class(5);
447        let matches = find_patterns(&graph, &pattern).unwrap();
448
449        assert_eq!(matches.len(), 1);
450        assert_eq!(matches[0].pattern_name, "God Class");
451        assert_eq!(matches[0].severity, Severity::High);
452    }
453
454    #[test]
455    fn test_circular_dependency_pattern() {
456        // Create 3-node cycle: 0 -> 1 -> 2 -> 0
457        let mut graph = CsrGraph::new();
458        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
459        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
460        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
461
462        let pattern = Pattern::circular_dependency(3);
463        let matches = find_patterns(&graph, &pattern).unwrap();
464
465        assert_eq!(matches.len(), 1);
466        assert_eq!(matches[0].pattern_name, "Circular Dependency");
467        assert_eq!(matches[0].severity, Severity::Critical);
468    }
469
470    #[test]
471    fn test_dead_code_pattern() {
472        // Node 0 -> Node 1, but Node 2 has no incoming edges
473        let mut graph = CsrGraph::new();
474        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
475        graph.add_edge(NodeId(2), NodeId(1), 1.0).unwrap(); // Node 2 exists but not called
476
477        // Manually expand graph to include node 3 with no callers
478        graph.add_edge(NodeId(3), NodeId(4), 1.0).unwrap();
479
480        let pattern = Pattern::dead_code();
481        let matches = find_patterns(&graph, &pattern).unwrap();
482
483        // Nodes with no incoming edges (except if they're source nodes in edge list)
484        assert!(!matches.is_empty());
485    }
486
487    #[test]
488    fn test_pattern_new() {
489        let edges = vec![(0, 1), (1, 2)];
490        let pattern = Pattern::new("Test Pattern".to_string(), edges, Severity::Medium);
491
492        assert_eq!(pattern.name, "Test Pattern");
493        assert_eq!(pattern.min_nodes, 3); // Nodes 0, 1, 2
494        assert_eq!(pattern.severity, Severity::Medium);
495    }
496
497    #[test]
498    fn test_no_circular_dependency() {
499        // Linear graph: 0 -> 1 -> 2 (no cycle)
500        let mut graph = CsrGraph::new();
501        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
502        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
503
504        let pattern = Pattern::circular_dependency(3);
505        let matches = find_patterns(&graph, &pattern).unwrap();
506
507        assert_eq!(matches.len(), 0); // No cycles found
508    }
509
510    #[test]
511    fn test_severity_ordering() {
512        assert!(Severity::Low < Severity::Medium);
513        assert!(Severity::Medium < Severity::High);
514        assert!(Severity::High < Severity::Critical);
515    }
516
517    #[test]
518    fn test_generic_pattern_triangle() {
519        // Create a triangle pattern: 0 -> 1, 1 -> 2, 2 -> 0
520        let pattern =
521            Pattern::new("Triangle".to_string(), vec![(0, 1), (1, 2), (2, 0)], Severity::Low);
522
523        // Graph with triangle
524        let mut graph = CsrGraph::new();
525        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
526        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
527        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
528
529        let matches = find_patterns(&graph, &pattern).unwrap();
530        assert!(!matches.is_empty());
531    }
532
533    #[test]
534    fn test_generic_pattern_line() {
535        // Create a line pattern: 0 -> 1 -> 2
536        let pattern = Pattern::new("Line".to_string(), vec![(0, 1), (1, 2)], Severity::Low);
537
538        // Graph with matching line
539        let mut graph = CsrGraph::new();
540        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
541        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
542
543        let matches = find_patterns(&graph, &pattern).unwrap();
544        assert!(!matches.is_empty());
545    }
546
547    #[test]
548    fn test_generic_pattern_no_match() {
549        // Create a pattern that won't match
550        let pattern = Pattern::new("V-shape".to_string(), vec![(0, 1), (0, 2)], Severity::Low);
551
552        // Graph with different structure (linear)
553        let mut graph = CsrGraph::new();
554        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
555
556        let matches = find_patterns(&graph, &pattern).unwrap();
557        assert_eq!(matches.len(), 0);
558    }
559
560    #[test]
561    fn test_pattern_with_max_nodes() {
562        let mut pattern = Pattern::circular_dependency(3);
563        pattern.max_nodes = Some(3);
564
565        let mut graph = CsrGraph::new();
566        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
567        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
568        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
569
570        let matches = find_patterns(&graph, &pattern).unwrap();
571        assert_eq!(matches.len(), 1);
572    }
573
574    #[test]
575    fn test_multiple_god_classes() {
576        // Two nodes with high fan-out
577        let mut graph = CsrGraph::new();
578        // Node 0 calls 5 functions
579        for i in 1..=5 {
580            graph.add_edge(NodeId(0), NodeId(i), 1.0).unwrap();
581        }
582        // Node 6 calls 5 functions
583        for i in 7..=11 {
584            graph.add_edge(NodeId(6), NodeId(i), 1.0).unwrap();
585        }
586
587        let pattern = Pattern::god_class(5);
588        let matches = find_patterns(&graph, &pattern).unwrap();
589
590        assert_eq!(matches.len(), 2);
591    }
592
593    #[test]
594    fn test_multiple_cycles() {
595        // Create two separate 3-node cycles
596        let mut graph = CsrGraph::new();
597        // Cycle 1: 0 -> 1 -> 2 -> 0
598        graph.add_edge(NodeId(0), NodeId(1), 1.0).unwrap();
599        graph.add_edge(NodeId(1), NodeId(2), 1.0).unwrap();
600        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
601        // Cycle 2: 3 -> 4 -> 5 -> 3
602        graph.add_edge(NodeId(3), NodeId(4), 1.0).unwrap();
603        graph.add_edge(NodeId(4), NodeId(5), 1.0).unwrap();
604        graph.add_edge(NodeId(5), NodeId(3), 1.0).unwrap();
605
606        let pattern = Pattern::circular_dependency(3);
607        let matches = find_patterns(&graph, &pattern).unwrap();
608
609        assert_eq!(matches.len(), 2);
610    }
611
612    #[test]
613    fn test_dead_code_with_callers() {
614        // Node 0 has callers, node 1 has no callers
615        let mut graph = CsrGraph::new();
616        graph.add_edge(NodeId(2), NodeId(0), 1.0).unwrap();
617        graph.add_edge(NodeId(1), NodeId(3), 1.0).unwrap();
618
619        let pattern = Pattern::dead_code();
620        let matches = find_patterns(&graph, &pattern).unwrap();
621
622        // Should find nodes 1 and 2 (no incoming edges)
623        assert!(matches.len() >= 2);
624    }
625}
trueno_graph/algorithms/pattern.rs

trueno_graph/algorithms/
pattern.rs
