2 use crate::convert::TryFrom;
4 use crate::ops::{self, Try};
7 FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, TrustedStep,
10 // Safety: All invariants are upheld.
11 macro_rules! unsafe_impl_trusted_step {
13 #[unstable(feature = "trusted_step", issue = "85731")]
14 unsafe impl TrustedStep for $type {}
17 unsafe_impl_trusted_step![char i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize];
19 /// Objects that have a notion of *successor* and *predecessor* operations.
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`.
27 /// Returns `None` if the number of steps would overflow `usize`
28 /// (or is infinite, or if `end` would never be reached).
32 /// For any `a`, `b`, and `n`:
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>;
43 /// Returns the value that would be obtained by taking the *successor*
44 /// of `self` `count` times.
46 /// If this would overflow the range of values supported by `Self`, returns `None`.
50 /// For any `a`, `n`, and `m`:
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))`
54 /// For any `a`, `n`, and `m` where `n + m` does not overflow:
56 /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, n + m)`
58 /// For any `a` and `n`:
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>;
64 /// Returns the value that would be obtained by taking the *successor*
65 /// of `self` `count` times.
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.
72 /// Unsafe code should not rely on the correctness of behavior after overflow.
76 /// For any `a`, `n`, and `m`, where no overflow occurs:
78 /// * `Step::forward(Step::forward(a, n), m) == Step::forward(a, n + m)`
80 /// For any `a` and `n`, where no overflow occurs:
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`")
91 /// Returns the value that would be obtained by taking the *successor*
92 /// of `self` `count` times.
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.
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`.
108 /// For any `a` and `n`, where no overflow occurs:
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)
115 /// Returns the value that would be obtained by taking the *predecessor*
116 /// of `self` `count` times.
118 /// If this would overflow the range of values supported by `Self`, returns `None`.
122 /// For any `a`, `n`, and `m`:
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)?) }`
127 /// For any `a` and `n`:
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>;
133 /// Returns the value that would be obtained by taking the *predecessor*
134 /// of `self` `count` times.
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.
141 /// Unsafe code should not rely on the correctness of behavior after overflow.
145 /// For any `a`, `n`, and `m`, where no overflow occurs:
147 /// * `Step::backward(Step::backward(a, n), m) == Step::backward(a, n + m)`
149 /// For any `a` and `n`, where no overflow occurs:
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`")
160 /// Returns the value that would be obtained by taking the *predecessor*
161 /// of `self` `count` times.
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.
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`.
177 /// For any `a` and `n`, where no overflow occurs:
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)
185 // These are still macro-generated because the integer literals resolve to different types.
186 macro_rules! step_identical_methods {
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) }
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) }
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;
209 // Do wrapping math to allow e.g. `Step::forward(-128i8, 255)`.
210 start.wrapping_add(n as Self)
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;
222 // Do wrapping math to allow e.g. `Step::backward(127i8, 255)`.
223 start.wrapping_sub(n as Self)
228 macro_rules! step_integer_impls {
230 narrower than or same width as usize:
231 $( [ $u_narrower:ident $i_narrower:ident ] ),+;
233 $( [ $u_wider:ident $i_wider:ident ] ),+;
236 #[allow(unreachable_patterns)]
237 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
238 impl Step for $u_narrower {
239 step_identical_methods!();
242 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
244 // This relies on $u_narrower <= usize
245 Some((*end - *start) as usize)
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
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
268 #[allow(unreachable_patterns)]
269 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
270 impl Step for $i_narrower {
271 step_identical_methods!();
274 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
276 // This relies on $i_narrower <= usize
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)
288 fn forward_checked(start: Self, n: usize) -> Option<Self> {
289 match $u_narrower::try_from(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 {
298 None // Addition overflowed
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.
309 fn backward_checked(start: Self, n: usize) -> Option<Self> {
310 match $u_narrower::try_from(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 {
319 None // Subtraction overflowed
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.
332 #[allow(unreachable_patterns)]
333 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
334 impl Step for $u_wider {
335 step_identical_methods!();
338 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
340 usize::try_from(*end - *start).ok()
347 fn forward_checked(start: Self, n: usize) -> Option<Self> {
348 start.checked_add(n as Self)
352 fn backward_checked(start: Self, n: usize) -> Option<Self> {
353 start.checked_sub(n as Self)
357 #[allow(unreachable_patterns)]
358 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
359 impl Step for $i_wider {
360 step_identical_methods!();
363 fn steps_between(start: &Self, end: &Self) -> Option<usize> {
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.
377 fn forward_checked(start: Self, n: usize) -> Option<Self> {
378 start.checked_add(n as Self)
382 fn backward_checked(start: Self, n: usize) -> Option<Self> {
383 start.checked_sub(n as Self)
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];
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];
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];
408 #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")]
411 fn steps_between(&start: &char, &end: &char) -> Option<usize> {
412 let start = start as u32;
413 let end = end as u32;
415 let count = end - start;
416 if start < 0xD800 && 0xE000 <= end {
417 usize::try_from(count - 0x800).ok()
419 usize::try_from(count).ok()
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)?;
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) })
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)?;
449 // SAFETY: res is a valid unicode scalar
450 // (below 0x110000 and not in 0xD800..0xE000)
451 Some(unsafe { char::from_u32_unchecked(res) })
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) };
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) }
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) };
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) }
487 macro_rules! range_exact_iter_impl {
489 #[stable(feature = "rust1", since = "1.0.0")]
490 impl ExactSizeIterator for ops::Range<$t> { }
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 {
499 #[unstable(feature = "trusted_random_access", issue = "none")]
500 unsafe impl TrustedRandomAccess for ops::Range<$t> {}
503 #[unstable(feature = "trusted_random_access", issue = "none")]
504 unsafe impl TrustedRandomAccessNoCoerce for ops::Range<$t> {
505 const MAY_HAVE_SIDE_EFFECT: bool = false;
510 macro_rules! range_incl_exact_iter_impl {
512 #[stable(feature = "inclusive_range", since = "1.26.0")]
513 impl ExactSizeIterator for ops::RangeInclusive<$t> { }
517 /// Specialization implementations for `Range`.
518 trait RangeIteratorImpl {
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>;
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>;
532 impl<A: Step> RangeIteratorImpl for ops::Range<A> {
536 default fn spec_next(&mut self) -> Option<A> {
537 if self.start < self.end {
539 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
540 Some(mem::replace(&mut self.start, n))
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 {
551 Step::forward_checked(plus_n.clone(), 1).expect("`Step` invariants not upheld");
556 self.start = self.end.clone();
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)
568 let taken = available.min(n);
571 Step::forward_checked(self.start.clone(), taken).expect("`Step` invariants not upheld");
573 if taken < n { Err(taken) } else { Ok(()) }
577 default fn spec_next_back(&mut self) -> Option<A> {
578 if self.start < self.end {
580 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
581 Some(self.end.clone())
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 {
592 Step::backward_checked(minus_n, 1).expect("`Step` invariants not upheld");
593 return Some(self.end.clone());
597 self.end = self.start.clone();
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)
609 let taken = available.min(n);
612 Step::backward_checked(self.end.clone(), taken).expect("`Step` invariants not upheld");
614 if taken < n { Err(taken) } else { Ok(()) }
618 impl<T: TrustedStep> RangeIteratorImpl for ops::Range<T> {
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))
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) };
640 self.start = self.end.clone();
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)
652 let taken = available.min(n);
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) };
660 if taken < n { Err(taken) } else { Ok(()) }
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())
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());
684 self.end = self.start.clone();
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)
696 let taken = available.min(n);
698 // SAFETY: same as the spec_advance_by() implementation
699 self.end = unsafe { Step::backward_unchecked(self.end.clone(), taken) };
701 if taken < n { Err(taken) } else { Ok(()) }
705 #[stable(feature = "rust1", since = "1.0.0")]
706 impl<A: Step> Iterator for ops::Range<A> {
710 fn next(&mut self) -> Option<A> {
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)
725 fn nth(&mut self, n: usize) -> Option<A> {
730 fn last(mut self) -> Option<A> {
735 fn min(mut self) -> Option<A> {
740 fn max(mut self) -> Option<A> {
745 fn is_sorted(self) -> bool {
750 fn advance_by(&mut self, n: usize) -> Result<(), usize> {
751 self.spec_advance_by(n)
756 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
758 Self: TrustedRandomAccessNoCoerce,
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) }
768 // These macros generate `ExactSizeIterator` impls for various range types.
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! {
780 // These are incorect 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.
788 unsafe_range_trusted_random_access_impl! {
793 #[cfg(target_pointer_width = "32")]
794 unsafe_range_trusted_random_access_impl! {
798 #[cfg(target_pointer_width = "64")]
799 unsafe_range_trusted_random_access_impl! {
804 range_incl_exact_iter_impl! {
808 // These are incorect 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.
816 #[stable(feature = "rust1", since = "1.0.0")]
817 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
819 fn next_back(&mut self) -> Option<A> {
820 self.spec_next_back()
824 fn nth_back(&mut self, n: usize) -> Option<A> {
825 self.spec_nth_back(n)
829 fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
830 self.spec_advance_back_by(n)
835 // The following invariants for `Step::steps_between` exist:
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
841 // > * `steps_between(&a, &b) == None` if `a > b`
843 // The first invariant is what is generally required for `TrustedLen` to be
844 // sound. The note addendum satisfies an additional `TrustedLen` invariant.
846 // > The upper bound must only be `None` if the actual iterator length is larger
847 // > than `usize::MAX`
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> {}
856 #[stable(feature = "fused", since = "1.26.0")]
857 impl<A: Step> FusedIterator for ops::Range<A> {}
859 #[stable(feature = "rust1", since = "1.0.0")]
860 impl<A: Step> Iterator for ops::RangeFrom<A> {
864 fn next(&mut self) -> Option<A> {
865 let n = Step::forward(self.start.clone(), 1);
866 Some(mem::replace(&mut self.start, n))
870 fn size_hint(&self) -> (usize, Option<usize>) {
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);
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> {}
886 #[stable(feature = "fused", since = "1.26.0")]
887 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
889 trait RangeInclusiveIteratorImpl {
893 fn spec_next(&mut self) -> Option<Self::Item>;
894 fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R
897 F: FnMut(B, Self::Item) -> R,
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
905 F: FnMut(B, Self::Item) -> R,
909 impl<A: Step> RangeInclusiveIteratorImpl for ops::RangeInclusive<A> {
913 default fn spec_next(&mut self) -> Option<A> {
917 let is_iterating = self.start < self.end;
918 Some(if is_iterating {
920 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
921 mem::replace(&mut self.start, n)
923 self.exhausted = true;
929 default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
939 let mut accum = init;
941 while self.start < self.end {
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)?;
948 self.exhausted = true;
950 if self.start == self.end {
951 accum = f(accum, self.start.clone())?;
958 default fn spec_next_back(&mut self) -> Option<A> {
962 let is_iterating = self.start < self.end;
963 Some(if is_iterating {
965 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
966 mem::replace(&mut self.end, n)
968 self.exhausted = true;
974 default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
984 let mut accum = init;
986 while self.start < self.end {
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)?;
993 self.exhausted = true;
995 if self.start == self.end {
996 accum = f(accum, self.start.clone())?;
1003 impl<T: TrustedStep> RangeInclusiveIteratorImpl for ops::RangeInclusive<T> {
1005 fn spec_next(&mut self) -> Option<T> {
1006 if self.is_empty() {
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)
1015 self.exhausted = true;
1021 fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1024 F: FnMut(B, T) -> R,
1027 if self.is_empty() {
1028 return try { init };
1031 let mut accum = init;
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)?;
1040 self.exhausted = true;
1042 if self.start == self.end {
1043 accum = f(accum, self.start.clone())?;
1050 fn spec_next_back(&mut self) -> Option<T> {
1051 if self.is_empty() {
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)
1060 self.exhausted = true;
1066 fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1069 F: FnMut(B, T) -> R,
1072 if self.is_empty() {
1073 return try { init };
1076 let mut accum = init;
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)?;
1085 self.exhausted = true;
1087 if self.start == self.end {
1088 accum = f(accum, self.start.clone())?;
1095 #[stable(feature = "inclusive_range", since = "1.26.0")]
1096 impl<A: Step> Iterator for ops::RangeInclusive<A> {
1100 fn next(&mut self) -> Option<A> {
1105 fn size_hint(&self) -> (usize, Option<usize>) {
1106 if self.is_empty() {
1107 return (0, Some(0));
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),
1117 fn nth(&mut self, n: usize) -> Option<A> {
1118 if self.is_empty() {
1122 if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
1123 use crate::cmp::Ordering::*;
1125 match plus_n.partial_cmp(&self.end) {
1127 self.start = Step::forward(plus_n.clone(), 1);
1128 return Some(plus_n);
1131 self.start = plus_n.clone();
1132 self.exhausted = true;
1133 return Some(plus_n);
1139 self.start = self.end.clone();
1140 self.exhausted = true;
1145 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
1148 F: FnMut(B, Self::Item) -> R,
1151 self.spec_try_fold(init, f)
1155 fn fold<B, F>(mut self, init: B, f: F) -> B
1158 F: FnMut(B, Self::Item) -> B,
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))
1165 self.try_fold(init, ok(f)).unwrap()
1169 fn last(mut self) -> Option<A> {
1174 fn min(mut self) -> Option<A> {
1179 fn max(mut self) -> Option<A> {
1184 fn is_sorted(self) -> bool {
1189 #[stable(feature = "inclusive_range", since = "1.26.0")]
1190 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
1192 fn next_back(&mut self) -> Option<A> {
1193 self.spec_next_back()
1197 fn nth_back(&mut self, n: usize) -> Option<A> {
1198 if self.is_empty() {
1202 if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
1203 use crate::cmp::Ordering::*;
1205 match minus_n.partial_cmp(&self.start) {
1207 self.end = Step::backward(minus_n.clone(), 1);
1208 return Some(minus_n);
1211 self.end = minus_n.clone();
1212 self.exhausted = true;
1213 return Some(minus_n);
1219 self.end = self.start.clone();
1220 self.exhausted = true;
1225 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
1228 F: FnMut(B, Self::Item) -> R,
1231 self.spec_try_rfold(init, f)
1235 fn rfold<B, F>(mut self, init: B, f: F) -> B
1238 F: FnMut(B, Self::Item) -> B,
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))
1245 self.try_rfold(init, ok(f)).unwrap()
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> {}
1253 #[stable(feature = "fused", since = "1.26.0")]
1254 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}