1//! Macros used by iterators of slice.
2
3/// Convenience & performance macro for consuming the `end_or_len` field, by
4/// giving a `(&mut) usize` or `(&mut) NonNull<T>` depending whether `T` is
5/// or is not a ZST respectively.
6///
7/// Internally, this reads the `end` through a pointer-to-`NonNull` so that
8/// it'll get the appropriate non-null metadata in the backend without needing
9/// to call `assume` manually.
10macro_rules! if_zst {
11 (mut $this:ident, $len:ident => $zst_body:expr, $end:ident => $other_body:expr,) => {{
12 #![allow(unused_unsafe)] // we're sometimes used within an unsafe block
13
14 if T::IS_ZST {
15 // SAFETY: for ZSTs, the pointer is storing a provenance-free length,
16 // so consuming and updating it as a `usize` is fine.
17 let $len = unsafe { &mut *ptr::addr_of_mut!($this.end_or_len).cast::<usize>() };
18 $zst_body
19 } else {
20 // SAFETY: for non-ZSTs, the type invariant ensures it cannot be null
21 let $end = unsafe { &mut *ptr::addr_of_mut!($this.end_or_len).cast::<NonNull<T>>() };
22 $other_body
23 }
24 }};
25 ($this:ident, $len:ident => $zst_body:expr, $end:ident => $other_body:expr,) => {{
26 #![allow(unused_unsafe)] // we're sometimes used within an unsafe block
27
28 if T::IS_ZST {
29 let $len = $this.end_or_len.addr();
30 $zst_body
31 } else {
32 // SAFETY: for non-ZSTs, the type invariant ensures it cannot be null
33 let $end = unsafe { *ptr::addr_of!($this.end_or_len).cast::<NonNull<T>>() };
34 $other_body
35 }
36 }};
37}
38
39// Inlining is_empty and len makes a huge performance difference
40macro_rules! is_empty {
41 ($self: ident) => {
42 if_zst!($self,
43 len => len == 0,
44 end => $self.ptr == end,
45 )
46 };
47}
48
49macro_rules! len {
50 ($self: ident) => {{
51 if_zst!($self,
52 len => len,
53 end => {
54 // To get rid of some bounds checks (see `position`), we use ptr_sub instead of
55 // offset_from (Tested by `codegen/slice-position-bounds-check`.)
56 // SAFETY: by the type invariant pointers are aligned and `start <= end`
57 unsafe { end.sub_ptr($self.ptr) }
58 },
59 )
60 }};
61}
62
63// The shared definition of the `Iter` and `IterMut` iterators
64macro_rules! iterator {
65 (
66 struct $name:ident -> $ptr:ty,
67 $elem:ty,
68 $raw_mut:tt,
69 {$( $mut_:tt )?},
70 $into_ref:ident,
71 {$($extra:tt)*}
72 ) => {
73 // Returns the first element and moves the start of the iterator forwards by 1.
74 // Greatly improves performance compared to an inlined function. The iterator
75 // must not be empty.
76 macro_rules! next_unchecked {
77 ($self: ident) => { $self.post_inc_start(1).$into_ref() }
78 }
79
80 // Returns the last element and moves the end of the iterator backwards by 1.
81 // Greatly improves performance compared to an inlined function. The iterator
82 // must not be empty.
83 macro_rules! next_back_unchecked {
84 ($self: ident) => { $self.pre_dec_end(1).$into_ref() }
85 }
86
87 impl<'a, T> $name<'a, T> {
88 // Helper function for creating a slice from the iterator.
89 #[inline(always)]
90 fn make_slice(&self) -> &'a [T] {
91 // SAFETY: the iterator was created from a slice with pointer
92 // `self.ptr` and length `len!(self)`. This guarantees that all
93 // the prerequisites for `from_raw_parts` are fulfilled.
94 unsafe { from_raw_parts(self.ptr.as_ptr(), len!(self)) }
95 }
96
97 // Helper function for moving the start of the iterator forwards by `offset` elements,
98 // returning the old start.
99 // Unsafe because the offset must not exceed `self.len()`.
100 #[inline(always)]
101 unsafe fn post_inc_start(&mut self, offset: usize) -> NonNull<T> {
102 let old = self.ptr;
103
104 // SAFETY: the caller guarantees that `offset` doesn't exceed `self.len()`,
105 // so this new pointer is inside `self` and thus guaranteed to be non-null.
106 unsafe {
107 if_zst!(mut self,
108 len => *len = len.unchecked_sub(offset),
109 _end => self.ptr = self.ptr.add(offset),
110 );
111 }
112 old
113 }
114
115 // Helper function for moving the end of the iterator backwards by `offset` elements,
116 // returning the new end.
117 // Unsafe because the offset must not exceed `self.len()`.
118 #[inline(always)]
119 unsafe fn pre_dec_end(&mut self, offset: usize) -> NonNull<T> {
120 if_zst!(mut self,
121 // SAFETY: By our precondition, `offset` can be at most the
122 // current length, so the subtraction can never overflow.
123 len => unsafe {
124 *len = len.unchecked_sub(offset);
125 self.ptr
126 },
127 // SAFETY: the caller guarantees that `offset` doesn't exceed `self.len()`,
128 // which is guaranteed to not overflow an `isize`. Also, the resulting pointer
129 // is in bounds of `slice`, which fulfills the other requirements for `offset`.
130 end => unsafe {
131 *end = end.sub(offset);
132 *end
133 },
134 )
135 }
136 }
137
138 #[stable(feature = "rust1", since = "1.0.0")]
139 impl<T> ExactSizeIterator for $name<'_, T> {
140 #[inline(always)]
141 fn len(&self) -> usize {
142 len!(self)
143 }
144
145 #[inline(always)]
146 fn is_empty(&self) -> bool {
147 is_empty!(self)
148 }
149 }
150
151 #[stable(feature = "rust1", since = "1.0.0")]
152 impl<'a, T> Iterator for $name<'a, T> {
153 type Item = $elem;
154
155 #[inline]
156 fn next(&mut self) -> Option<$elem> {
157 // could be implemented with slices, but this avoids bounds checks
158
159 // SAFETY: The call to `next_unchecked!` is
160 // safe since we check if the iterator is empty first.
161 unsafe {
162 if is_empty!(self) {
163 None
164 } else {
165 Some(next_unchecked!(self))
166 }
167 }
168 }
169
170 #[inline]
171 fn size_hint(&self) -> (usize, Option<usize>) {
172 let exact = len!(self);
173 (exact, Some(exact))
174 }
175
176 #[inline]
177 fn count(self) -> usize {
178 len!(self)
179 }
180
181 #[inline]
182 fn nth(&mut self, n: usize) -> Option<$elem> {
183 if n >= len!(self) {
184 // This iterator is now empty.
185 if_zst!(mut self,
186 len => *len = 0,
187 end => self.ptr = *end,
188 );
189 return None;
190 }
191 // SAFETY: We are in bounds. `post_inc_start` does the right thing even for ZSTs.
192 unsafe {
193 self.post_inc_start(n);
194 Some(next_unchecked!(self))
195 }
196 }
197
198 #[inline]
199 fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
200 let advance = cmp::min(len!(self), n);
201 // SAFETY: By construction, `advance` does not exceed `self.len()`.
202 unsafe { self.post_inc_start(advance) };
203 NonZero::new(n - advance).map_or(Ok(()), Err)
204 }
205
206 #[inline]
207 fn last(mut self) -> Option<$elem> {
208 self.next_back()
209 }
210
211 #[inline]
212 fn fold<B, F>(self, init: B, mut f: F) -> B
213 where
214 F: FnMut(B, Self::Item) -> B,
215 {
216 // this implementation consists of the following optimizations compared to the
217 // default implementation:
218 // - do-while loop, as is llvm's preferred loop shape,
219 // see https://releases.llvm.org/16.0.0/docs/LoopTerminology.html#more-canonical-loops
220 // - bumps an index instead of a pointer since the latter case inhibits
221 // some optimizations, see #111603
222 // - avoids Option wrapping/matching
223 if is_empty!(self) {
224 return init;
225 }
226 let mut acc = init;
227 let mut i = 0;
228 let len = len!(self);
229 loop {
230 // SAFETY: the loop iterates `i in 0..len`, which always is in bounds of
231 // the slice allocation
232 acc = f(acc, unsafe { & $( $mut_ )? *self.ptr.add(i).as_ptr() });
233 // SAFETY: `i` can't overflow since it'll only reach usize::MAX if the
234 // slice had that length, in which case we'll break out of the loop
235 // after the increment
236 i = unsafe { i.unchecked_add(1) };
237 if i == len {
238 break;
239 }
240 }
241 acc
242 }
243
244 // We override the default implementation, which uses `try_fold`,
245 // because this simple implementation generates less LLVM IR and is
246 // faster to compile.
247 #[inline]
248 fn for_each<F>(mut self, mut f: F)
249 where
250 Self: Sized,
251 F: FnMut(Self::Item),
252 {
253 while let Some(x) = self.next() {
254 f(x);
255 }
256 }
257
258 // We override the default implementation, which uses `try_fold`,
259 // because this simple implementation generates less LLVM IR and is
260 // faster to compile.
261 #[inline]
262 fn all<F>(&mut self, mut f: F) -> bool
263 where
264 Self: Sized,
265 F: FnMut(Self::Item) -> bool,
266 {
267 while let Some(x) = self.next() {
268 if !f(x) {
269 return false;
270 }
271 }
272 true
273 }
274
275 // We override the default implementation, which uses `try_fold`,
276 // because this simple implementation generates less LLVM IR and is
277 // faster to compile.
278 #[inline]
279 fn any<F>(&mut self, mut f: F) -> bool
280 where
281 Self: Sized,
282 F: FnMut(Self::Item) -> bool,
283 {
284 while let Some(x) = self.next() {
285 if f(x) {
286 return true;
287 }
288 }
289 false
290 }
291
292 // We override the default implementation, which uses `try_fold`,
293 // because this simple implementation generates less LLVM IR and is
294 // faster to compile.
295 #[inline]
296 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
297 where
298 Self: Sized,
299 P: FnMut(&Self::Item) -> bool,
300 {
301 while let Some(x) = self.next() {
302 if predicate(&x) {
303 return Some(x);
304 }
305 }
306 None
307 }
308
309 // We override the default implementation, which uses `try_fold`,
310 // because this simple implementation generates less LLVM IR and is
311 // faster to compile.
312 #[inline]
313 fn find_map<B, F>(&mut self, mut f: F) -> Option<B>
314 where
315 Self: Sized,
316 F: FnMut(Self::Item) -> Option<B>,
317 {
318 while let Some(x) = self.next() {
319 if let Some(y) = f(x) {
320 return Some(y);
321 }
322 }
323 None
324 }
325
326 // We override the default implementation, which uses `try_fold`,
327 // because this simple implementation generates less LLVM IR and is
328 // faster to compile. Also, the `assume` avoids a bounds check.
329 #[inline]
330 #[rustc_inherit_overflow_checks]
331 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
332 Self: Sized,
333 P: FnMut(Self::Item) -> bool,
334 {
335 let n = len!(self);
336 let mut i = 0;
337 while let Some(x) = self.next() {
338 if predicate(x) {
339 // SAFETY: we are guaranteed to be in bounds by the loop invariant:
340 // when `i >= n`, `self.next()` returns `None` and the loop breaks.
341 unsafe { assert_unchecked(i < n) };
342 return Some(i);
343 }
344 i += 1;
345 }
346 None
347 }
348
349 // We override the default implementation, which uses `try_fold`,
350 // because this simple implementation generates less LLVM IR and is
351 // faster to compile. Also, the `assume` avoids a bounds check.
352 #[inline]
353 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
354 P: FnMut(Self::Item) -> bool,
355 Self: Sized + ExactSizeIterator + DoubleEndedIterator
356 {
357 let n = len!(self);
358 let mut i = n;
359 while let Some(x) = self.next_back() {
360 i -= 1;
361 if predicate(x) {
362 // SAFETY: `i` must be lower than `n` since it starts at `n`
363 // and is only decreasing.
364 unsafe { assert_unchecked(i < n) };
365 return Some(i);
366 }
367 }
368 None
369 }
370
371 #[inline]
372 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
373 // SAFETY: the caller must guarantee that `i` is in bounds of
374 // the underlying slice, so `i` cannot overflow an `isize`, and
375 // the returned references is guaranteed to refer to an element
376 // of the slice and thus guaranteed to be valid.
377 //
378 // Also note that the caller also guarantees that we're never
379 // called with the same index again, and that no other methods
380 // that will access this subslice are called, so it is valid
381 // for the returned reference to be mutable in the case of
382 // `IterMut`
383 unsafe { & $( $mut_ )? * self.ptr.as_ptr().add(idx) }
384 }
385
386 $($extra)*
387 }
388
389 #[stable(feature = "rust1", since = "1.0.0")]
390 impl<'a, T> DoubleEndedIterator for $name<'a, T> {
391 #[inline]
392 fn next_back(&mut self) -> Option<$elem> {
393 // could be implemented with slices, but this avoids bounds checks
394
395 // SAFETY: The call to `next_back_unchecked!`
396 // is safe since we check if the iterator is empty first.
397 unsafe {
398 if is_empty!(self) {
399 None
400 } else {
401 Some(next_back_unchecked!(self))
402 }
403 }
404 }
405
406 #[inline]
407 fn nth_back(&mut self, n: usize) -> Option<$elem> {
408 if n >= len!(self) {
409 // This iterator is now empty.
410 if_zst!(mut self,
411 len => *len = 0,
412 end => *end = self.ptr,
413 );
414 return None;
415 }
416 // SAFETY: We are in bounds. `pre_dec_end` does the right thing even for ZSTs.
417 unsafe {
418 self.pre_dec_end(n);
419 Some(next_back_unchecked!(self))
420 }
421 }
422
423 #[inline]
424 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
425 let advance = cmp::min(len!(self), n);
426 // SAFETY: By construction, `advance` does not exceed `self.len()`.
427 unsafe { self.pre_dec_end(advance) };
428 NonZero::new(n - advance).map_or(Ok(()), Err)
429 }
430 }
431
432 #[stable(feature = "fused", since = "1.26.0")]
433 impl<T> FusedIterator for $name<'_, T> {}
434
435 #[unstable(feature = "trusted_len", issue = "37572")]
436 unsafe impl<T> TrustedLen for $name<'_, T> {}
437
438 impl<'a, T> UncheckedIterator for $name<'a, T> {
439 unsafe fn next_unchecked(&mut self) -> $elem {
440 // SAFETY: The caller promised there's at least one more item.
441 unsafe {
442 next_unchecked!(self)
443 }
444 }
445 }
446
447 #[stable(feature = "default_iters", since = "1.70.0")]
448 impl<T> Default for $name<'_, T> {
449 /// Creates an empty slice iterator.
450 ///
451 /// ```
452 #[doc = concat!("# use core::slice::", stringify!($name), ";")]
453 #[doc = concat!("let iter: ", stringify!($name<'_, u8>), " = Default::default();")]
454 /// assert_eq!(iter.len(), 0);
455 /// ```
456 fn default() -> Self {
457 (& $( $mut_ )? []).into_iter()
458 }
459 }
460 }
461}
462
463macro_rules! forward_iterator {
464 ($name:ident: $elem:ident, $iter_of:ty) => {
465 #[stable(feature = "rust1", since = "1.0.0")]
466 impl<'a, $elem, P> Iterator for $name<'a, $elem, P>
467 where
468 P: FnMut(&T) -> bool,
469 {
470 type Item = $iter_of;
471
472 #[inline]
473 fn next(&mut self) -> Option<$iter_of> {
474 self.inner.next()
475 }
476
477 #[inline]
478 fn size_hint(&self) -> (usize, Option<usize>) {
479 self.inner.size_hint()
480 }
481 }
482
483 #[stable(feature = "fused", since = "1.26.0")]
484 impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P> where P: FnMut(&T) -> bool {}
485 };
486}
487