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

forge_core/cfg/
mod.rs
