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