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