Skip to main content

core/ops/
index_range.rs

1use crate::iter::{FusedIterator, TrustedLen};
2use crate::num::NonZero;
3use crate::ops::{NeverShortCircuit, Try};
4use crate::ub_checks;
5
6/// Like a `Range<usize>`, but with a safety invariant that `start <= end`.
7///
8/// This means that `end - start` cannot overflow, allowing some μoptimizations.
9///
10/// (Normal `Range` code needs to handle degenerate ranges like `10..0`,
11///  which takes extra checks compared to only handling the canonical form.)
12#[derive(Debug)]
13#[derive_const(Clone, Eq, PartialEq)]
14#[ferrocene::prevalidated]
15pub(crate) struct IndexRange {
16    start: usize,
17    end: usize,
18}
19
20impl IndexRange {
21    /// # Safety
22    /// - `start <= end`
23    #[inline]
24    #[track_caller]
25    #[ferrocene::prevalidated]
26    pub(crate) const unsafe fn new_unchecked(start: usize, end: usize) -> Self {
27        ub_checks::assert_unsafe_precondition!(
28            check_library_ub,
29            "IndexRange::new_unchecked requires `start <= end`",
30            (start: usize = start, end: usize = end) => start <= end,
31        );
32        IndexRange { start, end }
33    }
34
35    #[inline]
36    #[ferrocene::prevalidated]
37    pub(crate) const fn zero_to(end: usize) -> Self {
38        IndexRange { start: 0, end }
39    }
40
41    #[inline]
42    #[ferrocene::prevalidated]
43    pub(crate) const fn start(&self) -> usize {
44        self.start
45    }
46
47    #[inline]
48    #[ferrocene::prevalidated]
49    pub(crate) const fn end(&self) -> usize {
50        self.end
51    }
52
53    #[inline]
54    #[ferrocene::prevalidated]
55    pub(crate) const fn len(&self) -> usize {
56        // SAFETY: By invariant, this cannot wrap
57        // Using the intrinsic because a UB check here impedes LLVM optimization. (#131563)
58        unsafe { crate::intrinsics::unchecked_sub(self.end, self.start) }
59    }
60
61    /// # Safety
62    /// - Can only be called when `start < end`, aka when `len > 0`.
63    #[inline]
64    #[ferrocene::prevalidated]
65    const unsafe fn next_unchecked(&mut self) -> usize {
66        debug_assert!(self.start < self.end);
67
68        let value = self.start;
69        // SAFETY: The range isn't empty, so this cannot overflow
70        self.start = unsafe { value.unchecked_add(1) };
71        value
72    }
73
74    /// # Safety
75    /// - Can only be called when `start < end`, aka when `len > 0`.
76    #[inline]
77    #[ferrocene::prevalidated]
78    const unsafe fn next_back_unchecked(&mut self) -> usize {
79        debug_assert!(self.start < self.end);
80
81        // SAFETY: The range isn't empty, so this cannot overflow
82        let value = unsafe { self.end.unchecked_sub(1) };
83        self.end = value;
84        value
85    }
86
87    /// Removes the first `n` items from this range, returning them as an `IndexRange`.
88    /// If there are fewer than `n`, then the whole range is returned and
89    /// `self` is left empty.
90    ///
91    /// This is designed to help implement `Iterator::advance_by`.
92    #[inline]
93    #[ferrocene::prevalidated]
94    pub(crate) fn take_prefix(&mut self, n: usize) -> Self {
95        let mid = if n <= self.len() {
96            // SAFETY: We just checked that this will be between start and end,
97            // and thus the addition cannot overflow.
98            // Using the intrinsic avoids a superfluous UB check.
99            unsafe { crate::intrinsics::unchecked_add(self.start, n) }
100        } else {
101            self.end
102        };
103        let prefix = Self { start: self.start, end: mid };
104        self.start = mid;
105        prefix
106    }
107
108    /// Removes the last `n` items from this range, returning them as an `IndexRange`.
109    /// If there are fewer than `n`, then the whole range is returned and
110    /// `self` is left empty.
111    ///
112    /// This is designed to help implement `Iterator::advance_back_by`.
113    #[inline]
114    #[ferrocene::prevalidated]
115    pub(crate) fn take_suffix(&mut self, n: usize) -> Self {
116        let mid = if n <= self.len() {
117            // SAFETY: We just checked that this will be between start and end,
118            // and thus the subtraction cannot overflow.
119            // Using the intrinsic avoids a superfluous UB check.
120            unsafe { crate::intrinsics::unchecked_sub(self.end, n) }
121        } else {
122            self.start
123        };
124        let suffix = Self { start: mid, end: self.end };
125        self.end = mid;
126        suffix
127    }
128
129    #[inline]
130    #[ferrocene::prevalidated]
131    const fn assume_range(&self) {
132        // SAFETY: This is the type invariant
133        unsafe { crate::hint::assert_unchecked(self.start <= self.end) }
134    }
135}
136
137impl Iterator for IndexRange {
138    type Item = usize;
139
140    #[inline]
141    #[ferrocene::prevalidated]
142    fn next(&mut self) -> Option<usize> {
143        if self.len() > 0 {
144            // SAFETY: We just checked that the range is non-empty
145            unsafe { Some(self.next_unchecked()) }
146        } else {
147            None
148        }
149    }
150
151    #[inline]
152    #[ferrocene::prevalidated]
153    fn size_hint(&self) -> (usize, Option<usize>) {
154        let len = self.len();
155        (len, Some(len))
156    }
157
158    #[inline]
159    #[ferrocene::prevalidated]
160    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
161        let taken = self.take_prefix(n);
162        NonZero::new(n - taken.len()).map_or(Ok(()), Err)
163    }
164
165    #[inline]
166    #[ferrocene::prevalidated]
167    fn fold<B, F: FnMut(B, usize) -> B>(mut self, init: B, f: F) -> B {
168        self.try_fold(init, NeverShortCircuit::wrap_mut_2(f)).0
169    }
170
171    #[inline]
172    #[ferrocene::prevalidated]
173    fn try_fold<B, F, R>(&mut self, mut accum: B, mut f: F) -> R
174    where
175        Self: Sized,
176        F: FnMut(B, Self::Item) -> R,
177        R: Try<Output = B>,
178    {
179        // `Range` needs to check `start < end`, but thanks to our type invariant
180        // we can loop on the stricter `start != end`.
181
182        self.assume_range();
183        while self.start != self.end {
184            // SAFETY: We just checked that the range is non-empty
185            let i = unsafe { self.next_unchecked() };
186            accum = f(accum, i)?;
187        }
188        try { accum }
189    }
190}
191
192impl DoubleEndedIterator for IndexRange {
193    #[inline]
194    #[ferrocene::prevalidated]
195    fn next_back(&mut self) -> Option<usize> {
196        if self.len() > 0 {
197            // SAFETY: We just checked that the range is non-empty
198            unsafe { Some(self.next_back_unchecked()) }
199        } else {
200            None
201        }
202    }
203
204    #[inline]
205    #[ferrocene::prevalidated]
206    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
207        let taken = self.take_suffix(n);
208        NonZero::new(n - taken.len()).map_or(Ok(()), Err)
209    }
210
211    #[inline]
212    #[ferrocene::prevalidated]
213    fn rfold<B, F: FnMut(B, usize) -> B>(mut self, init: B, f: F) -> B {
214        self.try_rfold(init, NeverShortCircuit::wrap_mut_2(f)).0
215    }
216
217    #[inline]
218    #[ferrocene::prevalidated]
219    fn try_rfold<B, F, R>(&mut self, mut accum: B, mut f: F) -> R
220    where
221        Self: Sized,
222        F: FnMut(B, Self::Item) -> R,
223        R: Try<Output = B>,
224    {
225        // `Range` needs to check `start < end`, but thanks to our type invariant
226        // we can loop on the stricter `start != end`.
227
228        self.assume_range();
229        while self.start != self.end {
230            // SAFETY: We just checked that the range is non-empty
231            let i = unsafe { self.next_back_unchecked() };
232            accum = f(accum, i)?;
233        }
234        try { accum }
235    }
236}
237
238impl ExactSizeIterator for IndexRange {
239    #[ferrocene::prevalidated]
240    #[inline]
241    fn len(&self) -> usize {
242        self.len()
243    }
244}
245
246// SAFETY: Because we only deal in `usize`, our `len` is always perfect.
247unsafe impl TrustedLen for IndexRange {}
248
249impl FusedIterator for IndexRange {}