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