weavatrix_graph/algo/
dominance_frontier.rs

1use super::{Dominators, dominators_filtered};
2use crate::{IndexGraphView, Vec};
3
4#[derive(Debug, Clone, PartialEq, Eq)]
5pub struct DominanceFrontiers<Node> {
6    root: Node,
7    entries: Vec<(Node, Vec<Node>)>,
8}
9
10impl<Node> DominanceFrontiers<Node>
11where
12    Node: Copy + Eq,
13{
14    #[must_use]
15    pub const fn root(&self) -> Node {
16        self.root
17    }
18
19    #[must_use]
20    pub fn frontier(&self, node: Node) -> Option<&[Node]> {
21        self.entries
22            .iter()
23            .find_map(|(candidate, frontier)| (*candidate == node).then_some(frontier.as_slice()))
24    }
25
26    pub fn iter(&self) -> impl Iterator<Item = (Node, &[Node])> {
27        self.entries
28            .iter()
29            .map(|(node, frontier)| (*node, frontier.as_slice()))
30    }
31}
32
33#[must_use]
34pub fn dominance_frontiers<G>(graph: &G, root: G::Node) -> Option<DominanceFrontiers<G::Node>>
35where
36    G: IndexGraphView,
37{
38    dominance_frontiers_filtered(graph, root, |_| true)
39}
40
41#[must_use]
42pub fn dominance_frontiers_filtered<G, F>(
43    graph: &G,
44    root: G::Node,
45    allows_edge: F,
46) -> Option<DominanceFrontiers<G::Node>>
47where
48    G: IndexGraphView,
49    F: Fn(G::Edge) -> bool,
50{
51    let mut allowed = vec![false; graph.edge_bound()];
52    for edge in graph.edge_indices() {
53        allowed[G::edge_slot(edge)] = allows_edge(edge);
54    }
55    let dominators = dominators_filtered(graph, root, |edge| allowed[G::edge_slot(edge)])?;
56    let predecessors = reachable_predecessors(graph, &dominators, &allowed);
57    let mut immediate = vec![None; graph.node_bound()];
58    immediate[G::node_slot(root)] = Some(root);
59    for (node, parent) in dominators.immediate_dominators() {
60        immediate[G::node_slot(node)] = Some(parent);
61    }
62    let mut frontiers = vec![Vec::new(); graph.node_bound()];
63    for &join in dominators.reachable_nodes() {
64        let join_slot = G::node_slot(join);
65        if predecessors[join_slot].len() < 2 {
66            continue;
67        }
68        let stop = immediate[join_slot]?;
69        for &predecessor in &predecessors[join_slot] {
70            propagate::<G>(predecessor, stop, join, &immediate, &mut frontiers);
71        }
72    }
73    let entries = dominators
74        .reachable_nodes()
75        .iter()
76        .copied()
77        .map(|node| {
78            let frontier = &mut frontiers[G::node_slot(node)];
79            frontier.sort_unstable_by_key(|candidate| G::node_slot(*candidate));
80            frontier.dedup();
81            (node, core::mem::take(frontier))
82        })
83        .collect();
84    Some(DominanceFrontiers { root, entries })
85}
86
87fn reachable_predecessors<G>(
88    graph: &G,
89    dominators: &Dominators<G::Node>,
90    allowed: &[bool],
91) -> Vec<Vec<G::Node>>
92where
93    G: IndexGraphView,
94{
95    let mut reachable = vec![false; graph.node_bound()];
96    for &node in dominators.reachable_nodes() {
97        reachable[G::node_slot(node)] = true;
98    }
99    let mut predecessors = vec![Vec::new(); graph.node_bound()];
100    for (edge, endpoints) in graph.edge_references() {
101        if !allowed[G::edge_slot(edge)] {
102            continue;
103        }
104        let source_slot = G::node_slot(endpoints.source());
105        let target_slot = G::node_slot(endpoints.target());
106        if !reachable[source_slot] || !reachable[target_slot] {
107            continue;
108        }
109        let incoming = &mut predecessors[target_slot];
110        if !incoming.contains(&endpoints.source()) {
111            incoming.push(endpoints.source());
112        }
113    }
114    predecessors
115}
116
117fn propagate<G>(
118    mut runner: G::Node,
119    stop: G::Node,
120    join: G::Node,
121    immediate: &[Option<G::Node>],
122    frontiers: &mut [Vec<G::Node>],
123) where
124    G: IndexGraphView,
125{
126    while runner != stop {
127        let slot = G::node_slot(runner);
128        frontiers[slot].push(join);
129        let Some(parent) = immediate[slot] else {
130            break;
131        };
132        if parent == runner {
133            break;
134        }
135        runner = parent;
136    }
137}
weavatrix_graph/algo/dominance_frontier.rs

weavatrix_graph/algo/
dominance_frontier.rs
