library/core/src/slice/iter/macros.rs

   1 //! Macros used by iterators of slice.
   2
   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
   6     // and non-ZST.
   7     ($self: ident) => {
   8         $self.ptr.as_ptr() as *const T == $self.end
   9     };
  10 }
  11
  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`.)
  14 macro_rules! len {
  15     ($self: ident) => {{
  16         #![allow(unused_unsafe)] // we're sometimes used within an unsafe block
  17
  18         let start = $self.ptr;
  19         let size = size_from_ptr(start.as_ptr());
  20         if size == 0 {
  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())
  24         } else {
  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) }
  36         }
  37     }};
  38 }
  39
  40 // The shared definition of the `Iter` and `IterMut` iterators
  41 macro_rules! iterator {
  42     (
  43         struct $name:ident -> $ptr:ty,
  44         $elem:ty,
  45         $raw_mut:tt,
  46         {$( $mut_:tt )?},
  47         {$($extra:tt)*}
  48     ) => {
  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
  51         // must not be empty.
  52         macro_rules! next_unchecked {
  53             ($self: ident) => {& $( $mut_ )? *$self.post_inc_start(1)}
  54         }
  55
  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
  58         // must not be empty.
  59         macro_rules! next_back_unchecked {
  60             ($self: ident) => {& $( $mut_ )? *$self.pre_dec_end(1)}
  61         }
  62
  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);
  68             }
  69         }
  70
  71         impl<'a, T> $name<'a, T> {
  72             // Helper function for creating a slice from the iterator.
  73             #[inline(always)]
  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)) }
  79             }
  80
  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()`.
  84             #[inline(always)]
  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);
  88                     self.ptr.as_ptr()
  89                 } else {
  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)) };
  94                     old
  95                 }
  96             }
  97
  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()`.
 101             #[inline(always)]
 102             unsafe fn pre_dec_end(&mut self, offset: usize) -> * $raw_mut T {
 103                 if T::IS_ZST {
 104                     zst_shrink!(self, offset);
 105                     self.ptr.as_ptr()
 106                 } else {
 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) };
 111                     self.end
 112                 }
 113             }
 114         }
 115
 116         #[stable(feature = "rust1", since = "1.0.0")]
 117         impl<T> ExactSizeIterator for $name<'_, T> {
 118             #[inline(always)]
 119             fn len(&self) -> usize {
 120                 len!(self)
 121             }
 122
 123             #[inline(always)]
 124             fn is_empty(&self) -> bool {
 125                 is_empty!(self)
 126             }
 127         }
 128
 129         #[stable(feature = "rust1", since = "1.0.0")]
 130         impl<'a, T> Iterator for $name<'a, T> {
 131             type Item = $elem;
 132
 133             #[inline]
 134             fn next(&mut self) -> Option<$elem> {
 135                 // could be implemented with slices, but this avoids bounds checks
 136
 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.
 141                 unsafe {
 142                     assume(!self.ptr.as_ptr().is_null());
 143                     if !<T>::IS_ZST {
 144                         assume(!self.end.is_null());
 145                     }
 146                     if is_empty!(self) {
 147                         None
 148                     } else {
 149                         Some(next_unchecked!(self))
 150                     }
 151                 }
 152             }
 153
 154             #[inline]
 155             fn size_hint(&self) -> (usize, Option<usize>) {
 156                 let exact = len!(self);
 157                 (exact, Some(exact))
 158             }
 159
 160             #[inline]
 161             fn count(self) -> usize {
 162                 len!(self)
 163             }
 164
 165             #[inline]
 166             fn nth(&mut self, n: usize) -> Option<$elem> {
 167                 if n >= len!(self) {
 168                     // This iterator is now empty.
 169                     if T::IS_ZST {
 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();
 173                     } else {
 174                         // SAFETY: end can't be 0 if T isn't ZST because ptr isn't 0 and end >= ptr
 175                         unsafe {
 176                             self.ptr = NonNull::new_unchecked(self.end as *mut T);
 177                         }
 178                     }
 179                     return None;
 180                 }
 181                 // SAFETY: We are in bounds. `post_inc_start` does the right thing even for ZSTs.
 182                 unsafe {
 183                     self.post_inc_start(n);
 184                     Some(next_unchecked!(self))
 185                 }
 186             }
 187
 188             #[inline]
 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) }
 194             }
 195
 196             #[inline]
 197             fn last(mut self) -> Option<$elem> {
 198                 self.next_back()
 199             }
 200
 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.
 204             #[inline]
 205             fn for_each<F>(mut self, mut f: F)
 206             where
 207                 Self: Sized,
 208                 F: FnMut(Self::Item),
 209             {
 210                 while let Some(x) = self.next() {
 211                     f(x);
 212                 }
 213             }
 214
 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.
 218             #[inline]
 219             fn all<F>(&mut self, mut f: F) -> bool
 220             where
 221                 Self: Sized,
 222                 F: FnMut(Self::Item) -> bool,
 223             {
 224                 while let Some(x) = self.next() {
 225                     if !f(x) {
 226                         return false;
 227                     }
 228                 }
 229                 true
 230             }
 231
 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.
 235             #[inline]
 236             fn any<F>(&mut self, mut f: F) -> bool
 237             where
 238                 Self: Sized,
 239                 F: FnMut(Self::Item) -> bool,
 240             {
 241                 while let Some(x) = self.next() {
 242                     if f(x) {
 243                         return true;
 244                     }
 245                 }
 246                 false
 247             }
 248
 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.
 252             #[inline]
 253             fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
 254             where
 255                 Self: Sized,
 256                 P: FnMut(&Self::Item) -> bool,
 257             {
 258                 while let Some(x) = self.next() {
 259                     if predicate(&x) {
 260                         return Some(x);
 261                     }
 262                 }
 263                 None
 264             }
 265
 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.
 269             #[inline]
 270             fn find_map<B, F>(&mut self, mut f: F) -> Option<B>
 271             where
 272                 Self: Sized,
 273                 F: FnMut(Self::Item) -> Option<B>,
 274             {
 275                 while let Some(x) = self.next() {
 276                     if let Some(y) = f(x) {
 277                         return Some(y);
 278                     }
 279                 }
 280                 None
 281             }
 282
 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.
 286             #[inline]
 287             #[rustc_inherit_overflow_checks]
 288             fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
 289                 Self: Sized,
 290                 P: FnMut(Self::Item) -> bool,
 291             {
 292                 let n = len!(self);
 293                 let mut i = 0;
 294                 while let Some(x) = self.next() {
 295                     if predicate(x) {
 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) };
 299                         return Some(i);
 300                     }
 301                     i += 1;
 302                 }
 303                 None
 304             }
 305
 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.
 309             #[inline]
 310             fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
 311                 P: FnMut(Self::Item) -> bool,
 312                 Self: Sized + ExactSizeIterator + DoubleEndedIterator
 313             {
 314                 let n = len!(self);
 315                 let mut i = n;
 316                 while let Some(x) = self.next_back() {
 317                     i -= 1;
 318                     if predicate(x) {
 319                         // SAFETY: `i` must be lower than `n` since it starts at `n`
 320                         // and is only decreasing.
 321                         unsafe { assume(i < n) };
 322                         return Some(i);
 323                     }
 324                 }
 325                 None
 326             }
 327
 328             #[inline]
 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.
 334                 //
 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
 339                 // `IterMut`
 340                 unsafe { & $( $mut_ )? * self.ptr.as_ptr().add(idx) }
 341             }
 342
 343             $($extra)*
 344         }
 345
 346         #[stable(feature = "rust1", since = "1.0.0")]
 347         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
 348             #[inline]
 349             fn next_back(&mut self) -> Option<$elem> {
 350                 // could be implemented with slices, but this avoids bounds checks
 351
 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
 355                 // empty first.
 356                 unsafe {
 357                     assume(!self.ptr.as_ptr().is_null());
 358                     if !<T>::IS_ZST {
 359                         assume(!self.end.is_null());
 360                     }
 361                     if is_empty!(self) {
 362                         None
 363                     } else {
 364                         Some(next_back_unchecked!(self))
 365                     }
 366                 }
 367             }
 368
 369             #[inline]
 370             fn nth_back(&mut self, n: usize) -> Option<$elem> {
 371                 if n >= len!(self) {
 372                     // This iterator is now empty.
 373                     self.end = self.ptr.as_ptr();
 374                     return None;
 375                 }
 376                 // SAFETY: We are in bounds. `pre_dec_end` does the right thing even for ZSTs.
 377                 unsafe {
 378                     self.pre_dec_end(n);
 379                     Some(next_back_unchecked!(self))
 380                 }
 381             }
 382
 383             #[inline]
 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) }
 389             }
 390         }
 391
 392         #[stable(feature = "fused", since = "1.26.0")]
 393         impl<T> FusedIterator for $name<'_, T> {}
 394
 395         #[unstable(feature = "trusted_len", issue = "37572")]
 396         unsafe impl<T> TrustedLen for $name<'_, T> {}
 397     }
 398 }
 399
 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>
 404         where
 405             P: FnMut(&T) -> bool,
 406         {
 407             type Item = $iter_of;
 408
 409             #[inline]
 410             fn next(&mut self) -> Option<$iter_of> {
 411                 self.inner.next()
 412             }
 413
 414             #[inline]
 415             fn size_hint(&self) -> (usize, Option<usize>) {
 416                 self.inner.size_hint()
 417             }
 418         }
 419
 420         #[stable(feature = "fused", since = "1.26.0")]
 421         impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P> where P: FnMut(&T) -> bool {}
 422     };
 423 }