1use crate::iter::{FusedIterator, TrustedLen};
2use crate::num::NonZero;
3use crate::ub_checks;
4
5/// Like a `Range<usize>`, but with a safety invariant that `start <= end`.
6///
7/// This means that `end - start` cannot overflow, allowing some μoptimizations.
8///
9/// (Normal `Range` code needs to handle degenerate ranges like `10..0`,
10/// which takes extra checks compared to only handling the canonical form.)
11#[derive(Clone, Debug, PartialEq, Eq)]
12pub(crate) struct IndexRange {
13 start: usize,
14 end: usize,
15}
16
17impl IndexRange {
18 /// # Safety
19 /// - `start <= end`
20 #[inline]
21 pub(crate) const unsafe fn new_unchecked(start: usize, end: usize) -> Self {
22 ub_checks::assert_unsafe_precondition!(
23 check_library_ub,
24 "IndexRange::new_unchecked requires `start <= end`",
25 (start: usize = start, end: usize = end) => start <= end,
26 );
27 IndexRange { start, end }
28 }
29
30 #[inline]
31 pub(crate) const fn zero_to(end: usize) -> Self {
32 IndexRange { start: 0, end }
33 }
34
35 #[inline]
36 pub(crate) const fn start(&self) -> usize {
37 self.start
38 }
39
40 #[inline]
41 pub(crate) const fn end(&self) -> usize {
42 self.end
43 }
44
45 #[inline]
46 pub(crate) const fn len(&self) -> usize {
47 // SAFETY: By invariant, this cannot wrap
48 // Using the intrinsic because a UB check here impedes LLVM optimization. (#131563)
49 unsafe { crate::intrinsics::unchecked_sub(self.end, self.start) }
50 }
51
52 /// # Safety
53 /// - Can only be called when `start < end`, aka when `len > 0`.
54 #[inline]
55 unsafe fn next_unchecked(&mut self) -> usize {
56 debug_assert!(self.start < self.end);
57
58 let value = self.start;
59 // SAFETY: The range isn't empty, so this cannot overflow
60 self.start = unsafe { value.unchecked_add(1) };
61 value
62 }
63
64 /// # Safety
65 /// - Can only be called when `start < end`, aka when `len > 0`.
66 #[inline]
67 unsafe fn next_back_unchecked(&mut self) -> usize {
68 debug_assert!(self.start < self.end);
69
70 // SAFETY: The range isn't empty, so this cannot overflow
71 let value = unsafe { self.end.unchecked_sub(1) };
72 self.end = value;
73 value
74 }
75
76 /// Removes the first `n` items from this range, returning them as an `IndexRange`.
77 /// If there are fewer than `n`, then the whole range is returned and
78 /// `self` is left empty.
79 ///
80 /// This is designed to help implement `Iterator::advance_by`.
81 #[inline]
82 pub(crate) fn take_prefix(&mut self, n: usize) -> Self {
83 let mid = if n <= self.len() {
84 // SAFETY: We just checked that this will be between start and end,
85 // and thus the addition cannot overflow.
86 // Using the intrinsic avoids a superfluous UB check.
87 unsafe { crate::intrinsics::unchecked_add(self.start, n) }
88 } else {
89 self.end
90 };
91 let prefix = Self { start: self.start, end: mid };
92 self.start = mid;
93 prefix
94 }
95
96 /// Removes the last `n` items from this range, returning them as an `IndexRange`.
97 /// If there are fewer than `n`, then the whole range is returned and
98 /// `self` is left empty.
99 ///
100 /// This is designed to help implement `Iterator::advance_back_by`.
101 #[inline]
102 pub(crate) fn take_suffix(&mut self, n: usize) -> Self {
103 let mid = if n <= self.len() {
104 // SAFETY: We just checked that this will be between start and end,
105 // and thus the subtraction cannot overflow.
106 // Using the intrinsic avoids a superfluous UB check.
107 unsafe { crate::intrinsics::unchecked_sub(self.end, n) }
108 } else {
109 self.start
110 };
111 let suffix = Self { start: mid, end: self.end };
112 self.end = mid;
113 suffix
114 }
115}
116
117impl Iterator for IndexRange {
118 type Item = usize;
119
120 #[inline]
121 fn next(&mut self) -> Option<usize> {
122 if self.len() > 0 {
123 // SAFETY: We just checked that the range is non-empty
124 unsafe { Some(self.next_unchecked()) }
125 } else {
126 None
127 }
128 }
129
130 #[inline]
131 fn size_hint(&self) -> (usize, Option<usize>) {
132 let len = self.len();
133 (len, Some(len))
134 }
135
136 #[inline]
137 fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
138 let taken = self.take_prefix(n);
139 NonZero::new(n - taken.len()).map_or(Ok(()), Err)
140 }
141}
142
143impl DoubleEndedIterator for IndexRange {
144 #[inline]
145 fn next_back(&mut self) -> Option<usize> {
146 if self.len() > 0 {
147 // SAFETY: We just checked that the range is non-empty
148 unsafe { Some(self.next_back_unchecked()) }
149 } else {
150 None
151 }
152 }
153
154 #[inline]
155 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
156 let taken: IndexRange = self.take_suffix(n);
157 NonZero::new(n - taken.len()).map_or(default:Ok(()), f:Err)
158 }
159}
160
161impl ExactSizeIterator for IndexRange {
162 #[inline]
163 fn len(&self) -> usize {
164 self.len()
165 }
166}
167
168// SAFETY: Because we only deal in `usize`, our `len` is always perfect.
169unsafe impl TrustedLen for IndexRange {}
170
171impl FusedIterator for IndexRange {}
172