]>
Commit | Line | Data |
---|---|---|
f9f354fc | 1 | use crate::char; |
48663c56 XL |
2 | use crate::convert::TryFrom; |
3 | use crate::mem; | |
4 | use crate::ops::{self, Add, Sub, Try}; | |
a7813a04 | 5 | |
c30ab7b3 | 6 | use super::{FusedIterator, TrustedLen}; |
a7813a04 | 7 | |
f9f354fc | 8 | /// Objects that have a notion of *successor* and *predecessor* operations. |
a7813a04 | 9 | /// |
f9f354fc XL |
10 | /// The *successor* operation moves towards values that compare greater. |
11 | /// The *predecessor* operation moves towards values that compare lesser. | |
12 | /// | |
13 | /// # Safety | |
14 | /// | |
15 | /// This trait is `unsafe` because its implementation must be correct for | |
16 | /// the safety of `unsafe trait TrustedLen` implementations, and the results | |
17 | /// of using this trait can otherwise be trusted by `unsafe` code to be correct | |
18 | /// and fulfill the listed obligations. | |
19 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] | |
20 | pub unsafe trait Step: Clone + PartialOrd + Sized { | |
21 | /// Returns the number of *successor* steps required to get from `start` to `end`. | |
22 | /// | |
23 | /// Returns `None` if the number of steps would overflow `usize` | |
24 | /// (or is infinite, or if `end` would never be reached). | |
25 | /// | |
26 | /// # Invariants | |
27 | /// | |
28 | /// For any `a`, `b`, and `n`: | |
29 | /// | |
30 | /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::forward_checked(&a, n) == Some(b)` | |
31 | /// * `steps_between(&a, &b) == Some(n)` if and only if `Step::backward_checked(&a, n) == Some(a)` | |
32 | /// * `steps_between(&a, &b) == Some(n)` only if `a <= b` | |
33 | /// * Corollary: `steps_between(&a, &b) == Some(0)` if and only if `a == b` | |
34 | /// * Note that `a <= b` does _not_ imply `steps_between(&a, &b) != None`; | |
35 | /// this is the case wheen it would require more than `usize::MAX` steps to get to `b` | |
36 | /// * `steps_between(&a, &b) == None` if `a > b` | |
041b39d2 | 37 | fn steps_between(start: &Self, end: &Self) -> Option<usize>; |
3157f602 | 38 | |
f9f354fc XL |
39 | /// Returns the value that would be obtained by taking the *successor* |
40 | /// of `self` `count` times. | |
41 | /// | |
42 | /// If this would overflow the range of values supported by `Self`, returns `None`. | |
43 | /// | |
44 | /// # Invariants | |
45 | /// | |
46 | /// For any `a`, `n`, and `m`: | |
47 | /// | |
48 | /// * `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))` | |
60c5eb7d | 49 | /// |
f9f354fc XL |
50 | /// For any `a`, `n`, and `m` where `n + m` does not overflow: |
51 | /// | |
52 | /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, n + m)` | |
53 | /// | |
54 | /// For any `a` and `n`: | |
55 | /// | |
56 | /// * `Step::forward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::forward_checked(&x, 1))` | |
57 | /// * Corollary: `Step::forward_checked(&a, 0) == Some(a)` | |
58 | #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] | |
59 | fn forward_checked(start: Self, count: usize) -> Option<Self>; | |
3157f602 | 60 | |
f9f354fc XL |
61 | /// Returns the value that would be obtained by taking the *successor* |
62 | /// of `self` `count` times. | |
63 | /// | |
64 | /// If this would overflow the range of values supported by `Self`, | |
65 | /// this function is allowed to panic, wrap, or saturate. | |
66 | /// The suggested behavior is to panic when debug assertions are enabled, | |
67 | /// and to wrap or saturate otherwise. | |
68 | /// | |
69 | /// Unsafe code should not rely on the correctness of behavior after overflow. | |
60c5eb7d | 70 | /// |
f9f354fc XL |
71 | /// # Invariants |
72 | /// | |
73 | /// For any `a`, `n`, and `m`, where no overflow occurs: | |
74 | /// | |
75 | /// * `Step::forward(Step::forward(a, n), m) == Step::forward(a, n + m)` | |
76 | /// | |
77 | /// For any `a` and `n`, where no overflow occurs: | |
78 | /// | |
79 | /// * `Step::forward_checked(a, n) == Some(Step::forward(a, n))` | |
80 | /// * `Step::forward(a, n) == (0..n).fold(a, |x, _| Step::forward(x, 1))` | |
81 | /// * Corollary: `Step::forward(a, 0) == a` | |
82 | /// * `Step::forward(a, n) >= a` | |
83 | /// * `Step::backward(Step::forward(a, n), n) == a` | |
84 | #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] | |
85 | fn forward(start: Self, count: usize) -> Self { | |
86 | Step::forward_checked(start, count).expect("overflow in `Step::forward`") | |
87 | } | |
3157f602 | 88 | |
f9f354fc XL |
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 | /// | |
106 | /// For any `a` and `n`, where no overflow occurs: | |
107 | /// | |
108 | /// * `Step::forward_unchecked(a, n)` is equivalent to `Step::forward(a, n)` | |
109 | #[unstable(feature = "unchecked_math", reason = "niche optimization path", issue = "none")] | |
110 | unsafe fn forward_unchecked(start: Self, count: usize) -> Self { | |
111 | Step::forward(start, count) | |
112 | } | |
3157f602 | 113 | |
f9f354fc XL |
114 | /// Returns the value that would be obtained by taking the *successor* |
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 | #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] | |
131 | fn backward_checked(start: Self, count: usize) -> Option<Self>; | |
041b39d2 | 132 | |
f9f354fc XL |
133 | /// Returns the value that would be obtained by taking the *predecessor* |
134 | /// of `self` `count` times. | |
135 | /// | |
136 | /// If this would overflow the range of values supported by `Self`, | |
137 | /// this function is allowed to panic, wrap, or saturate. | |
138 | /// The suggested behavior is to panic when debug assertions are enabled, | |
139 | /// and to wrap or saturate otherwise. | |
140 | /// | |
141 | /// Unsafe code should not rely on the correctness of behavior after overflow. | |
142 | /// | |
143 | /// # Invariants | |
144 | /// | |
145 | /// For any `a`, `n`, and `m`, where no overflow occurs: | |
146 | /// | |
147 | /// * `Step::backward(Step::backward(a, n), m) == Step::backward(a, n + m)` | |
148 | /// | |
149 | /// For any `a` and `n`, where no overflow occurs: | |
150 | /// | |
151 | /// * `Step::backward_checked(a, n) == Some(Step::backward(a, n))` | |
152 | /// * `Step::backward(a, n) == (0..n).fold(a, |x, _| Step::backward(x, 1))` | |
153 | /// * Corollary: `Step::backward(a, 0) == a` | |
154 | /// * `Step::backward(a, n) <= a` | |
155 | /// * `Step::forward(Step::backward(a, n), n) == a` | |
156 | #[unstable(feature = "step_trait_ext", reason = "recently added", issue = "42168")] | |
157 | fn backward(start: Self, count: usize) -> Self { | |
158 | Step::backward_checked(start, count).expect("overflow in `Step::backward`") | |
159 | } | |
dc9dc135 | 160 | |
f9f354fc XL |
161 | /// Returns the value that would be obtained by taking the *predecessor* |
162 | /// of `self` `count` times. | |
163 | /// | |
164 | /// # Safety | |
165 | /// | |
166 | /// It is undefined behavior for this operation to overflow the | |
167 | /// range of values supported by `Self`. If you cannot guarantee that this | |
168 | /// will not overflow, use `backward` or `backward_checked` instead. | |
169 | /// | |
170 | /// # Invariants | |
171 | /// | |
172 | /// For any `a`: | |
173 | /// | |
174 | /// * if there exists `b` such that `b < a`, it is safe to call `Step::backward_unchecked(a, 1)` | |
175 | /// * if there exists `b`, `n` such that `steps_between(&b, &a) == Some(n)`, | |
176 | /// it is safe to call `Step::backward_unchecked(a, m)` for any `m <= n`. | |
177 | /// | |
178 | /// For any `a` and `n`, where no overflow occurs: | |
179 | /// | |
180 | /// * `Step::backward_unchecked(a, n)` is equivalent to `Step::backward(a, n)` | |
181 | #[unstable(feature = "unchecked_math", reason = "niche optimization path", issue = "none")] | |
182 | unsafe fn backward_unchecked(start: Self, count: usize) -> Self { | |
183 | Step::backward(start, count) | |
dc9dc135 | 184 | } |
041b39d2 XL |
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] | |
f9f354fc XL |
191 | unsafe fn forward_unchecked(start: Self, n: usize) -> Self { |
192 | start.unchecked_add(n as Self) | |
041b39d2 XL |
193 | } |
194 | ||
195 | #[inline] | |
f9f354fc XL |
196 | unsafe fn backward_unchecked(start: Self, n: usize) -> Self { |
197 | start.unchecked_sub(n as Self) | |
041b39d2 XL |
198 | } |
199 | ||
200 | #[inline] | |
f9f354fc XL |
201 | fn forward(start: Self, n: usize) -> Self { |
202 | // In debug builds, trigger a panic on overflow. | |
203 | // This should optimize completely out in release builds. | |
204 | if Self::forward_checked(start, n).is_none() { | |
205 | let _ = Add::add(Self::MAX, 1); | |
206 | } | |
207 | // Do wrapping math to allow e.g. `Step::forward(-128i8, 255)`. | |
208 | start.wrapping_add(n as Self) | |
041b39d2 XL |
209 | } |
210 | ||
211 | #[inline] | |
f9f354fc XL |
212 | fn backward(start: Self, n: usize) -> Self { |
213 | // In debug builds, trigger a panic on overflow. | |
214 | // This should optimize completely out in release builds. | |
215 | if Self::backward_checked(start, n).is_none() { | |
216 | let _ = Sub::sub(Self::MIN, 1); | |
217 | } | |
218 | // Do wrapping math to allow e.g. `Step::backward(127i8, 255)`. | |
219 | start.wrapping_sub(n as Self) | |
041b39d2 | 220 | } |
f9f354fc | 221 | }; |
a7813a04 XL |
222 | } |
223 | ||
f9f354fc XL |
224 | macro_rules! step_integer_impls { |
225 | { | |
226 | narrower than or same width as usize: | |
227 | $( [ $u_narrower:ident $i_narrower:ident ] ),+; | |
228 | wider than usize: | |
229 | $( [ $u_wider:ident $i_wider:ident ] ),+; | |
230 | } => { | |
231 | $( | |
232 | #[allow(unreachable_patterns)] | |
233 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] | |
234 | unsafe impl Step for $u_narrower { | |
235 | step_identical_methods!(); | |
236 | ||
237 | #[inline] | |
238 | fn steps_between(start: &Self, end: &Self) -> Option<usize> { | |
239 | if *start <= *end { | |
240 | // This relies on $u_narrower <= usize | |
241 | Some((*end - *start) as usize) | |
242 | } else { | |
243 | None | |
244 | } | |
a7813a04 | 245 | } |
3157f602 | 246 | |
f9f354fc XL |
247 | #[inline] |
248 | fn forward_checked(start: Self, n: usize) -> Option<Self> { | |
249 | match Self::try_from(n) { | |
250 | Ok(n) => start.checked_add(n), | |
251 | Err(_) => None, // if n is out of range, `unsigned_start + n` is too | |
252 | } | |
253 | } | |
254 | ||
255 | #[inline] | |
256 | fn backward_checked(start: Self, n: usize) -> Option<Self> { | |
257 | match Self::try_from(n) { | |
258 | Ok(n) => start.checked_sub(n), | |
259 | Err(_) => None, // if n is out of range, `unsigned_start - n` is too | |
260 | } | |
041b39d2 | 261 | } |
3157f602 XL |
262 | } |
263 | ||
dc9dc135 | 264 | #[allow(unreachable_patterns)] |
f9f354fc XL |
265 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
266 | unsafe impl Step for $i_narrower { | |
267 | step_identical_methods!(); | |
268 | ||
269 | #[inline] | |
270 | fn steps_between(start: &Self, end: &Self) -> Option<usize> { | |
271 | if *start <= *end { | |
272 | // This relies on $i_narrower <= usize | |
273 | // | |
274 | // Casting to isize extends the width but preserves the sign. | |
275 | // Use wrapping_sub in isize space and cast to usize to compute | |
276 | // the difference that may not fit inside the range of isize. | |
277 | Some((*end as isize).wrapping_sub(*start as isize) as usize) | |
278 | } else { | |
279 | None | |
280 | } | |
dc9dc135 | 281 | } |
dc9dc135 | 282 | |
f9f354fc XL |
283 | #[inline] |
284 | fn forward_checked(start: Self, n: usize) -> Option<Self> { | |
285 | match $u_narrower::try_from(n) { | |
286 | Ok(n) => { | |
287 | // Wrapping handles cases like | |
288 | // `Step::forward(-120_i8, 200) == Some(80_i8)`, | |
289 | // even though 200 is out of range for i8. | |
290 | let wrapped = start.wrapping_add(n as Self); | |
291 | if wrapped >= start { | |
292 | Some(wrapped) | |
293 | } else { | |
294 | None // Addition overflowed | |
295 | } | |
296 | } | |
297 | // If n is out of range of e.g. u8, | |
298 | // then it is bigger than the entire range for i8 is wide | |
299 | // so `any_i8 + n` necessarily overflows i8. | |
300 | Err(_) => None, | |
301 | } | |
302 | } | |
303 | ||
304 | #[inline] | |
305 | fn backward_checked(start: Self, n: usize) -> Option<Self> { | |
306 | match $u_narrower::try_from(n) { | |
307 | Ok(n) => { | |
308 | // Wrapping handles cases like | |
309 | // `Step::forward(-120_i8, 200) == Some(80_i8)`, | |
310 | // even though 200 is out of range for i8. | |
311 | let wrapped = start.wrapping_sub(n as Self); | |
312 | if wrapped <= start { | |
313 | Some(wrapped) | |
314 | } else { | |
315 | None // Subtraction overflowed | |
316 | } | |
317 | } | |
318 | // If n is out of range of e.g. u8, | |
319 | // then it is bigger than the entire range for i8 is wide | |
320 | // so `any_i8 - n` necessarily overflows i8. | |
321 | Err(_) => None, | |
322 | } | |
a7813a04 XL |
323 | } |
324 | } | |
f9f354fc | 325 | )+ |
3157f602 | 326 | |
f9f354fc | 327 | $( |
ea8adc8c | 328 | #[allow(unreachable_patterns)] |
f9f354fc XL |
329 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
330 | unsafe impl Step for $u_wider { | |
331 | step_identical_methods!(); | |
332 | ||
333 | #[inline] | |
334 | fn steps_between(start: &Self, end: &Self) -> Option<usize> { | |
335 | if *start <= *end { | |
336 | usize::try_from(*end - *start).ok() | |
337 | } else { | |
338 | None | |
041b39d2 | 339 | } |
f9f354fc XL |
340 | } |
341 | ||
342 | #[inline] | |
343 | fn forward_checked(start: Self, n: usize) -> Option<Self> { | |
344 | start.checked_add(n as Self) | |
345 | } | |
346 | ||
347 | #[inline] | |
348 | fn backward_checked(start: Self, n: usize) -> Option<Self> { | |
349 | start.checked_sub(n as Self) | |
041b39d2 | 350 | } |
3157f602 XL |
351 | } |
352 | ||
dc9dc135 | 353 | #[allow(unreachable_patterns)] |
f9f354fc XL |
354 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
355 | unsafe impl Step for $i_wider { | |
356 | step_identical_methods!(); | |
357 | ||
358 | #[inline] | |
359 | fn steps_between(start: &Self, end: &Self) -> Option<usize> { | |
360 | if *start <= *end { | |
361 | match end.checked_sub(*start) { | |
362 | Some(result) => usize::try_from(result).ok(), | |
363 | // If the difference is too big for e.g. i128, | |
364 | // it's also gonna be too big for usize with fewer bits. | |
365 | None => None, | |
dc9dc135 | 366 | } |
f9f354fc XL |
367 | } else { |
368 | None | |
dc9dc135 | 369 | } |
f9f354fc XL |
370 | } |
371 | ||
372 | #[inline] | |
373 | fn forward_checked(start: Self, n: usize) -> Option<Self> { | |
374 | start.checked_add(n as Self) | |
375 | } | |
376 | ||
377 | #[inline] | |
378 | fn backward_checked(start: Self, n: usize) -> Option<Self> { | |
379 | start.checked_sub(n as Self) | |
dc9dc135 XL |
380 | } |
381 | } | |
f9f354fc XL |
382 | )+ |
383 | }; | |
384 | } | |
dc9dc135 | 385 | |
f9f354fc XL |
386 | #[cfg(target_pointer_width = "64")] |
387 | step_integer_impls! { | |
388 | narrower than or same width as usize: [u8 i8], [u16 i16], [u32 i32], [u64 i64], [usize isize]; | |
389 | wider than usize: [u128 i128]; | |
390 | } | |
391 | ||
392 | #[cfg(target_pointer_width = "32")] | |
393 | step_integer_impls! { | |
394 | narrower than or same width as usize: [u8 i8], [u16 i16], [u32 i32], [usize isize]; | |
395 | wider than usize: [u64 i64], [u128 i128]; | |
396 | } | |
397 | ||
398 | #[cfg(target_pointer_width = "16")] | |
399 | step_integer_impls! { | |
400 | narrower than or same width as usize: [u8 i8], [u16 i16], [usize isize]; | |
401 | wider than usize: [u32 i32], [u64 i64], [u128 i128]; | |
a7813a04 XL |
402 | } |
403 | ||
f9f354fc XL |
404 | #[unstable(feature = "step_trait", reason = "recently redesigned", issue = "42168")] |
405 | unsafe impl Step for char { | |
406 | #[inline] | |
407 | fn steps_between(&start: &char, &end: &char) -> Option<usize> { | |
408 | let start = start as u32; | |
409 | let end = end as u32; | |
410 | if start <= end { | |
411 | let count = end - start; | |
412 | if start < 0xD800 && 0xE000 <= end { | |
413 | usize::try_from(count - 0x800).ok() | |
414 | } else { | |
415 | usize::try_from(count).ok() | |
416 | } | |
417 | } else { | |
418 | None | |
419 | } | |
420 | } | |
421 | ||
422 | #[inline] | |
423 | fn forward_checked(start: char, count: usize) -> Option<char> { | |
424 | let start = start as u32; | |
425 | let mut res = Step::forward_checked(start, count)?; | |
426 | if start < 0xD800 && 0xD800 <= res { | |
427 | res = Step::forward_checked(res, 0x800)?; | |
428 | } | |
429 | if res <= char::MAX as u32 { | |
430 | // SAFETY: res is a valid unicode scalar | |
431 | // (below 0x110000 and not in 0xD800..0xE000) | |
432 | Some(unsafe { char::from_u32_unchecked(res) }) | |
433 | } else { | |
434 | None | |
435 | } | |
436 | } | |
437 | ||
438 | #[inline] | |
439 | fn backward_checked(start: char, count: usize) -> Option<char> { | |
440 | let start = start as u32; | |
441 | let mut res = Step::backward_checked(start, count)?; | |
442 | if start >= 0xE000 && 0xE000 > res { | |
443 | res = Step::backward_checked(res, 0x800)?; | |
444 | } | |
445 | // SAFETY: res is a valid unicode scalar | |
446 | // (below 0x110000 and not in 0xD800..0xE000) | |
447 | Some(unsafe { char::from_u32_unchecked(res) }) | |
448 | } | |
449 | ||
450 | #[inline] | |
451 | unsafe fn forward_unchecked(start: char, count: usize) -> char { | |
452 | let start = start as u32; | |
453 | let mut res = Step::forward_unchecked(start, count); | |
454 | if start < 0xD800 && 0xD800 <= res { | |
455 | res = Step::forward_unchecked(res, 0x800); | |
456 | } | |
457 | char::from_u32_unchecked(res) | |
458 | } | |
459 | ||
460 | #[inline] | |
461 | unsafe fn backward_unchecked(start: char, count: usize) -> char { | |
462 | let start = start as u32; | |
463 | let mut res = Step::backward_unchecked(start, count); | |
464 | if start >= 0xE000 && 0xE000 > res { | |
465 | res = Step::backward_unchecked(res, 0x800); | |
466 | } | |
467 | char::from_u32_unchecked(res) | |
468 | } | |
469 | } | |
a7813a04 | 470 | |
a7813a04 XL |
471 | macro_rules! range_exact_iter_impl { |
472 | ($($t:ty)*) => ($( | |
473 | #[stable(feature = "rust1", since = "1.0.0")] | |
474 | impl ExactSizeIterator for ops::Range<$t> { } | |
c30ab7b3 SL |
475 | )*) |
476 | } | |
a7813a04 | 477 | |
c30ab7b3 SL |
478 | macro_rules! range_incl_exact_iter_impl { |
479 | ($($t:ty)*) => ($( | |
0531ce1d | 480 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
a7813a04 XL |
481 | impl ExactSizeIterator for ops::RangeInclusive<$t> { } |
482 | )*) | |
483 | } | |
484 | ||
485 | #[stable(feature = "rust1", since = "1.0.0")] | |
041b39d2 | 486 | impl<A: Step> Iterator for ops::Range<A> { |
a7813a04 XL |
487 | type Item = A; |
488 | ||
489 | #[inline] | |
490 | fn next(&mut self) -> Option<A> { | |
491 | if self.start < self.end { | |
f9f354fc XL |
492 | // SAFETY: just checked precondition |
493 | // We use the unchecked version here, because | |
494 | // this helps LLVM vectorize loops for some ranges | |
495 | // that don't get vectorized otherwise. | |
496 | let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; | |
497 | Some(mem::replace(&mut self.start, n)) | |
a7813a04 XL |
498 | } else { |
499 | None | |
500 | } | |
501 | } | |
502 | ||
503 | #[inline] | |
504 | fn size_hint(&self) -> (usize, Option<usize>) { | |
f9f354fc XL |
505 | if self.start < self.end { |
506 | let hint = Step::steps_between(&self.start, &self.end); | |
507 | (hint.unwrap_or(usize::MAX), hint) | |
508 | } else { | |
509 | (0, Some(0)) | |
a7813a04 XL |
510 | } |
511 | } | |
041b39d2 XL |
512 | |
513 | #[inline] | |
514 | fn nth(&mut self, n: usize) -> Option<A> { | |
f9f354fc | 515 | if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) { |
041b39d2 | 516 | if plus_n < self.end { |
f9f354fc | 517 | self.start = Step::forward(plus_n.clone(), 1); |
dfeec247 | 518 | return Some(plus_n); |
041b39d2 XL |
519 | } |
520 | } | |
521 | ||
522 | self.start = self.end.clone(); | |
523 | None | |
524 | } | |
2c00a5a8 XL |
525 | |
526 | #[inline] | |
527 | fn last(mut self) -> Option<A> { | |
528 | self.next_back() | |
529 | } | |
530 | ||
531 | #[inline] | |
532 | fn min(mut self) -> Option<A> { | |
533 | self.next() | |
534 | } | |
535 | ||
536 | #[inline] | |
537 | fn max(mut self) -> Option<A> { | |
538 | self.next_back() | |
539 | } | |
a7813a04 XL |
540 | } |
541 | ||
c30ab7b3 | 542 | // These macros generate `ExactSizeIterator` impls for various range types. |
c30ab7b3 | 543 | // |
f9f354fc XL |
544 | // * `ExactSizeIterator::len` is required to always return an exact `usize`, |
545 | // so no range can be longer than `usize::MAX`. | |
546 | // * For integer types in `Range<_>` this is the case for types narrower than or as wide as `usize`. | |
547 | // For integer types in `RangeInclusive<_>` | |
548 | // this is the case for types *strictly narrower* than `usize` | |
549 | // since e.g. `(0..=u64::MAX).len()` would be `u64::MAX + 1`. | |
550 | range_exact_iter_impl! { | |
551 | usize u8 u16 | |
552 | isize i8 i16 | |
553 | ||
554 | // These are incorect per the reasoning above, | |
555 | // but removing them would be a breaking change as they were stabilized in Rust 1.0.0. | |
556 | // So e.g. `(0..66_000_u32).len()` for example will compile without error or warnings | |
557 | // on 16-bit platforms, but continue to give a wrong result. | |
558 | u32 | |
559 | i32 | |
560 | } | |
561 | range_incl_exact_iter_impl! { | |
562 | u8 | |
563 | i8 | |
564 | ||
565 | // These are incorect per the reasoning above, | |
566 | // but removing them would be a breaking change as they were stabilized in Rust 1.26.0. | |
567 | // So e.g. `(0..=u16::MAX).len()` for example will compile without error or warnings | |
568 | // on 16-bit platforms, but continue to give a wrong result. | |
569 | u16 | |
570 | i16 | |
571 | } | |
a7813a04 XL |
572 | |
573 | #[stable(feature = "rust1", since = "1.0.0")] | |
041b39d2 | 574 | impl<A: Step> DoubleEndedIterator for ops::Range<A> { |
a7813a04 XL |
575 | #[inline] |
576 | fn next_back(&mut self) -> Option<A> { | |
577 | if self.start < self.end { | |
f9f354fc | 578 | self.end = Step::backward(self.end.clone(), 1); |
a7813a04 XL |
579 | Some(self.end.clone()) |
580 | } else { | |
581 | None | |
582 | } | |
583 | } | |
dc9dc135 XL |
584 | |
585 | #[inline] | |
586 | fn nth_back(&mut self, n: usize) -> Option<A> { | |
f9f354fc | 587 | if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { |
dc9dc135 | 588 | if minus_n > self.start { |
f9f354fc | 589 | self.end = Step::backward(minus_n, 1); |
dfeec247 | 590 | return Some(self.end.clone()); |
dc9dc135 XL |
591 | } |
592 | } | |
593 | ||
594 | self.end = self.start.clone(); | |
595 | None | |
596 | } | |
a7813a04 XL |
597 | } |
598 | ||
f9f354fc XL |
599 | #[unstable(feature = "trusted_len", issue = "37572")] |
600 | unsafe impl<A: Step> TrustedLen for ops::Range<A> {} | |
601 | ||
0531ce1d | 602 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 603 | impl<A: Step> FusedIterator for ops::Range<A> {} |
9e0c209e | 604 | |
a7813a04 | 605 | #[stable(feature = "rust1", since = "1.0.0")] |
041b39d2 | 606 | impl<A: Step> Iterator for ops::RangeFrom<A> { |
a7813a04 XL |
607 | type Item = A; |
608 | ||
609 | #[inline] | |
610 | fn next(&mut self) -> Option<A> { | |
f9f354fc XL |
611 | let n = Step::forward(self.start.clone(), 1); |
612 | Some(mem::replace(&mut self.start, n)) | |
a7813a04 | 613 | } |
7cac9316 XL |
614 | |
615 | #[inline] | |
616 | fn size_hint(&self) -> (usize, Option<usize>) { | |
617 | (usize::MAX, None) | |
618 | } | |
041b39d2 XL |
619 | |
620 | #[inline] | |
621 | fn nth(&mut self, n: usize) -> Option<A> { | |
f9f354fc XL |
622 | let plus_n = Step::forward(self.start.clone(), n); |
623 | self.start = Step::forward(plus_n.clone(), 1); | |
041b39d2 XL |
624 | Some(plus_n) |
625 | } | |
a7813a04 XL |
626 | } |
627 | ||
0531ce1d | 628 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 629 | impl<A: Step> FusedIterator for ops::RangeFrom<A> {} |
9e0c209e | 630 | |
2c00a5a8 XL |
631 | #[unstable(feature = "trusted_len", issue = "37572")] |
632 | unsafe impl<A: Step> TrustedLen for ops::RangeFrom<A> {} | |
633 | ||
0531ce1d | 634 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
041b39d2 | 635 | impl<A: Step> Iterator for ops::RangeInclusive<A> { |
a7813a04 XL |
636 | type Item = A; |
637 | ||
638 | #[inline] | |
639 | fn next(&mut self) -> Option<A> { | |
74b04a01 | 640 | if self.is_empty() { |
8faf50e0 | 641 | return None; |
a7813a04 | 642 | } |
8faf50e0 | 643 | let is_iterating = self.start < self.end; |
8faf50e0 | 644 | Some(if is_iterating { |
f9f354fc XL |
645 | // SAFETY: just checked precondition |
646 | // We use the unchecked version here, because | |
647 | // otherwise `for _ in '\0'..=char::MAX` | |
648 | // does not successfully remove panicking code. | |
649 | let n = unsafe { Step::forward_unchecked(self.start.clone(), 1) }; | |
8faf50e0 XL |
650 | mem::replace(&mut self.start, n) |
651 | } else { | |
74b04a01 | 652 | self.exhausted = true; |
8faf50e0 XL |
653 | self.start.clone() |
654 | }) | |
a7813a04 XL |
655 | } |
656 | ||
657 | #[inline] | |
658 | fn size_hint(&self) -> (usize, Option<usize>) { | |
8faf50e0 | 659 | if self.is_empty() { |
7cac9316 XL |
660 | return (0, Some(0)); |
661 | } | |
a7813a04 | 662 | |
041b39d2 | 663 | match Step::steps_between(&self.start, &self.end) { |
7cac9316 | 664 | Some(hint) => (hint.saturating_add(1), hint.checked_add(1)), |
532ac7d7 | 665 | None => (usize::MAX, None), |
a7813a04 XL |
666 | } |
667 | } | |
041b39d2 XL |
668 | |
669 | #[inline] | |
670 | fn nth(&mut self, n: usize) -> Option<A> { | |
74b04a01 | 671 | if self.is_empty() { |
8faf50e0 XL |
672 | return None; |
673 | } | |
674 | ||
f9f354fc | 675 | if let Some(plus_n) = Step::forward_checked(self.start.clone(), n) { |
48663c56 | 676 | use crate::cmp::Ordering::*; |
041b39d2 XL |
677 | |
678 | match plus_n.partial_cmp(&self.end) { | |
679 | Some(Less) => { | |
f9f354fc | 680 | self.start = Step::forward(plus_n.clone(), 1); |
9fa01778 | 681 | return Some(plus_n); |
041b39d2 XL |
682 | } |
683 | Some(Equal) => { | |
74b04a01 XL |
684 | self.start = plus_n.clone(); |
685 | self.exhausted = true; | |
9fa01778 | 686 | return Some(plus_n); |
041b39d2 XL |
687 | } |
688 | _ => {} | |
689 | } | |
690 | } | |
691 | ||
74b04a01 XL |
692 | self.start = self.end.clone(); |
693 | self.exhausted = true; | |
041b39d2 XL |
694 | None |
695 | } | |
2c00a5a8 | 696 | |
9fa01778 XL |
697 | #[inline] |
698 | fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R | |
699 | where | |
dfeec247 XL |
700 | Self: Sized, |
701 | F: FnMut(B, Self::Item) -> R, | |
702 | R: Try<Ok = B>, | |
9fa01778 | 703 | { |
9fa01778 XL |
704 | if self.is_empty() { |
705 | return Try::from_ok(init); | |
706 | } | |
707 | ||
708 | let mut accum = init; | |
709 | ||
710 | while self.start < self.end { | |
f9f354fc | 711 | let n = Step::forward(self.start.clone(), 1); |
9fa01778 XL |
712 | let n = mem::replace(&mut self.start, n); |
713 | accum = f(accum, n)?; | |
714 | } | |
715 | ||
74b04a01 | 716 | self.exhausted = true; |
9fa01778 XL |
717 | |
718 | if self.start == self.end { | |
719 | accum = f(accum, self.start.clone())?; | |
720 | } | |
721 | ||
722 | Try::from_ok(accum) | |
723 | } | |
724 | ||
f9f354fc XL |
725 | #[inline] |
726 | fn fold<B, F>(mut self, init: B, f: F) -> B | |
727 | where | |
728 | Self: Sized, | |
729 | F: FnMut(B, Self::Item) -> B, | |
730 | { | |
731 | #[inline] | |
732 | fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> { | |
733 | move |acc, x| Ok(f(acc, x)) | |
734 | } | |
735 | ||
736 | self.try_fold(init, ok(f)).unwrap() | |
737 | } | |
738 | ||
2c00a5a8 XL |
739 | #[inline] |
740 | fn last(mut self) -> Option<A> { | |
741 | self.next_back() | |
742 | } | |
743 | ||
744 | #[inline] | |
745 | fn min(mut self) -> Option<A> { | |
746 | self.next() | |
747 | } | |
748 | ||
749 | #[inline] | |
750 | fn max(mut self) -> Option<A> { | |
751 | self.next_back() | |
752 | } | |
a7813a04 XL |
753 | } |
754 | ||
0531ce1d | 755 | #[stable(feature = "inclusive_range", since = "1.26.0")] |
041b39d2 | 756 | impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> { |
a7813a04 XL |
757 | #[inline] |
758 | fn next_back(&mut self) -> Option<A> { | |
74b04a01 | 759 | if self.is_empty() { |
8faf50e0 | 760 | return None; |
2c00a5a8 | 761 | } |
8faf50e0 | 762 | let is_iterating = self.start < self.end; |
8faf50e0 | 763 | Some(if is_iterating { |
f9f354fc | 764 | let n = Step::backward(self.end.clone(), 1); |
8faf50e0 XL |
765 | mem::replace(&mut self.end, n) |
766 | } else { | |
74b04a01 | 767 | self.exhausted = true; |
8faf50e0 XL |
768 | self.end.clone() |
769 | }) | |
a7813a04 | 770 | } |
9fa01778 | 771 | |
dc9dc135 XL |
772 | #[inline] |
773 | fn nth_back(&mut self, n: usize) -> Option<A> { | |
74b04a01 | 774 | if self.is_empty() { |
dc9dc135 XL |
775 | return None; |
776 | } | |
777 | ||
f9f354fc | 778 | if let Some(minus_n) = Step::backward_checked(self.end.clone(), n) { |
dc9dc135 XL |
779 | use crate::cmp::Ordering::*; |
780 | ||
781 | match minus_n.partial_cmp(&self.start) { | |
782 | Some(Greater) => { | |
f9f354fc | 783 | self.end = Step::backward(minus_n.clone(), 1); |
dc9dc135 XL |
784 | return Some(minus_n); |
785 | } | |
786 | Some(Equal) => { | |
74b04a01 XL |
787 | self.end = minus_n.clone(); |
788 | self.exhausted = true; | |
dc9dc135 XL |
789 | return Some(minus_n); |
790 | } | |
791 | _ => {} | |
792 | } | |
793 | } | |
794 | ||
74b04a01 XL |
795 | self.end = self.start.clone(); |
796 | self.exhausted = true; | |
dc9dc135 XL |
797 | None |
798 | } | |
799 | ||
9fa01778 | 800 | #[inline] |
dfeec247 XL |
801 | fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R |
802 | where | |
803 | Self: Sized, | |
804 | F: FnMut(B, Self::Item) -> R, | |
805 | R: Try<Ok = B>, | |
9fa01778 | 806 | { |
9fa01778 XL |
807 | if self.is_empty() { |
808 | return Try::from_ok(init); | |
809 | } | |
810 | ||
811 | let mut accum = init; | |
812 | ||
813 | while self.start < self.end { | |
f9f354fc | 814 | let n = Step::backward(self.end.clone(), 1); |
9fa01778 XL |
815 | let n = mem::replace(&mut self.end, n); |
816 | accum = f(accum, n)?; | |
817 | } | |
818 | ||
74b04a01 | 819 | self.exhausted = true; |
9fa01778 XL |
820 | |
821 | if self.start == self.end { | |
822 | accum = f(accum, self.start.clone())?; | |
823 | } | |
824 | ||
825 | Try::from_ok(accum) | |
826 | } | |
f9f354fc XL |
827 | |
828 | #[inline] | |
829 | fn rfold<B, F>(mut self, init: B, f: F) -> B | |
830 | where | |
831 | Self: Sized, | |
832 | F: FnMut(B, Self::Item) -> B, | |
833 | { | |
834 | #[inline] | |
835 | fn ok<B, T>(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result<B, !> { | |
836 | move |acc, x| Ok(f(acc, x)) | |
837 | } | |
838 | ||
839 | self.try_rfold(init, ok(f)).unwrap() | |
840 | } | |
a7813a04 XL |
841 | } |
842 | ||
f9f354fc XL |
843 | #[unstable(feature = "trusted_len", issue = "37572")] |
844 | unsafe impl<A: Step> TrustedLen for ops::RangeInclusive<A> {} | |
845 | ||
0531ce1d | 846 | #[stable(feature = "fused", since = "1.26.0")] |
041b39d2 | 847 | impl<A: Step> FusedIterator for ops::RangeInclusive<A> {} |