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)
755 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
757 Self: TrustedRandomAccessNoCoerce,
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) }
767 // These macros generate `ExactSizeIterator` impls for various range types.
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! {
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.
787 unsafe_range_trusted_random_access_impl! {
792 #[cfg(target_pointer_width = "32")]
793 unsafe_range_trusted_random_access_impl! {
797 #[cfg(target_pointer_width = "64")]
798 unsafe_range_trusted_random_access_impl! {
803 range_incl_exact_iter_impl! {
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.
815 #[stable(feature = "rust1", since = "1.0.0")]
816 impl<A: Step> DoubleEndedIterator for ops::Range<A> {
818 fn next_back(&mut self) -> Option<A> {
819 self.spec_next_back()
823 fn nth_back(&mut self, n: usize) -> Option<A> {
824 self.spec_nth_back(n)
828 fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
829 self.spec_advance_back_by(n)
834 // The following invariants for `Step::steps_between` exist:
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
840 // > * `steps_between(&a, &b) == None` if `a > b`
842 // The first invariant is what is generally required for `TrustedLen` to be
843 // sound. The note addendum satisfies an additional `TrustedLen` invariant.
845 // > The upper bound must only be `None` if the actual iterator length is larger
846 // > than `usize::MAX`
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> {}
855 #[stable(feature = "fused", since = "1.26.0")]
856 impl<A: Step> FusedIterator for ops::Range<A> {}
858 #[stable(feature = "rust1", since = "1.0.0")]
859 impl<A: Step> Iterator for ops::RangeFrom<A> {
863 fn next(&mut self) -> Option<A> {
864 let n = Step::forward(self.start.clone(), 1);
865 Some(mem::replace(&mut self.start, n))
869 fn size_hint(&self) -> (usize, Option<usize>) {
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);
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> {}
885 #[stable(feature = "fused", since = "1.26.0")]
886 impl<A: Step> FusedIterator for ops::RangeFrom<A> {}
888 trait RangeInclusiveIteratorImpl {
892 fn spec_next(&mut self) -> Option<Self::Item>;
893 fn spec_try_fold<B, F, R>(&mut self, init: B, f: F) -> R
896 F: FnMut(B, Self::Item) -> R,
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
904 F: FnMut(B, Self::Item) -> R,
908 impl<A: Step> RangeInclusiveIteratorImpl for ops::RangeInclusive<A> {
912 default fn spec_next(&mut self) -> Option<A> {
916 let is_iterating = self.start < self.end;
917 Some(if is_iterating {
919 Step::forward_checked(self.start.clone(), 1).expect("`Step` invariants not upheld");
920 mem::replace(&mut self.start, n)
922 self.exhausted = true;
928 default fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
938 let mut accum = init;
940 while self.start < self.end {
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)?;
947 self.exhausted = true;
949 if self.start == self.end {
950 accum = f(accum, self.start.clone())?;
957 default fn spec_next_back(&mut self) -> Option<A> {
961 let is_iterating = self.start < self.end;
962 Some(if is_iterating {
964 Step::backward_checked(self.end.clone(), 1).expect("`Step` invariants not upheld");
965 mem::replace(&mut self.end, n)
967 self.exhausted = true;
973 default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
983 let mut accum = init;
985 while self.start < self.end {
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)?;
992 self.exhausted = true;
994 if self.start == self.end {
995 accum = f(accum, self.start.clone())?;
1002 impl<T: TrustedStep> RangeInclusiveIteratorImpl for ops::RangeInclusive<T> {
1004 fn spec_next(&mut self) -> Option<T> {
1005 if self.is_empty() {
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)
1014 self.exhausted = true;
1020 fn spec_try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1023 F: FnMut(B, T) -> R,
1026 if self.is_empty() {
1027 return try { init };
1030 let mut accum = init;
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)?;
1039 self.exhausted = true;
1041 if self.start == self.end {
1042 accum = f(accum, self.start.clone())?;
1049 fn spec_next_back(&mut self) -> Option<T> {
1050 if self.is_empty() {
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)
1059 self.exhausted = true;
1065 fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1068 F: FnMut(B, T) -> R,
1071 if self.is_empty() {
1072 return try { init };
1075 let mut accum = init;
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)?;
1084 self.exhausted = true;
1086 if self.start == self.end {
1087 accum = f(accum, self.start.clone())?;
1094 #[stable(feature = "inclusive_range", since = "1.26.0")]
1095 impl<A: Step> Iterator for ops::RangeInclusive<A> {
1099 fn next(&mut self) -> Option<A> {
1104 fn size_hint(&self) -> (usize, Option<usize>) {
1105 if self.is_empty() {
1106 return (0, Some(0));
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),
1116 fn nth(&mut self, n: usize) -> Option<A> {
1117 if self.is_empty() {
1121 if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) {
1122 use crate::cmp::Ordering::*;
1124 match plus_n.partial_cmp(&self.end) {
1126 self.start = Step::forward(plus_n.clone(), 1);
1127 return Some(plus_n);
1130 self.start = plus_n.clone();
1131 self.exhausted = true;
1132 return Some(plus_n);
1138 self.start = self.end.clone();
1139 self.exhausted = true;
1144 fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
1147 F: FnMut(B, Self::Item) -> R,
1150 self.spec_try_fold(init, f)
1153 impl_fold_via_try_fold! { fold -> try_fold }
1156 fn last(mut self) -> Option<A> {
1161 fn min(mut self) -> Option<A> {
1166 fn max(mut self) -> Option<A> {
1171 fn is_sorted(self) -> bool {
1176 #[stable(feature = "inclusive_range", since = "1.26.0")]
1177 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
1179 fn next_back(&mut self) -> Option<A> {
1180 self.spec_next_back()
1184 fn nth_back(&mut self, n: usize) -> Option<A> {
1185 if self.is_empty() {
1189 if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) {
1190 use crate::cmp::Ordering::*;
1192 match minus_n.partial_cmp(&self.start) {
1194 self.end = Step::backward(minus_n.clone(), 1);
1195 return Some(minus_n);
1198 self.end = minus_n.clone();
1199 self.exhausted = true;
1200 return Some(minus_n);
1206 self.end = self.start.clone();
1207 self.exhausted = true;
1212 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
1215 F: FnMut(B, Self::Item) -> R,
1218 self.spec_try_rfold(init, f)
1221 impl_fold_via_try_fold! { rfold -> try_rfold }
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> {}
1228 #[stable(feature = "fused", since = "1.26.0")]
1229 impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}