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 *(&raw 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 *(&raw 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 { mem::transmute::<*const T, NonNull<T>>($this.end_or_len) };
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.offset_from_unsigned($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 $array_ref:ident,
72 {$($extra:tt)*}
73 ) => {
74 impl<'a, T> $name<'a, T> {
75 /// Returns the last element and moves the end of the iterator backwards by 1.
76 ///
77 /// # Safety
78 ///
79 /// The iterator must not be empty
80 #[inline]
81 unsafe fn next_back_unchecked(&mut self) -> $elem {
82 // SAFETY: the caller promised it's not empty, so
83 // the offsetting is in-bounds and there's an element to return.
84 unsafe { self.pre_dec_end(1).$into_ref() }
85 }
86
87 // Helper function for creating a slice from the iterator.
88 #[inline(always)]
89 fn make_slice(&self) -> &'a [T] {
90 // SAFETY: the iterator was created from a slice with pointer
91 // `self.ptr` and length `len!(self)`. This guarantees that all
92 // the prerequisites for `from_raw_parts` are fulfilled.
93 unsafe { from_raw_parts(self.ptr.as_ptr(), len!(self)) }
94 }
95
96 // Helper function for moving the start of the iterator forwards by `offset` elements,
97 // returning the old start.
98 // Unsafe because the offset must not exceed `self.len()`.
99 #[inline(always)]
100 unsafe fn post_inc_start(&mut self, offset: usize) -> NonNull<T> {
101 let old = self.ptr;
102
103 // SAFETY: the caller guarantees that `offset` doesn't exceed `self.len()`,
104 // so this new pointer is inside `self` and thus guaranteed to be non-null.
105 unsafe {
106 if_zst!(mut self,
107 // Using the intrinsic directly avoids emitting a UbCheck
108 len => *len = crate::intrinsics::unchecked_sub(*len, 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 // Using the intrinsic directly avoids emitting a UbCheck
125 *len = crate::intrinsics::unchecked_sub(*len, offset);
126 self.ptr
127 },
128 // SAFETY: the caller guarantees that `offset` doesn't exceed `self.len()`,
129 // which is guaranteed to not overflow an `isize`. Also, the resulting pointer
130 // is in bounds of `slice`, which fulfills the other requirements for `offset`.
131 end => unsafe {
132 *end = end.sub(offset);
133 *end
134 },
135 )
136 }
137 }
138
139 #[stable(feature = "rust1", since = "1.0.0")]
140 impl<T> ExactSizeIterator for $name<'_, T> {
141 #[inline(always)]
142 fn len(&self) -> usize {
143 len!(self)
144 }
145
146 #[inline(always)]
147 fn is_empty(&self) -> bool {
148 is_empty!(self)
149 }
150 }
151
152 #[stable(feature = "rust1", since = "1.0.0")]
153 impl<'a, T> Iterator for $name<'a, T> {
154 type Item = $elem;
155
156 #[inline]
157 fn next(&mut self) -> Option<$elem> {
158 // intentionally not using the helpers because this is
159 // one of the most mono'd things in the library.
160
161 let ptr = self.ptr;
162 let end_or_len = self.end_or_len;
163 // SAFETY: See inner comments. (For some reason having multiple
164 // block breaks inlining this -- if you can fix that please do!)
165 unsafe {
166 if T::IS_ZST {
167 let len = end_or_len.addr();
168 if len == 0 {
169 return None;
170 }
171 // SAFETY: just checked that it's not zero, so subtracting one
172 // cannot wrap. (Ideally this would be `checked_sub`, which
173 // does the same thing internally, but as of 2025-02 that
174 // doesn't optimize quite as small in MIR.)
175 self.end_or_len = without_provenance_mut(len.unchecked_sub(1));
176 } else {
177 // SAFETY: by type invariant, the `end_or_len` field is always
178 // non-null for a non-ZST pointee. (This transmute ensures we
179 // get `!nonnull` metadata on the load of the field.)
180 if ptr == crate::intrinsics::transmute::<$ptr, NonNull<T>>(end_or_len) {
181 return None;
182 }
183 // SAFETY: since it's not empty, per the check above, moving
184 // forward one keeps us inside the slice, and this is valid.
185 self.ptr = ptr.add(1);
186 }
187 // SAFETY: Now that we know it wasn't empty and we've moved past
188 // the first one (to avoid giving a duplicate `&mut` next time),
189 // we can give out a reference to it.
190 Some({ptr}.$into_ref())
191 }
192 }
193
194 fn next_chunk<const N:usize>(&mut self) -> Result<[$elem; N], crate::array::IntoIter<$elem, N>> {
195 if T::IS_ZST {
196 return crate::array::iter_next_chunk(self);
197 }
198 let len = len!(self);
199 if len >= N {
200 // SAFETY: we are just getting an array of [T; N] and moving the pointer over a little
201 let r = unsafe { self.post_inc_start(N).cast_array().$into_ref() }
202 .$array_ref(); // must convert &[T; N] to [&T; N]
203 Ok(r)
204 } else {
205 // cant use $array_ref because theres no builtin for &mut [MU<T>; N] -> [&mut MU<T>; N]
206 // cant use copy_nonoverlapping as the $elem is of type &{mut} T instead of T
207 let mut a = [const { crate::mem::MaybeUninit::<$elem>::uninit() }; N];
208 for into in (&mut a).into_iter().take(len) {
209 // SAFETY: take(n) limits to remainder (slice produces worse codegen)
210 into.write(unsafe { self.post_inc_start(1).$into_ref() });
211 }
212 // SAFETY: we just initialized elements 0..len
213 unsafe { Err(crate::array::IntoIter::new_unchecked(a, 0..len)) }
214 }
215 }
216
217 #[inline]
218 fn size_hint(&self) -> (usize, Option<usize>) {
219 let exact = len!(self);
220 (exact, Some(exact))
221 }
222
223 #[inline]
224 fn count(self) -> usize {
225 len!(self)
226 }
227
228 #[inline]
229 fn nth(&mut self, n: usize) -> Option<$elem> {
230 if n >= len!(self) {
231 // This iterator is now empty.
232 if_zst!(mut self,
233 len => *len = 0,
234 end => self.ptr = *end,
235 );
236 return None;
237 }
238 // SAFETY: We are in bounds. `post_inc_start` does the right thing even for ZSTs.
239 unsafe {
240 self.post_inc_start(n);
241 Some(self.next_unchecked())
242 }
243 }
244
245 #[inline]
246 fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
247 let advance = cmp::min(len!(self), n);
248 // SAFETY: By construction, `advance` does not exceed `self.len()`.
249 unsafe { self.post_inc_start(advance) };
250 NonZero::new(n - advance).map_or(Ok(()), Err)
251 }
252
253 #[inline]
254 fn last(mut self) -> Option<$elem> {
255 self.next_back()
256 }
257
258 #[inline]
259 fn fold<B, F>(self, init: B, mut f: F) -> B
260 where
261 F: FnMut(B, Self::Item) -> B,
262 {
263 // this implementation consists of the following optimizations compared to the
264 // default implementation:
265 // - do-while loop, as is llvm's preferred loop shape,
266 // see https://releases.llvm.org/16.0.0/docs/LoopTerminology.html#more-canonical-loops
267 // - bumps an index instead of a pointer since the latter case inhibits
268 // some optimizations, see #111603
269 // - avoids Option wrapping/matching
270 if is_empty!(self) {
271 return init;
272 }
273 let mut acc = init;
274 let mut i = 0;
275 let len = len!(self);
276 loop {
277 // SAFETY: the loop iterates `i in 0..len`, which always is in bounds of
278 // the slice allocation
279 acc = f(acc, unsafe { & $( $mut_ )? *self.ptr.add(i).as_ptr() });
280 // SAFETY: `i` can't overflow since it'll only reach usize::MAX if the
281 // slice had that length, in which case we'll break out of the loop
282 // after the increment
283 i = unsafe { i.unchecked_add(1) };
284 if i == len {
285 break;
286 }
287 }
288 acc
289 }
290
291 // We override the default implementation, which uses `try_fold`,
292 // because this simple implementation generates less LLVM IR and is
293 // faster to compile.
294 #[inline]
295 fn for_each<F>(mut self, mut f: F)
296 where
297 Self: Sized,
298 F: FnMut(Self::Item),
299 {
300 while let Some(x) = self.next() {
301 f(x);
302 }
303 }
304
305 // We override the default implementation, which uses `try_fold`,
306 // because this simple implementation generates less LLVM IR and is
307 // faster to compile.
308 #[inline]
309 fn all<F>(&mut self, mut f: F) -> bool
310 where
311 Self: Sized,
312 F: FnMut(Self::Item) -> bool,
313 {
314 while let Some(x) = self.next() {
315 if !f(x) {
316 return false;
317 }
318 }
319 true
320 }
321
322 // We override the default implementation, which uses `try_fold`,
323 // because this simple implementation generates less LLVM IR and is
324 // faster to compile.
325 #[inline]
326 fn any<F>(&mut self, mut f: F) -> bool
327 where
328 Self: Sized,
329 F: FnMut(Self::Item) -> bool,
330 {
331 while let Some(x) = self.next() {
332 if f(x) {
333 return true;
334 }
335 }
336 false
337 }
338
339 // We override the default implementation, which uses `try_fold`,
340 // because this simple implementation generates less LLVM IR and is
341 // faster to compile.
342 #[inline]
343 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
344 where
345 Self: Sized,
346 P: FnMut(&Self::Item) -> bool,
347 {
348 while let Some(x) = self.next() {
349 if predicate(&x) {
350 return Some(x);
351 }
352 }
353 None
354 }
355
356 // We override the default implementation, which uses `try_fold`,
357 // because this simple implementation generates less LLVM IR and is
358 // faster to compile.
359 #[inline]
360 fn find_map<B, F>(&mut self, mut f: F) -> Option<B>
361 where
362 Self: Sized,
363 F: FnMut(Self::Item) -> Option<B>,
364 {
365 while let Some(x) = self.next() {
366 if let Some(y) = f(x) {
367 return Some(y);
368 }
369 }
370 None
371 }
372
373 // We override the default implementation, which uses `try_fold`,
374 // because this simple implementation generates less LLVM IR and is
375 // faster to compile. Also, the `assume` avoids a bounds check.
376 #[inline]
377 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
378 Self: Sized,
379 P: FnMut(Self::Item) -> bool,
380 {
381 let n = len!(self);
382 let mut i = 0;
383 while let Some(x) = self.next() {
384 if predicate(x) {
385 // SAFETY: we are guaranteed to be in bounds by the loop invariant:
386 // when `i >= n`, `self.next()` returns `None` and the loop breaks.
387 unsafe { assert_unchecked(i < n) };
388 return Some(i);
389 }
390 i += 1;
391 }
392 None
393 }
394
395 // We override the default implementation, which uses `try_fold`,
396 // because this simple implementation generates less LLVM IR and is
397 // faster to compile. Also, the `assume` avoids a bounds check.
398 #[inline]
399 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
400 P: FnMut(Self::Item) -> bool,
401 Self: Sized + ExactSizeIterator + DoubleEndedIterator
402 {
403 let n = len!(self);
404 let mut i = n;
405 while let Some(x) = self.next_back() {
406 i -= 1;
407 if predicate(x) {
408 // SAFETY: `i` must be lower than `n` since it starts at `n`
409 // and is only decreasing.
410 unsafe { assert_unchecked(i < n) };
411 return Some(i);
412 }
413 }
414 None
415 }
416
417 #[inline]
418 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
419 // SAFETY: the caller must guarantee that `i` is in bounds of
420 // the underlying slice, so `i` cannot overflow an `isize`, and
421 // the returned references is guaranteed to refer to an element
422 // of the slice and thus guaranteed to be valid.
423 //
424 // Also note that the caller also guarantees that we're never
425 // called with the same index again, and that no other methods
426 // that will access this subslice are called, so it is valid
427 // for the returned reference to be mutable in the case of
428 // `IterMut`
429 unsafe { & $( $mut_ )? * self.ptr.as_ptr().add(idx) }
430 }
431
432 $($extra)*
433 }
434
435 #[stable(feature = "rust1", since = "1.0.0")]
436 impl<'a, T> DoubleEndedIterator for $name<'a, T> {
437 #[inline]
438 fn next_back(&mut self) -> Option<$elem> {
439 // could be implemented with slices, but this avoids bounds checks
440
441 // SAFETY: The call to `next_back_unchecked`
442 // is safe since we check if the iterator is empty first.
443 unsafe {
444 if is_empty!(self) {
445 None
446 } else {
447 Some(self.next_back_unchecked())
448 }
449 }
450 }
451
452 #[inline]
453 fn nth_back(&mut self, n: usize) -> Option<$elem> {
454 if n >= len!(self) {
455 // This iterator is now empty.
456 if_zst!(mut self,
457 len => *len = 0,
458 end => *end = self.ptr,
459 );
460 return None;
461 }
462 // SAFETY: We are in bounds. `pre_dec_end` does the right thing even for ZSTs.
463 unsafe {
464 self.pre_dec_end(n);
465 Some(self.next_back_unchecked())
466 }
467 }
468
469 #[inline]
470 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
471 let advance = cmp::min(len!(self), n);
472 // SAFETY: By construction, `advance` does not exceed `self.len()`.
473 unsafe { self.pre_dec_end(advance) };
474 NonZero::new(n - advance).map_or(Ok(()), Err)
475 }
476 }
477
478 #[stable(feature = "fused", since = "1.26.0")]
479 impl<T> FusedIterator for $name<'_, T> {}
480
481 #[unstable(feature = "trusted_len", issue = "37572")]
482 unsafe impl<T> TrustedLen for $name<'_, T> {}
483
484 impl<'a, T> UncheckedIterator for $name<'a, T> {
485 #[inline]
486 unsafe fn next_unchecked(&mut self) -> $elem {
487 // SAFETY: The caller promised there's at least one more item.
488 unsafe {
489 self.post_inc_start(1).$into_ref()
490 }
491 }
492 }
493
494 #[stable(feature = "default_iters", since = "1.70.0")]
495 impl<T> Default for $name<'_, T> {
496 /// Creates an empty slice iterator.
497 ///
498 /// ```
499 #[doc = concat!("# use core::slice::", stringify!($name), ";")]
500 #[doc = concat!("let iter: ", stringify!($name<'_, u8>), " = Default::default();")]
501 /// assert_eq!(iter.len(), 0);
502 /// ```
503 fn default() -> Self {
504 (& $( $mut_ )? []).into_iter()
505 }
506 }
507 }
508}
509
510macro_rules! forward_iterator {
511 ($name:ident: $elem:ident, $iter_of:ty) => {
512 #[stable(feature = "rust1", since = "1.0.0")]
513 impl<'a, $elem, P> Iterator for $name<'a, $elem, P>
514 where
515 P: FnMut(&T) -> bool,
516 {
517 type Item = $iter_of;
518
519 #[inline]
520 fn next(&mut self) -> Option<$iter_of> {
521 self.inner.next()
522 }
523
524 #[inline]
525 fn size_hint(&self) -> (usize, Option<usize>) {
526 self.inner.size_hint()
527 }
528 }
529
530 #[stable(feature = "fused", since = "1.26.0")]
531 impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P> where P: FnMut(&T) -> bool {}
532 };
533}
534