index: add method for checking range on DenseBitSet

2 files changed, 45 insertions, 0 deletions

diff --git a/compiler/rustc_index/src/bit_set.rs b/compiler/rustc_index/src/bit_set.rs
index 07934389158..a4885aabe1f 100644
--- a/compiler/rustc_index/src/bit_set.rs
+++ b/compiler/rustc_index/src/bit_set.rs
@@ -234,6 +234,32 @@ impl<T: Idx> DenseBitSet<T> {
         self.clear_excess_bits();
     }
 
+    /// Checks whether any bit in the given range is a 1.
+    #[inline]
+    pub fn contains_any(&self, elems: impl RangeBounds<T>) -> bool {
+        let Some((start, end)) = inclusive_start_end(elems, self.domain_size) else {
+            return false;
+        };
+        let (start_word_index, start_mask) = word_index_and_mask(start);
+        let (end_word_index, end_mask) = word_index_and_mask(end);
+
+        if start_word_index == end_word_index {
+            self.words[start_word_index] & (end_mask | (end_mask - start_mask)) != 0
+        } else {
+            if self.words[start_word_index] & !(start_mask - 1) != 0 {
+                return true;
+            }
+
+            let remaining = start_word_index + 1..end_word_index;
+            if remaining.start <= remaining.end {
+                self.words[remaining].iter().any(|&w| w != 0)
+                    || self.words[end_word_index] & (end_mask | (end_mask - 1)) != 0
+            } else {
+                false
+            }
+        }
+    }
+
     /// Returns `true` if the set has changed.
     #[inline]
     pub fn remove(&mut self, elem: T) -> bool {
diff --git a/compiler/rustc_index/src/bit_set/tests.rs b/compiler/rustc_index/src/bit_set/tests.rs
index 323a66ddc6f..9ce4cf4293f 100644
--- a/compiler/rustc_index/src/bit_set/tests.rs
+++ b/compiler/rustc_index/src/bit_set/tests.rs
@@ -692,6 +692,25 @@ fn dense_last_set_before() {
     }
 }
 
+#[test]
+fn dense_contains_any() {
+    let mut set: DenseBitSet<usize> = DenseBitSet::new_empty(300);
+    assert!(!set.contains_any(0..300));
+    set.insert_range(10..20);
+    set.insert_range(60..70);
+    set.insert_range(150..=250);
+
+    assert!(set.contains_any(0..30));
+    assert!(set.contains_any(5..100));
+    assert!(set.contains_any(250..255));
+
+    assert!(!set.contains_any(20..59));
+    assert!(!set.contains_any(256..290));
+
+    set.insert(22);
+    assert!(set.contains_any(20..59));
+}
+
 #[bench]
 fn bench_insert(b: &mut Bencher) {
     let mut bs = DenseBitSet::new_filled(99999usize);