clippy_utils/mir/
transitive_relation.rs

1use rustc_data_structures::fx::FxHashMap;
2use rustc_index::bit_set::DenseBitSet;
3use rustc_middle::mir;
4
5#[derive(Default)]
6pub(super) struct TransitiveRelation {
7    relations: FxHashMap<mir::Local, Vec<mir::Local>>,
8}
9
10impl TransitiveRelation {
11    pub fn add(&mut self, a: mir::Local, b: mir::Local) {
12        self.relations.entry(a).or_default().push(b);
13    }
14
15    pub fn reachable_from(&self, a: mir::Local, domain_size: usize) -> DenseBitSet<mir::Local> {
16        let mut seen = DenseBitSet::new_empty(domain_size);
17        let mut stack = vec![a];
18        while let Some(u) = stack.pop() {
19            if let Some(edges) = self.relations.get(&u) {
20                for &v in edges {
21                    if seen.insert(v) {
22                        stack.push(v);
23                    }
24                }
25            }
26        }
27        seen
28    }
29}