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