1 | use crate::ascii::Char as AsciiChar; |
2 | use crate::convert::TryFrom; |
3 | use crate::mem; |
4 | use crate::net::{Ipv4Addr, Ipv6Addr}; |
5 | use crate::num::NonZeroUsize; |
6 | use crate::ops::{self, Try}; |
7 | |
8 | use super::{ |
9 | FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, TrustedStep, |
10 | }; |
11 | |
12 | // Safety: All invariants are upheld. |
13 | macro_rules! unsafe_impl_trusted_step { |
14 | ($($type:ty)*) => {$( |
15 | #[unstable(feature = "trusted_step" , issue = "85731" )] |
16 | unsafe impl TrustedStep for $type {} |
17 | )*}; |
18 | } |
19 | unsafe_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" )] |
26 | pub 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. |
188 | macro_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 | |
230 | macro_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" )] |
393 | step_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" )] |
399 | step_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" )] |
405 | step_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" )] |
411 | impl 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" )] |
490 | impl 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" )] |
532 | impl 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" )] |
564 | impl 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 | |
595 | macro_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`. |
604 | macro_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 | |
618 | macro_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`. |
626 | trait 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 | |
640 | impl<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 | |
726 | impl<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" )] |
815 | impl<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`. |
899 | range_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 | |
911 | unsafe_range_trusted_random_access_impl! { |
912 | usize u8 u16 |
913 | isize i8 i16 |
914 | } |
915 | |
916 | #[cfg (target_pointer_width = "32" )] |
917 | unsafe_range_trusted_random_access_impl! { |
918 | u32 i32 |
919 | } |
920 | |
921 | #[cfg (target_pointer_width = "64" )] |
922 | unsafe_range_trusted_random_access_impl! { |
923 | u32 i32 |
924 | u64 i64 |
925 | } |
926 | |
927 | range_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" )] |
940 | impl<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" )] |
977 | unsafe impl<A: TrustedStep> TrustedLen for ops::Range<A> {} |
978 | |
979 | #[stable (feature = "fused" , since = "1.26.0" )] |
980 | impl<A: Step> FusedIterator for ops::Range<A> {} |
981 | |
982 | #[stable (feature = "rust1" , since = "1.0.0" )] |
983 | impl<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" )] |
1007 | unsafe impl<A: TrustedStep> TrustedLen for ops::RangeFrom<A> {} |
1008 | |
1009 | #[stable (feature = "fused" , since = "1.26.0" )] |
1010 | impl<A: Step> FusedIterator for ops::RangeFrom<A> {} |
1011 | |
1012 | trait 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 | |
1032 | impl<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 | |
1126 | impl<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" )] |
1219 | impl<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" )] |
1318 | impl<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" )] |
1367 | unsafe impl<A: TrustedStep> TrustedLen for ops::RangeInclusive<A> {} |
1368 | |
1369 | #[stable (feature = "fused" , since = "1.26.0" )] |
1370 | impl<A: Step> FusedIterator for ops::RangeInclusive<A> {} |
1371 | |