1 files changed, 29 insertions, 0 deletions
diff --git a/src/tools/clippy/clippy_utils/src/mir/transitive_relation.rs b/src/tools/clippy/clippy_utils/src/mir/transitive_relation.rs
new file mode 100644
index 000000000..7fe296073
--- /dev/null
+++ b/src/tools/clippy/clippy_utils/src/mir/transitive_relation.rs
@@ -0,0 +1,29 @@
+use rustc_data_structures::fx::FxHashMap;
+use rustc_index::bit_set::HybridBitSet;
+use rustc_middle::mir;
+
+#[derive(Default)]
+pub(super) struct TransitiveRelation {
+    relations: FxHashMap<mir::Local, Vec<mir::Local>>,
+}
+
+impl TransitiveRelation {
+    pub fn add(&mut self, a: mir::Local, b: mir::Local) {
+        self.relations.entry(a).or_default().push(b);
+    }
+
+    pub fn reachable_from(&self, a: mir::Local, domain_size: usize) -> HybridBitSet<mir::Local> {
+        let mut seen = HybridBitSet::new_empty(domain_size);
+        let mut stack = vec![a];
+        while let Some(u) = stack.pop() {
+            if let Some(edges) = self.relations.get(&u) {
+                for &v in edges {
+                    if seen.insert(v) {
+                        stack.push(v);
+                    }
+                }
+            }
+        }
+        seen
+    }
+}