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

core/iter/
range.rs
