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     #[doc(hidden)]
 756     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
 757     where
 758         Self: TrustedRandomAccessNoCoerce,
 759     {
 760         // SAFETY: The TrustedRandomAccess contract requires that callers only  pass an index
 761         // that is in bounds.
 762         // Additionally Self: TrustedRandomAccess is only implemented for Copy types
 763         // which means even repeated reads of the same index would be safe.
 764         unsafe { Step::forward_unchecked(self.start.clone(), idx) }
 765     }
 766 }
 767
 768 // These macros generate `ExactSizeIterator` impls for various range types.
 769 //
 770 // * `ExactSizeIterator::len` is required to always return an exact `usize`,
 771 //   so no range can be longer than `usize::MAX`.
 772 // * For integer types in `Range<_>` this is the case for types narrower than or as wide as `usize`.
 773 //   For integer types in `RangeInclusive<_>`
 774 //   this is the case for types *strictly narrower* than `usize`
 775 //   since e.g. `(0..=u64::MAX).len()` would be `u64::MAX + 1`.
 776 range_exact_iter_impl! {
 777     usize u8 u16
 778     isize i8 i16
 779
 780     // These are incorrect per the reasoning above,
 781     // but removing them would be a breaking change as they were stabilized in Rust 1.0.0.
 782     // So e.g. `(0..66_000_u32).len()` for example will compile without error or warnings
 783     // on 16-bit platforms, but continue to give a wrong result.
 784     u32
 785     i32
 786 }
 787
 788 unsafe_range_trusted_random_access_impl! {
 789     usize u8 u16
 790     isize i8 i16
 791 }
 792
 793 #[cfg(target_pointer_width = "32")]
 794 unsafe_range_trusted_random_access_impl! {
 795     u32 i32
 796 }
 797
 798 #[cfg(target_pointer_width = "64")]
 799 unsafe_range_trusted_random_access_impl! {
 800     u32 i32
 801     u64 i64
 802 }
 803
 804 range_incl_exact_iter_impl! {
 805     u8
 806     i8
 807
 808     // These are incorrect per the reasoning above,
 809     // but removing them would be a breaking change as they were stabilized in Rust 1.26.0.
 810     // So e.g. `(0..=u16::MAX).len()` for example will compile without error or warnings
 811     // on 16-bit platforms, but continue to give a wrong result.
 812     u16
 813     i16
 814 }
 815
 816 #[stable(feature = "rust1", since = "1.0.0")]
 817 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
 818     #[inline]
 819     fn next_back(&mut self) -> Option<A> {
 820         self.spec_next_back()
 821     }
 822
 823     #[inline]
 824     fn nth_back(&mut self, n: usize) -> Option<A> {
 825         self.spec_nth_back(n)
 826     }
 827
 828     #[inline]
 829     fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 830         self.spec_advance_back_by(n)
 831     }
 832 }
 833
 834 // Safety:
 835 // The following invariants for `Step::steps_between` exist:
 836 //
 837 // > * `steps_between(&a, &b) == Some(n)` only if `a <= b`
 838 // >   * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`;
 839 // >     this is the case when it would require more than `usize::MAX` steps to
 840 // >     get to `b`
 841 // > * `steps_between(&a, &b) == None` if `a > b`
 842 //
 843 // The first invariant is what is generally required for `TrustedLen` to be
 844 // sound. The note addendum satisfies an additional `TrustedLen` invariant.
 845 //
 846 // > The upper bound must only be `None` if the actual iterator length is larger
 847 // > than `usize::MAX`
 848 //
 849 // The second invariant logically follows the first so long as the `PartialOrd`
 850 // implementation is correct; regardless it is explicitly stated. If `a < b`
 851 // then `(0, Some(0))` is returned by `ops::Range<A: Step>::size_hint`. As such
 852 // the second invariant is upheld.
 853 #[unstable(feature = "trusted_len", issue = "37572")]
 854 unsafe impl<A: TrustedStep> TrustedLen for ops::Range<A> {}
 855
 856 #[stable(feature = "fused", since = "1.26.0")]
 857 impl<A: Step> FusedIterator for ops::Range<A> {}
 858
 859 #[stable(feature = "rust1", since = "1.0.0")]
 860 impl<A: Step> Iterator for ops::RangeFrom<A> {
 861     type Item = A;
 862
 863     #[inline]
 864     fn next(&mut self) -> Option<A> {
 865         let n = Step::forward(self.start.clone(), 1);
 866         Some(mem::replace(&mut self.start, n))
 867     }
 868
 869     #[inline]
 870     fn size_hint(&self) -> (usize, Option<usize>) {
 871         (usize::MAX, None)
 872     }
 873
 874     #[inline]
 875     fn nth(&mut self, n: usize) -> Option<A> {
 876         let plus_n = Step::forward(self.start.clone(), n);
 877         self.start = Step::forward(plus_n.clone(), 1);
 878         Some(plus_n)
 879     }
 880 }
 881
 882 // Safety: See above implementation for `ops::Range<A>`
 883 #[unstable(feature = "trusted_len", issue = "37572")]
 884 unsafe impl<A: TrustedStep> TrustedLen for ops::RangeFrom<A> {}
 885
 886 #[stable(feature = "fused", since = "1.26.0")]
 887 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
 888
 889 trait RangeInclusiveIteratorImpl {
 890     type Item;
 891
 892     // Iterator
 893     fn spec_next(&mut self) -> Option<Self::Item>;
 894     fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R
 895     where
 896         Self: Sized,
 897         F: FnMut(B, Self::Item) -> R,
 898         R: Try<Output = B>;
 899
 900     // DoubleEndedIterator
 901     fn spec_next_back(&mut self) -> Option<Self::Item>;
 902     fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
 903     where
 904         Self: Sized,
 905         F: FnMut(B, Self::Item) -> R,
 906         R: Try<Output = B>;
 907 }
 908
 909 impl<A: Step> RangeInclusiveIteratorImpl for ops::RangeInclusive<A> {
 910     type Item = A;
 911
 912     #[inline]
 913     default fn spec_next(&mut self) -> Option<A> {
 914         if self.is_empty() {
 915             return None;
 916         }
 917         let is_iterating = self.start < self.end;
 918         Some(if is_iterating {
 919             let n =
 920                 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
 921             mem::replace(&mut self.start, n)
 922         } else {
 923             self.exhausted = true;
 924             self.start.clone()
 925         })
 926     }
 927
 928     #[inline]
 929     default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
 930     where
 931         Self: Sized,
 932         F: FnMut(B, A) -> R,
 933         R: Try<Output = B>,
 934     {
 935         if self.is_empty() {
 936             return try { init };
 937         }
 938
 939         let mut accum = init;
 940
 941         while self.start < self.end {
 942             let n =
 943                 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
 944             let n = mem::replace(&mut self.start, n);
 945             accum = f(accum, n)?;
 946         }
 947
 948         self.exhausted = true;
 949
 950         if self.start == self.end {
 951             accum = f(accum, self.start.clone())?;
 952         }
 953
 954         try { accum }
 955     }
 956
 957     #[inline]
 958     default fn spec_next_back(&mut self) -> Option<A> {
 959         if self.is_empty() {
 960             return None;
 961         }
 962         let is_iterating = self.start < self.end;
 963         Some(if is_iterating {
 964             let n =
 965                 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
 966             mem::replace(&mut self.end, n)
 967         } else {
 968             self.exhausted = true;
 969             self.end.clone()
 970         })
 971     }
 972
 973     #[inline]
 974     default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
 975     where
 976         Self: Sized,
 977         F: FnMut(B, A) -> R,
 978         R: Try<Output = B>,
 979     {
 980         if self.is_empty() {
 981             return try { init };
 982         }
 983
 984         let mut accum = init;
 985
 986         while self.start < self.end {
 987             let n =
 988                 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
 989             let n = mem::replace(&mut self.end, n);
 990             accum = f(accum, n)?;
 991         }
 992
 993         self.exhausted = true;
 994
 995         if self.start == self.end {
 996             accum = f(accum, self.start.clone())?;
 997         }
 998
 999         try { accum }
1000     }
1001 }
1002
1003 impl<T: TrustedStep> RangeInclusiveIteratorImpl for ops::RangeInclusive<T> {
1004     #[inline]
1005     fn spec_next(&mut self) -> Option<T> {
1006         if self.is_empty() {
1007             return None;
1008         }
1009         let is_iterating = self.start < self.end;
1010         Some(if is_iterating {
1011             // SAFETY: just checked precondition
1012             let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) };
1013             mem::replace(&mut self.start, n)
1014         } else {
1015             self.exhausted = true;
1016             self.start.clone()
1017         })
1018     }
1019
1020     #[inline]
1021     fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1022     where
1023         Self: Sized,
1024         F: FnMut(B, T) -> R,
1025         R: Try<Output = B>,
1026     {
1027         if self.is_empty() {
1028             return try { init };
1029         }
1030
1031         let mut accum = init;
1032
1033         while self.start < self.end {
1034             // SAFETY: just checked precondition
1035             let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) };
1036             let n = mem::replace(&mut self.start, n);
1037             accum = f(accum, n)?;
1038         }
1039
1040         self.exhausted = true;
1041
1042         if self.start == self.end {
1043             accum = f(accum, self.start.clone())?;
1044         }
1045
1046         try { accum }
1047     }
1048
1049     #[inline]
1050     fn spec_next_back(&mut self) -> Option<T> {
1051         if self.is_empty() {
1052             return None;
1053         }
1054         let is_iterating = self.start < self.end;
1055         Some(if is_iterating {
1056             // SAFETY: just checked precondition
1057             let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) };
1058             mem::replace(&mut self.end, n)
1059         } else {
1060             self.exhausted = true;
1061             self.end.clone()
1062         })
1063     }
1064
1065     #[inline]
1066     fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1067     where
1068         Self: Sized,
1069         F: FnMut(B, T) -> R,
1070         R: Try<Output = B>,
1071     {
1072         if self.is_empty() {
1073             return try { init };
1074         }
1075
1076         let mut accum = init;
1077
1078         while self.start < self.end {
1079             // SAFETY: just checked precondition
1080             let n = unsafe { Step::backward_unchecked(self.end.clone(), 1) };
1081             let n = mem::replace(&mut self.end, n);
1082             accum = f(accum, n)?;
1083         }
1084
1085         self.exhausted = true;
1086
1087         if self.start == self.end {
1088             accum = f(accum, self.start.clone())?;
1089         }
1090
1091         try { accum }
1092     }
1093 }
1094
1095 #[stable(feature = "inclusive_range", since = "1.26.0")]
1096 impl<A: Step> Iterator for ops::RangeInclusive<A> {
1097     type Item = A;
1098
1099     #[inline]
1100     fn next(&mut self) -> Option<A> {
1101         self.spec_next()
1102     }
1103
1104     #[inline]
1105     fn size_hint(&self) -> (usize, Option<usize>) {
1106         if self.is_empty() {
1107             return (0, Some(0));
1108         }
1109
1110         match Step::steps_between(&self.start, &self.end) {
1111             Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
1112             None => (usize::MAX, None),
1113         }
1114     }
1115
1116     #[inline]
1117     fn nth(&mut self, n: usize) -> Option<A> {
1118         if self.is_empty() {
1119             return None;
1120         }
1121
1122         if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
1123             use crate::cmp::Ordering::*;
1124
1125             match plus_n.partial_cmp(&self.end) {
1126                 Some(Less) => {
1127                     self.start = Step::forward(plus_n.clone(), 1);
1128                     return Some(plus_n);
1129                 }
1130                 Some(Equal) => {
1131                     self.start = plus_n.clone();
1132                     self.exhausted = true;
1133                     return Some(plus_n);
1134                 }
1135                 _ => {}
1136             }
1137         }
1138
1139         self.start = self.end.clone();
1140         self.exhausted = true;
1141         None
1142     }
1143
1144     #[inline]
1145     fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
1146     where
1147         Self: Sized,
1148         F: FnMut(B, Self::Item) -> R,
1149         R: Try<Output = B>,
1150     {
1151         self.spec_try_fold(init, f)
1152     }
1153
1154     #[inline]
1155     fn fold<B, F>(mut self, init: B, f: F) -> B
1156     where
1157         Self: Sized,
1158         F: FnMut(B, Self::Item) -> B,
1159     {
1160         #[inline]
1161         fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
1162             move |acc, x| Ok(f(acc, x))
1163         }
1164
1165         self.try_fold(init, ok(f)).unwrap()
1166     }
1167
1168     #[inline]
1169     fn last(mut self) -> Option<A> {
1170         self.next_back()
1171     }
1172
1173     #[inline]
1174     fn min(mut self) -> Option<A> {
1175         self.next()
1176     }
1177
1178     #[inline]
1179     fn max(mut self) -> Option<A> {
1180         self.next_back()
1181     }
1182
1183     #[inline]
1184     fn is_sorted(self) -> bool {
1185         true
1186     }
1187 }
1188
1189 #[stable(feature = "inclusive_range", since = "1.26.0")]
1190 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
1191     #[inline]
1192     fn next_back(&mut self) -> Option<A> {
1193         self.spec_next_back()
1194     }
1195
1196     #[inline]
1197     fn nth_back(&mut self, n: usize) -> Option<A> {
1198         if self.is_empty() {
1199             return None;
1200         }
1201
1202         if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
1203             use crate::cmp::Ordering::*;
1204
1205             match minus_n.partial_cmp(&self.start) {
1206                 Some(Greater) => {
1207                     self.end = Step::backward(minus_n.clone(), 1);
1208                     return Some(minus_n);
1209                 }
1210                 Some(Equal) => {
1211                     self.end = minus_n.clone();
1212                     self.exhausted = true;
1213                     return Some(minus_n);
1214                 }
1215                 _ => {}
1216             }
1217         }
1218
1219         self.end = self.start.clone();
1220         self.exhausted = true;
1221         None
1222     }
1223
1224     #[inline]
1225     fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
1226     where
1227         Self: Sized,
1228         F: FnMut(B, Self::Item) -> R,
1229         R: Try<Output = B>,
1230     {
1231         self.spec_try_rfold(init, f)
1232     }
1233
1234     #[inline]
1235     fn rfold<B, F>(mut self, init: B, f: F) -> B
1236     where
1237         Self: Sized,
1238         F: FnMut(B, Self::Item) -> B,
1239     {
1240         #[inline]
1241         fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> {
1242             move |acc, x| Ok(f(acc, x))
1243         }
1244
1245         self.try_rfold(init, ok(f)).unwrap()
1246     }
1247 }
1248
1249 // Safety: See above implementation for `ops::Range<A>`
1250 #[unstable(feature = "trusted_len", issue = "37572")]
1251 unsafe impl<A: TrustedStep> TrustedLen for ops::RangeInclusive<A> {}
1252
1253 #[stable(feature = "fused", since = "1.26.0")]
1254 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}