core/iter/
range.rs

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

core/iter/
range.rs
