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