1 files changed, 30 insertions, 6 deletions

diff --git a/compiler/rustc_index/src/interval.rs b/compiler/rustc_index/src/interval.rs
index d809740c6..d3cf267dc 100644
--- a/compiler/rustc_index/src/interval.rs
+++ b/compiler/rustc_index/src/interval.rs
@@ -3,10 +3,11 @@ use std::marker::PhantomData;
 use std::ops::RangeBounds;
 use std::ops::{Bound, Range};
 
-use crate::vec::Idx;
-use crate::vec::IndexVec;
 use smallvec::SmallVec;
 
+use crate::idx::Idx;
+use crate::vec::IndexVec;
+
 #[cfg(test)]
 mod tests;
 
@@ -180,6 +181,30 @@ impl<I: Idx> IntervalSet<I> {
         self.map.is_empty()
     }
 
+    /// Equivalent to `range.iter().find(|i| !self.contains(i))`.
+    pub fn first_unset_in(&self, range: impl RangeBounds<I> + Clone) -> Option<I> {
+        let start = inclusive_start(range.clone());
+        let Some(end) = inclusive_end(self.domain, range) else {
+            // empty range
+            return None;
+        };
+        if start > end {
+            return None;
+        }
+        let Some(last) = self.map.partition_point(|r| r.0 <= start).checked_sub(1) else {
+            // All ranges in the map start after the new range's end
+            return Some(I::new(start as usize));
+        };
+        let (_, prev_end) = self.map[last];
+        if start > prev_end {
+            Some(I::new(start as usize))
+        } else if prev_end < end {
+            Some(I::new(prev_end as usize + 1))
+        } else {
+            None
+        }
+    }
+
     /// Returns the maximum (last) element present in the set from `range`.
     pub fn last_set_in(&self, range: impl RangeBounds<I> + Clone) -> Option<I> {
         let start = inclusive_start(range.clone());
@@ -223,7 +248,7 @@ impl<I: Idx> IntervalSet<I> {
     fn check_invariants(&self) -> bool {
         let mut current: Option<u32> = None;
         for (start, end) in &self.map {
-            if start > end || current.map_or(false, |x| x + 1 >= *start) {
+            if start > end || current.is_some_and(|x| x + 1 >= *start) {
                 return false;
             }
             current = Some(*end);
@@ -261,8 +286,7 @@ impl<R: Idx, C: Step + Idx> SparseIntervalMatrix<R, C> {
     }
 
     fn ensure_row(&mut self, row: R) -> &mut IntervalSet<C> {
-        self.rows.ensure_contains_elem(row, || IntervalSet::new(self.column_size));
-        &mut self.rows[row]
+        self.rows.ensure_contains_elem(row, || IntervalSet::new(self.column_size))
     }
 
     pub fn union_row(&mut self, row: R, from: &IntervalSet<C>) -> bool
@@ -297,6 +321,6 @@ impl<R: Idx, C: Step + Idx> SparseIntervalMatrix<R, C> {
     }
 
     pub fn contains(&self, row: R, point: C) -> bool {
-        self.row(row).map_or(false, |r| r.contains(point))
+        self.row(row).is_some_and(|r| r.contains(point))
     }
 }