core/iter/
range.rs

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

core/iter/
range.rs
