core/iter/
range.rs

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

core/iter/
range.rs
