core/iter/
range.rs

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

core/iter/
range.rs
