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