core/iter/
range.rs

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

core/iter/
range.rs
