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

core/iter/
range.rs
