petgraph/algo/
dominators.rs

1//! Compute dominators of a control-flow graph.
2//!
3//! # The Dominance Relation
4//!
5//! In a directed graph with a root node **R**, a node **A** is said to *dominate* a
6//! node **B** iff every path from **R** to **B** contains **A**.
7//!
8//! The node **A** is said to *strictly dominate* the node **B** iff **A** dominates
9//! **B** and **A ≠ B**.
10//!
11//! The node **A** is said to be the *immediate dominator* of a node **B** iff it
12//! strictly dominates **B** and there does not exist any node **C** where **A**
13//! dominates **C** and **C** dominates **B**.
14
15use std::collections::{HashMap, HashSet};
16use std::hash::Hash;
17
18use visit::{DfsPostOrder, GraphBase, IntoNeighbors, Visitable, Walker};
19
20/// The dominance relation for some graph and root.
21#[derive(Debug, Clone)]
22pub struct Dominators<N>
23    where N: Copy + Eq + Hash
24{
25    root: N,
26    dominators: HashMap<N, N>,
27}
28
29impl<N> Dominators<N>
30    where N: Copy + Eq + Hash
31{
32    /// Get the root node used to construct these dominance relations.
33    pub fn root(&self) -> N {
34        self.root
35    }
36
37    /// Get the immediate dominator of the given node.
38    ///
39    /// Returns `None` for any node that is not reachable from the root, and for
40    /// the root itself.
41    pub fn immediate_dominator(&self, node: N) -> Option<N> {
42        if node == self.root {
43            None
44        } else {
45            self.dominators.get(&node).cloned()
46        }
47    }
48
49    /// Iterate over the given node's that strict dominators.
50    ///
51    /// If the given node is not reachable from the root, then `None` is
52    /// returned.
53    pub fn strict_dominators(&self, node: N) -> Option<DominatorsIter<N>> {
54        if self.dominators.contains_key(&node) {
55            Some(DominatorsIter {
56                dominators: self,
57                node: self.immediate_dominator(node),
58            })
59        } else {
60            None
61        }
62    }
63
64    /// Iterate over all of the given node's dominators (including the given
65    /// node itself).
66    ///
67    /// If the given node is not reachable from the root, then `None` is
68    /// returned.
69    pub fn dominators(&self, node: N) -> Option<DominatorsIter<N>> {
70        if self.dominators.contains_key(&node) {
71            Some(DominatorsIter {
72                dominators: self,
73                node: Some(node),
74            })
75        } else {
76            None
77        }
78    }
79}
80
81/// Iterator for a node's dominators.
82pub struct DominatorsIter<'a, N>
83    where N: 'a + Copy + Eq + Hash
84{
85    dominators: &'a Dominators<N>,
86    node: Option<N>,
87}
88
89impl<'a, N> Iterator for DominatorsIter<'a, N>
90    where N: 'a + Copy + Eq + Hash
91{
92    type Item = N;
93
94    fn next(&mut self) -> Option<Self::Item> {
95        let next = self.node.take();
96        if let Some(next) = next {
97            self.node = self.dominators.immediate_dominator(next);
98        }
99        next
100    }
101}
102
103/// The undefined dominator sentinel, for when we have not yet discovered a
104/// node's dominator.
105const UNDEFINED: usize = ::std::usize::MAX;
106
107/// This is an implementation of the engineered ["Simple, Fast Dominance
108/// Algorithm"][0] discovered by Cooper et al.
109///
110/// This algorithm is **O(|V|²)**, and therefore has slower theoretical running time
111/// than the Lenguaer-Tarjan algorithm (which is **O(|E| log |V|)**. However,
112/// Cooper et al found it to be faster in practice on control flow graphs of up
113/// to ~30,000 vertices.
114///
115/// [0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf
116pub fn simple_fast<G>(graph: G, root: G::NodeId) -> Dominators<G::NodeId>
117    where G: IntoNeighbors + Visitable,
118          <G as GraphBase>::NodeId: Eq + Hash
119{
120    let (post_order, predecessor_sets) = simple_fast_post_order(graph, root);
121    let length = post_order.len();
122    debug_assert!(length > 0);
123    debug_assert!(post_order.last() == Some(&root));
124
125    // From here on out we use indices into `post_order` instead of actual
126    // `NodeId`s wherever possible. This greatly improves the performance of
127    // this implementation, but we have to pay a little bit of upfront cost to
128    // convert our data structures to play along first.
129
130    // Maps a node to its index into `post_order`.
131    let node_to_post_order_idx: HashMap<_, _> = post_order.iter()
132        .enumerate()
133        .map(|(idx, &node)| (node, idx))
134        .collect();
135
136    // Maps a node's `post_order` index to its set of predecessors's indices
137    // into `post_order` (as a vec).
138    let idx_to_predecessor_vec =
139        predecessor_sets_to_idx_vecs(&post_order, &node_to_post_order_idx, predecessor_sets);
140
141    let mut dominators = vec![UNDEFINED; length];
142    dominators[length - 1] = length - 1;
143
144    let mut changed = true;
145    while changed {
146        changed = false;
147
148        // Iterate in reverse post order, skipping the root.
149
150        for idx in (0..length - 1).rev() {
151            debug_assert!(post_order[idx] != root);
152
153            // Take the intersection of every predecessor's dominator set; that
154            // is the current best guess at the immediate dominator for this
155            // node.
156
157            let new_idom_idx = {
158                let mut predecessors =
159                    idx_to_predecessor_vec[idx].iter().filter(|&&p| dominators[p] != UNDEFINED);
160                let new_idom_idx = predecessors.next()
161                    .expect("Because the root is initialized to dominate itself, and is the \
162                             first node in every path, there must exist a predecessor to this \
163                             node that also has a dominator");
164                predecessors.fold(*new_idom_idx, |new_idom_idx, &predecessor_idx| {
165                    intersect(&dominators, new_idom_idx, predecessor_idx)
166                })
167            };
168
169            debug_assert!(new_idom_idx < length);
170
171            if new_idom_idx != dominators[idx] {
172                dominators[idx] = new_idom_idx;
173                changed = true;
174            }
175        }
176    }
177
178    // All done! Translate the indices back into proper `G::NodeId`s.
179
180    debug_assert!(!dominators.iter().any(|&dom| dom == UNDEFINED));
181
182    Dominators {
183        root: root,
184        dominators: dominators.into_iter()
185            .enumerate()
186            .map(|(idx, dom_idx)| (post_order[idx], post_order[dom_idx]))
187            .collect(),
188    }
189}
190
191fn intersect(dominators: &[usize], mut finger1: usize, mut finger2: usize) -> usize {
192    while finger1 != finger2 {
193        if finger1 < finger2 {
194            finger1 = dominators[finger1];
195        } else if finger2 < finger1 {
196            finger2 = dominators[finger2];
197        }
198    }
199    finger1
200}
201
202fn predecessor_sets_to_idx_vecs<N>(post_order: &[N],
203                                   node_to_post_order_idx: &HashMap<N, usize>,
204                                   mut predecessor_sets: HashMap<N, HashSet<N>>)
205                                   -> Vec<Vec<usize>>
206    where N: Copy + Eq + Hash
207{
208    post_order.iter()
209        .map(|node| {
210            predecessor_sets.remove(node)
211                .map(|predecessors| {
212                    predecessors.into_iter()
213                        .map(|p| *node_to_post_order_idx.get(&p).unwrap())
214                        .collect()
215                })
216                .unwrap_or_else(Vec::new)
217        })
218        .collect()
219}
220
221fn simple_fast_post_order<G>(graph: G,
222                             root: G::NodeId)
223                             -> (Vec<G::NodeId>, HashMap<G::NodeId, HashSet<G::NodeId>>)
224    where G: IntoNeighbors + Visitable,
225          <G as GraphBase>::NodeId: Eq + Hash
226{
227    let mut post_order = vec![];
228    let mut predecessor_sets = HashMap::new();
229
230    for node in DfsPostOrder::new(graph, root).iter(graph) {
231        post_order.push(node);
232
233        for successor in graph.neighbors(node) {
234            predecessor_sets.entry(successor)
235                .or_insert_with(HashSet::new)
236                .insert(node);
237        }
238    }
239
240    (post_order, predecessor_sets)
241}
242
243#[cfg(test)]
244mod tests {
245    use super::*;
246
247    #[test]
248    fn test_iter_dominators() {
249        let doms: Dominators<u32> = Dominators {
250            root: 0,
251            dominators: [(2, 1), (1, 0), (0, 0)]
252                .iter()
253                .cloned()
254                .collect(),
255        };
256
257        let all_doms: Vec<_> = doms.dominators(2).unwrap().collect();
258        assert_eq!(vec![2, 1, 0], all_doms);
259
260        assert_eq!(None::<()>, doms.dominators(99).map(|_| unreachable!()));
261
262        let strict_doms: Vec<_> = doms.strict_dominators(2).unwrap().collect();
263        assert_eq!(vec![1, 0], strict_doms);
264
265        assert_eq!(None::<()>, doms.strict_dominators(99).map(|_| unreachable!()));
266    }
267}
petgraph/algo/dominators.rs

petgraph/algo/
dominators.rs
