Skip to main content

rustc_index/
interval.rs

1use std::iter::Step;
2use std::marker::PhantomData;
3use std::ops::{Bound, RangeBounds};
4use std::range::RangeInclusive;
5
6use smallvec::SmallVec;
7
8use crate::idx::Idx;
9use crate::vec::IndexVec;
10
11#[cfg(test)]
12mod tests;
13
14/// Stores a set of intervals on the indices.
15///
16/// The elements in `map` are sorted and non-adjacent, which means
17/// the second value of the previous element is *greater* than the
18/// first value of the following element.
19#[derive(#[automatically_derived]impl<I: ::core::fmt::Debug> ::core::fmt::Debug for
    IntervalSet<I> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field3_finish(f,
            "IntervalSet map domain _data", &self.map, &self.domain,
            &&self._data)
    }
}Debug, #[automatically_derived]impl<I: ::core::clone::Clone> ::core::clone::Clone for
    IntervalSet<I> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        IntervalSet {
            map: ::core::clone::Clone::clone(&self.map),
            domain: ::core::clone::Clone::clone(&self.domain),
            _data: ::core::clone::Clone::clone(&self._data),
        }
    }
}Clone)]
20pub struct IntervalSet<I> {
21    // Start, end (both inclusive)
22    map: SmallVec<[(u32, u32); 2]>,
23    domain: usize,
24    _data: PhantomData<I>,
25}
26
27#[inline]
28fn inclusive_start<T: Idx>(range: impl RangeBounds<T>) -> u32 {
29    match range.start_bound() {
30        Bound::Included(start) => start.index() as u32,
31        Bound::Excluded(start) => start.index() as u32 + 1,
32        Bound::Unbounded => 0,
33    }
34}
35
36#[inline]
37fn inclusive_end<T: Idx>(domain: usize, range: impl RangeBounds<T>) -> Option<u32> {
38    let end = match range.end_bound() {
39        Bound::Included(end) => end.index() as u32,
40        Bound::Excluded(end) => end.index().checked_sub(1)? as u32,
41        Bound::Unbounded => domain.checked_sub(1)? as u32,
42    };
43    Some(end)
44}
45
46impl<I: Idx> IntervalSet<I> {
47    pub fn new(domain: usize) -> IntervalSet<I> {
48        IntervalSet { map: SmallVec::new(), domain, _data: PhantomData }
49    }
50
51    pub fn clear(&mut self) {
52        self.map.clear();
53    }
54
55    pub fn iter(&self) -> impl Iterator<Item = I>
56    where
57        I: Step,
58    {
59        self.iter_intervals().flatten()
60    }
61
62    /// Iterates through intervals stored in the set, in order.
63    pub fn iter_intervals(&self) -> impl Iterator<Item = RangeInclusive<I>>
64    where
65        I: Step,
66    {
67        self.map.iter().map(|&(start, end)| RangeInclusive {
68            start: I::new(start as usize),
69            last: I::new(end as usize),
70        })
71    }
72
73    /// Returns true if we increased the number of elements present.
74    pub fn insert(&mut self, point: I) -> bool {
75        self.insert_range(point..=point)
76    }
77
78    /// Returns true if we increased the number of elements present.
79    pub fn insert_range(&mut self, range: impl RangeBounds<I> + Clone) -> bool {
80        let start = inclusive_start(range.clone());
81        let Some(end) = inclusive_end(self.domain, range) else {
82            // empty range
83            return false;
84        };
85        if start > end {
86            return false;
87        }
88
89        // This condition looks a bit weird, but actually makes sense.
90        //
91        // if r.0 == end + 1, then we're actually adjacent, so we want to
92        // continue to the next range. We're looking here for the first
93        // range which starts *non-adjacently* to our end.
94        let next = self.map.partition_point(|r| r.0 <= end + 1);
95        let result = if let Some(right) = next.checked_sub(1) {
96            let (prev_start, prev_end) = self.map[right];
97            if prev_end + 1 >= start {
98                // If the start for the inserted range is adjacent to the
99                // end of the previous, we can extend the previous range.
100                if start < prev_start {
101                    // The first range which ends *non-adjacently* to our start.
102                    // And we can ensure that left <= right.
103                    let left = self.map.partition_point(|l| l.1 + 1 < start);
104                    let min = std::cmp::min(self.map[left].0, start);
105                    let max = std::cmp::max(prev_end, end);
106                    self.map[right] = (min, max);
107                    if left != right {
108                        self.map.drain(left..right);
109                    }
110                    true
111                } else {
112                    // We overlap with the previous range, increase it to
113                    // include us.
114                    //
115                    // Make sure we're actually going to *increase* it though --
116                    // it may be that end is just inside the previously existing
117                    // set.
118                    if end > prev_end {
119                        self.map[right].1 = end;
120                        true
121                    } else {
122                        false
123                    }
124                }
125            } else {
126                // Otherwise, we don't overlap, so just insert
127                self.map.insert(right + 1, (start, end));
128                true
129            }
130        } else {
131            if self.map.is_empty() {
132                // Quite common in practice, and expensive to call memcpy
133                // with length zero.
134                self.map.push((start, end));
135            } else {
136                self.map.insert(next, (start, end));
137            }
138            true
139        };
140        if true {
    if !self.check_invariants() {
        {
            ::core::panicking::panic_fmt(format_args!("wrong intervals after insert {0:?}..={1:?} to {2:?}",
                    start, end, self));
        }
    };
};debug_assert!(
141            self.check_invariants(),
142            "wrong intervals after insert {start:?}..={end:?} to {self:?}"
143        );
144        result
145    }
146
147    /// Specialized version of `insert` when we know that the inserted point is *after* any
148    /// contained.
149    pub fn append(&mut self, point: I) {
150        let point = point.index() as u32;
151
152        if let Some((_, last_end)) = self.map.last_mut() {
153            if !(*last_end <= point) {
    ::core::panicking::panic("assertion failed: *last_end <= point")
};assert!(*last_end <= point);
154            if point == *last_end {
155                // The point is already in the set.
156            } else if point == *last_end + 1 {
157                *last_end = point;
158            } else {
159                self.map.push((point, point));
160            }
161        } else {
162            self.map.push((point, point));
163        }
164
165        if true {
    if !self.check_invariants() {
        {
            ::core::panicking::panic_fmt(format_args!("wrong intervals after append {0:?} to {1:?}",
                    point, self));
        }
    };
};debug_assert!(
166            self.check_invariants(),
167            "wrong intervals after append {point:?} to {self:?}"
168        );
169    }
170
171    /// Specialized version of `insert_range` when we know that the inserted point is *after* any
172    /// contained.
173    pub fn append_range(&mut self, range: impl RangeBounds<I> + Clone) {
174        let start = inclusive_start(range.clone());
175        let Some(end) = inclusive_end(self.domain, range) else {
176            // empty range
177            return;
178        };
179        if start > end {
180            return;
181        }
182
183        if let Some((_, last_end)) = self.map.last_mut() {
184            if !(*last_end <= start) {
    ::core::panicking::panic("assertion failed: *last_end <= start")
};assert!(*last_end <= start);
185            // The start is already adjacent to the set.
186            if start <= *last_end + 1 {
187                *last_end = end;
188            } else {
189                self.map.push((start, end));
190            }
191        } else {
192            self.map.push((start, end));
193        }
194
195        if true {
    if !self.check_invariants() {
        {
            ::core::panicking::panic_fmt(format_args!("wrong intervals after append {0:?}..={1:?} to {2:?}",
                    start, end, self));
        }
    };
};debug_assert!(
196            self.check_invariants(),
197            "wrong intervals after append {start:?}..={end:?} to {self:?}"
198        );
199    }
200
201    pub fn contains(&self, needle: I) -> bool {
202        let needle = needle.index() as u32;
203        let Some(last) = self.map.partition_point(|r| r.0 <= needle).checked_sub(1) else {
204            // All ranges in the map start after the new range's end
205            return false;
206        };
207        let (_, prev_end) = &self.map[last];
208        needle <= *prev_end
209    }
210
211    /// Returns whether any point in `range` is contained in the set.
212    pub fn intersects_range(&self, range: impl RangeBounds<I> + Clone) -> bool {
213        let start = inclusive_start(range.clone());
214        let Some(end) = inclusive_end(self.domain, range) else {
215            // empty range
216            return false;
217        };
218        if start > end {
219            return false;
220        }
221
222        // Find the last interval whose start is <= end.
223        let Some(last) = self.map.partition_point(|r| r.0 <= end).checked_sub(1) else {
224            // All ranges in the map start after the new range's end
225            return false;
226        };
227        let (_, prev_end) = &self.map[last];
228        start <= *prev_end
229    }
230
231    pub fn superset(&self, other: &IntervalSet<I>) -> bool
232    where
233        I: Step,
234    {
235        let mut sup_iter = self.iter_intervals();
236        let mut current = None;
237        let contains = |sup: RangeInclusive<I>,
238                        sub: RangeInclusive<I>,
239                        current: &mut Option<RangeInclusive<I>>| {
240            if sup.last < sub.start {
241                None // continue to the next sup
242            } else if sup.last >= sub.last && sup.start <= sub.start {
243                *current = Some(sup); // save the current sup
244                Some(true)
245            } else {
246                Some(false)
247            }
248        };
249        other.iter_intervals().all(|sub| {
250            current
251                .take()
252                .and_then(|sup| contains(sup, sub, &mut current))
253                .or_else(|| sup_iter.find_map(|sup| contains(sup, sub, &mut current)))
254                .unwrap_or(false)
255        })
256    }
257
258    pub fn disjoint(&self, other: &IntervalSet<I>) -> bool
259    where
260        I: Step,
261    {
262        let helper = move || {
263            let mut self_iter = self.iter_intervals();
264            let mut other_iter = other.iter_intervals();
265
266            let mut self_current = self_iter.next()?;
267            let mut other_current = other_iter.next()?;
268
269            loop {
270                if self_current.last < other_current.start {
271                    self_current = self_iter.next()?;
272                    continue;
273                }
274                if other_current.last < self_current.start {
275                    other_current = other_iter.next()?;
276                    continue;
277                }
278                return Some(false);
279            }
280        };
281        helper().unwrap_or(true)
282    }
283
284    pub fn is_empty(&self) -> bool {
285        self.map.is_empty()
286    }
287
288    /// Equivalent to `range.iter().find(|i| !self.contains(i))`.
289    pub fn first_unset_in(&self, range: impl RangeBounds<I> + Clone) -> Option<I> {
290        let start = inclusive_start(range.clone());
291        let Some(end) = inclusive_end(self.domain, range) else {
292            // empty range
293            return None;
294        };
295        if start > end {
296            return None;
297        }
298        let Some(last) = self.map.partition_point(|r| r.0 <= start).checked_sub(1) else {
299            // All ranges in the map start after the new range's end
300            return Some(I::new(start as usize));
301        };
302        let (_, prev_end) = self.map[last];
303        if start > prev_end {
304            Some(I::new(start as usize))
305        } else if prev_end < end {
306            Some(I::new(prev_end as usize + 1))
307        } else {
308            None
309        }
310    }
311
312    /// Returns the maximum (last) element present in the set from `range`.
313    pub fn last_set_in(&self, range: impl RangeBounds<I> + Clone) -> Option<I> {
314        let start = inclusive_start(range.clone());
315        let Some(end) = inclusive_end(self.domain, range) else {
316            // empty range
317            return None;
318        };
319        if start > end {
320            return None;
321        }
322        let Some(last) = self.map.partition_point(|r| r.0 <= end).checked_sub(1) else {
323            // All ranges in the map start after the new range's end
324            return None;
325        };
326        let (_, prev_end) = &self.map[last];
327        if start <= *prev_end { Some(I::new(std::cmp::min(*prev_end, end) as usize)) } else { None }
328    }
329
330    pub fn insert_all(&mut self) {
331        self.clear();
332        if let Some(end) = self.domain.checked_sub(1) {
333            self.map.push((0, end.try_into().unwrap()));
334        }
335        if true {
    if !self.check_invariants() {
        ::core::panicking::panic("assertion failed: self.check_invariants()")
    };
};debug_assert!(self.check_invariants());
336    }
337
338    pub fn union(&mut self, other: &IntervalSet<I>) -> bool
339    where
340        I: Step,
341    {
342        {
    match (&self.domain, &other.domain) {
        (left_val, right_val) => {
            if !(*left_val == *right_val) {
                let kind = ::core::panicking::AssertKind::Eq;
                ::core::panicking::assert_failed(kind, &*left_val,
                    &*right_val, ::core::option::Option::None);
            }
        }
    }
};assert_eq!(self.domain, other.domain);
343        if self.map.len() < other.map.len() {
344            let backup = self.clone();
345            self.map.clone_from(&other.map);
346            return self.union(&backup);
347        }
348
349        let mut did_insert = false;
350        for range in other.iter_intervals() {
351            did_insert |= self.insert_range(range);
352        }
353        if true {
    if !self.check_invariants() {
        ::core::panicking::panic("assertion failed: self.check_invariants()")
    };
};debug_assert!(self.check_invariants());
354        did_insert
355    }
356
357    // Check the intervals are valid, sorted and non-adjacent
358    fn check_invariants(&self) -> bool {
359        let mut current: Option<u32> = None;
360        for (start, end) in &self.map {
361            if start > end || current.is_some_and(|x| x + 1 >= *start) {
362                return false;
363            }
364            current = Some(*end);
365        }
366        current.is_none_or(|x| x < self.domain as u32)
367    }
368}
369
370/// This data structure optimizes for cases where the stored bits in each row
371/// are expected to be highly contiguous (long ranges of 1s or 0s), in contrast
372/// to BitMatrix and SparseBitMatrix which are optimized for
373/// "random"/non-contiguous bits and cheap(er) point queries at the expense of
374/// memory usage.
375#[derive(#[automatically_derived]impl<R: ::core::clone::Clone, C: ::core::clone::Clone>
    ::core::clone::Clone for SparseIntervalMatrix<R, C> where R: Idx, C: Idx {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        SparseIntervalMatrix {
            rows: ::core::clone::Clone::clone(&self.rows),
            column_size: ::core::clone::Clone::clone(&self.column_size),
        }
    }
}Clone)]
376pub struct SparseIntervalMatrix<R, C>
377where
378    R: Idx,
379    C: Idx,
380{
381    rows: IndexVec<R, IntervalSet<C>>,
382    column_size: usize,
383}
384
385impl<R: Idx, C: Step + Idx> SparseIntervalMatrix<R, C> {
386    pub fn new(column_size: usize) -> SparseIntervalMatrix<R, C> {
387        SparseIntervalMatrix { rows: IndexVec::new(), column_size }
388    }
389
390    pub fn rows(&self) -> impl Iterator<Item = R> {
391        self.rows.indices()
392    }
393
394    pub fn row(&self, row: R) -> Option<&IntervalSet<C>> {
395        self.rows.get(row)
396    }
397
398    pub fn iter_enumerated(&self) -> impl Iterator<Item = (R, &IntervalSet<C>)> {
399        self.rows.iter_enumerated()
400    }
401
402    pub fn clear_row(&mut self, row: R) {
403        if let Some(row) = self.rows.get_mut(row) {
404            row.clear();
405        }
406    }
407
408    fn ensure_row(&mut self, row: R) -> &mut IntervalSet<C> {
409        self.rows.ensure_contains_elem(row, || IntervalSet::new(self.column_size))
410    }
411
412    pub fn union_row(&mut self, row: R, from: &IntervalSet<C>) -> bool
413    where
414        C: Step,
415    {
416        self.ensure_row(row).union(from)
417    }
418
419    pub fn union_rows(&mut self, read: R, write: R) -> bool
420    where
421        C: Step,
422    {
423        if read == write || self.rows.get(read).is_none() {
424            return false;
425        }
426        self.ensure_row(write);
427        let (read_row, write_row) = self.rows.pick2_mut(read, write);
428        write_row.union(read_row)
429    }
430
431    pub fn disjoint_rows(&self, a: R, b: R) -> bool
432    where
433        C: Step,
434    {
435        let (Some(a), Some(b)) = (self.rows.get(a), self.rows.get(b)) else {
436            return true;
437        };
438        a.disjoint(b)
439    }
440
441    pub fn insert_all_into_row(&mut self, row: R) {
442        self.ensure_row(row).insert_all();
443    }
444
445    pub fn insert_range(&mut self, row: R, range: impl RangeBounds<C> + Clone) {
446        self.ensure_row(row).insert_range(range);
447    }
448
449    pub fn insert(&mut self, row: R, point: C) -> bool {
450        self.ensure_row(row).insert(point)
451    }
452
453    pub fn append(&mut self, row: R, point: C) {
454        self.ensure_row(row).append(point)
455    }
456
457    pub fn append_range(&mut self, row: R, point: impl RangeBounds<C> + Clone) {
458        self.ensure_row(row).append_range(point)
459    }
460
461    pub fn contains(&self, row: R, point: C) -> bool {
462        self.row(row).is_some_and(|r| r.contains(point))
463    }
464}