forgekit_core/cfg/
dominators.rs

1//! Dominator tree — control-flow dominance analysis.
2//!
3//! Extracted from `types.rs` (SPLIT-23). Will be delegated to sqlitegraph
4//! native dominators when magellan v4 lands.
5
6use crate::types::BlockId;
7use std::collections::HashMap;
8
9#[derive(Clone, Debug, PartialEq, Eq)]
10pub struct DominatorTree {
11    pub root: BlockId,
12    pub dominators: HashMap<BlockId, BlockId>,
13}
14
15impl DominatorTree {
16    pub fn new(root: BlockId) -> Self {
17        Self {
18            root,
19            dominators: HashMap::new(),
20        }
21    }
22
23    pub fn immediate_dominator(&self, block: BlockId) -> Option<BlockId> {
24        self.dominators.get(&block).copied()
25    }
26
27    pub fn dominates(&self, dominator: BlockId, block: BlockId) -> bool {
28        if dominator == block {
29            return true;
30        }
31        if dominator == self.root {
32            return true;
33        }
34        let mut current = block;
35        while let Some(idom) = self.dominators.get(&current) {
36            if *idom == dominator {
37                return true;
38            }
39            current = *idom;
40        }
41        false
42    }
43
44    pub fn insert(&mut self, block: BlockId, dominator: BlockId) {
45        self.dominators.insert(block, dominator);
46    }
47
48    pub fn len(&self) -> usize {
49        self.dominators.len() + 1
50    }
51
52    pub fn is_empty(&self) -> bool {
53        self.dominators.is_empty()
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_dominator_tree_creation() {
63        let tree = DominatorTree::new(BlockId(0));
64        assert_eq!(tree.root, BlockId(0));
65        assert!(tree.is_empty());
66        assert_eq!(tree.len(), 1);
67    }
68
69    #[test]
70    fn test_dominator_tree_insert() {
71        let mut tree = DominatorTree::new(BlockId(0));
72        tree.insert(BlockId(1), BlockId(0));
73        tree.insert(BlockId(2), BlockId(1));
74
75        assert_eq!(tree.len(), 3);
76        assert_eq!(tree.immediate_dominator(BlockId(1)), Some(BlockId(0)));
77        assert_eq!(tree.immediate_dominator(BlockId(2)), Some(BlockId(1)));
78        assert_eq!(tree.immediate_dominator(BlockId(0)), None);
79    }
80
81    #[test]
82    fn test_dominator_tree_dominates() {
83        let mut tree = DominatorTree::new(BlockId(0));
84        tree.insert(BlockId(1), BlockId(0));
85        tree.insert(BlockId(2), BlockId(1));
86
87        assert!(tree.dominates(BlockId(0), BlockId(0)));
88        assert!(tree.dominates(BlockId(0), BlockId(1)));
89        assert!(tree.dominates(BlockId(0), BlockId(2)));
90        assert!(tree.dominates(BlockId(1), BlockId(1)));
91        assert!(!tree.dominates(BlockId(1), BlockId(0)));
92    }
93}
forgekit_core/cfg/dominators.rs

forgekit_core/cfg/
dominators.rs
