domtree/lib.rs
1#![cfg_attr(feature = "materialized_idf", feature(associated_type_bounds))]
2//! `domtree` provides a generic implementation to calculate the dominator tree of
3//! a directed graph. The algorithm basically follows the description in
4//! "A Simple, Fast Dominance Algorithm" by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.
5//!
6//! To implement the trait for your own graph structure, you need to prepare several fields:
7//! ```ignore
8//! #[derive(Clone)]
9//! struct VecSet<Y>(Vec<Y>);
10//!
11//! impl<Y: Clone + Default> AssocSet<usize, Y> for VecSet<Y> {
12//! fn get(&self, target: usize) -> Y {
13//! self.0[target].clone()
14//! }
15//!
16//! fn set(&mut self, key: usize, val: Y) {
17//! self.0[key] = val;
18//! }
19//! }
20//!
21//! #[derive(Clone, Debug)]
22//! impl<T: PartialEq + Eq + Hash + Clone> MemberSet<T> for HashMemberSet<T> {
23//! fn contains(&self, target: T) -> bool {
24//! self.0.contains(&target)
25//! }
26//!
27//! fn insert(&mut self, target: T) {
28//! self.0.insert(target);
29//! }
30//!
31//! type MemberIter<'a> = Cloned<std::collections::hash_set::Iter<'a, T>> where Self : 'a;
32//!
33//! fn iter<'a>(&'a self) -> Self::MemberIter<'a> {
34//! self.0.iter().cloned()
35//! }
36//! }
37//!
38//! #[derive(Debug)]
39//! struct Node {
40//! tag: usize, // node's identifier
41//! dom: Option<usize>, // node's immediate dominator
42//! frontiers: UnsafeCell<HashMemberSet<usize>>, // node's dominance frontiers
43//! incoming_edges: Vec<usize>, // node's in-edges
44//! outgoing_edges: Vec<usize> // node's out-edges
45//! }
46//!
47//! #[derive(Debug)]
48//! struct Graph {
49//! nodes: Vec<Node>,
50//! }
51//! ```
52//! Then, one needs to first expose some APIs such that this crate can run DFS on the graph.
53//! ```ignore
54//! use std::iter::Cloned;
55//! use std::slice::Iter;
56//! use domtree::dfs::DFSGraph;
57//! impl DFSGraph for Graph {
58//! type Identifier = usize;
59//! type Set<Y> = VecSet<Y> where Y: Clone + Default;
60//! type SuccessorIter<'a> = Cloned<Iter<'a, usize>> where Self: 'a;
61//!
62//! fn create_set<Y>(&self) -> Self::Set<Y> where Y: Clone + Default {
63//! let mut data = Vec::new();
64//! data.resize(self.nodes.len(), Default::default());
65//! VecSet(data)
66//! }
67//!
68//! fn outgoing_edges<'a>(&'a self, id: Self::Identifier) -> Self::SuccessorIter<'a> {
69//! self.nodes[id].outgoing_edges.iter().cloned()
70//! }
71//! }
72//! ```
73//! After this, one also need to specify how the algorithm can access the fields related to the
74//! dominance tree.
75//! ```ignore
76//! impl DomTree for Graph {
77//! type MutDomIter<'a> = Map<IterMut<'a, Node>, fn(&'a mut Node)->&'a mut Option<usize>> where Self: 'a;
78//! type PredecessorIter<'a> = Cloned<Iter<'a, usize>> where Self: 'a;
79//!
80//! fn dom(&self, id: Self::Identifier) -> Option<Self::Identifier> {
81//! self.nodes[id].dom.clone()
82//! }
83//!
84//! fn set_dom(&mut self, id: Self::Identifier, target: Option<Self::Identifier>) {
85//! self.nodes[id].dom = target;
86//! }
87//!
88//! fn predecessor_iter<'a>(&'a self, id: Self::Identifier) -> Self::PredecessorIter<'a> {
89//! self.nodes[id].incoming_edges.iter().cloned()
90//! }
91//!
92//! fn doms_mut<'a>(&'a mut self) -> Self::MutDomIter<'a> {
93//! self.nodes.iter_mut().map(|x|&mut x.dom)
94//! }
95//! }
96//!
97//! impl DominanceFrontier for Graph {
98//! type FrontierSet = HashMemberSet<usize>;
99//! type NodeIter<'a> = Range<usize> where Self: 'a ;
100//!
101//! fn frontiers_cell(&self, id: Self::Identifier) -> &UnsafeCell<Self::FrontierSet> {
102//! &self.nodes[id].frontiers
103//! }
104//!
105//! fn node_iter<'a>(&'a self) -> Self::NodeIter<'a> {
106//! 0..self.nodes.len()
107//! }
108//! }
109//! ```
110//! Then, one can just run populate the dominance tree and the dominance frontiers
111//! ```ignore
112//! let mut g = random_graph(10000);
113//! dump_graph(&g);
114//! g.populate_dom(0);
115//! g.populate_frontiers();
116//! ```
117use crate::dfs::DFSGraph;
118use crate::set::AssocSet;
119
120/// DFS related interfaces.
121pub mod dfs;
122/// DJ graphs.
123pub mod djgraph;
124/// Domaination frontiers.
125pub mod frontier;
126#[cfg(feature = "materialized_idf")]
127/// Materialized IDF support.
128pub mod materialized_idf;
129/// Housekeeping data structure interfaces.
130pub mod set;
131
132#[cfg(test)]
133mod test;
134
135/// An iterator over the dominators of a given node.
136pub struct DominatorIter<'a, T: DomTree> {
137 tree: &'a T,
138 current: T::Identifier,
139}
140
141impl<'a, T: DomTree> Iterator for DominatorIter<'a, T> {
142 type Item = T::Identifier;
143 fn next(&mut self) -> Option<Self::Item> {
144 let dom = self.tree.dom(self.current).filter(|x| *x != self.current);
145 if let Some(x) = dom {
146 self.current = x;
147 }
148 dom
149 }
150}
151
152/// Interfaces related to Dominance Tree construction.
153pub trait DomTree: DFSGraph + Sized {
154 /// [`Self::MutDomIter`] is used in [`Self::doms_mut`] to get an iterator
155 /// over all nodes and return the mutable references to their immediate dominator identifiers.
156 type MutDomIter<'a>: Iterator<Item = &'a mut Option<Self::Identifier>>
157 where
158 Self: 'a;
159 /// [`Self::PredecessorIter`] is similiar to [`DFSGraph::SuccessorIter`], but it returns
160 /// incoming edges instead.
161 type PredecessorIter<'a>: Iterator<Item = Self::Identifier>
162 where
163 Self: 'a;
164
165 /// Returns the identifier of the immediate dominator of the given node.
166 fn dom(&self, id: Self::Identifier) -> Option<Self::Identifier>;
167 /// Updates the immediate dominator identifier of the given node.
168 fn set_dom(&mut self, id: Self::Identifier, target: Option<Self::Identifier>);
169 /// Returns an iterator over the incoming edges of the given node.
170 fn predecessor_iter(&self, id: Self::Identifier) -> Self::PredecessorIter<'_>;
171 /// Returns an iterator over all nodes which yields the mutable references to their immediate
172 /// dominator identifiers.
173 fn doms_mut(&mut self) -> Self::MutDomIter<'_>;
174 /// Returns an iterator over all the **strict** dominators of a node.
175 fn dom_iter(&self, id: Self::Identifier) -> DominatorIter<Self> {
176 DominatorIter {
177 tree: self,
178 current: id,
179 }
180 }
181 /// Calculate all the immediate dominator for all nodes. This will form the dominator tree.
182 fn populate_dom(&mut self, root: Self::Identifier) {
183 // two-pointer algorithm to trace LCA.
184 fn intersect<D: DomTree>(
185 tree: &D,
186 order_map: &D::Set<usize>,
187 mut x: D::Identifier,
188 mut y: D::Identifier,
189 ) -> D::Identifier {
190 unsafe {
191 while x != y {
192 while order_map.get(x) < order_map.get(y) {
193 // safe because we are processing in reverse post order.
194 x = tree.dom(x).unwrap_unchecked();
195 }
196 while order_map.get(y) < order_map.get(x) {
197 // safe because we are processing in reverse post order.
198 y = tree.dom(y).unwrap_unchecked();
199 }
200 }
201 }
202 x
203 }
204 // initialize all immediate dominators to None.
205 self.doms_mut().for_each(|x| *x = None);
206 // set root to be its own immediate dominator.
207 self.set_dom(root, Some(root));
208
209 // establish post oder using DFS.
210 let post_order = self.post_order_sequence(root);
211 let mut post_order_map = self.create_set();
212 for (i, k) in post_order.iter().cloned().enumerate() {
213 post_order_map.set(k, i);
214 }
215
216 // Iterate until the fixed point is reached.
217 let mut changed = true;
218 while changed {
219 changed = false;
220 for (order, i) in post_order.iter().cloned().enumerate().rev() {
221 if i == root {
222 continue;
223 }
224 let dom = unsafe {
225 self.predecessor_iter(i)
226 .find(|x| post_order_map.get(*x) > order)
227 // safe because we are processing in reverse post order.
228 .unwrap_unchecked()
229 };
230 let dom = self
231 .predecessor_iter(i)
232 .filter(|x| *x != dom && self.dom(*x).is_some())
233 .fold(dom, |dom, x| intersect(self, &post_order_map, x, dom));
234
235 if self.dom(i).map(|x| x != dom).unwrap_or(true) {
236 self.set_dom(i, Some(dom));
237 changed = true;
238 }
239 }
240 }
241 }
242}