core/iter/
range.rs

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

core/iter/
range.rs
