diff options
Diffstat (limited to 'compiler/rustc_mir_transform/src/coverage')
4 files changed, 1 insertions, 131 deletions
diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs index 5568d42ab8f..879a20e771d 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters.rs @@ -16,7 +16,6 @@ use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph}; mod balanced_flow; pub(crate) mod node_flow; -mod union_find; /// Struct containing the results of [`prepare_bcb_counters_data`]. pub(crate) struct BcbCountersData { diff --git a/compiler/rustc_mir_transform/src/coverage/counters/node_flow.rs b/compiler/rustc_mir_transform/src/coverage/counters/node_flow.rs index 91ed54b8b59..e063f75887b 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters/node_flow.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters/node_flow.rs @@ -7,13 +7,12 @@ //! (Knuth & Stevenson, 1973). use rustc_data_structures::graph; +use rustc_data_structures::union_find::UnionFind; use rustc_index::bit_set::DenseBitSet; use rustc_index::{Idx, IndexSlice, IndexVec}; pub(crate) use rustc_middle::mir::coverage::NodeFlowData; use rustc_middle::mir::coverage::Op; -use crate::coverage::counters::union_find::UnionFind; - #[cfg(test)] mod tests; diff --git a/compiler/rustc_mir_transform/src/coverage/counters/union_find.rs b/compiler/rustc_mir_transform/src/coverage/counters/union_find.rs deleted file mode 100644 index a826a953fa6..00000000000 --- a/compiler/rustc_mir_transform/src/coverage/counters/union_find.rs +++ /dev/null @@ -1,96 +0,0 @@ -use std::cmp::Ordering; -use std::mem; - -use rustc_index::{Idx, IndexVec}; - -#[cfg(test)] -mod tests; - -/// Simple implementation of a union-find data structure, i.e. a disjoint-set -/// forest. -#[derive(Debug)] -pub(crate) struct UnionFind<Key: Idx> { - table: IndexVec<Key, UnionFindEntry<Key>>, -} - -#[derive(Debug)] -struct UnionFindEntry<Key> { - /// Transitively points towards the "root" of the set containing this key. - /// - /// Invariant: A root key is its own parent. - parent: Key, - /// When merging two "root" keys, their ranks determine which key becomes - /// the new root, to prevent the parent tree from becoming unnecessarily - /// tall. See [`UnionFind::unify`] for details. - rank: u32, -} - -impl<Key: Idx> UnionFind<Key> { - /// Creates a new disjoint-set forest containing the keys `0..num_keys`. - /// Initially, every key is part of its own one-element set. - pub(crate) fn new(num_keys: usize) -> Self { - // Initially, every key is the root of its own set, so its parent is itself. - Self { table: IndexVec::from_fn_n(|key| UnionFindEntry { parent: key, rank: 0 }, num_keys) } - } - - /// Returns the "root" key of the disjoint-set containing the given key. - /// If two keys have the same root, they belong to the same set. - /// - /// Also updates internal data structures to make subsequent `find` - /// operations faster. - pub(crate) fn find(&mut self, key: Key) -> Key { - // Loop until we find a key that is its own parent. - let mut curr = key; - while let parent = self.table[curr].parent - && curr != parent - { - // Perform "path compression" by peeking one layer ahead, and - // setting the current key's parent to that value. - // (This works even when `parent` is the root of its set, because - // of the invariant that a root is its own parent.) - let parent_parent = self.table[parent].parent; - self.table[curr].parent = parent_parent; - - // Advance by one step and continue. - curr = parent; - } - curr - } - - /// Merges the set containing `a` and the set containing `b` into one set. - /// - /// Returns the common root of both keys, after the merge. - pub(crate) fn unify(&mut self, a: Key, b: Key) -> Key { - let mut a = self.find(a); - let mut b = self.find(b); - - // If both keys have the same root, they're already in the same set, - // so there's nothing more to do. - if a == b { - return a; - }; - - // Ensure that `a` has strictly greater rank, swapping if necessary. - // If both keys have the same rank, increment the rank of `a` so that - // future unifications will also prefer `a`, leading to flatter trees. - match Ord::cmp(&self.table[a].rank, &self.table[b].rank) { - Ordering::Less => mem::swap(&mut a, &mut b), - Ordering::Equal => self.table[a].rank += 1, - Ordering::Greater => {} - } - - debug_assert!(self.table[a].rank > self.table[b].rank); - debug_assert_eq!(self.table[b].parent, b); - - // Make `a` the parent of `b`. - self.table[b].parent = a; - - a - } - - /// Takes a "snapshot" of the current state of this disjoint-set forest, in - /// the form of a vector that directly maps each key to its current root. - pub(crate) fn snapshot(&mut self) -> IndexVec<Key, Key> { - self.table.indices().map(|key| self.find(key)).collect() - } -} diff --git a/compiler/rustc_mir_transform/src/coverage/counters/union_find/tests.rs b/compiler/rustc_mir_transform/src/coverage/counters/union_find/tests.rs deleted file mode 100644 index 34a4e4f8e6e..00000000000 --- a/compiler/rustc_mir_transform/src/coverage/counters/union_find/tests.rs +++ /dev/null @@ -1,32 +0,0 @@ -use super::UnionFind; - -#[test] -fn empty() { - let mut sets = UnionFind::<u32>::new(10); - - for i in 1..10 { - assert_eq!(sets.find(i), i); - } -} - -#[test] -fn transitive() { - let mut sets = UnionFind::<u32>::new(10); - - sets.unify(3, 7); - sets.unify(4, 2); - - assert_eq!(sets.find(7), sets.find(3)); - assert_eq!(sets.find(2), sets.find(4)); - assert_ne!(sets.find(3), sets.find(4)); - - sets.unify(7, 4); - - assert_eq!(sets.find(7), sets.find(3)); - assert_eq!(sets.find(2), sets.find(4)); - assert_eq!(sets.find(3), sets.find(4)); - - for i in [0, 1, 5, 6, 8, 9] { - assert_eq!(sets.find(i), i); - } -} |