library/core/src/iter/range.rs

   1 use crate::char;
   2 use crate::convert::TryFrom;
   3 use crate::mem;
   4 use crate::ops::{self, Try};
   5
   6 use super::{
   7     FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, TrustedStep,
   8 };
   9
  10 // Safety: All invariants are upheld.
  11 macro_rules! unsafe_impl_trusted_step {
  12     ($($type:ty)*) => {$(
  13         #[unstable(feature = "trusted_step", issue = "85731")]
  14         unsafe impl TrustedStep for $type {}
  15     )*};
  16 }
  17 unsafe_impl_trusted_step![char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize];
  18
  19 /// Objects that have a notion of *successor* and *predecessor* operations.
  20 ///
  21 /// The *successor* operation moves towards values that compare greater.
  22 /// The *predecessor* operation moves towards values that compare lesser.
  23 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
  24 pub trait Step: Clone + PartialOrd + Sized {
  25     /// Returns the number of *successor* steps required to get from `start` to `end`.
  26     ///
  27     /// Returns `None` if the number of steps would overflow `usize`
  28     /// (or is infinite, or if `end` would never be reached).
  29     ///
  30     /// # Invariants
  31     ///
  32     /// For any `a`, `b`, and `n`:
  33     ///
  34     /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::forward_checked(&a, n) == Some(b)`
  35     /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::backward_checked(&b, n) == Some(a)`
  36     /// * `steps_between(&a, &b) == Some(n)` only if `a <= b`
  37     ///   * Corollary: `steps_between(&a, &b) == Some(0)` if and only if `a == b`
  38     ///   * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`;
  39     ///     this is the case when it would require more than `usize::MAX` steps to get to `b`
  40     /// * `steps_between(&a, &b) == None` if `a > b`
  41     fn steps_between(start: &Self, end: &Self) -> Option<usize>;
  42
  43     /// Returns the value that would be obtained by taking the *successor*
  44     /// of `self` `count` times.
  45     ///
  46     /// If this would overflow the range of values supported by `Self`, returns `None`.
  47     ///
  48     /// # Invariants
  49     ///
  50     /// For any `a`, `n`, and `m`:
  51     ///
  52     /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, m).and_then(|x| Step::forward_checked(x, n))`
  53     ///
  54     /// For any `a`, `n`, and `m` where `n + m` does not overflow:
  55     ///
  56     /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, n + m)`
  57     ///
  58     /// For any `a` and `n`:
  59     ///
  60     /// * `Step::forward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::forward_checked(&x, 1))`
  61     ///   * Corollary: `Step::forward_checked(&a, 0) == Some(a)`
  62     fn forward_checked(start: Self, count: usize) -> Option<Self>;
  63
  64     /// Returns the value that would be obtained by taking the *successor*
  65     /// of `self` `count` times.
  66     ///
  67     /// If this would overflow the range of values supported by `Self`,
  68     /// this function is allowed to panic, wrap, or saturate.
  69     /// The suggested behavior is to panic when debug assertions are enabled,
  70     /// and to wrap or saturate otherwise.
  71     ///
  72     /// Unsafe code should not rely on the correctness of behavior after overflow.
  73     ///
  74     /// # Invariants
  75     ///
  76     /// For any `a`, `n`, and `m`, where no overflow occurs:
  77     ///
  78     /// * `Step::forward(Step::forward(a, n), m) == Step::forward(a, n + m)`
  79     ///
  80     /// For any `a` and `n`, where no overflow occurs:
  81     ///
  82     /// * `Step::forward_checked(a, n) == Some(Step::forward(a, n))`
  83     /// * `Step::forward(a, n) == (0..n).fold(a, |x, _| Step::forward(x, 1))`
  84     ///   * Corollary: `Step::forward(a, 0) == a`
  85     /// * `Step::forward(a, n) >= a`
  86     /// * `Step::backward(Step::forward(a, n), n) == a`
  87     fn forward(start: Self, count: usize) -> Self {
  88         Step::forward_checked(start, count).expect("overflow in `Step::forward`")
  89     }
  90
  91     /// Returns the value that would be obtained by taking the *successor*
  92     /// of `self` `count` times.
  93     ///
  94     /// # Safety
  95     ///
  96     /// It is undefined behavior for this operation to overflow the
  97     /// range of values supported by `Self`. If you cannot guarantee that this
  98     /// will not overflow, use `forward` or `forward_checked` instead.
  99     ///
 100     /// # Invariants
 101     ///
 102     /// For any `a`:
 103     ///
 104     /// * if there exists `b` such that `b > a`, it is safe to call `Step::forward_unchecked(a, 1)`
 105     /// * if there exists `b`, `n` such that `steps_between(&a, &b) == Some(n)`,
 106     ///   it is safe to call `Step::forward_unchecked(a, m)` for any `m <= n`.
 107     ///
 108     /// For any `a` and `n`, where no overflow occurs:
 109     ///
 110     /// * `Step::forward_unchecked(a, n)` is equivalent to `Step::forward(a, n)`
 111     unsafe fn forward_unchecked(start: Self, count: usize) -> Self {
 112         Step::forward(start, count)
 113     }
 114
 115     /// Returns the value that would be obtained by taking the *predecessor*
 116     /// of `self` `count` times.
 117     ///
 118     /// If this would overflow the range of values supported by `Self`, returns `None`.
 119     ///
 120     /// # Invariants
 121     ///
 122     /// For any `a`, `n`, and `m`:
 123     ///
 124     /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == n.checked_add(m).and_then(|x| Step::backward_checked(a, x))`
 125     /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == try { Step::backward_checked(a, n.checked_add(m)?) }`
 126     ///
 127     /// For any `a` and `n`:
 128     ///
 129     /// * `Step::backward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::backward_checked(&x, 1))`
 130     ///   * Corollary: `Step::backward_checked(&a, 0) == Some(a)`
 131     fn backward_checked(start: Self, count: usize) -> Option<Self>;
 132
 133     /// Returns the value that would be obtained by taking the *predecessor*
 134     /// of `self` `count` times.
 135     ///
 136     /// If this would overflow the range of values supported by `Self`,
 137     /// this function is allowed to panic, wrap, or saturate.
 138     /// The suggested behavior is to panic when debug assertions are enabled,
 139     /// and to wrap or saturate otherwise.
 140     ///
 141     /// Unsafe code should not rely on the correctness of behavior after overflow.
 142     ///
 143     /// # Invariants
 144     ///
 145     /// For any `a`, `n`, and `m`, where no overflow occurs:
 146     ///
 147     /// * `Step::backward(Step::backward(a, n), m) == Step::backward(a, n + m)`
 148     ///
 149     /// For any `a` and `n`, where no overflow occurs:
 150     ///
 151     /// * `Step::backward_checked(a, n) == Some(Step::backward(a, n))`
 152     /// * `Step::backward(a, n) == (0..n).fold(a, |x, _| Step::backward(x, 1))`
 153     ///   * Corollary: `Step::backward(a, 0) == a`
 154     /// * `Step::backward(a, n) <= a`
 155     /// * `Step::forward(Step::backward(a, n), n) == a`
 156     fn backward(start: Self, count: usize) -> Self {
 157         Step::backward_checked(start, count).expect("overflow in `Step::backward`")
 158     }
 159
 160     /// Returns the value that would be obtained by taking the *predecessor*
 161     /// of `self` `count` times.
 162     ///
 163     /// # Safety
 164     ///
 165     /// It is undefined behavior for this operation to overflow the
 166     /// range of values supported by `Self`. If you cannot guarantee that this
 167     /// will not overflow, use `backward` or `backward_checked` instead.
 168     ///
 169     /// # Invariants
 170     ///
 171     /// For any `a`:
 172     ///
 173     /// * if there exists `b` such that `b < a`, it is safe to call `Step::backward_unchecked(a, 1)`
 174     /// * if there exists `b`, `n` such that `steps_between(&b, &a) == Some(n)`,
 175     ///   it is safe to call `Step::backward_unchecked(a, m)` for any `m <= n`.
 176     ///
 177     /// For any `a` and `n`, where no overflow occurs:
 178     ///
 179     /// * `Step::backward_unchecked(a, n)` is equivalent to `Step::backward(a, n)`
 180     unsafe fn backward_unchecked(start: Self, count: usize) -> Self {
 181         Step::backward(start, count)
 182     }
 183 }
 184
 185 // These are still macro-generated because the integer literals resolve to different types.
 186 macro_rules! step_identical_methods {
 187     () => {
 188         #[inline]
 189         unsafe fn forward_unchecked(start: Self, n: usize) -> Self {
 190             // SAFETY: the caller has to guarantee that `start + n` doesn't overflow.
 191             unsafe { start.unchecked_add(n as Self) }
 192         }
 193
 194         #[inline]
 195         unsafe fn backward_unchecked(start: Self, n: usize) -> Self {
 196             // SAFETY: the caller has to guarantee that `start - n` doesn't overflow.
 197             unsafe { start.unchecked_sub(n as Self) }
 198         }
 199
 200         #[inline]
 201         #[allow(arithmetic_overflow)]
 202         #[rustc_inherit_overflow_checks]
 203         fn forward(start: Self, n: usize) -> Self {
 204             // In debug builds, trigger a panic on overflow.
 205             // This should optimize completely out in release builds.
 206             if Self::forward_checked(start, n).is_none() {
 207                 let _ = Self::MAX + 1;
 208             }
 209             // Do wrapping math to allow e.g. `Step::forward(-128i8, 255)`.
 210             start.wrapping_add(n as Self)
 211         }
 212
 213         #[inline]
 214         #[allow(arithmetic_overflow)]
 215         #[rustc_inherit_overflow_checks]
 216         fn backward(start: Self, n: usize) -> Self {
 217             // In debug builds, trigger a panic on overflow.
 218             // This should optimize completely out in release builds.
 219             if Self::backward_checked(start, n).is_none() {
 220                 let _ = Self::MIN - 1;
 221             }
 222             // Do wrapping math to allow e.g. `Step::backward(127i8, 255)`.
 223             start.wrapping_sub(n as Self)
 224         }
 225     };
 226 }
 227
 228 macro_rules! step_integer_impls {
 229     {
 230         narrower than or same width as usize:
 231             $( [ $u_narrower:ident $i_narrower:ident ] ),+;
 232         wider than usize:
 233             $( [ $u_wider:ident $i_wider:ident ] ),+;
 234     } => {
 235         $(
 236             #[allow(unreachable_patterns)]
 237             #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
 238             impl Step for $u_narrower {
 239                 step_identical_methods!();
 240
 241                 #[inline]
 242                 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
 243                     if *start <= *end {
 244                         // This relies on $u_narrower <= usize
 245                         Some((*end - *start) as usize)
 246                     } else {
 247                         None
 248                     }
 249                 }
 250
 251                 #[inline]
 252                 fn forward_checked(start: Self, n: usize) -> Option<Self> {
 253                     match Self::try_from(n) {
 254                         Ok(n) => start.checked_add(n),
 255                         Err(_) => None, // if n is out of range, `unsigned_start + n` is too
 256                     }
 257                 }
 258
 259                 #[inline]
 260                 fn backward_checked(start: Self, n: usize) -> Option<Self> {
 261                     match Self::try_from(n) {
 262                         Ok(n) => start.checked_sub(n),
 263                         Err(_) => None, // if n is out of range, `unsigned_start - n` is too
 264                     }
 265                 }
 266             }
 267
 268             #[allow(unreachable_patterns)]
 269             #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
 270             impl Step for $i_narrower {
 271                 step_identical_methods!();
 272
 273                 #[inline]
 274                 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
 275                     if *start <= *end {
 276                         // This relies on $i_narrower <= usize
 277                         //
 278                         // Casting to isize extends the width but preserves the sign.
 279                         // Use wrapping_sub in isize space and cast to usize to compute
 280                         // the difference that might not fit inside the range of isize.
 281                         Some((*end as isize).wrapping_sub(*start as isize) as usize)
 282                     } else {
 283                         None
 284                     }
 285                 }
 286
 287                 #[inline]
 288                 fn forward_checked(start: Self, n: usize) -> Option<Self> {
 289                     match $u_narrower::try_from(n) {
 290                         Ok(n) => {
 291                             // Wrapping handles cases like
 292                             // `Step::forward(-120_i8, 200) == Some(80_i8)`,
 293                             // even though 200 is out of range for i8.
 294                             let wrapped = start.wrapping_add(n as Self);
 295                             if wrapped >= start {
 296                                 Some(wrapped)
 297                             } else {
 298                                 None // Addition overflowed
 299                             }
 300                         }
 301                         // If n is out of range of e.g. u8,
 302                         // then it is bigger than the entire range for i8 is wide
 303                         // so `any_i8 + n` necessarily overflows i8.
 304                         Err(_) => None,
 305                     }
 306                 }
 307
 308                 #[inline]
 309                 fn backward_checked(start: Self, n: usize) -> Option<Self> {
 310                     match $u_narrower::try_from(n) {
 311                         Ok(n) => {
 312                             // Wrapping handles cases like
 313                             // `Step::forward(-120_i8, 200) == Some(80_i8)`,
 314                             // even though 200 is out of range for i8.
 315                             let wrapped = start.wrapping_sub(n as Self);
 316                             if wrapped <= start {
 317                                 Some(wrapped)
 318                             } else {
 319                                 None // Subtraction overflowed
 320                             }
 321                         }
 322                         // If n is out of range of e.g. u8,
 323                         // then it is bigger than the entire range for i8 is wide
 324                         // so `any_i8 - n` necessarily overflows i8.
 325                         Err(_) => None,
 326                     }
 327                 }
 328             }
 329         )+
 330
 331         $(
 332             #[allow(unreachable_patterns)]
 333             #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
 334             impl Step for $u_wider {
 335                 step_identical_methods!();
 336
 337                 #[inline]
 338                 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
 339                     if *start <= *end {
 340                         usize::try_from(*end - *start).ok()
 341                     } else {
 342                         None
 343                     }
 344                 }
 345
 346                 #[inline]
 347                 fn forward_checked(start: Self, n: usize) -> Option<Self> {
 348                     start.checked_add(n as Self)
 349                 }
 350
 351                 #[inline]
 352                 fn backward_checked(start: Self, n: usize) -> Option<Self> {
 353                     start.checked_sub(n as Self)
 354                 }
 355             }
 356
 357             #[allow(unreachable_patterns)]
 358             #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
 359             impl Step for $i_wider {
 360                 step_identical_methods!();
 361
 362                 #[inline]
 363                 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
 364                     if *start <= *end {
 365                         match end.checked_sub(*start) {
 366                             Some(result) => usize::try_from(result).ok(),
 367                             // If the difference is too big for e.g. i128,
 368                             // it's also gonna be too big for usize with fewer bits.
 369                             None => None,
 370                         }
 371                     } else {
 372                         None
 373                     }
 374                 }
 375
 376                 #[inline]
 377                 fn forward_checked(start: Self, n: usize) -> Option<Self> {
 378                     start.checked_add(n as Self)
 379                 }
 380
 381                 #[inline]
 382                 fn backward_checked(start: Self, n: usize) -> Option<Self> {
 383                     start.checked_sub(n as Self)
 384                 }
 385             }
 386         )+
 387     };
 388 }
 389
 390 #[cfg(target_pointer_width = "64")]
 391 step_integer_impls! {
 392     narrower than or same width as usize: [u8 i8], [u16 i16], [u32 i32], [u64 i64], [usize isize];
 393     wider than usize: [u128 i128];
 394 }
 395
 396 #[cfg(target_pointer_width = "32")]
 397 step_integer_impls! {
 398     narrower than or same width as usize: [u8 i8], [u16 i16], [u32 i32], [usize isize];
 399     wider than usize: [u64 i64], [u128 i128];
 400 }
 401
 402 #[cfg(target_pointer_width = "16")]
 403 step_integer_impls! {
 404     narrower than or same width as usize: [u8 i8], [u16 i16], [usize isize];
 405     wider than usize: [u32 i32], [u64 i64], [u128 i128];
 406 }
 407
 408 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
 409 impl Step for char {
 410     #[inline]
 411     fn steps_between(&start: &char, &end: &char) -> Option<usize> {
 412         let start = start as u32;
 413         let end = end as u32;
 414         if start <= end {
 415             let count = end - start;
 416             if start < 0xD800 && 0xE000 <= end {
 417                 usize::try_from(count - 0x800).ok()
 418             } else {
 419                 usize::try_from(count).ok()
 420             }
 421         } else {
 422             None
 423         }
 424     }
 425
 426     #[inline]
 427     fn forward_checked(start: char, count: usize) -> Option<char> {
 428         let start = start as u32;
 429         let mut res = Step::forward_checked(start, count)?;
 430         if start < 0xD800 && 0xD800 <= res {
 431             res = Step::forward_checked(res, 0x800)?;
 432         }
 433         if res <= char::MAX as u32 {
 434             // SAFETY: res is a valid unicode scalar
 435             // (below 0x110000 and not in 0xD800..0xE000)
 436             Some(unsafe { char::from_u32_unchecked(res) })
 437         } else {
 438             None
 439         }
 440     }
 441
 442     #[inline]
 443     fn backward_checked(start: char, count: usize) -> Option<char> {
 444         let start = start as u32;
 445         let mut res = Step::backward_checked(start, count)?;
 446         if start >= 0xE000 && 0xE000 > res {
 447             res = Step::backward_checked(res, 0x800)?;
 448         }
 449         // SAFETY: res is a valid unicode scalar
 450         // (below 0x110000 and not in 0xD800..0xE000)
 451         Some(unsafe { char::from_u32_unchecked(res) })
 452     }
 453
 454     #[inline]
 455     unsafe fn forward_unchecked(start: char, count: usize) -> char {
 456         let start = start as u32;
 457         // SAFETY: the caller must guarantee that this doesn't overflow
 458         // the range of values for a char.
 459         let mut res = unsafe { Step::forward_unchecked(start, count) };
 460         if start < 0xD800 && 0xD800 <= res {
 461             // SAFETY: the caller must guarantee that this doesn't overflow
 462             // the range of values for a char.
 463             res = unsafe { Step::forward_unchecked(res, 0x800) };
 464         }
 465         // SAFETY: because of the previous contract, this is guaranteed
 466         // by the caller to be a valid char.
 467         unsafe { char::from_u32_unchecked(res) }
 468     }
 469
 470     #[inline]
 471     unsafe fn backward_unchecked(start: char, count: usize) -> char {
 472         let start = start as u32;
 473         // SAFETY: the caller must guarantee that this doesn't overflow
 474         // the range of values for a char.
 475         let mut res = unsafe { Step::backward_unchecked(start, count) };
 476         if start >= 0xE000 && 0xE000 > res {
 477             // SAFETY: the caller must guarantee that this doesn't overflow
 478             // the range of values for a char.
 479             res = unsafe { Step::backward_unchecked(res, 0x800) };
 480         }
 481         // SAFETY: because of the previous contract, this is guaranteed
 482         // by the caller to be a valid char.
 483         unsafe { char::from_u32_unchecked(res) }
 484     }
 485 }
 486
 487 macro_rules! range_exact_iter_impl {
 488     ($($t:ty)*) => ($(
 489         #[stable(feature = "rust1", since = "1.0.0")]
 490         impl ExactSizeIterator for ops::Range<$t> { }
 491     )*)
 492 }
 493
 494 /// Safety: This macro must only be used on types that are `Copy` and result in ranges
 495 /// which have an exact `size_hint()` where the upper bound must not be `None`.
 496 macro_rules! unsafe_range_trusted_random_access_impl {
 497     ($($t:ty)*) => ($(
 498         #[doc(hidden)]
 499         #[unstable(feature = "trusted_random_access", issue = "none")]
 500         unsafe impl TrustedRandomAccess for ops::Range<$t> {}
 501
 502         #[doc(hidden)]
 503         #[unstable(feature = "trusted_random_access", issue = "none")]
 504         unsafe impl TrustedRandomAccessNoCoerce for ops::Range<$t> {
 505             const MAY_HAVE_SIDE_EFFECT: bool = false;
 506         }
 507     )*)
 508 }
 509
 510 macro_rules! range_incl_exact_iter_impl {
 511     ($($t:ty)*) => ($(
 512         #[stable(feature = "inclusive_range", since = "1.26.0")]
 513         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
 514     )*)
 515 }
 516
 517 /// Specialization implementations for `Range`.
 518 trait RangeIteratorImpl {
 519     type Item;
 520
 521     // Iterator
 522     fn spec_next(&mut self) -> Option<Self::Item>;
 523     fn spec_nth(&mut self, n: usize) -> Option<Self::Item>;
 524     fn spec_advance_by(&mut self, n: usize) -> Result<(), usize>;
 525
 526     // DoubleEndedIterator
 527     fn spec_next_back(&mut self) -> Option<Self::Item>;
 528     fn spec_nth_back(&mut self, n: usize) -> Option<Self::Item>;
 529     fn spec_advance_back_by(&mut self, n: usize) -> Result<(), usize>;
 530 }
 531
 532 impl<A: Step> RangeIteratorImpl for ops::Range<A> {
 533     type Item = A;
 534
 535     #[inline]
 536     default fn spec_next(&mut self) -> Option<A> {
 537         if self.start < self.end {
 538             let n =
 539                 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
 540             Some(mem::replace(&mut self.start, n))
 541         } else {
 542             None
 543         }
 544     }
 545
 546     #[inline]
 547     default fn spec_nth(&mut self, n: usize) -> Option<A> {
 548         if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
 549             if plus_n < self.end {
 550                 self.start =
 551                     Step::forward_checked(plus_n.clone(), 1).expect("`Step` invariants not upheld");
 552                 return Some(plus_n);
 553             }
 554         }
 555
 556         self.start = self.end.clone();
 557         None
 558     }
 559
 560     #[inline]
 561     default fn spec_advance_by(&mut self, n: usize) -> Result<(), usize> {
 562         let available = if self.start <= self.end {
 563             Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX)
 564         } else {
 565             0
 566         };
 567
 568         let taken = available.min(n);
 569
 570         self.start =
 571             Step::forward_checked(self.start.clone(), taken).expect("`Step` invariants not upheld");
 572
 573         if taken < n { Err(taken) } else { Ok(()) }
 574     }
 575
 576     #[inline]
 577     default fn spec_next_back(&mut self) -> Option<A> {
 578         if self.start < self.end {
 579             self.end =
 580                 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
 581             Some(self.end.clone())
 582         } else {
 583             None
 584         }
 585     }
 586
 587     #[inline]
 588     default fn spec_nth_back(&mut self, n: usize) -> Option<A> {
 589         if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
 590             if minus_n > self.start {
 591                 self.end =
 592                     Step::backward_checked(minus_n, 1).expect("`Step` invariants not upheld");
 593                 return Some(self.end.clone());
 594             }
 595         }
 596
 597         self.end = self.start.clone();
 598         None
 599     }
 600
 601     #[inline]
 602     default fn spec_advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 603         let available = if self.start <= self.end {
 604             Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX)
 605         } else {
 606             0
 607         };
 608
 609         let taken = available.min(n);
 610
 611         self.end =
 612             Step::backward_checked(self.end.clone(), taken).expect("`Step` invariants not upheld");
 613
 614         if taken < n { Err(taken) } else { Ok(()) }
 615     }
 616 }
 617
 618 impl<T: TrustedStep> RangeIteratorImpl for ops::Range<T> {
 619     #[inline]
 620     fn spec_next(&mut self) -> Option<T> {
 621         if self.start < self.end {
 622             // SAFETY: just checked precondition
 623             let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) };
 624             Some(mem::replace(&mut self.start, n))
 625         } else {
 626             None
 627         }
 628     }
 629
 630     #[inline]
 631     fn spec_nth(&mut self, n: usize) -> Option<T> {
 632         if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
 633             if plus_n < self.end {
 634                 // SAFETY: just checked precondition
 635                 self.start = unsafe { Step::forward_unchecked(plus_n.clone(), 1) };
 636                 return Some(plus_n);
 637             }
 638         }
 639
 640         self.start = self.end.clone();
 641         None
 642     }
 643
 644     #[inline]
 645     fn spec_advance_by(&mut self, n: usize) -> Result<(), usize> {
 646         let available = if self.start <= self.end {
 647             Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX)
 648         } else {
 649             0
 650         };
 651
 652         let taken = available.min(n);
 653
 654         // SAFETY: the conditions above ensure that the count is in bounds. If start <= end
 655         // then steps_between either returns a bound to which we clamp or returns None which
 656         // together with the initial inequality implies more than usize::MAX steps.
 657         // Otherwise 0 is returned which always safe to use.
 658         self.start = unsafe { Step::forward_unchecked(self.start.clone(), taken) };
 659
 660         if taken < n { Err(taken) } else { Ok(()) }
 661     }
 662
 663     #[inline]
 664     fn spec_next_back(&mut self) -> Option<T> {
 665         if self.start < self.end {
 666             // SAFETY: just checked precondition
 667             self.end = unsafe { Step::backward_unchecked(self.end.clone(), 1) };
 668             Some(self.end.clone())
 669         } else {
 670             None
 671         }
 672     }
 673
 674     #[inline]
 675     fn spec_nth_back(&mut self, n: usize) -> Option<T> {
 676         if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
 677             if minus_n > self.start {
 678                 // SAFETY: just checked precondition
 679                 self.end = unsafe { Step::backward_unchecked(minus_n, 1) };
 680                 return Some(self.end.clone());
 681             }
 682         }
 683
 684         self.end = self.start.clone();
 685         None
 686     }
 687
 688     #[inline]
 689     fn spec_advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 690         let available = if self.start <= self.end {
 691             Step::steps_between(&self.start, &self.end).unwrap_or(usize::MAX)
 692         } else {
 693             0
 694         };
 695
 696         let taken = available.min(n);
 697
 698         // SAFETY: same as the spec_advance_by() implementation
 699         self.end = unsafe { Step::backward_unchecked(self.end.clone(), taken) };
 700
 701         if taken < n { Err(taken) } else { Ok(()) }
 702     }
 703 }
 704
 705 #[stable(feature = "rust1", since = "1.0.0")]
 706 impl<A: Step> Iterator for ops::Range<A> {
 707     type Item = A;
 708
 709     #[inline]
 710     fn next(&mut self) -> Option<A> {
 711         self.spec_next()
 712     }
 713
 714     #[inline]
 715     fn size_hint(&self) -> (usize, Option<usize>) {
 716         if self.start < self.end {
 717             let hint = Step::steps_between(&self.start, &self.end);
 718             (hint.unwrap_or(usize::MAX), hint)
 719         } else {
 720             (0, Some(0))
 721         }
 722     }
 723
 724     #[inline]
 725     fn nth(&mut self, n: usize) -> Option<A> {
 726         self.spec_nth(n)
 727     }
 728
 729     #[inline]
 730     fn last(mut self) -> Option<A> {
 731         self.next_back()
 732     }
 733
 734     #[inline]
 735     fn min(mut self) -> Option<A> {
 736         self.next()
 737     }
 738
 739     #[inline]
 740     fn max(mut self) -> Option<A> {
 741         self.next_back()
 742     }
 743
 744     #[inline]
 745     fn is_sorted(self) -> bool {
 746         true
 747     }
 748
 749     #[inline]
 750     fn advance_by(&mut self, n: usize) -> Result<(), usize> {
 751         self.spec_advance_by(n)
 752     }
 753
 754     #[inline]
 755     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
 756     where
 757         Self: TrustedRandomAccessNoCoerce,
 758     {
 759         // SAFETY: The TrustedRandomAccess contract requires that callers only pass an index
 760         // that is in bounds.
 761         // Additionally Self: TrustedRandomAccess is only implemented for Copy types
 762         // which means even repeated reads of the same index would be safe.
 763         unsafe { Step::forward_unchecked(self.start.clone(), idx) }
 764     }
 765 }
 766
 767 // These macros generate `ExactSizeIterator` impls for various range types.
 768 //
 769 // * `ExactSizeIterator::len` is required to always return an exact `usize`,
 770 //   so no range can be longer than `usize::MAX`.
 771 // * For integer types in `Range<_>` this is the case for types narrower than or as wide as `usize`.
 772 //   For integer types in `RangeInclusive<_>`
 773 //   this is the case for types *strictly narrower* than `usize`
 774 //   since e.g. `(0..=u64::MAX).len()` would be `u64::MAX + 1`.
 775 range_exact_iter_impl! {
 776     usize u8 u16
 777     isize i8 i16
 778
 779     // These are incorrect per the reasoning above,
 780     // but removing them would be a breaking change as they were stabilized in Rust 1.0.0.
 781     // So e.g. `(0..66_000_u32).len()` for example will compile without error or warnings
 782     // on 16-bit platforms, but continue to give a wrong result.
 783     u32
 784     i32
 785 }
 786
 787 unsafe_range_trusted_random_access_impl! {
 788     usize u8 u16
 789     isize i8 i16
 790 }
 791
 792 #[cfg(target_pointer_width = "32")]
 793 unsafe_range_trusted_random_access_impl! {
 794     u32 i32
 795 }
 796
 797 #[cfg(target_pointer_width = "64")]
 798 unsafe_range_trusted_random_access_impl! {
 799     u32 i32
 800     u64 i64
 801 }
 802
 803 range_incl_exact_iter_impl! {
 804     u8
 805     i8
 806
 807     // These are incorrect per the reasoning above,
 808     // but removing them would be a breaking change as they were stabilized in Rust 1.26.0.
 809     // So e.g. `(0..=u16::MAX).len()` for example will compile without error or warnings
 810     // on 16-bit platforms, but continue to give a wrong result.
 811     u16
 812     i16
 813 }
 814
 815 #[stable(feature = "rust1", since = "1.0.0")]
 816 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
 817     #[inline]
 818     fn next_back(&mut self) -> Option<A> {
 819         self.spec_next_back()
 820     }
 821
 822     #[inline]
 823     fn nth_back(&mut self, n: usize) -> Option<A> {
 824         self.spec_nth_back(n)
 825     }
 826
 827     #[inline]
 828     fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 829         self.spec_advance_back_by(n)
 830     }
 831 }
 832
 833 // Safety:
 834 // The following invariants for `Step::steps_between` exist:
 835 //
 836 // > * `steps_between(&a, &b) == Some(n)` only if `a <= b`
 837 // >   * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`;
 838 // >     this is the case when it would require more than `usize::MAX` steps to
 839 // >     get to `b`
 840 // > * `steps_between(&a, &b) == None` if `a > b`
 841 //
 842 // The first invariant is what is generally required for `TrustedLen` to be
 843 // sound. The note addendum satisfies an additional `TrustedLen` invariant.
 844 //
 845 // > The upper bound must only be `None` if the actual iterator length is larger
 846 // > than `usize::MAX`
 847 //
 848 // The second invariant logically follows the first so long as the `PartialOrd`
 849 // implementation is correct; regardless it is explicitly stated. If `a < b`
 850 // then `(0, Some(0))` is returned by `ops::Range<A: Step>::size_hint`. As such
 851 // the second invariant is upheld.
 852 #[unstable(feature = "trusted_len", issue = "37572")]
 853 unsafe impl<A: TrustedStep> TrustedLen for ops::Range<A> {}
 854
 855 #[stable(feature = "fused", since = "1.26.0")]
 856 impl<A: Step> FusedIterator for ops::Range<A> {}
 857
 858 #[stable(feature = "rust1", since = "1.0.0")]
 859 impl<A: Step> Iterator for ops::RangeFrom<A> {
 860     type Item = A;
 861
 862     #[inline]
 863     fn next(&mut self) -> Option<A> {
 864         let n = Step::forward(self.start.clone(), 1);
 865         Some(mem::replace(&mut self.start, n))
 866     }
 867
 868     #[inline]
 869     fn size_hint(&self) -> (usize, Option<usize>) {
 870         (usize::MAX, None)
 871     }
 872
 873     #[inline]
 874     fn nth(&mut self, n: usize) -> Option<A> {
 875         let plus_n = Step::forward(self.start.clone(), n);
 876         self.start = Step::forward(plus_n.clone(), 1);
 877         Some(plus_n)
 878     }
 879 }
 880
 881 // Safety: See above implementation for `ops::Range<A>`
 882 #[unstable(feature = "trusted_len", issue = "37572")]
 883 unsafe impl<A: TrustedStep> TrustedLen for ops::RangeFrom<A> {}
 884
 885 #[stable(feature = "fused", since = "1.26.0")]
 886 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
 887
 888 trait RangeInclusiveIteratorImpl {
 889     type Item;
 890
 891     // Iterator
 892     fn spec_next(&mut self) -> Option<Self::Item>;
 893     fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R
 894     where
 895         Self: Sized,
 896         F: FnMut(B, Self::Item) -> R,
 897         R: Try<Output = B>;
 898
 899     // DoubleEndedIterator
 900     fn spec_next_back(&mut self) -> Option<Self::Item>;
 901     fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
 902     where
 903         Self: Sized,
 904         F: FnMut(B, Self::Item) -> R,
 905         R: Try<Output = B>;
 906 }
 907
 908 impl<A: Step> RangeInclusiveIteratorImpl for ops::RangeInclusive<A> {
 909     type Item = A;
 910
 911     #[inline]
 912     default fn spec_next(&mut self) -> Option<A> {
 913         if self.is_empty() {
 914             return None;
 915         }
 916         let is_iterating = self.start < self.end;
 917         Some(if is_iterating {
 918             let n =
 919                 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
 920             mem::replace(&mut self.start, n)
 921         } else {
 922             self.exhausted = true;
 923             self.start.clone()
 924         })
 925     }
 926
 927     #[inline]
 928     default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
 929     where
 930         Self: Sized,
 931         F: FnMut(B, A) -> R,
 932         R: Try<Output = B>,
 933     {
 934         if self.is_empty() {
 935             return try { init };
 936         }
 937
 938         let mut accum = init;
 939
 940         while self.start < self.end {
 941             let n =
 942                 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
 943             let n = mem::replace(&mut self.start, n);
 944             accum = f(accum, n)?;
 945         }
 946
 947         self.exhausted = true;
 948
 949         if self.start == self.end {
 950             accum = f(accum, self.start.clone())?;
 951         }
 952
 953         try { accum }
 954     }
 955
 956     #[inline]
 957     default fn spec_next_back(&mut self) -> Option<A> {
 958         if self.is_empty() {
 959             return None;
 960         }
 961         let is_iterating = self.start < self.end;
 962         Some(if is_iterating {
 963             let n =
 964                 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
 965             mem::replace(&mut self.end, n)
 966         } else {
 967             self.exhausted = true;
 968             self.end.clone()
 969         })
 970     }
 971
 972     #[inline]
 973     default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
 974     where
 975         Self: Sized,
 976         F: FnMut(B, A) -> R,
 977         R: Try<Output = B>,
 978     {
 979         if self.is_empty() {
 980             return try { init };
 981         }
 982
 983         let mut accum = init;
 984
 985         while self.start < self.end {
 986             let n =
 987                 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
 988             let n = mem::replace(&mut self.end, n);
 989             accum = f(accum, n)?;
 990         }
 991
 992         self.exhausted = true;
 993
 994         if self.start == self.end {
 995             accum = f(accum, self.start.clone())?;
 996         }
 997
 998         try { accum }
 999     }
1000 }
1001
1002 impl<T: TrustedStep> RangeInclusiveIteratorImpl for ops::RangeInclusive<T> {
1003     #[inline]
1004     fn spec_next(&mut self) -> Option<T> {
1005         if self.is_empty() {
1006             return None;
1007         }
1008         let is_iterating = self.start < self.end;
1009         Some(if is_iterating {
1010             // SAFETY: just checked precondition
1011             let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) };
1012             mem::replace(&mut self.start, n)
1013         } else {
1014             self.exhausted = true;
1015             self.start.clone()
1016         })
1017     }
1018
1019     #[inline]
1020     fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1021     where
1022         Self: Sized,
1023         F: FnMut(B, T) -> R,
1024         R: Try<Output = B>,
1025     {
1026         if self.is_empty() {
1027             return try { init };
1028         }
1029
1030         let mut accum = init;
1031
1032         while self.start < self.end {
1033             // SAFETY: just checked precondition
1034             let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) };
1035             let n = mem::replace(&mut self.start, n);
1036             accum = f(accum, n)?;
1037         }
1038
1039         self.exhausted = true;
1040
1041         if self.start == self.end {
1042             accum = f(accum, self.start.clone())?;
1043         }
1044
1045         try { accum }
1046     }
1047
1048     #[inline]
1049     fn spec_next_back(&mut self) -> Option<T> {
1050         if self.is_empty() {
1051             return None;
1052         }
1053         let is_iterating = self.start < self.end;
1054         Some(if is_iterating {
1055             // SAFETY: just checked precondition
1056             let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) };
1057             mem::replace(&mut self.end, n)
1058         } else {
1059             self.exhausted = true;
1060             self.end.clone()
1061         })
1062     }
1063
1064     #[inline]
1065     fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1066     where
1067         Self: Sized,
1068         F: FnMut(B, T) -> R,
1069         R: Try<Output = B>,
1070     {
1071         if self.is_empty() {
1072             return try { init };
1073         }
1074
1075         let mut accum = init;
1076
1077         while self.start < self.end {
1078             // SAFETY: just checked precondition
1079             let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) };
1080             let n = mem::replace(&mut self.end, n);
1081             accum = f(accum, n)?;
1082         }
1083
1084         self.exhausted = true;
1085
1086         if self.start == self.end {
1087             accum = f(accum, self.start.clone())?;
1088         }
1089
1090         try { accum }
1091     }
1092 }
1093
1094 #[stable(feature = "inclusive_range", since = "1.26.0")]
1095 impl<A: Step> Iterator for ops::RangeInclusive<A> {
1096     type Item = A;
1097
1098     #[inline]
1099     fn next(&mut self) -> Option<A> {
1100         self.spec_next()
1101     }
1102
1103     #[inline]
1104     fn size_hint(&self) -> (usize, Option<usize>) {
1105         if self.is_empty() {
1106             return (0, Some(0));
1107         }
1108
1109         match Step::steps_between(&self.start, &self.end) {
1110             Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
1111             None => (usize::MAX, None),
1112         }
1113     }
1114
1115     #[inline]
1116     fn nth(&mut self, n: usize) -> Option<A> {
1117         if self.is_empty() {
1118             return None;
1119         }
1120
1121         if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
1122             use crate::cmp::Ordering::*;
1123
1124             match plus_n.partial_cmp(&self.end) {
1125                 Some(Less) => {
1126                     self.start = Step::forward(plus_n.clone(), 1);
1127                     return Some(plus_n);
1128                 }
1129                 Some(Equal) => {
1130                     self.start = plus_n.clone();
1131                     self.exhausted = true;
1132                     return Some(plus_n);
1133                 }
1134                 _ => {}
1135             }
1136         }
1137
1138         self.start = self.end.clone();
1139         self.exhausted = true;
1140         None
1141     }
1142
1143     #[inline]
1144     fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
1145     where
1146         Self: Sized,
1147         F: FnMut(B, Self::Item) -> R,
1148         R: Try<Output = B>,
1149     {
1150         self.spec_try_fold(init, f)
1151     }
1152
1153     impl_fold_via_try_fold! { fold -> try_fold }
1154
1155     #[inline]
1156     fn last(mut self) -> Option<A> {
1157         self.next_back()
1158     }
1159
1160     #[inline]
1161     fn min(mut self) -> Option<A> {
1162         self.next()
1163     }
1164
1165     #[inline]
1166     fn max(mut self) -> Option<A> {
1167         self.next_back()
1168     }
1169
1170     #[inline]
1171     fn is_sorted(self) -> bool {
1172         true
1173     }
1174 }
1175
1176 #[stable(feature = "inclusive_range", since = "1.26.0")]
1177 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
1178     #[inline]
1179     fn next_back(&mut self) -> Option<A> {
1180         self.spec_next_back()
1181     }
1182
1183     #[inline]
1184     fn nth_back(&mut self, n: usize) -> Option<A> {
1185         if self.is_empty() {
1186             return None;
1187         }
1188
1189         if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
1190             use crate::cmp::Ordering::*;
1191
1192             match minus_n.partial_cmp(&self.start) {
1193                 Some(Greater) => {
1194                     self.end = Step::backward(minus_n.clone(), 1);
1195                     return Some(minus_n);
1196                 }
1197                 Some(Equal) => {
1198                     self.end = minus_n.clone();
1199                     self.exhausted = true;
1200                     return Some(minus_n);
1201                 }
1202                 _ => {}
1203             }
1204         }
1205
1206         self.end = self.start.clone();
1207         self.exhausted = true;
1208         None
1209     }
1210
1211     #[inline]
1212     fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
1213     where
1214         Self: Sized,
1215         F: FnMut(B, Self::Item) -> R,
1216         R: Try<Output = B>,
1217     {
1218         self.spec_try_rfold(init, f)
1219     }
1220
1221     impl_fold_via_try_fold! { rfold -> try_rfold }
1222 }
1223
1224 // Safety: See above implementation for `ops::Range<A>`
1225 #[unstable(feature = "trusted_len", issue = "37572")]
1226 unsafe impl<A: TrustedStep> TrustedLen for ops::RangeInclusive<A> {}
1227
1228 #[stable(feature = "fused", since = "1.26.0")]
1229 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}