New upstream version 1.63.0+dfsg1

[rustc.git] / compiler / rustc_index / src / bit_set.rs

diff --git a/compiler/rustc_index/src/bit_set.rs b/compiler/rustc_index/src/bit_set.rs
index 059755a743b6676f9db2cba0b79fb3acd13329e6..976874c7cee83a701643d7a657dbb085e0ff909d 100644 (file)
--- a/compiler/rustc_index/src/bit_set.rs
+++ b/compiler/rustc_index/src/bit_set.rs
@@ -340,6 +340,12 @@ impl<T: Idx> BitRelations<BitSet<T>> for BitSet<T> {
     }
 }
 
+impl<T: Idx> From<GrowableBitSet<T>> for BitSet<T> {
+    fn from(bit_set: GrowableBitSet<T>) -> Self {
+        bit_set.bit_set
+    }
+}
+
 /// A fixed-size bitset type with a partially dense, partially sparse
 /// representation. The bitset is broken into chunks, and chunks that are all
 /// zeros or all ones are represented and handled very efficiently.
@@ -681,6 +687,48 @@ impl<T: Idx> BitRelations<HybridBitSet<T>> for ChunkedBitSet<T> {
     }
 }
 
+impl<T: Idx> BitRelations<ChunkedBitSet<T>> for BitSet<T> {
+    fn union(&mut self, other: &ChunkedBitSet<T>) -> bool {
+        sequential_update(|elem| self.insert(elem), other.iter())
+    }
+
+    fn subtract(&mut self, _other: &ChunkedBitSet<T>) -> bool {
+        unimplemented!("implement if/when necessary");
+    }
+
+    fn intersect(&mut self, other: &ChunkedBitSet<T>) -> bool {
+        assert_eq!(self.domain_size(), other.domain_size);
+        let mut changed = false;
+        for (i, chunk) in other.chunks.iter().enumerate() {
+            let mut words = &mut self.words[i * CHUNK_WORDS..];
+            if words.len() > CHUNK_WORDS {
+                words = &mut words[..CHUNK_WORDS];
+            }
+            match chunk {
+                Chunk::Zeros(..) => {
+                    for word in words {
+                        if *word != 0 {
+                            changed = true;
+                            *word = 0;
+                        }
+                    }
+                }
+                Chunk::Ones(..) => (),
+                Chunk::Mixed(_, _, data) => {
+                    for (i, word) in words.iter_mut().enumerate() {
+                        let new_val = *word & data[i];
+                        if new_val != *word {
+                            changed = true;
+                            *word = new_val;
+                        }
+                    }
+                }
+            }
+        }
+        changed
+    }
+}
+
 impl<T> Clone for ChunkedBitSet<T> {
     fn clone(&self) -> Self {
         ChunkedBitSet {
@@ -743,6 +791,41 @@ impl<'a, T: Idx> Iterator for ChunkedBitIter<'a, T> {
         }
         None
     }
+
+    fn fold<B, F>(mut self, mut init: B, mut f: F) -> B
+    where
+        F: FnMut(B, Self::Item) -> B,
+    {
+        // If `next` has already been called, we may not be at the start of a chunk, so we first
+        // advance the iterator to the start of the next chunk, before proceeding in chunk sized
+        // steps.
+        while self.index % CHUNK_BITS != 0 {
+            let Some(item) = self.next() else {
+                return init
+            };
+            init = f(init, item);
+        }
+        let start_chunk = self.index / CHUNK_BITS;
+        let chunks = &self.bitset.chunks[start_chunk..];
+        for (i, chunk) in chunks.iter().enumerate() {
+            let base = (start_chunk + i) * CHUNK_BITS;
+            match chunk {
+                Chunk::Zeros(_) => (),
+                Chunk::Ones(limit) => {
+                    for j in 0..(*limit as usize) {
+                        init = f(init, T::new(base + j));
+                    }
+                }
+                Chunk::Mixed(_, _, words) => {
+                    init = BitIter::new(&**words).fold(init, |val, mut item: T| {
+                        item.increment_by(base);
+                        f(val, item)
+                    });
+                }
+            }
+        }
+        init
+    }
 }
 
 impl Chunk {
@@ -799,11 +882,7 @@ fn sequential_update<T: Idx>(
     mut self_update: impl FnMut(T) -> bool,
     it: impl Iterator<Item = T>,
 ) -> bool {
-    let mut changed = false;
-    for elem in it {
-        changed |= self_update(elem);
-    }
-    changed
+    it.fold(false, |changed, elem| self_update(elem) | changed)
 }
 
 // Optimization of intersection for SparseBitSet that's generic
@@ -1469,6 +1548,12 @@ impl<T: Idx> GrowableBitSet<T> {
     }
 }
 
+impl<T: Idx> From<BitSet<T>> for GrowableBitSet<T> {
+    fn from(bit_set: BitSet<T>) -> Self {
+        Self { bit_set }
+    }
+}
+
 /// A fixed-size 2D bit matrix type with a dense representation.
 ///
 /// `R` and `C` are index types used to identify rows and columns respectively;