domtree 0.2.0

dominance relation calculation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

use std::cell::UnsafeCell;

use crate::set::MemberSet;
use crate::DomTree;

/// Interfaces related to dominance frontier calculation
pub trait DominanceFrontier: DomTree {
    /// [`Self::FrontierSet`] is used to maintain the dominance frontier.
    /// Each node should hold a separate [`Self::FrontierSet`].
    type FrontierSet: MemberSet<Self::Identifier>;
    /// [`Self::NodeIter`] is an iterator over all nodes of the graph.
    type NodeIter<'a>: Iterator<Item = Self::Identifier>
    where
        Self: 'a;
    /// Due to mutable reference limitations, the trait expects [`Self::FrontierSet`] to
    /// be wrapped in a [`UnsafeCell`] to allow iterated update. This method is used to
    /// access the [`UnsafeCell`].
    fn frontiers_cell(&self, id: Self::Identifier) -> &UnsafeCell<Self::FrontierSet>;
    /// A helper function that is auto derived for user to access the dominance frontiers of
    /// the given node.
    fn frontiers(&self, id: Self::Identifier) -> &Self::FrontierSet {
        unsafe { &*self.frontiers_cell(id).get() }
    }
    /// Gets an iterator over all nodes of the graph.
    fn node_iter(&self) -> Self::NodeIter<'_>;

    /// Calculate the dominance frontiers of all nodes. The immediate dominators must be
    /// calculated before calling this function. Otherwise, it will not crash but the answers can get
    /// wrong.
    fn populate_frontiers(&mut self) {
        for i in self.node_iter() {
            for mut p in self.predecessor_iter(i) {
                if let Some(dom) = self.dom(i) {
                    while p != dom {
                        unsafe {
                            (*self.frontiers_cell(p).get()).insert(i);
                        }
                        if let Some(pdom) = self.dom(p) {
                            p = pdom;
                        } else {
                            break;
                        }
                    }
                }
            }
        }
    }
}