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

core/iter/
range.rs
