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