core/iter/
range.rs

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

core/iter/
range.rs
