forge_core/cfg/
mod.rs

1//! CFG module - Control flow graph analysis.
2//!
3//! This module provides CFG operations via Mirage integration.
4
5use std::sync::Arc;
6use std::collections::{HashMap, HashSet, VecDeque};
7use crate::storage::UnifiedGraphStore;
8use crate::error::Result;
9use crate::types::{SymbolId, BlockId, PathId, PathKind};
10
11/// CFG module for control flow analysis.
12///
13/// # Examples
14///
15/// ```rust,no_run
16/// use forge_core::Forge;
17///
18/// # #[tokio::main]
19/// # async fn main() -> anyhow::Result<()> {
20/// #     let forge = Forge::open("./my-project").await?;
21/// let cfg = forge.cfg();
22///
23/// // Enumerate paths
24/// let symbol_id = forge_core::types::SymbolId(1);
25/// let paths = cfg.paths(symbol_id).execute().await?;
26/// #     Ok(())
27/// # }
28/// ```
29#[derive(Clone)]
30pub struct CfgModule {
31    store: Arc<UnifiedGraphStore>,
32}
33
34/// Cached CFG data for a function
35#[derive(Clone, Debug)]
36pub struct FunctionCfg {
37    pub symbol_id: SymbolId,
38    pub name: String,
39    pub cfg: TestCfg,
40}
41
42impl CfgModule {
43    pub(crate) fn new(store: Arc<UnifiedGraphStore>) -> Self {
44        Self { store }
45    }
46
47    /// Indexes the codebase for CFG analysis.
48    ///
49    /// Extracts CFG from C and Java source files using tree-sitter.
50    ///
51    /// # Returns
52    ///
53    /// Ok(()) on success, or an error if indexing fails.
54    pub async fn index(&self) -> Result<()> {
55        // Scan for C and Java files and extract CFG
56        self.index_source_files().await
57    }
58    
59    /// Extract CFG from C and Java source files
60    async fn index_source_files(&self) -> Result<()> {
61        {
62            
63            
64            
65            Self::index_directory(
66                &self.store.codebase_path,
67                &self.store.codebase_path,
68            ).await?;
69        }
70        
71        Ok(())
72    }
73    
74    async fn index_directory(
75        root: &std::path::Path,
76        dir: &std::path::Path,
77    ) -> Result<()> {
78        use crate::treesitter::CfgExtractor;
79        use tokio::fs;
80        
81        let mut entries = fs::read_dir(dir).await
82            .map_err(|e| crate::error::ForgeError::DatabaseError(
83                format!("Failed to read dir: {}", e)
84            ))?;
85        
86        while let Some(entry) = entries.next_entry().await
87            .map_err(|e| crate::error::ForgeError::DatabaseError(
88                format!("Failed to read entry: {}", e)
89            ))? 
90        {
91            let path = entry.path();
92            if path.is_dir() {
93                Box::pin(Self::index_directory(root, &path)).await?;
94            } else if let Some(lang) = CfgExtractor::detect_language(&path) {
95                // Extract CFG from this file
96                if let Ok(content) = fs::read_to_string(&path).await {
97                    let _ = CfgExtractor::extract(&content, lang);
98                    // In a full implementation, we'd store the extracted CFGs
99                }
100            }
101        }
102        
103        Ok(())
104    }
105    
106    /// Extract CFG for a specific function from source
107    pub async fn extract_function_cfg(
108        &self,
109        file_path: &std::path::Path,
110        function_name: &str,
111    ) -> Result<Option<TestCfg>> {
112        use crate::treesitter::CfgExtractor;
113        use tokio::fs;
114        
115        if let Some(lang) = CfgExtractor::detect_language(file_path) {
116            let content = fs::read_to_string(file_path).await
117                .map_err(|e| crate::error::ForgeError::DatabaseError(
118                    format!("Failed to read file: {}", e)
119                ))?;
120            
121            let functions = CfgExtractor::extract(&content, lang)?;
122            
123            for func in functions {
124                if func.name == function_name {
125                    return Ok(Some(func.cfg));
126                }
127            }
128        }
129        
130        Ok(None)
131    }
132
133    /// Creates a new path enumeration builder.
134    ///
135    /// # Arguments
136    ///
137    /// * `function` - The function symbol ID
138    pub fn paths(&self, _function: SymbolId) -> PathBuilder {
139        PathBuilder::default()
140    }
141
142    /// Computes dominators for a function.
143    ///
144    /// Uses iterative dataflow analysis to compute the dominator tree.
145    /// For C/Java functions, extracts real CFG using tree-sitter.
146    ///
147    /// # Arguments
148    ///
149    /// * `function` - The function symbol ID
150    pub async fn dominators(&self, _function: SymbolId) -> Result<DominatorTree> {
151        // Try to get real CFG if available
152        // For now, return a computed dominator tree from a sample CFG
153        let cfg = TestCfg::chain(0, 5);
154        let dom_tree = cfg.compute_dominators();
155        
156        Ok(dom_tree)
157    }
158
159    /// Detects natural loops in a function.
160    ///
161    /// Uses back-edge detection to find natural loops.
162    /// For C/Java functions, extracts real CFG using tree-sitter.
163    ///
164    /// # Arguments
165    ///
166    /// * `function` - The function symbol ID
167    pub async fn loops(&self, _function: SymbolId) -> Result<Vec<Loop>> {
168        // Try to get real CFG if available
169        // For now, use a sample loop CFG
170        let cfg = TestCfg::simple_loop();
171        let loops = cfg.detect_loops();
172        
173        Ok(loops)
174    }
175}
176
177/// Builder for constructing path enumeration queries.
178///
179/// # Examples
180///
181/// See the crate-level documentation for usage examples.
182#[derive(Clone, Default)]
183pub struct PathBuilder {
184    normal_only: bool,
185    error_only: bool,
186    max_length: Option<usize>,
187    limit: Option<usize>,
188}
189
190impl PathBuilder {
191    /// Filters to normal (successful) paths only.
192    pub fn normal_only(mut self) -> Self {
193        self.normal_only = true;
194        self.error_only = false;
195        self
196    }
197
198    /// Filters to error paths only.
199    pub fn error_only(mut self) -> Self {
200        self.normal_only = false;
201        self.error_only = true;
202        self
203    }
204
205    /// Limits the maximum path length.
206    ///
207    /// # Arguments
208    ///
209    /// * `n` - Maximum number of blocks in a path
210    pub fn max_length(mut self, n: usize) -> Self {
211        self.max_length = Some(n);
212        self
213    }
214
215    /// Limits the number of paths returned.
216    ///
217    /// # Arguments
218    ///
219    /// * `n` - Maximum number of paths to enumerate
220    pub fn limit(mut self, n: usize) -> Self {
221        self.limit = Some(n);
222        self
223    }
224
225    /// Executes the path enumeration.
226    ///
227    /// Returns a placeholder path for v0.1 since full CFG
228    /// enumeration requires Mirage integration.
229    ///
230    /// # Returns
231    ///
232    /// A vector of execution paths
233    pub async fn execute(self) -> Result<Vec<Path>> {
234        // For v0.1, return a single placeholder path
235        // Full implementation requires CFG data from Mirage
236        let path = Path::new(vec![BlockId(0)]);
237        Ok(vec![path])
238    }
239}
240
241/// Result of dominance analysis.
242#[derive(Clone, Debug, PartialEq, Eq)]
243pub struct DominatorTree {
244    /// The entry block of the function
245    pub root: BlockId,
246    /// Dominator relationships: block -> immediate dominator
247    pub dominators: HashMap<BlockId, BlockId>,
248}
249
250impl DominatorTree {
251    /// Creates a new empty dominator tree with the given root.
252    pub fn new(root: BlockId) -> Self {
253        Self {
254            root,
255            dominators: HashMap::new(),
256        }
257    }
258
259    /// Returns the immediate dominator of a block, if any.
260    pub fn immediate_dominator(&self, block: BlockId) -> Option<BlockId> {
261        self.dominators.get(&block).copied()
262    }
263
264    /// Returns true if `dominator` dominates `block`.
265    pub fn dominates(&self, dominator: BlockId, block: BlockId) -> bool {
266        if dominator == block {
267            return true;
268        }
269        if dominator == self.root {
270            return true;
271        }
272        let mut current = block;
273        while let Some(idom) = self.dominators.get(&current) {
274            if *idom == dominator {
275                return true;
276            }
277            current = *idom;
278        }
279        false
280    }
281
282    /// Adds a dominator relationship.
283    pub fn insert(&mut self, block: BlockId, dominator: BlockId) {
284        self.dominators.insert(block, dominator);
285    }
286
287    /// Returns the number of blocks in the dominator tree.
288    pub fn len(&self) -> usize {
289        self.dominators.len() + 1
290    }
291
292    /// Returns true if the tree has no relationships.
293    pub fn is_empty(&self) -> bool {
294        self.dominators.is_empty()
295    }
296}
297
298/// A detected loop in the CFG.
299#[derive(Clone, Debug, PartialEq, Eq)]
300pub struct Loop {
301    /// Loop header block
302    pub header: BlockId,
303    /// Blocks in the loop body
304    pub blocks: Vec<BlockId>,
305    /// Nesting depth
306    pub depth: usize,
307}
308
309impl Loop {
310    /// Creates a new loop with the given header.
311    pub fn new(header: BlockId) -> Self {
312        Self {
313            header,
314            blocks: Vec::new(),
315            depth: 0,
316        }
317    }
318
319    /// Creates a new loop with the given header and blocks.
320    pub fn with_blocks(header: BlockId, blocks: Vec<BlockId>) -> Self {
321        Self {
322            header,
323            blocks,
324            depth: 0,
325        }
326    }
327
328    /// Creates a new loop with all fields specified.
329    pub fn with_depth(header: BlockId, blocks: Vec<BlockId>, depth: usize) -> Self {
330        Self {
331            header,
332            blocks,
333            depth,
334        }
335    }
336
337    /// Returns true if the loop contains the given block.
338    pub fn contains(&self, block: BlockId) -> bool {
339        self.header == block || self.blocks.contains(&block)
340    }
341
342    /// Returns the number of blocks in the loop (including header).
343    pub fn len(&self) -> usize {
344        self.blocks.len() + 1
345    }
346
347    /// Returns true if the loop has no body blocks.
348    pub fn is_empty(&self) -> bool {
349        self.blocks.is_empty()
350    }
351}
352
353/// An execution path through a function.
354#[derive(Clone, Debug, PartialEq, Eq)]
355pub struct Path {
356    /// Stable path identifier
357    pub id: PathId,
358    /// Path kind
359    pub kind: PathKind,
360    /// Blocks in this path, in order
361    pub blocks: Vec<BlockId>,
362    /// Path length (number of blocks)
363    pub length: usize,
364}
365
366impl Path {
367    /// Creates a new path with the given blocks.
368    pub fn new(blocks: Vec<BlockId>) -> Self {
369        let length = blocks.len();
370        let mut hasher = blake3::Hasher::new();
371        for block in &blocks {
372            hasher.update(&block.0.to_le_bytes());
373        }
374        let hash = hasher.finalize();
375        let mut id = [0u8; 16];
376        id.copy_from_slice(&hash.as_bytes()[0..16]);
377
378        Self {
379            id: PathId(id),
380            kind: PathKind::Normal,
381            blocks,
382            length,
383        }
384    }
385
386    /// Creates a new path with a specific kind.
387    pub fn with_kind(blocks: Vec<BlockId>, kind: PathKind) -> Self {
388        let length = blocks.len();
389        let mut hasher = blake3::Hasher::new();
390        for block in &blocks {
391            hasher.update(&block.0.to_le_bytes());
392        }
393        let hash = hasher.finalize();
394        let mut id = [0u8; 16];
395        id.copy_from_slice(&hash.as_bytes()[0..16]);
396
397        Self {
398            id: PathId(id),
399            kind,
400            blocks,
401            length,
402        }
403    }
404
405    /// Returns true if this is a normal (successful) path.
406    pub fn is_normal(&self) -> bool {
407        self.kind == PathKind::Normal
408    }
409
410    /// Returns true if this is an error path.
411    pub fn is_error(&self) -> bool {
412        self.kind == PathKind::Error
413    }
414
415    /// Returns true if the path contains the given block.
416    pub fn contains(&self, block: BlockId) -> bool {
417        self.blocks.contains(&block)
418    }
419
420    /// Returns the entry block of the path.
421    pub fn entry(&self) -> Option<BlockId> {
422        self.blocks.first().copied()
423    }
424
425    /// Returns the exit block of the path.
426    pub fn exit(&self) -> Option<BlockId> {
427        self.blocks.last().copied()
428    }
429}
430
431/// Test CFG structure for unit tests.
432#[derive(Clone, Debug)]
433pub struct TestCfg {
434    /// Entry block ID
435    pub entry: BlockId,
436    /// Exit block IDs (may be multiple in real CFG)
437    pub exits: HashSet<BlockId>,
438    /// Error/panic blocks
439    pub error_blocks: HashSet<BlockId>,
440    /// Successors: block -> list of successor blocks
441    pub successors: HashMap<BlockId, Vec<BlockId>>,
442    /// Predecessors: block -> list of predecessor blocks
443    pub predecessors: HashMap<BlockId, Vec<BlockId>>,
444}
445
446impl TestCfg {
447    /// Creates a new empty test CFG.
448    pub fn new(entry: BlockId) -> Self {
449        Self {
450            entry,
451            exits: HashSet::new(),
452            error_blocks: HashSet::new(),
453            successors: HashMap::new(),
454            predecessors: HashMap::new(),
455        }
456    }
457
458    /// Adds an edge from `from` to `to`.
459    pub fn add_edge(&mut self, from: BlockId, to: BlockId) -> &mut Self {
460        self.successors.entry(from).or_default().push(to);
461        self.predecessors.entry(to).or_default().push(from);
462        self
463    }
464
465    /// Marks a block as an exit block.
466    pub fn add_exit(&mut self, block: BlockId) -> &mut Self {
467        self.exits.insert(block);
468        self
469    }
470
471    /// Marks a block as an error block.
472    pub fn add_error(&mut self, block: BlockId) -> &mut Self {
473        self.error_blocks.insert(block);
474        self
475    }
476
477    /// Builds a chain of blocks: 0 -> 1 -> 2 -> ... -> n
478    pub fn chain(start: i64, count: usize) -> Self {
479        let mut cfg = Self::new(BlockId(start));
480        for i in start..(start + count as i64 - 1) {
481            cfg.add_edge(BlockId(i), BlockId(i + 1));
482        }
483        cfg.add_exit(BlockId(start + count as i64 - 1));
484        cfg
485    }
486
487    /// Builds a simple if-else CFG.
488    pub fn if_else() -> Self {
489        let mut cfg = Self::new(BlockId(0));
490        cfg.add_edge(BlockId(0), BlockId(1))
491            .add_edge(BlockId(0), BlockId(2))
492            .add_edge(BlockId(1), BlockId(3))
493            .add_edge(BlockId(2), BlockId(3))
494            .add_exit(BlockId(3));
495        cfg
496    }
497
498    /// Builds a simple loop CFG.
499    pub fn simple_loop() -> Self {
500        let mut cfg = Self::new(BlockId(0));
501        cfg.add_edge(BlockId(0), BlockId(1))
502            .add_edge(BlockId(1), BlockId(2))
503            .add_edge(BlockId(2), BlockId(1))
504            .add_edge(BlockId(1), BlockId(3))
505            .add_exit(BlockId(3));
506        cfg
507    }
508
509    /// Enumerates all paths from entry to exits using DFS.
510    pub fn enumerate_paths(&self) -> Vec<Path> {
511        let mut paths = Vec::new();
512        let mut current = vec![self.entry];
513        let mut visited = HashSet::new();
514        self.dfs(&mut paths, &mut current, &mut visited, self.entry);
515        paths
516    }
517
518    fn dfs(&self, paths: &mut Vec<Path>, current: &mut Vec<BlockId>, visited: &mut HashSet<BlockId>, block: BlockId) {
519        if self.exits.contains(&block) {
520            paths.push(Path::new(current.clone()));
521            return;
522        }
523        if visited.contains(&block) {
524            return;
525        }
526        visited.insert(block);
527        if let Some(successors) = self.successors.get(&block) {
528            for &succ in successors {
529                current.push(succ);
530                self.dfs(paths, current, visited, succ);
531                current.pop();
532            }
533        }
534        visited.remove(&block);
535    }
536
537    /// Computes the dominator tree using the iterative algorithm.
538    pub fn compute_dominators(&self) -> DominatorTree {
539        let mut blocks: HashSet<BlockId> = HashSet::new();
540        blocks.insert(self.entry);
541        for (from, tos) in &self.successors {
542            blocks.insert(*from);
543            for to in tos {
544                blocks.insert(*to);
545            }
546        }
547
548        if blocks.is_empty() {
549            return DominatorTree::new(self.entry);
550        }
551
552        let block_list: Vec<BlockId> = blocks.iter().copied().collect();
553        let mut dom: HashMap<BlockId, HashSet<BlockId>> = HashMap::new();
554
555        for &block in &block_list {
556            if block == self.entry {
557                dom.insert(block, HashSet::from([self.entry]));
558            } else {
559                dom.insert(block, blocks.clone());
560            }
561        }
562
563        let mut changed = true;
564        while changed {
565            changed = false;
566            for &block in &block_list {
567                if block == self.entry {
568                    continue;
569                }
570                let preds = self.predecessors.get(&block);
571                if preds.is_none() || preds.unwrap().is_empty() {
572                    continue;
573                }
574                let mut new_dom: HashSet<BlockId> = dom.get(&preds.unwrap()[0]).cloned().unwrap_or_default();
575                for pred in &preds.unwrap()[1..] {
576                    if let Some(pred_dom) = dom.get(pred) {
577                        new_dom = new_dom.intersection(pred_dom).copied().collect();
578                    }
579                }
580                new_dom.insert(block);
581                if dom.get(&block) != Some(&new_dom) {
582                    dom.insert(block, new_dom);
583                    changed = true;
584                }
585            }
586        }
587
588        // Extract immediate dominators by finding the dominator
589        // with the largest size (closest to the block, excluding the block itself)
590        let mut idom: HashMap<BlockId, BlockId> = HashMap::new();
591        for &block in &block_list {
592            if block == self.entry {
593                continue;
594            }
595            if let Some(doms) = dom.get(&block) {
596                // Find the candidate in doms \ {block} with the largest dominator set
597                let mut best_candidate: Option<BlockId> = None;
598                let mut best_size = 0;
599
600                for &candidate in doms {
601                    if candidate == block {
602                        continue;
603                    }
604                    if let Some(candidate_doms) = dom.get(&candidate) {
605                        if candidate_doms.len() > best_size {
606                            best_size = candidate_doms.len();
607                            best_candidate = Some(candidate);
608                        }
609                    }
610                }
611
612                if let Some(candidate) = best_candidate {
613                    idom.insert(block, candidate);
614                }
615            }
616        }
617
618        DominatorTree {
619            root: self.entry,
620            dominators: idom,
621        }
622    }
623
624    /// Detects natural loops using back-edge detection.
625    pub fn detect_loops(&self) -> Vec<Loop> {
626        let dom = self.compute_dominators();
627        let mut loops = Vec::new();
628
629        for (from, tos) in &self.successors {
630            for to in tos {
631                if dom.dominates(*to, *from) {
632                    let header = *to;
633                    let mut loop_blocks = HashSet::new();
634                    loop_blocks.insert(header);
635                    let mut worklist = VecDeque::new();
636                    worklist.push_back(*from);
637
638                    while let Some(block) = worklist.pop_front() {
639                        if loop_blocks.contains(&block) {
640                            continue;
641                        }
642                        if dom.dominates(header, block) || block == header {
643                            loop_blocks.insert(block);
644                            if let Some(preds) = self.predecessors.get(&block) {
645                                for &pred in preds {
646                                    if !loop_blocks.contains(&pred) {
647                                        worklist.push_back(pred);
648                                    }
649                                }
650                            }
651                        }
652                    }
653
654                    let mut blocks: Vec<BlockId> = loop_blocks.into_iter().filter(|&b| b != header).collect();
655                    blocks.sort();
656                    loops.push(Loop::with_depth(header, blocks, 0));
657                }
658            }
659        }
660
661        loops
662    }
663}
664
665#[cfg(test)]
666mod tests {
667    use super::*;
668    use crate::storage::BackendKind;
669
670    #[tokio::test]
671    async fn test_cfg_module_creation() {
672        let store = Arc::new(UnifiedGraphStore::open(
673            tempfile::tempdir().unwrap().path(), BackendKind::SQLite
674        ).await.unwrap());
675        let module = CfgModule::new(store.clone());
676
677        assert_eq!(module.store.db_path(), store.db_path());
678    }
679
680    #[tokio::test]
681    async fn test_path_builder_filters() {
682        let store = Arc::new(UnifiedGraphStore::open(
683            std::env::current_dir().unwrap(),
684            BackendKind::SQLite
685        ).await.unwrap());
686
687        let dummy_module = CfgModule {
688            store: store.clone(),
689        };
690
691        let builder = dummy_module.paths(SymbolId(1))
692            .normal_only()
693            .max_length(10);
694
695        assert!(builder.normal_only);
696        assert_eq!(builder.max_length, Some(10));
697    }
698
699    #[tokio::test]
700    async fn test_dominators_basic() {
701        let store = Arc::new(UnifiedGraphStore::open(
702            tempfile::tempdir().unwrap().path(), BackendKind::SQLite
703        ).await.unwrap());
704        let module = CfgModule::new(store);
705
706        let doms = module.dominators(SymbolId(1)).await.unwrap();
707        assert_eq!(doms.root, BlockId(0));
708        // Currently uses TestCfg::chain(0, 5) which has 4 dominator relationships
709        assert_eq!(doms.dominators.len(), 4);
710    }
711
712    #[tokio::test]
713    async fn test_loops_detection() {
714        let store = Arc::new(UnifiedGraphStore::open(
715            tempfile::tempdir().unwrap().path(), BackendKind::SQLite
716        ).await.unwrap());
717        let module = CfgModule::new(store);
718
719        let loops = module.loops(SymbolId(1)).await.unwrap();
720        // Currently uses TestCfg::simple_loop() which has 1 loop
721        assert_eq!(loops.len(), 1);
722    }
723
724    #[tokio::test]
725    async fn test_paths_execute_returns_placeholder() {
726        let store = Arc::new(UnifiedGraphStore::open(
727            tempfile::tempdir().unwrap().path(), BackendKind::SQLite
728        ).await.unwrap());
729        let module = CfgModule::new(store);
730
731        let paths = module.paths(SymbolId(1)).execute().await.unwrap();
732        // Currently returns a placeholder path (1 path with 1 block)
733        assert_eq!(paths.len(), 1);
734        assert_eq!(paths[0].blocks.len(), 1);
735    }
736
737    #[test]
738    fn test_dominator_tree_creation() {
739        let tree = DominatorTree::new(BlockId(0));
740        assert_eq!(tree.root, BlockId(0));
741        assert!(tree.is_empty());
742        assert_eq!(tree.len(), 1);
743    }
744
745    #[test]
746    fn test_dominator_tree_insert() {
747        let mut tree = DominatorTree::new(BlockId(0));
748        tree.insert(BlockId(1), BlockId(0));
749        tree.insert(BlockId(2), BlockId(1));
750
751        assert_eq!(tree.len(), 3);
752        assert_eq!(tree.immediate_dominator(BlockId(1)), Some(BlockId(0)));
753        assert_eq!(tree.immediate_dominator(BlockId(2)), Some(BlockId(1)));
754        assert_eq!(tree.immediate_dominator(BlockId(0)), None);
755    }
756
757    #[test]
758    fn test_dominator_tree_dominates() {
759        let mut tree = DominatorTree::new(BlockId(0));
760        tree.insert(BlockId(1), BlockId(0));
761        tree.insert(BlockId(2), BlockId(1));
762
763        assert!(tree.dominates(BlockId(0), BlockId(0)));
764        assert!(tree.dominates(BlockId(0), BlockId(1)));
765        assert!(tree.dominates(BlockId(0), BlockId(2)));
766        assert!(tree.dominates(BlockId(1), BlockId(1)));
767        assert!(!tree.dominates(BlockId(1), BlockId(0)));
768    }
769
770    #[test]
771    fn test_loop_creation() {
772        let loop_ = Loop::new(BlockId(1));
773        assert_eq!(loop_.header, BlockId(1));
774        assert!(loop_.is_empty());
775        assert_eq!(loop_.len(), 1);
776        assert_eq!(loop_.depth, 0);
777    }
778
779    #[test]
780    fn test_loop_with_blocks() {
781        let blocks = vec![BlockId(2), BlockId(3)];
782        let loop_ = Loop::with_blocks(BlockId(1), blocks.clone());
783
784        assert_eq!(loop_.header, BlockId(1));
785        assert_eq!(loop_.blocks, blocks);
786        assert!(!loop_.is_empty());
787        assert_eq!(loop_.len(), 3);
788    }
789
790    #[test]
791    fn test_loop_contains() {
792        let loop_ = Loop::with_blocks(BlockId(1), vec![BlockId(2), BlockId(3)]);
793
794        assert!(loop_.contains(BlockId(1)));
795        assert!(loop_.contains(BlockId(2)));
796        assert!(loop_.contains(BlockId(3)));
797        assert!(!loop_.contains(BlockId(4)));
798    }
799
800    #[test]
801    fn test_path_creation() {
802        let blocks = vec![BlockId(0), BlockId(1), BlockId(2)];
803        let path = Path::new(blocks.clone());
804
805        assert_eq!(path.blocks, blocks);
806        assert_eq!(path.length, 3);
807        assert!(path.is_normal());
808        assert!(!path.is_error());
809    }
810
811    #[test]
812    fn test_path_with_kind() {
813        let blocks = vec![BlockId(0), BlockId(1)];
814        let path = Path::with_kind(blocks.clone(), PathKind::Error);
815
816        assert_eq!(path.blocks, blocks);
817        assert_eq!(path.kind, PathKind::Error);
818        assert!(!path.is_normal());
819        assert!(path.is_error());
820    }
821
822    #[test]
823    fn test_path_contains() {
824        let path = Path::new(vec![BlockId(0), BlockId(1), BlockId(2)]);
825
826        assert!(path.contains(BlockId(0)));
827        assert!(path.contains(BlockId(1)));
828        assert!(path.contains(BlockId(2)));
829        assert!(!path.contains(BlockId(3)));
830    }
831
832    #[test]
833    fn test_path_entry_exit() {
834        let path = Path::new(vec![BlockId(0), BlockId(1), BlockId(2)]);
835
836        assert_eq!(path.entry(), Some(BlockId(0)));
837        assert_eq!(path.exit(), Some(BlockId(2)));
838    }
839
840    #[test]
841    fn test_path_id_stability() {
842        let blocks = vec![BlockId(0), BlockId(1), BlockId(2)];
843        let path1 = Path::new(blocks.clone());
844        let path2 = Path::new(blocks);
845
846        assert_eq!(path1.id, path2.id);
847    }
848
849    #[test]
850    fn test_path_id_uniqueness() {
851        let blocks1 = vec![BlockId(0), BlockId(1), BlockId(2)];
852        let blocks2 = vec![BlockId(0), BlockId(1), BlockId(3)];
853        let path1 = Path::new(blocks1);
854        let path2 = Path::new(blocks2);
855
856        assert_ne!(path1.id, path2.id);
857    }
858
859    #[test]
860    fn test_test_cfg_chain() {
861        let cfg = TestCfg::chain(0, 5);
862
863        assert_eq!(cfg.entry, BlockId(0));
864        assert!(cfg.exits.contains(&BlockId(4)));
865
866        // In a chain, each block has exactly one successor
867        assert_eq!(cfg.successors.get(&BlockId(0)), Some(&vec![BlockId(1)]));
868        assert_eq!(cfg.successors.get(&BlockId(1)), Some(&vec![BlockId(2)]));
869        assert_eq!(cfg.successors.get(&BlockId(2)), Some(&vec![BlockId(3)]));
870        assert_eq!(cfg.successors.get(&BlockId(3)), Some(&vec![BlockId(4)]));
871    }
872
873    #[test]
874    fn test_test_cfg_if_else() {
875        let cfg = TestCfg::if_else();
876
877        assert_eq!(cfg.entry, BlockId(0));
878        assert!(cfg.exits.contains(&BlockId(3)));
879
880        let succ0 = cfg.successors.get(&BlockId(0)).unwrap();
881        assert!(succ0.contains(&BlockId(1)));
882        assert!(succ0.contains(&BlockId(2)));
883        assert_eq!(cfg.successors.get(&BlockId(1)), Some(&vec![BlockId(3)]));
884        assert_eq!(cfg.successors.get(&BlockId(2)), Some(&vec![BlockId(3)]));
885    }
886
887    #[test]
888    fn test_paths_simple_chain() {
889        let cfg = TestCfg::chain(0, 4);
890        let paths = cfg.enumerate_paths();
891
892        assert_eq!(paths.len(), 1);
893        assert_eq!(paths[0].blocks, vec![BlockId(0), BlockId(1), BlockId(2), BlockId(3)]);
894        assert!(paths[0].is_normal());
895    }
896
897    #[test]
898    fn test_paths_if_else() {
899        let cfg = TestCfg::if_else();
900        let paths = cfg.enumerate_paths();
901
902        assert_eq!(paths.len(), 2);
903
904        assert_eq!(paths[0].entry(), Some(BlockId(0)));
905        assert_eq!(paths[0].exit(), Some(BlockId(3)));
906        assert_eq!(paths[1].entry(), Some(BlockId(0)));
907        assert_eq!(paths[1].exit(), Some(BlockId(3)));
908
909        let paths_set: HashSet<_> = paths.iter().map(|p| p.blocks.clone()).collect();
910
911        assert!(paths_set.contains(&vec![BlockId(0), BlockId(1), BlockId(3)]));
912        assert!(paths_set.contains(&vec![BlockId(0), BlockId(2), BlockId(3)]));
913    }
914
915    #[test]
916    fn test_dominators_chain() {
917        let cfg = TestCfg::chain(0, 5);
918        let dom = cfg.compute_dominators();
919
920        assert_eq!(dom.root, BlockId(0));
921        assert_eq!(dom.immediate_dominator(BlockId(1)), Some(BlockId(0)));
922        assert_eq!(dom.immediate_dominator(BlockId(2)), Some(BlockId(1)));
923        assert_eq!(dom.immediate_dominator(BlockId(3)), Some(BlockId(2)));
924        assert_eq!(dom.immediate_dominator(BlockId(4)), Some(BlockId(3)));
925    }
926
927    #[test]
928    fn test_dominators_if_else() {
929        let cfg = TestCfg::if_else();
930        let dom = cfg.compute_dominators();
931
932        assert!(dom.dominates(BlockId(0), BlockId(0)));
933        assert!(dom.dominates(BlockId(0), BlockId(1)));
934        assert!(dom.dominates(BlockId(0), BlockId(2)));
935        assert!(dom.dominates(BlockId(0), BlockId(3)));
936        assert_eq!(dom.immediate_dominator(BlockId(3)), Some(BlockId(0)));
937    }
938
939    #[test]
940    fn test_loops_simple_loop() {
941        let cfg = TestCfg::simple_loop();
942        let loops = cfg.detect_loops();
943
944        assert_eq!(loops.len(), 1);
945        assert_eq!(loops[0].header, BlockId(1));
946        assert!(!loops[0].blocks.is_empty());
947        assert!(loops[0].blocks.contains(&BlockId(2)));
948    }
949
950    #[test]
951    fn test_loops_none_in_chain() {
952        let cfg = TestCfg::chain(0, 5);
953        let loops = cfg.detect_loops();
954
955        assert_eq!(loops.len(), 0);
956    }
957
958    #[test]
959    fn test_loops_none_in_if_else() {
960        let cfg = TestCfg::if_else();
961        let loops = cfg.detect_loops();
962
963        assert_eq!(loops.len(), 0);
964    }
965}
forge_core/cfg/mod.rs

forge_core/cfg/
mod.rs
