core/iter/
range.rs

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

core/iter/
range.rs
