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. |
10 | macro_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 |
40 | macro_rules! is_empty { |
41 | ($self: ident) => { |
42 | if_zst!($self, |
43 | len => len == 0, |
44 | end => $self.ptr == end, |
45 | ) |
46 | }; |
47 | } |
48 | |
49 | macro_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 |
64 | macro_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 | |
463 | macro_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 | |