1 //! Macros used by iterators of slice.
3 // Inlining is_empty and len makes a huge performance difference
4 macro_rules! is_empty {
5 // The way we encode the length of a ZST iterator, this works both for ZST
8 $self.ptr.as_ptr() as *const T == $self.end
12 // To get rid of some bounds checks (see `position`), we compute the length in a somewhat
13 // unexpected way. (Tested by `codegen/slice-position-bounds-check`.)
16 #![allow(unused_unsafe)] // we're sometimes used within an unsafe block
18 let start = $self.ptr;
19 let size = size_from_ptr(start.as_ptr());
21 // This _cannot_ use `unchecked_sub` because we depend on wrapping
22 // to represent the length of long ZST slice iterators.
23 $self.end.addr().wrapping_sub(start.as_ptr().addr())
25 // We know that `start <= end`, so can do better than `offset_from`,
26 // which needs to deal in signed. By setting appropriate flags here
27 // we can tell LLVM this, which helps it remove bounds checks.
28 // SAFETY: By the type invariant, `start <= end`
29 let diff = unsafe { unchecked_sub($self.end.addr(), start.as_ptr().addr()) };
30 // By also telling LLVM that the pointers are apart by an exact
31 // multiple of the type size, it can optimize `len() == 0` down to
32 // `start == end` instead of `(end - start) < size`.
33 // SAFETY: By the type invariant, the pointers are aligned so the
34 // distance between them must be a multiple of pointee size
35 unsafe { exact_div(diff, size) }
40 // The shared definition of the `Iter` and `IterMut` iterators
41 macro_rules! iterator {
43 struct $name:ident -> $ptr:ty,
49 // Returns the first element and moves the start of the iterator forwards by 1.
50 // Greatly improves performance compared to an inlined function. The iterator
52 macro_rules! next_unchecked {
53 ($self: ident) => {& $( $mut_ )? *$self.post_inc_start(1)}
56 // Returns the last element and moves the end of the iterator backwards by 1.
57 // Greatly improves performance compared to an inlined function. The iterator
59 macro_rules! next_back_unchecked {
60 ($self: ident) => {& $( $mut_ )? *$self.pre_dec_end(1)}
63 // Shrinks the iterator when T is a ZST, by moving the end of the iterator
64 // backwards by `n`. `n` must not exceed `self.len()`.
65 macro_rules! zst_shrink {
66 ($self: ident, $n: ident) => {
67 $self.end = $self.end.wrapping_byte_sub($n);
71 impl<'a, T> $name<'a, T> {
72 // Helper function for creating a slice from the iterator.
74 fn make_slice(&self) -> &'a [T] {
75 // SAFETY: the iterator was created from a slice with pointer
76 // `self.ptr` and length `len!(self)`. This guarantees that all
77 // the prerequisites for `from_raw_parts` are fulfilled.
78 unsafe { from_raw_parts(self.ptr.as_ptr(), len!(self)) }
81 // Helper function for moving the start of the iterator forwards by `offset` elements,
82 // returning the old start.
83 // Unsafe because the offset must not exceed `self.len()`.
85 unsafe fn post_inc_start(&mut self, offset: usize) -> * $raw_mut T {
86 if mem::size_of::<T>() == 0 {
87 zst_shrink!(self, offset);
90 let old = self.ptr.as_ptr();
91 // SAFETY: the caller guarantees that `offset` doesn't exceed `self.len()`,
92 // so this new pointer is inside `self` and thus guaranteed to be non-null.
93 self.ptr = unsafe { NonNull::new_unchecked(self.ptr.as_ptr().add(offset)) };
98 // Helper function for moving the end of the iterator backwards by `offset` elements,
99 // returning the new end.
100 // Unsafe because the offset must not exceed `self.len()`.
102 unsafe fn pre_dec_end(&mut self, offset: usize) -> * $raw_mut T {
104 zst_shrink!(self, offset);
107 // SAFETY: the caller guarantees that `offset` doesn't exceed `self.len()`,
108 // which is guaranteed to not overflow an `isize`. Also, the resulting pointer
109 // is in bounds of `slice`, which fulfills the other requirements for `offset`.
110 self.end = unsafe { self.end.sub(offset) };
116 #[stable(feature = "rust1", since = "1.0.0")]
117 impl<T> ExactSizeIterator for $name<'_, T> {
119 fn len(&self) -> usize {
124 fn is_empty(&self) -> bool {
129 #[stable(feature = "rust1", since = "1.0.0")]
130 impl<'a, T> Iterator for $name<'a, T> {
134 fn next(&mut self) -> Option<$elem> {
135 // could be implemented with slices, but this avoids bounds checks
137 // SAFETY: `assume` calls are safe since a slice's start pointer
138 // must be non-null, and slices over non-ZSTs must also have a
139 // non-null end pointer. The call to `next_unchecked!` is safe
140 // since we check if the iterator is empty first.
142 assume(!self.ptr.as_ptr().is_null());
144 assume(!self.end.is_null());
149 Some(next_unchecked!(self))
155 fn size_hint(&self) -> (usize, Option<usize>) {
156 let exact = len!(self);
161 fn count(self) -> usize {
166 fn nth(&mut self, n: usize) -> Option<$elem> {
168 // This iterator is now empty.
170 // We have to do it this way as `ptr` may never be 0, but `end`
171 // could be (due to wrapping).
172 self.end = self.ptr.as_ptr();
174 // SAFETY: end can't be 0 if T isn't ZST because ptr isn't 0 and end >= ptr
176 self.ptr = NonNull::new_unchecked(self.end as *mut T);
181 // SAFETY: We are in bounds. `post_inc_start` does the right thing even for ZSTs.
183 self.post_inc_start(n);
184 Some(next_unchecked!(self))
189 fn advance_by(&mut self, n: usize) -> Result<(), usize> {
190 let advance = cmp::min(len!(self), n);
191 // SAFETY: By construction, `advance` does not exceed `self.len()`.
192 unsafe { self.post_inc_start(advance) };
193 if advance == n { Ok(()) } else { Err(advance) }
197 fn last(mut self) -> Option<$elem> {
201 // We override the default implementation, which uses `try_fold`,
202 // because this simple implementation generates less LLVM IR and is
203 // faster to compile.
205 fn for_each<F>(mut self, mut f: F)
208 F: FnMut(Self::Item),
210 while let Some(x) = self.next() {
215 // We override the default implementation, which uses `try_fold`,
216 // because this simple implementation generates less LLVM IR and is
217 // faster to compile.
219 fn all<F>(&mut self, mut f: F) -> bool
222 F: FnMut(Self::Item) -> bool,
224 while let Some(x) = self.next() {
232 // We override the default implementation, which uses `try_fold`,
233 // because this simple implementation generates less LLVM IR and is
234 // faster to compile.
236 fn any<F>(&mut self, mut f: F) -> bool
239 F: FnMut(Self::Item) -> bool,
241 while let Some(x) = self.next() {
249 // We override the default implementation, which uses `try_fold`,
250 // because this simple implementation generates less LLVM IR and is
251 // faster to compile.
253 fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
256 P: FnMut(&Self::Item) -> bool,
258 while let Some(x) = self.next() {
266 // We override the default implementation, which uses `try_fold`,
267 // because this simple implementation generates less LLVM IR and is
268 // faster to compile.
270 fn find_map<B, F>(&mut self, mut f: F) -> Option<B>
273 F: FnMut(Self::Item) -> Option<B>,
275 while let Some(x) = self.next() {
276 if let Some(y) = f(x) {
283 // We override the default implementation, which uses `try_fold`,
284 // because this simple implementation generates less LLVM IR and is
285 // faster to compile. Also, the `assume` avoids a bounds check.
287 #[rustc_inherit_overflow_checks]
288 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
290 P: FnMut(Self::Item) -> bool,
294 while let Some(x) = self.next() {
296 // SAFETY: we are guaranteed to be in bounds by the loop invariant:
297 // when `i >= n`, `self.next()` returns `None` and the loop breaks.
298 unsafe { assume(i < n) };
306 // We override the default implementation, which uses `try_fold`,
307 // because this simple implementation generates less LLVM IR and is
308 // faster to compile. Also, the `assume` avoids a bounds check.
310 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
311 P: FnMut(Self::Item) -> bool,
312 Self: Sized + ExactSizeIterator + DoubleEndedIterator
316 while let Some(x) = self.next_back() {
319 // SAFETY: `i` must be lower than `n` since it starts at `n`
320 // and is only decreasing.
321 unsafe { assume(i < n) };
329 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
330 // SAFETY: the caller must guarantee that `i` is in bounds of
331 // the underlying slice, so `i` cannot overflow an `isize`, and
332 // the returned references is guaranteed to refer to an element
333 // of the slice and thus guaranteed to be valid.
335 // Also note that the caller also guarantees that we're never
336 // called with the same index again, and that no other methods
337 // that will access this subslice are called, so it is valid
338 // for the returned reference to be mutable in the case of
340 unsafe { & $( $mut_ )? * self.ptr.as_ptr().add(idx) }
346 #[stable(feature = "rust1", since = "1.0.0")]
347 impl<'a, T> DoubleEndedIterator for $name<'a, T> {
349 fn next_back(&mut self) -> Option<$elem> {
350 // could be implemented with slices, but this avoids bounds checks
352 // SAFETY: `assume` calls are safe since a slice's start pointer must be non-null,
353 // and slices over non-ZSTs must also have a non-null end pointer.
354 // The call to `next_back_unchecked!` is safe since we check if the iterator is
357 assume(!self.ptr.as_ptr().is_null());
359 assume(!self.end.is_null());
364 Some(next_back_unchecked!(self))
370 fn nth_back(&mut self, n: usize) -> Option<$elem> {
372 // This iterator is now empty.
373 self.end = self.ptr.as_ptr();
376 // SAFETY: We are in bounds. `pre_dec_end` does the right thing even for ZSTs.
379 Some(next_back_unchecked!(self))
384 fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
385 let advance = cmp::min(len!(self), n);
386 // SAFETY: By construction, `advance` does not exceed `self.len()`.
387 unsafe { self.pre_dec_end(advance) };
388 if advance == n { Ok(()) } else { Err(advance) }
392 #[stable(feature = "fused", since = "1.26.0")]
393 impl<T> FusedIterator for $name<'_, T> {}
395 #[unstable(feature = "trusted_len", issue = "37572")]
396 unsafe impl<T> TrustedLen for $name<'_, T> {}
400 macro_rules! forward_iterator {
401 ($name:ident: $elem:ident, $iter_of:ty) => {
402 #[stable(feature = "rust1", since = "1.0.0")]
403 impl<'a, $elem, P> Iterator for $name<'a, $elem, P>
405 P: FnMut(&T) -> bool,
407 type Item = $iter_of;
410 fn next(&mut self) -> Option<$iter_of> {
415 fn size_hint(&self) -> (usize, Option<usize>) {
416 self.inner.size_hint()
420 #[stable(feature = "fused", since = "1.26.0")]
421 impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P> where P: FnMut(&T) -> bool {}