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

core/iter/
range.rs
