core/iter/
range.rs

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

core/iter/
range.rs
