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

core/iter/
range.rs
